Countability in Induction

[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?

 

[AKG]

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?

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.

 

[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!

 

[PatrickPowers]

> 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!

You might want to look at "transfinite induction."

 

[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.

 

[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.

 

[AKG]

> 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!

You need to read about ordinal numbers:

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$.

 

[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.

 

[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?

 

[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.

 

[AKG]

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

Start counting the natural numbers and let me know when you're done :D.

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

Thanks.

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, …, ω^ω, …, ω^ωω, …, ε₀, ….

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?

 

[valjok]

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

Sure. Both N and N² 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.

 

[AKG]

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

 

[Office_Shredder]

We land in the area where we count uncountable. This means that logic is broken somewhere.

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

 

[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.

 

[bpet]

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?

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.