- #1

- 71

- 0

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

- Thread starter valjok
- Start date

- #1

- 71

- 0

- #2

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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 iswell-orderingtopic 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?

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

- 71

- 0

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

- 240

- 1

You might want to look at "transfinite induction."

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!

- #5

- 34

- 0

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 [itex]\in[/itex]). The natural numbers [itex]\omega[/itex] 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

- 71

- 0

- #7

AKG

Science Advisor

Homework Helper

- 2,565

- 4

You need to read about ordinal numbers:

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!

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

and transfinite induction:

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

The [itex]\alpha[/itex] 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 [itex]\alpha[/itex] and [itex]\alpha+1[/itex].

- #8

- 71

- 0

- #9

AKG

Science Advisor

Homework Helper

- 2,565

- 4

- #10

- 71

- 0

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

AKG

Science Advisor

Homework Helper

- 2,565

- 4

Start counting the natural numbers and let me know when you're done :D.Why not? Countable is something that has one-to-one correspondence with naturals and I can definitely count them.

Do you see how the following picture:I cannot understand counting (enumerating, getting next index of) uncountable.

Thanks.

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

shows a well-ordering of [itex]\omega_0[/itex] copies of [itex]\omega_0[/itex]? A well order like this is said to have type [itex]\omega_0\cdot\omega_0[/itex] or simply, [itex]\omega_0^2[/itex]. 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 [itex]\mathbb{N}\times\mathbb{N}[/itex] and [itex]\mathbb{N}[/itex]). However the order type here is not [itex]\omega_0[/itex], because you can see it has an initial part that's ordered like [itex]\omega_0[/itex], but then it goes on.

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

[tex]\omega < \omega^2;\ \ |\omega| = |\omega^2| = |\mathbb{N}|[/tex]

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 [itex]\alpha[/itex] in this set (e.g. ω

Last edited:

- #12

- 71

- 0

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

Sure. Both N and N

- #13

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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

- #14

Office_Shredder

Staff Emeritus

Science Advisor

Gold Member

- 4,174

- 333

The word 'count' here is being used in the colloquial sense, and the word 'uncountable' in the technical mathematical sense. Don't confuse the twoWe land in the area where we count uncountable. This means that logic is broken somewhere.

- #15

- 71

- 0

- #16

- 526

- 5

The underlying set does not have to be well-ordered - see http://en.wikipedia.org/wiki/Well-founded_relation.well-orderingtopic 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?

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.

- Replies
- 5

- Views
- 5K

- Replies
- 10

- Views
- 734

- Last Post

- Replies
- 5

- Views
- 3K

- Last Post

- Replies
- 9

- Views
- 3K

- Replies
- 13

- Views
- 4K

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 6K

- Last Post

- Replies
- 12

- Views
- 4K

- Last Post

- Replies
- 3

- Views
- 941

- Last Post

- Replies
- 1

- Views
- 1K