1

Source: Mathematical Proofs, 2nd ed. by Chartrand. p. 121.

An element belonging to some prescribed set $A$ and possessing a certain property $P$ is unique if it is the only element of $A$ having property $P$. Typically, to prove that only one element of $A$ has property $P$, we proceed in one of two ways:

  1. We assume that $a$ and $b$ are elements of $A$ possessing property $P$ and show that $a= b.$
  2. We assume that $a$ and $b$ are distinct elements of $A$ possessing property $P$ and show that $a= b.$ Contradiction to $a \neq b$.

Although (1) results in a direct proof and (2) results in a proof by contradiction, it is $\color{red}{often}$ [Emphasis mine] the case that either proof technique can be used.

The $\color{red}{often}$ spurs these questions: When will either method fail? When to prefer one over the other?

  • 1
    It can't hurt to assume $a$ and $b$ are distinct. Then after you've finished your proof, you can look back to see whether you ever used this assumption, and, if you didn't, you can omit it. – WillO Sep 07 '13 at 14:51
  • I can't think of an example of such a proof where you actually use the hypothesis $a\ne b$ in the argument. Thus, the contradiction is redundant. Do you have an example where the proof by contradiction is needed? – Ted Shifrin Sep 07 '13 at 15:48
  • @TedShifrin: Unfortunately, I don't have one at the moment. I'll write back once I do. (À propos, j'espère que vous vous êtes amusé en France.) –  Sep 13 '13 at 15:18

1 Answers1

2

The answer to your question is "yes" in the weak sense that, if you have a proof of either sort, you can always "pad" it to produce a proof of the other sort.

Half of that claim is trivial: A proof in the form (1) still works as a proof in the form (2), which just happens to have an extra hypothesis that $a$ and $b$ are distinct, but which never uses that hypothesis.

In the reverse direction, suppose you have a proof in the form (2). Then you can produce the following proof in the form (1). Assume $a$ and $b$ are elements of $A$ with property $P$. We proceed by cases according to whether $a=b$ or not. In case $a=b$, we're done, as that's the conclusion we want in (1). In the other case, where $a\neq b$, we have all the hypotheses for the form (2) proof, so we again get the desired conclusion $a=b$. So we have $a=b$ in all cases, and that completes the proof in form (1).

Of course, in the preceding paragraph, the proof in form (1) is essentially just the original proof in form (2) with some padding to make it technically of form (1). Another way to say this is that the preceding paragraph is just working out explicitly, in this particular situation, the general fact that the law of the excluded middle (in this case saying $a=b$ or $a\neq b$, so that the two cases are exhaustive) justifies proof by contradiction.

Andreas Blass
  • 71,833
  • Thank you very much. Could you please confirm whether this précis depicts 100% how Proof Form $2$ $\Longrightarrow$ Proof Form $1$, with the "padding" in blue and the cited/given Form #2 in green? $\color{blue}{\text{Assume $a$ and $b$ are elements of A with property $P.$ Proceed by the 2 cases based on the Law of the Excluded Middle. $\Large{1.}$ If $a = b$, then this is the desired conclusion. End of Case 1.}}$ $\color{green}{{\Large{2.}} \text{If $a \neq b$, then by the hypotheses of Proof #2, $a = b$ can be concluded. Contradiction to $a \neq b$. So $a = b$.}}$ –  Sep 13 '13 at 15:55
  • This looks good, except that in Case 2 you don't need "Contradiction to $a\neq b$." You've already proved $a=b$ in this case, so you're done. – Andreas Blass Sep 13 '13 at 16:05
  • Many thanks again. I upvoted. –  Sep 13 '13 at 16:24