# Countability in Induction

1. Nov 23, 2011

### valjok

I remember my discrete math course in university, where professor told that we can apply induction only to discrete sets. Yet, neither Wikipedia nor Google say nothing about countability importance for induction. They say that underlying set must be well-ordered. The well-ordering topic says nothing about countability also, though gives natural numbers as example. I do not understand why a closed interval of reals cannot be well-ordered?

2. Nov 24, 2011

### AKG

Induction can be applied to any well-ordered set, and there are arbitrarily large uncountable well-ordered sets - the canonical examples being the transfinite ordinals - so you're correct, countability is not necessary at all. (And in fact, induction can be applied to an even broader class of ordered sets than the well-ordered sets, namely the well-founded sets.)

Whether or not a closed interval of the reals can be well-ordered is an entirely different question. That any closed interval can be well-ordered is a consequence of the Axiom of Choice; on the other hand it is consistent for the Axiom of Choice to fail and, moreover, for every closed set of reals to be non-well-orderable.

3. Nov 24, 2011

### valjok

> so you're correct, countability is not necessary at all

Let's suppose Axiom of Choice gives us a well-ordering for the real set. Induction still uses countable indexes. How can you address uncountable matters with natural indices? Cantor's cardinality says that we cannot index real numbers with naturals!

4. Nov 24, 2011

### PatrickPowers

You might want to look at "transfinite induction."

5. Nov 24, 2011

### praeclarum

Even without assuming Choice, we can still apply what is known as "Epsilon Induction" to sets, assuming the Axiom of Regularity (ZF).

Succinctly, it states that if A contains its powerset, then A must be the universe.
http://en.wikipedia.org/wiki/Epsilon-induction

There is also a transfinite induction across the ordinals (which are themselves well-ordered by $\in$). The natural numbers $\omega$ are a tiny subset of the ordinals, and we can even define arithmetic within ordinals. Transfinite induction here would require you to prove something for the empty set, the successor, and the limit ordinal. This form of induction requires neither Regularity nor Choice (nor Infinity).

And then there is the (somewhat counter-intuitive) Well-Ordering principle, equivalent to the Axiom of Choice, which says that every set can be well-ordered.

6. Nov 24, 2011

### valjok

The transfinite induction does the same: It says that P(α+1) follows from P(α). Do you see that k+1? What about elements between α and α+1? So, anyway, counting the reals contradicts to the fact that continuum is not countable.

7. Nov 24, 2011

### AKG

http://en.wikipedia.org/wiki/Ordinal_number

and transfinite induction:

http://en.wikipedia.org/wiki/Transfinite_induction

The $\alpha$ you're referring to in your last post is an ordinal (which could be used as an index for a real number), not a real number. In particular, there are no ordinals between $\alpha$ and $\alpha+1$.

8. Nov 25, 2011

### valjok

I started a topic here just because I couldn't understand that matter. They start by natural nubmers and count to W0. Finally, they get into transfinite area, where you say we can count uncountable. I do not understand this.

9. Nov 25, 2011

### AKG

A set is "countable" if there is a surjection from the set of natural numbers to the set in question. It doesn't mean you can actually, physically "count" the elements of the set. A set is "uncountable" if it is not countable. Nobody is saying that we can "count uncountable." What exactly is it that you don't understand? If you've read the Wikipedia articles, what parts are confusing?

10. Nov 26, 2011

### valjok

> A set is "countable" if there is a surjection from the set of natural numbers to the set in question. It doesn't mean you can actually, physically "count" the elements of the set.

Why not? Countable is something that has one-to-one correspondence with naturals and I can definitely count them.

I cannot understand counting (enumerating, getting next index of) uncountable.

Thanks.

11. Nov 26, 2011

### AKG

Start counting the natural numbers and let me know when you're done :D.
Do you see how the following picture:

http://en.wikipedia.org/wiki/File:Omega_squared.png

shows a well-ordering of $\omega_0$ copies of $\omega_0$? A well order like this is said to have type $\omega_0\cdot\omega_0$ or simply, $\omega_0^2$. Now this is still countable, since one can find a bijection between the "matchsticks" in this picture and the natural numbers (just as one can find a bijection between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$). However the order type here is not $\omega_0$, because you can see it has an initial part that's ordered like $\omega_0$, but then it goes on.

So $\omega^2$ is a countable ordinal, but it has larger order type than $\omega$. Technically, we could write:

$$\omega < \omega^2;\ \ |\omega| = |\omega^2| = |\mathbb{N}|$$

Does this make sense to you so far?

Now, can you imagine the collection of all countable ordinals?

ω, ω + 1, ω + 2, …, ω·2, ω·2 + 1, …, ω2, …, ω3, …, ωω, …, ωωω, …, ε0, ….

Can you see that this collection will be (a) uncountable (by virtue of containing all the countable ordinals), and (b) well-ordered (since you can see it's a listing of increasing ordinals)? And for any element $\alpha$ in this set (e.g. ωω+5), you can find its successor $\alpha+1$ (e.g. ωω+6) which is a countable well-ordering that looks like $\alpha$, and then has one more element tacked on at the end?

Last edited: Nov 26, 2011
12. Nov 30, 2011

### valjok

> Does this make sense to you so far?
> Now, can you imagine the collection of all countable ordinals?

Sure. Both N and N2 are countable. I admit that counting all countable you hit uncountable. Yet, I do not understand how you manage to count uncountable. It seems that we transcend out of the logic. We land in the area where we count uncountable. This means that logic is broken somewhere.

13. Nov 30, 2011

### AKG

Yes, you're right, we're counting the uncountable, and logic is broken.

14. Nov 30, 2011

### Office_Shredder

Staff Emeritus
The word 'count' here is being used in the colloquial sense, and the word 'uncountable' in the technical mathematical sense. Don't confuse the two

15. Nov 30, 2011

### valjok

When I studied discrete math, there was no difference. The general meaning of counting was matching the difference between countable and uncountable exactly. When teacher introduced the subject, I have realized that I cannot state the next real, larger than zero. It exactly matches the general meaning of uncountable. Now, it seems that your Axiom of Choice can change the things.

16. Dec 3, 2011

### bpet

The underlying set does not have to be well-ordered - see http://en.wikipedia.org/wiki/Well-founded_relation.

Your teacher may have been referring to "simple" induction (i.e. prove for n=0 and prove that n implies n+1) which only applies to countable sets. The version of induction applied to well-found relations is Complete Induction.

Also, it's easy to see why complete induction works: by the well-foundedness property, if there are any untrue statements then there must be at least one "minimal" such statement that would also contradict the inductive statement.