Why is $\omega$ the smallest $\infty$?

Question

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 $\Omega$ and $|\Omega| = \aleph_i$, then (assuming continuum hypothesis) the cardinality of $2^{\Omega}$ is $|2^{\Omega}| = \aleph_{i+1} > \aleph_i$ and we have $\aleph_{i+1} = 2^{\aleph_i}$.

I am fine with these argument.

What I don't understand is why should there be a smallest $\infty$? Is there a proof (or) an axiom that there exists a smallest $\infty$ 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 $\mathbb{N}$"?

The reason why I am asking this question is in "some sense" $\aleph_i = \log_2(\aleph_{i+1})$. I do not completely understand why this process should stop when $\aleph_i = \aleph_0$.

(Though coming to think about it I can feel that if I take an infinite set with $\log_2 \aleph_0$ elements I can still put it in one-to-one correspondence with the Natural number set. So Is $\log_2 \aleph_0 = \aleph_0$ (or) am I just confused? If $n \rightarrow \infty$, then $2^n \rightarrow \infty$ faster while $\log (n) \rightarrow \infty$ slower and $\log (\log (n)) \rightarrow \infty$ even slower and $\log(\log(\log (n))) \rightarrow \infty$ 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)

Answer 1

First, let me clear up a misunderstanding.

Question: Does $2^\omega = \aleph_1$? More generally, does $2^{\aleph_\alpha} = \aleph_{\alpha+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 $\omega$ 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 $\in$. One defines an "ordinal number" to be any transitive set $X$ such that $(X,\in)$ is a well ordered set. (Here, "transitive" means "every element is a subset". It's a weird condition which basically means that $\in$ is a transitive relation). For example, if $X = \emptyset$ or $X=\{\emptyset\}$ or $X = \{\{\emptyset\},\emptyset\}$, then $X$ is an ordinal. However, if $X=\{\{\emptyset\}\}$, 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 $\alpha$ and $\beta$, precisely one of the following holds: $\alpha\in\beta$ or $\beta\in\alpha$ or $\beta = \alpha$. In fact, it turns out the the collection of ordinals is well ordered by $\in$, 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 = \log_2(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 $2^k$ for some cardinal $k$.

Answer 2

Suppose $A$ is an infinite set. In particular, it is not empty, so there exists a $x_1\in A$. Now $A$ is infinite, so it is not $\{x_1\}$, so there exists an $x_2\in A$ such that $x_2\neq x_1$. Now $A$ is infinite, so it is not $\{x_1,x_2\}$, so there exists an $x_3\in A$ such that $x_3\neq x_1$ and $x_3\neq x_2$. Now $A$ is infinite, so it is not $\{x_1,x_2,x_3\}$, so there exists an $x_4\in A$ such that $x_4\neq x_1$, $x_4\neq x_2$ and $x_4\neq x_3$... And so on.

This was you can construct a sequence $(x_n)_{n\geq1}$ of elements of $A$ such that $x_i\neq x_j$ if $i\neq j$. If you define a function $f:\mathbb N\to A$ so that $f(i)=x_i$ for all $i\in\mathbb N$, then $f$ is injective.

By definition, then, the cardinal of $A$ is greater or equal to that of $\mathbb N$.

Since $\mathbb N$ is itself infinite, this shows that the smallest infinite cardinal is $\aleph_0=|\mathbb N|$.

Answer 3

Despite the fact that this is a very old question, with some very good answers there is a point I would like to add.

Assume $ZF$, if $A$ is an infinite set such that if $|B|<|A|$ then $B$ is finite, this implies $|A| = \aleph_0$. Namely, even without the axiom of choice (or any infinitary fragment of it) $\omega$ is still a minimal infinite cardinality, and it is still the only minimal infinite cardinal. This is an important distinction because without the axiom of choice it is consistent for some sets to be infinite (i.e. not in bijection with $\{0,\ldots,n-1\}$ for a natural number $n$) but have no countably infinite subset.

The Proof:

Suppose $A$ is an infinite set, which is minimal with respect to infinite cardinalities. Take $a\in A$, then $A_1 = A\setminus\{a\}$ is still an infinite set, and $A_1\subsetneq A$ therefore $|A_1|\le |A|$. By our assumption, since $A_1$ is infinite, $|A_1| = |A|$.

Take $f\colon A\to A_1$ to be a bijection, existing from the above conclusion, then $a\notin\operatorname{Rng}(f)$, reiterate the function on $A_1$, it is still a bijection between $A_1$ and $f[A_1]$.

Claim: $A_1\neq f[A_1]$

Proof: Consider $f(a)=b\in A_1$, suppose $b\in f[A_1]$ then $b=f(a')$ for some $a'\in A_1$. Since $f$ is a bijection it is injective and $f(a') = f(a)\implies a=a'$ in contradiction to the definition of $A_1=A\setminus\{a\}$.

We define the set $\{f^n(a)\mid n\in\omega\}=B$. This set is $\{a\}$ closed under the action of $f$. Since $f$ is injective, by the above argument $f^n(a) = f^m(a)\implies n=m$, and therefore this is a countable subset of $A$.

It seems questionable why we can define $B$ without some form of choice, the answer is that since we fixed $f$ we can in fact do that, if we think of $f$ as a relation, every element of $A$ is in its domain and all but $a$ are in its range. Take the transitive closure (as a relation, not as a set) of $f$, it is no longer a function, but if we take all those who stand with $a$ we have exactly $B$.

This proves $\aleph_0\le|A|$, we return to the assumption on $A$ that if a cardinal number is strictly less than $|A|$ then it is finite, and therefore $|A|=\aleph_0$.

This property cannot be proved from $ZF$ alone for any other cardinal. For example, take the model in which all reals have the perfect set property, $\aleph_1\nleq 2^{\aleph_0}$, and $CH$ holds (namely, every set of reals is countable or continuum in its size).

This means that $2^{\aleph_0}$ is a minimal cardinal over $\aleph_0$ but it is not $\aleph_1$.

---

This also shows that the cardinal numbers are quite the twisted place in the absence of choice, for example consider a model of $ZF$ with an amorphous set $A$.

That is $B\subseteq A$ then either $B$ is finite or $A\setminus B$ is finite.

If $B\subseteq A$ is a nonempty finite subset then $|A\setminus B|<|A|$, while $A\setminus B$ is still infinite. This forms a decreasing chain of infinite cardinal numbers.

To go further, if the axiom of choice does not hold there is some set which cannot be well-ordered, and will witness the illfoundedness of the cardinality relation - i.e. an infinite decreasing chain of cardinals.

Answer 4

If you assume both the continuum hypothesis and the (weaker) axiom of countable choice, then no infinite set can have cardinality strictly smaller than that of $\mathbb{N}$.

First, assume the continuum hypothesis, that there is no set of cardinality strictly between $\aleph_{0} = | \mathbb{N} |$ and $2^{\aleph_{0}} = \aleph_{1}$. Suppose $X$ is an infinite set of cardinality strictly smaller than $\aleph_{0} = |\mathbb{N}|$. Then the corresponding power sets must satisfy $|\mathcal{P}(X)| = 2^{|X|} \leq 2^{|\mathbb{N}|} = \aleph_{1}$.

If $|\mathcal{P}(X)| = \aleph_{1}$, then it follows that $2^{|X|} = 2^{|\mathbb{N}|}$, hence $|X| = |\mathbb{N}|$, which is impossible by construction. Thus, $|\mathcal{P}(X)|$ < $\aleph_{1}$, and by CH, we have $|\mathcal{P}(X)|$ < $\aleph_{0}$. Certainly, $|X|$ < $|\mathcal{P}(X)|$.

To summarize, the set $X$ has cardinality strictly less than a set (its power set) that has cardinality strictly less than $\aleph_{0}$. Continuing in this fashion, we find an infinite sequence of decreasing transfinite cardinals, and $X$ is an infinite set with arbitrarily small transfinite cardinality. (If we also assume the generalized continuum hypothesis, then there are no infinite sets with cardinality between these sets either.)

The axiom of countable choice says that there is a least transfinite cardinal, and no such pathological set $X$ can therefore exist.

Answer 5

Because $\omega$ is exactly defined to be the smallest infinite ordinal number.

You may ask why is there a smallest ordinal? The answer is: because ordinals are defined in a way that they will be well-ordered w.r.t. membership relation.

Since it is the smallest infinite ordinal, all smaller ordinals are finite and (the cardinality of) the powerset of any finite ordinal is a finite ordinal, so it cannot be the powerset of any finite ordinal. And by Cantor's diagonal argument, the cardinality of any set is strictly smaller than the cardinality of its powerset, so it cannot be the powerset of itself (or any other ordinal since any infinite ordinal contains it). So it cannot be (the cardinality of) the powerset of any ordinal.

Answer 6

I'd like to respond to a point you raised in your question that hasn't been addressed yet, as far as I can tell. You wrote: "why can't I find a set whose power set gives us N"?

Let's say there were a set $A$ such that $2^{|A|}=\aleph_0 = |\mathbb{N}|$. $A$ can be either finite or infinite. If it were infinite, this would mean its cardinality is at least $\aleph_0$. $2^{|{A}|} = 2^{\aleph_0} > \aleph_0$ by Cantor's theorem so this rules out one of the possibility. For $2^{|A|}=\aleph_0$ to hold true would therefore require a finite set the power set of which isn't finite but $2^n$ is always finite (i.e. $< |\mathbb{N}|$) for any finite $n=|A|$ therefore the set we're looking doesn't exist.

Say there is a set $B$ such that $|B| \le \aleph_0 = |\mathbb{N}|$. Start with listing the elements of $B$ as $b_1, b_2, b_3, \dots$. The list runs ad infinitum (if it stops somewhere, $B$ would be finite) and we've a way to injectively map all of $\mathbb{N}$ into $B$ by associating each $n \in \mathbb{N}$ with some $b_n \in B$ which gives us $|\mathbb{N}| \le |B|$. There's also an injection the other way around ($|B| \le |\mathbb{N}|$) and by CBS we have $|\mathbb{N}| = \aleph_0 = |B|$.