Cardinal of an infinite set

Question

In our course about combinatorics, our maths teacher recently introduced to us the notion of cardinality with the following definition:

Let $E$ be a set. If there exists an integer $n$ and a bijection $\Phi:[[1,n]] \rightarrow E$, the integer $n$ is unique and is called Cardinal.

But it doesn't cover the case where E is infinite. How could one calculate the cardinal of $\mathbb{R}$ for instance ?

Answer 1

The simplest way to look at cardinality for the first time is as a relation between sizes of sets; you can worry about the actual 'cardinal numbers' later.

(Also, the problem with cardinalities of infinite sets is that foundational issues bite really hard, so I should clarify that in what follows I work within ZFC.)

Two sets $X$ and $Y$ 'have the same cardinality' if there is a bijection between them, i.e. $|X|=|Y|$ if and only if there is some bijection $f : X \to Y$. Note I haven't defined what $|X|$ or $|Y|$ mean in isolation yet. So for example $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$, because there is a bijection $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ defined by $f(m,n)=2^m(2n+1)$ for all $m,n \in \mathbb{N}$. Another example is that $X$ is a finite set with $n$ elements if and only if $|X|=|[n]|$, where $[n] = \{ 1, 2, \dots, n \}$ - this is essentially the same as the definition of finite cardinality you've been given.

We can also define $|X| \le |Y|$ to mean that there is an injection $X \to Y$. The content of the Cantor-Schröder-Bernstein theorem is that if $|X| \le |Y|$ and $|Y| \le |X|$, then $|X|=|Y|$. We can then define $|X| < |Y|$ to mean $|X| \le |Y|$ and $|X| \ne |Y|$.

So although we haven't defined what the cardinality of a set is, we can now compare the cardinalities of sets by asking whether there is an injection and/or a bijection between them. For instance:

• $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|$. There is an injection $f : \mathbb{N} \to \mathcal{P}(\mathbb{N})$ given by $f(n)=\{n\}$ for all $n \in \mathbb{N}$. There is no bijection $\mathbb{N} \to \mathcal{P}(\mathbb{N})$ because any function $f : \mathbb{N} \to \mathbb{P}(\mathbb{N})$ is non-surjective (to see this, note that the subset $\{ n \in \mathbb{N} \mid n \not \in f(n) \}$ is not in the image of $f$.
• $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$. This can be proved using a few tricks to encode a real number as a subset of $\mathbb{N}$ and vice versa.
• If $X$ is finite then $|X| < |\mathbb{N}|$. This can be proved by induction on $|X|$ and isn't too hard.

We can give names to cardinals, for example, we normally write $\aleph_0$ for $|\mathbb{N}|$. Given a set $X$, we write $|\mathcal{P}(X)|=2^{|X|}$; thus the second bullet point above shows that $|\mathbb{R}|=2^{\aleph_0}$.

Answer 2

That is a major question in set theory, with no clear answer. In any case there is no hope in "calculating" the cardinal number of the real numbers, but you may be able to define it. This answer and concept may be beyond what you have learned so far about sets.

If your set theory is ZFC or NBGC, you can prove that any set has a bijection with at least one ordinal number. (See here if you don't know what infinite ordinal numbers are.) It is also true that there is a smallest such ordinal number. So you can define the cardinal number of $\Bbb R$ to be the smallest ordinal number that has a bijection with $\Bbb R$.

However, in many set theories, such as ZF or NBG without the axiom of choice, it is not provable that such an ordinal number exists. In "naïve" set theory (theories that existed in the 19th century), you could then define the cardinal number to be the set of all sets that has a bijection with your desired set. However, in ZF or NBG it can be proved that no such set exists: that concept is just too large to fit in the theory. In NBG there is a "class" of such sets, but again the class is so large that little can be done with it, so cardinal numbers are not defined in that way.

Does that help?