Non-circular

We were given a pseudo-assignment (not turned in or graded, but something we are supposed to do before class to facilitate discussion) in Set Theory to show that Weak Induction, Strong Induction, and Well-Ordering of the Naturals is all the same thing. That is, if you're given any one of them, you can prove the other two without any other axioms.

The logic isn't particularly complicated, but it is very hard not to get into circular arguments. The three assertions are so similar (especially Weak and Strong Induction) that you can easily end up proving what you started with or assuming what you were trying to prove.

For example, here's a proof of Strong Induction using Weak Induction to show that the conditions of Strong Induction imply the conditions of Weak Induction and therefore the conclusion of Weak Induction (!)

First, let's state what we're given, Weak Induction:

Let R be a subset of the Natural numbers {1, 2, 3, ...}. If

1. 1 is an element of R and
2. n is an element of R implies n+1 is an element of R

then R is the Natural numbers.

Now, what we're trying to show (renaming the conditions and the set, which should help keep them straight), Strong Induction:

Let S be a subset of the natural numbers. If

1. 1 is an element of S and
2. {1, 2, ..., n} is a subset of S implies n+1 is an element of S

then S is the Natural numbers.

We're going to show this by using Weak Induction twice. First to show that the conditions of Strong Induction imply the conditions of Weak Induction, and then to claim the result.

Obviously A implies 1 (they're the same thing).

Now, it gets harder to follow. It seems like B would necessarily imply 2 (it does, but we can't just claim that; we have to prove it). B requires that all the elements less than or equal to n be in S whereas 2 only requires that n be in R. So, rather than immediately claim the result, we have to show that it if n is in S, so is every other natural number less than n. Only then can we claim that 2 holds and use Weak Induction. The reason this argument gets hard to follow is that we prove this intermediate step using Weak Induction.

For n=1, we have that {1} is a subset of S by A.

For n≥1, we assume that {1, ..., n} is a subset of S. By B, we then know that n+1 is in S. Thus, {1, ..., n+1} is a subset of S. Therefore, by Weak Induction we have that {1, ..., n} is a subset of S for all n in the Natural numbers. If that is true, then both the condition and conclusion of 2 is true for all n in the Natural numbers and we have shown that A and B imply 1 and 2.

Therefore, S meets the conditions of Weak Induction and must be the complete set of Naturals.

That sure seems like a lot of work to show something that's pretty obvious. And, it is. But, Mathematics got in a whole pile of trouble a couple centuries ago by assuming too many things that seemed obvious in countable cases which then turned out to be very false when applied to more general sets. Rigorous proof is not an adequate defense against such things as there are some very real limits to logic, but, it's definitely the safer way to go.