Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
I however can see that any infinite subset of $\mathbb{N}$ can be put in a bijection with $\mathbb{N}$ itself. But what is the reason/property of $\mathbb{N}$ which makes us able to do this? – user17762 Nov 13 '10 at 4:04
Might I suggest a question title more along the lines of "Why is $\omega$ the smallest infinity?" As it stands your title is...vague :-) – Jason DeVito Nov 13 '10 at 4:27
@ Jason: have changed the title. – user17762 Nov 13 '10 at 4:48
In set theory we don't mind the "speed" of growth, only the cardinality required for it. That is, a monotonous function from one cardinal to another interests us not how quickly it would grow but rather if it is bounded or not, and whether or not it could be unbounded. – Asaf Karagila Nov 13 '10 at 7:22
Just to note that Conway's Surreal Numbers allow for non-ordinal infinities less than $\omega$. – Mark Bennet Jun 28 '11 at 9:04
up vote 58 down vote accepted

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

share|cite|improve this answer
Does anything make the elementary argument not rigorous? i.e. If we have an infinite set $T$, there is a surjection from $T$ onto the naturals $1,2,3...$ (assuming AC), showing any infinite set is at least countable. – rationalis May 25 at 8:44
I think it depends on a whole host of issues, for example, what your definition of infinite is. Also, how do you create the surjection from $T$ to the naturals in the first place? – Jason DeVito 2 days ago
Definition of infinite: not finite ; not in bijection with a set of finite (i.e. natural number) cardinality. Re: surjection $T \to \mathbb{N}$, see for the corresponding injection $\mathbb{N} \to T$. – rationalis 2 days ago
@rationalis: Well, you would still need something more, like the Cantor-Schroeder-Bernsetein theorem - all your argument would show is that $|\mathbb{N}|\leq |T|$. Without the CSB theorem (which, if I recall correctly, is provable without any form of AC), you could still have a $T$ with $|T|\leq |\mathbb{N}|$ and $|\mathbb{N}|\leq |T|$. (Incidentally, Set Theory is not my area of expertise, but I think in general, people prefer injections to surjections when discussing cardinality. I think injections are better behaved without choice) – Jason DeVito yesterday

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

share|cite|improve this answer
You seem to be using at least Countable Choice (hidden in "...And so on"). – Arturo Magidin Nov 13 '10 at 5:17
Yes, this uses some form of choice, but of course for cardinals to be comparable in general you need AC. – Robin Chapman Nov 13 '10 at 11:48

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.

share|cite|improve this answer
To get an infinite descending chain of cardinals from an amorphous set as you describe, wouldn't you need DC? And wouldn't DC preclude the existence of the amorphous set in the first place? – Trevor Wilson Sep 18 '12 at 5:29
@Trevor: No, of course you don't have an infinite descending chain of sets, but these are cardinals. Generally speaking, though, if there is an infinite D-finite set then there is an order preserving embedding of $\mathbb R$ into the cardinals as well. – Asaf Karagila Sep 18 '12 at 7:42
I am not doubting the consistency of infinite decreasing chains of cardinals. I just don't understand the argument. When you said "this forms a decreasing chain..." at first I assumed that you meant that because $A\setminus B$ is still infinite, you could subtract a nonempty finite subset $C$ to get a third infinite set, and so forth. But the "and so forth" part would require DC, so perhaps this is not what you meant. – Trevor Wilson Sep 18 '12 at 14:18
@Trevor: I am not specifying sets. I am not saying "Ah, here we have $A_n\subseteq A$ which is a decreasing sequence of sets". I am pointing out that there is a decreasing sequence of cardinals. Suppose that $A$ is amorphous, define on the infinite subsets of $A$ the cardinality relation, two subsets have the same cardinality if and only if their complement has the same size. Now since all those are co-finite, and you can find arbitrary large finite complements you are done. You don't choose a representative from each class, that would be impossible. You just take them all. No choice! – Asaf Karagila Sep 18 '12 at 15:16
Oh, I see! You are saying that the chain is the set of all cardinalities of cofinite subsets of $A$ because they are all comparable. I'll have to think about this, because it's not clear to me that if $B$ and $B'$ are subsets of $A$ of the same finite size, then $|A \setminus B| = |A \setminus B'|$. – Trevor Wilson Sep 18 '12 at 15:30

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.

share|cite|improve this answer
@Arturo: No. If $X\le\aleph_0$ then $X$ is finite or of size $\aleph_0$. The Dedekind-finite sets are easily seen to be precisely those sets that $\aleph_0$ does not inject into. So, Dedekind-finite infinite sets are incomparable with $\aleph_0$. – Andrés Caicedo Nov 13 '10 at 7:25
@Arturo: Yes, exactly. If we restrict ourselves to well-ordered sets, $\aleph_0$ is the smallest infinite. Outside, we potentially have all sorts of pathologies. – Andrés Caicedo Nov 13 '10 at 7:55
Just to clarify: The statement that $X\le\aleph_0$ implies that $X$ is either finite or of the same size as ${\mathbb N}$ is provable in ZF. We do not even need Schroeder-Bernstein for this. – Andrés Caicedo Nov 13 '10 at 16:02
@Nuno: Why would you need countable choice? Let $f$ simply list $X$ in increasing order; there is no choice here. – Andrés Caicedo Nov 15 '10 at 3:57
I should point out that countable choice+CH is not enough to have $2^{\aleph_0}=\aleph_1$. In Solovay's model (or models of ZF+AD) we have that every uncountable set of reals has size continuum; but $2^{\aleph_0}\neq\aleph_1$. – Asaf Karagila May 20 '12 at 18:58

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.

share|cite|improve this answer

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

share|cite|improve this answer
"If it were infinite, this would mean its cardinality is at least $\aleph_0$". This is precisely my question. – user17762 Dec 4 '12 at 23:34
@Marvis I was under the impression that part of the question was already resolved. If it isn't still, I've edited my post explaining how I think $\aleph_0$ is the least of infinite cardinals. – Mark Dec 5 '12 at 11:02

protected by Asaf Karagila Jan 29 '14 at 16:26

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?