2

I'm curious whether the following technique has ever been used in a proof of something. Assume two propositions $A$ and $B$, then derive a contradiction. Thus you know that either $\lnot A$ or $\lnot B$ or both, but you don't know which.

frabala
  • 3,732
Marius Kempe
  • 962
  • Because I'm not giving a specific example, I put this as a comment rather than answer. Yes! this happens all the time. It is very common to prove a statement such as A implies B or C. Then the contradiction proof follows as you describe. Then when you want to apply the theorem to a specific case you look at that specific case and try to show, for example that B cannot be true, and thus conclude C. – Owen Sizemore Aug 01 '13 at 12:58

2 Answers2

2

One of my favorite proofs uses this technique twice as parts of a proof by contradiction. Let

$A=$ "If $r, s$ are irrational, then $r^s$ is irrational."

$B=$ "$\sqrt{2}^\sqrt{2}$ is rational."

We get an immediate contradiction, so we know $\neg A\lor\neg B$. Now let's do the same thing with

$A=$ "If $r, s$ are irrational, then $r^s$ is irrational."

$\neg B=$ "$\sqrt{2}^\sqrt{2}$ is irrational."

Now from $A$ and $\neg B$ we can conclude that $(\sqrt{2}^\sqrt{2})^\sqrt{2} = 2$ must be irrational, which is again a contradiction, so we can conclude $\neg A\lor B$.

Finally, we have shown that $\neg A\lor\neg B$ and $\neg A\lor B$ so we can conclude $\neg A$, in other words, there is at least one pair of irrationals $r, s$ such that $r^s$ is rational. The cute part is that this proof doesn't tell us what $r$ and $s$ are, just that there is such a pair.

Community
  • 1
Rick Decker
  • 8,718
1

In A Concise Course in Algebraic Topology J.P. May proves the fundamental theorem of algebra by assuming $f\in\mathbb C[x]$ is nonconstant but has no zeros. He then splits this into two propositions.

(1) $f$ has no zeros in the set $\{x:|x|\le1\}$, and
(2) $f$ has no zeros in the set $\{x:|x|\ge 1\}$.

The contradiction comes when he calculates the degree of the function $\hat f=f/|f|$ in the two cases because in the first $\deg\hat f=0$ and in the second $\deg\hat f=\deg f\ne0$.

Karl Kroningfeld
  • 5,204