Alternative proofs to well-known statements

There’s many theorems for which there is a particularly well known proof. I’m curious to see some alternative ones.

I’ll start with one I particularly enjoy myself, a proof of the uncountability of the reals. Most people are familiar with the diagonalization argument, which relies on the decimal expansion of the reals. The one I want to present on the other hand directly uses the axiom which distinguishes the reals from the rationals: completeness. The axiom of completeness in the form I want to use it states:

Axiom (Completeness) For any two nonempty sets X, Y ⊆ ℝ which have the property that for all x∈X and all y∈Y we have x≤y, there exists a real number c such that c is “between X and Y”, i.e. x≤c≤y for all x∈X and y∈Y.

Informally, this axiom states that you cannot “split apart” the reals. It’s easy to see that this axiom fails for the rationals: consider X as the sets of all positive numbers x such that x²<2, and Y as the set of all positive numbers such that y²>2. Then we fulfill all conditions and the number c would be √2, which is not rational.

With this, we can show the following lemma:

Lemma (Nested Intervals): Let I₁ ⊇ I₂ ⊇ I₃… be a sequence of closed intervals [aᵢ, bᵢ] such that each is contained in the previous one, i.e. a₁ ≤ a₂ ≤ … ≤ b₂ ≤ b₁. Then there exists an element c which is contained in all of these intervals.

Proof: Let A be the set of all left endpoints of the intervals and B be the set of all right endpoints. Then the sets A and B fulfill all assumptions for the axiom of completeness, and so there exists a number c with aᵢ ≤ c ≤ bᵢ for all i. This means that for any i, c ∈ Iᵢ. □

With this setup done, we can now actually go to the fun part, namely the proof that the reals are uncountable. The proof presents itself as a game between Alice and Bob. Bob claims that he has found a way to enumerate the interval [0,1], i.e. he has a countable list with all real numbers of that interval on it. Each turn of the game, Bob will name a number and Alice will name an interval. At the end of the game (i.e. after countably infinitely many turns), if Alice has managed to produce a nonempty interval which still contains a number that Bob has not listed, then Alice wins and the interval [0,1] is uncountable (and therefore so are the reals, which contain it).

  • Alice begins by naming her first interval I₀ = [0,1].
  • Bob lists his first number, x₁.
  • Now, Alice makes a choice: If x₁ is ≤ ½, then Alice will pick I₁ = [⅔,1], else she’ll pick it as [0,⅓]. Note that in either case, I₁ does not contain x₁.
  • In every subsequent turn, Bob will simply list his next number.
  • Alice will, again, make a choice:
    • if Bob’s number is not in her current interval, then she’ll name the same one again.
    • If Bob’s number is in the left half of it (including the midpoint), then she’ll name the right third of her current interval.
    • If Bob’s number is in the right half (excluding the midpoint), then she’ll name the left third of her current interval.

In all cases, Alice’s next interval is contained in her previous one, and does not contain any of Bob’s previously named numbers. Now, after they play out their game Alice has a list of nested closed intervals. By the lemma above, there’s a number c which is contained in all of them. But then c cannot have been of Bob’s list, because that would directly contradict the way Alice has chosen her intervals (since every interval contains none of the already named numbers). Therefore Alice wins the game and [0,1] is uncountable. □

It’s a bit longer than the usual diagonal argument, but I like it a lot. The only drawback is that it really does require the nested intervals lemma and therefore some version of the axiom of completeness, which is a lot harder to explain than the things that come up in the diagonalization proof.

So, what’s your favourite lesser known proof?

submitted by /u/Adarain
[link] [comments]

Published by

Nevin Manimala

Nevin Manimala is interested in blogging and finding new blogs

Leave a Reply

Your email address will not be published. Required fields are marked *