3

My professor tells me that a proof by contradiction structure below is poor:

Proof. To prove: A implies B. So, assume A (in order to prove that B follows). Assume not B (in order to arrive at a contradiction). Succeed at showing that not A follows from the assumption of not B, thus arriving at the contradiction A and not A. Conclude that the initial assumption of not B must be false. So, conclude that B must be true, and so it follows from A, as desired.

I don't see what is wrong with it exactly. I don't see any obvious logical errors. Perhaps it is just a presentation issue?

John Davies
  • 565
  • 8
    What you are really doing here is proving $\neg B \Rightarrow \neg A$, which is proof by contraposition. – Orange Mushroom Feb 17 '24 at 06:30
  • 1
    If you work with Boolean algebra (which is quite common) then nothing is wrong with the proof and RAA is used. However if you work in intuitionistic logic then you are only allowed to conclude $\neg\neg B$ which is in that logic not considered to be the same as $B$. In that logic $\neg\neg B$ is a consequence of $B$ but not backwards. – drhab Feb 17 '24 at 07:50
  • 2
    I believe it's a matter of presentation. Your proof it's not wrong, but does more steps and is harder to read. Basically, you replicate the standard proof of $\lnot B \implies \lnot A$ implying $A \implies B$ instead of using this well-known fact. I'd start my proof with "We prove the contrapositive $\lnot B \implies \lnot A$ . So, assume $\lnot B$ ... We thus obtain $\lnot A$. QED" – chi Feb 17 '24 at 15:06

2 Answers2

7

I feel like this has already been answered somewhere but this hits too close to home as a student who did this regularly...

The pitfall which I too have fallen for (and might fall for still if I don't pay attention) is that, if you show $\mathrm{non}A$ from $\mathrm{non} B$ without using $A$, then you did not need to assume $A$! Thus you did not need a proof by contradiction, and you could have just proven that $\mathrm{non} B$ implies $\mathrm{non} A$ directly, unless you actually used $A$ to prove $\mathrm{non} A$ in this context but I feel like that's a rare situation to be in.

What a proof by contradiction is useful for is when you take a proposition $A$ by itself, assume $\mathrm{non} A$ and find a contradiction from there.

Bruno B
  • 5,027
  • 2
    "unless you actually used to prove non in this context but I feel like that's a rare situation to be in." << I think it's not so rare, and one of the reasons why proofs by contradiction are so popular is because they allow you to take as many assumptions as you can, including A and nonB instead of just A (for a direct proof) or just nonB (for a proof by contraposition). – Stef Feb 17 '24 at 17:29
  • 1
    But I think it's a good skill to be able to recognise, once the proof is written, that some assumptions were less useful than others, and rewrite a proof by contradiction into a (cleaner) proof by contraposition – Stef Feb 17 '24 at 17:31
2

Here's the standard proof that the reals are uncountable:

  • Suppose that the reals are countable.
  • Let $a_m$ be the $m$th real number in the interval $[0,1)$, and let $a_{m,n}$ be the $n$th digit after the decimal place.
  • Consider the number where the $n$th digit after the decimal place is $9-a_{n,n}$, call this number $b$, and let $b_n$ be the $n$th digit after the decimal place.
  • Because $b_n=9-a_{n,n}$, $b_n\neq a_{n,n}$, so $b\neq a_m$ for all $m$.
  • This means that we have found a real number $b\in[0,1)$ that is not in $\{a_m\}$, so that $\{a_m\}$ does not contain all the real numbers in $[0,1)$.
  • Contradiction.

Now, B is clear enough: "the reals are uncountable". So "not B" is "the reals are countable". The problem is, what is A? And even if we eventually decide that A is something like "everything we know about the reals so far", then what is "not A"? We've definitely not shown that "everything we know about the reals so far is false". All we've really shown is that if we assume A and "not B", then we arrive at a contradiction, which shows that if we assume A, then we can conclude B.

Final remarks:

  • As noted, your construction is a proof by contrapositive. This is usually a little cleaner than a proof by contradiction. So if you can do that, then you should.
  • Please avoid "Assume A and 'not B'. But A implies B. Contradiction. Therefore B.", which adds three extra steps around a straightforward proof.
  • I'm not a logician, so I'm skipping over the intuitionist question of whether not not B and B are different.
Teepeemm
  • 812
  • 1
    Interestingly, you never use the assumption that reals are countable in your "proof by contradiction" that the reals are uncountable. You consider a countable sequence (a_m), and prove that this sequence does not contain all real numbers by constructing number b which is not in the sequence. So you have proven that for any function $f : \mathbb N \to \mathbb R$, function $f$ is not surjective. This is a direct proof that the reals are uncountable! Adding "Assume the reals are countable" at the start and "Contradiction!" a the end of this direct proof is unnecessary for the proof to be correct. – Stef Feb 17 '24 at 17:23
  • But you do. If the reals are not countable then you cannot let a_m be the m-th real number in an interval. – gnasher729 Feb 18 '24 at 00:40