1.3: Cardinality

Note

Of course, vertical bars are used to denote other mathematical concepts; for instance, if \(x\) is a real number, \(|x|\) usually denotes the absolute value of \(x\text{.}\) You must determine from context, and from the nature of the expression within the bars, what vertical bars mean in a particular context.

Note that in the above definition, we omitted the definition of the cardinality of an infinite set. This is because defining the cardinality of an infinite set is a more complicated endeavor, and one which is, in the most general context, beyond the scope of this class. For us, it will suffice to distinguish between two types of infinite sets: countably infinite sets and uncountable (or uncountably infinite) sets.

Definition: Countable and Uncountable

A set \(S\) is said to be countably infinite if there exists a bijection from \(S\) to \(\mathbb{Z}\) (equivalently, if there exists a bijection from \(\mathbb{Z}\) to \(S\)). It is said to be countable if it is finite or countably infinite, and uncountable (or uncountably infinite) if it is not countable.

Here are some straightforward examples to get us started:

Example \(\PageIndex{1}\)

\(|\{a,b\}|=2\text{.}\)
\(|\emptyset|=0\text{.}\)
Clearly, \(\mathbb{Z}\) itself is countably infinite.

Remark

It turns out that countably infinite sets have the same cardinality as one another, while a countably infinite set and an uncountable set have different cardinalities. Intuitively, you can think of two countably infinite sets as having the same “size,” and a countable set and an uncountable set as having different “sizes”; however, this is a risky way of framing things, since it can make some results seem counterintuitive when you're used to dealing only with finite sets (see, for instance, Example \(1.3.2\)). Luckily, exploring the cardinality of infinite sets isn't the focus of this class.

Perhaps surprisingly, a proper subset of a set can have the same cardinality as its superset, as the following example shows.

Example \(\PageIndex{2}\)

We claim that \(\mathbb{Z}^+\) is countably infinite. Indeed, consider the function \(f:\mathbb{Z}^+ \to \mathbb{Z}\) defined by \(f(n)=(-1)^n \lfloor \frac{n}{2} \rfloor\text{,}\) where \(\lfloor x \rfloor\) denotes the greatest integer less than or equal to \(x\text{,}\) for each \(x\in \mathbb{R}\text{.}\) The fact that \(f\) is a bijection is demonstrated (though not proven) by the following visual representation, where each number maps via \(f\) to the value directly to the right of it:

\(\begin{array} &&1\;\;\;&0 \\&1\;\;\;&1 \\&2\;\;\;&-1 \\&3\;\;\;&2 \\&4\;\;\;&-2 \\&\vdots \;\;\;& \vdots \\ \end{array}\)

Note that this means that \(\mathbb{Z}\) and its proper subset \(\mathbb{Z}^+\) have the same cardinality, that is, the same “size”!

We summarize here examples of countably and uncountably infinite sets. (On pp. 5–6 of [1], Fraleigh sketches proofs of the facts that \(\mathbb{Q}\) is countable and that the interval \((0,1)\) in \(\mathbb{R}\) is uncountable. The proof then that \(\mathbb{R}\) is uncountable follows from Theorem \(1.3.1\), below.)

Countably infinite sets: \(\mathbb{Z}\text{,}\) \(\mathbb{Z}^+\text{,}\) \(\mathbb{Z}^-\text{,}\) \(\mathbb{Z}^*\text{,}\) \(\mathbb{Q}\text{,}\) \(\mathbb{Q}^+\text{,}\) \(\mathbb{Q}^-\text{,}\) \(\mathbb{Q}^*\text{,}\) \(\mathbb{N}\)

Uncountably infinite sets: \(\mathbb{R}\text{,}\) \(\mathbb{R}^+\text{,}\) \(\mathbb{R}^-\text{,}\) \(\mathbb{R}^*\text{,}\) \(\mathbb{C}\text{,}\) \(\mathbb{C}^*\text{,}\) the interval \((0,1)\) in \(\mathbb{R}\)

The key idea here for us is that if two sets are essentially “the same,” then they must have the same “size.” Thus, we see that there is some fundamental difference between the sets \(\mathbb{Z}\) and \(\mathbb{R}\) (in fact, there are many such differences). On the other hand, cardinality alone won't allow us to distinguish structurally between the sets \(\mathbb{Z}\) and \(\mathbb{Z}^+\text{.}\)

We end our preliminary chapter with the following theorem and a corollary of it (which can be proved using induction on \(n\)). We omit the proofs of the first two statements.

Theorem \(\PageIndex{1}\)

Let \(A\) and \(B\) be sets.

If \(A\subseteq B\) and \(A\) is infinite [uncountable] then so is \(B\text{.}\)
If \(A\subseteq B\) and \(B\) is finite [countable] then so is \(A\text{.}\)
If \(|A|=m\lt \infty\) and \(|B|=n\lt \infty\text{,}\) then \(|A\times B|=mn\text{.}\) More generally, if \(n>1\) is an integer and \(A_1, A_2, \ldots, A_n\) are sets with \(|A_i|=k_i\lt \infty\) for each \(i=1,2,\ldots, n\text{,}\) then \(|A_1 \times A_2 \times \cdots \times A_n|=k_1k_2\cdots k_n\text{.}\)
Let \(A\) and \(B\) be countable sets. Then \(A \times B\) is countable. More generally, if \(n>1\) be an integer and \(A_1,A_2,\ldots, A_n\) are countable sets, then \(A_1\times A_2\times \cdots \times A_n\) is countable.

Proof

You prove the first statement in Part 3 in your homework. The second statement in Part 3 follows using induction on the number of sets.

To prove the first statement in Part 4: Assume that \(A\) and \(B\) are both countably infinite. Since \(\mathbb{Z}^+\) is countably infinite, we can index the elements of \(A\) and of \(B\) by \(\mathbb{Z}^+\), writing

\(A=\{a_1,a_2,…\} \text{ and } B=\{b_1,b_2,…\}\).

Notice that the table

\(\begin{array} &&(a_1,b_1)\;\;\;&(a_1,b_2)\;\;\;&(a_1,b_3)\;\;\;&\cdots \\ &(a_2,b_1)\;\;\;&(a_2,b_2)\;\;\;&(a_2,b_3)\;\;\;&\cdots \\ &(a_3,b_1)\;\;\;&(a_3,b_2)\;\;\;&(a_3,b_3)\;\;\;&\cdots \\ &\vdots \;\;\;&\vdots \;\;\;&\vdots \;\;\;&\ddots \\ \end{array}\)

contains every element of \(A \times B\). We can then list the elements of \(A \times B\) by listing the elements in progressive upper-right to lower-left diagonals, starting with \((a_1,b_1)\) and moving to the right along the top row: that is, we can write

\(A×B=\{(a_1,b_1),(a_1,b_2),(a_2,b_1),(a_2,b_3),(a_2,b_2),(a_3,b_1, \cdots\}\).

This implicitly yields a bijection from \(\mathbb{Z}^+\) to \(A \times B\); thus, \(A \times B\) is countably infinite, and hence countable.

The proof in the case that one or both \(A\) and \(B\) are finite is similar; the corresponding table in that case will simply have either only finitely many rows or finitely many columns, or both.

The second statement in Part 4 follows using induction on the number of sets.

Remark

It is not true that any countable product of countable (or even finite) sets is countable. Indeed, even the set \(\{0,1\}\times \{0,1\}\times \cdots\) is uncountable. (If you want to get into the gory details of this, the key is that there is a bijection from this set to the power set of the natural numbers, which Cantor's Theorem tells us is uncountable. You are welcome to jump down this rabbit hole by googling “Cantor's Theorem,” if you desire, but know that you will not be responsible for that material in class.)