Proof by Contradiction

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

Problem Set 4

For question 3, “…there is no y in ℤ^-…” can translate as a negated existential quantifier. This gives a solution to Part A that looks like this:

In contrast to Part B, which uses two universal quantifiers:

The argument for why these are equivalent relies on the equivalencies for negations of quantifiers:

Contrapositive Discussion

When you summarize the proof from the Canvas discussion for me, I’m basically hoping you will verbally cut through the idea generation, dead ends, etc. and say the final proof in your own words.

Mid-Semester Feedback

There is a survey in Canvas that you can use to give me anonymous feedback on how this course is going for you and to suggest changes that would make it work better.

If you have things to say now, try to put them in the survey this week. I’ll try to look at it at the end of the week or over the weekend, and then periodically through the rest of the semester.

Proof by Contradiction

From section 3.3 in our textbook and the proof by contradiction discussion.

Discussion Example

Use a proof by contradiction to prove that for all integers n, if n ≡ 1 (mod 2), then n ≢ 2 (mod 4).

We wrote this up formally, using LaTeX. The source document and PDF output are available from Canvas.

As an example of proof writing, this particularly illustrates ways of telling a reader what method a proof is using (contradiction in this case) and of reminding them during the argument.

It also illustrates use of numbered equations where you want to refer to an equation in the proof’s text. As a general rule, only equations that need to be referenced in this way should be numbered.

The proof also demonstrates some new LaTeX features, including…

• The align environment, to produce a block of aligned equations, potentially with each equation numbered. Environments with a “*” at the end of their name are often non-numbering versions of environments that number things (equations, sections, etc.); the environments that number things don’t have the “*” in their name.
• The \nonumber command to prevent LaTeX from numbering particular lines
• A couple of new math commands, including \pmod to generate parenthesized “(mod …)” text, and \not to put a slash through an immediately succeeding relation symbol.

Another Example

In the previous proof, we assumed that no integer can be both odd and even. I think we, or our textbook, have also assumed this on other occasions too. But I don’t think we ever actually proved it. So let’s see if we can prove…

Conjecture: There is no integer that is both odd and even.

We outlined a nice proof by contradiction, as follows:

Suppose some integer n is both odd and even, so n = 2a and n = 2b + 1

Then 2a = 2b + 1, and so 2a - 2b = 1

You might remember proving that the difference of even integers is even, in which case this last equation is a contradiction, since 1 is odd.

Or if you don’t notice that a difference of even numbers must be even, you can go on and factor the 2 out of 2a - 2b: 2(a-b) = 1 or a-b = 1/2, which means 1/2 is an integer, since integers are closed under subtraction. But of course 1/2 is not an integer, so this is another contradiction.

This is a nice example of how proofs by contradiction don’t have any specific contradiction they need to establish, any one will do.

Next

Do irrational numbers actually exist? Are you sure that all those numbers you’ve been told are irrational really are?

Please read “Rational and Irrational Numbers” and “The Square Root of 2 Is an Irrational Number” in section 3.3 of the textbook.

Please also contribute to this discussion of irrational square roots and when proofs do and don’t follow the pattern from the textbook.

Next Lecture