Why is ω\omega the smallest ∞\infty?

I am comfortable with the different sizes of infinities and Cantor’s “diagonal argument” to prove that the set of all subsets of an infinite set has cardinality strictly greater than the set itself. So if we have a set Ω and |Ω|=i, then (assuming continuum hypothesis) the cardinality of 2Ω is |2Ω|=i+1>i and we have i+1=2i.

I am fine with these argument.

What I don’t understand is why should there be a smallest ? Is there a proof (or) an axiom that there exists a smallest and that this is what we address as “countably infinite”? or to rephrase the question “why can’t I find a set whose power set gives us N“?

The reason why I am asking this question is in “some sense” i=log2(i+1). I do not completely understand why this process should stop when i=0.

(Though coming to think about it I can feel that if I take an infinite set with log20 elements I can still put it in one-to-one correspondence with the Natural number set. So Is log20=0 (or) am I just confused? If n, then 2n faster while log(n) slower and log(log(n)) even slower and log(log(log(n))) even “more” slower and so on).

Is there a clean (and relatively elementary) way to explain this to me?

(I am totally fine if you direct me to some paper (or) webpage. I tried googling but could not find an answer to my question)


First, let me clear up a misunderstanding.

Question: Does 2ω=1? More generally, does 2α=α+1?

The answer of “yes” to the first question is known as the continuum hypothesis (CH), while an answer of “yes” to the second is known as the generalized continuum hypothesis (GCH).

Answer: Both are undecidable using ZFC. That is, Godel has proven that if you assume the answer to CH is “yes”, then you don’t add any new contradictions to set theory. In particular, this means it’s impossible to prove the answer is “no”.

Later, Cohen showed that if you assume the answer is “no”, then you don’t add any new contradictions to set theory. In particular, this means it’s impossible to prove the answer is “yes”.

The answer for GCH is the same.

All of this is just to say that while you are allowed to assume an answer of “yes” to GCH (which is what you did in your post), there is no way you can prove that you are correct.

With that out of the way, let me address your actual question.

Yes, there is a proof that ω is the smallest infinite cardinality. It all goes back to some very precise definitions. In short, when one does set theory, all one really has to work with is the “is a member of” relation . One defines an “ordinal number” to be any transitive set X such that (X,) is a well ordered set. (Here, “transitive” means “every element is a subset”. It’s a weird condition which basically means that is a transitive relation). For example, if X= or X={} or X={{},}, then X is an ordinal. However, if X={{}}, then X is not.

There are 2 important facts about ordinals. First, every well ordered set is (order) isomorphic to a unique ordinal. Second, for any two ordinals α and β, precisely one of the following holds: αβ or βα or β=α. In fact, it turns out the the collection of ordinals is well ordered by , modulo the detail that there is no set of ordinals.

Now, cardinal numbers are simply special kinds of ordinal numbers. They are ordinal numbers which can’t be bijected (in, perhaps NOT an order preserving way) with any smaller ordinal. It follows from this that the collection of all cardinal numbers is also well ordered. Hence, as long as there is one cardinal with a given property, there will be a least one. One example of such a property is “is infinite”.

Finally, let me just point out that for finite numbers (i.e. finite natural numbers), one usually cannot find a solution m to m=log2(n). Thus, as least from an inductive reasoning point of view, it’s not surprising that there are infinite cardinals which can’t be written as 2k for some cardinal k.

Source : Link , Question Author : Community , Answer Author : David Zhang

Leave a Comment