Infinite Sets and Cardinality
 Last updated
 Save as PDF
 Page ID
 28701
Preliminaries
\[ \mathbb{N}=\{1,2,3,4,...\}\mbox{ is the set of Natural Numbers, also known as the Counting Numbers}.\]
\(\mathbb{N}\) is an infinite set and is the same as \( \mathbb{Z}^+.\)
In this section, we will see how the the Natural Numbers are used as a standard to test if an infinite set is "countably infinite".
\[ \{1,2,3,...,n\} \mbox{ is a FINITE set of natural numbers from 1 to }n.\]
Recall: a onetoone correspondence between two sets is a bijection from one of those sets to the other. A bijection is a function that is onetoone and onto.
Finite Sets
Finite sets are either empty or have \(n\) elements. If a set has \(n\) elements, there exists a onetoone correspondence with the set of natural numbers, \(\{1, 2, 3, ..., n\}\) where \(n \in \mathbb{N}.\)
For example, \(\{p,q,r\}\) can be put into a onetoone correspondence with \(\{1,2,3\}\). One such function is \(p \rightarrow 1 \qquad q \rightarrow 2 \qquad r \rightarrow 3.\)
If set \(S\) has \(n\) elements, then \(S=n\). Also \(\emptyset=0.\)
Infinite Sets
An infinite set is a nonempty set which cannot be put into a onetoone correspondence with \(\{1, 2, 3, ..., n\}\) for any \(n \in \mathbb{N}\).
Cardinality
Cardinality is transitive (even for infinite sets).
\[\mbox{For all sets }A,B,C, \qquad \qquad \mbox{ if }A=B \mbox{ and } B=C \mbox{ then } A=C\]
Same Cardinality
If set \(A\) and set \(B\) have the same cardinality, then there is a onetoone correspondence from set \(A\) to set \(B\).
For a finite set, the cardinality of the set is the number of elements in the set.
Example \(\PageIndex{1}\)
Consider sets \(P\) and \(Q\). \(P=\{\mbox{olives, mushrooms, broccoli, tomatoes}\}\) and \(Q=\{\mbox{Jack, Queen, King, Ace}\}.\)
Since \(P=4 \mbox { and }Q=4\), they have the same cardinality and we can set up a onetoone correspondence such as:
\[\mbox{olives } \rightarrow \mbox{ Jack}\]
\[\mbox{mushrooms } \rightarrow \mbox{ Ace}\]
\[\mbox{broccoli } \rightarrow \mbox{ Queen}\]
\[\mbox{tomatoes } \rightarrow \mbox{ King}\]
Theorem \(\PageIndex{1}\)
An infinite set and one of its proper subsets could have the same cardinality.
 An example:

The set of integers \(\mathbb{Z}\) and its subset, set of even integers \(E = \{\ldots 4, 2, 0, 2, 4, \ldots\}.\)
The function \(f: \mathbb{Z} \to E\) given by \(f(n) = 2 n\) is onetoone and onto.
So, even though \(E \subset \mathbb{Z},\) \(E=\mathbb{Z}.\)
(This is an example, not a proof. It can be shown that this function is welldefined and a bijection.)
Countably and Uncountably Infinite
Countably Infinite
A set \(A\) is countably infinite if and only if set \(A\) has the same cardinality as \(\mathbb{N}\) (the natural numbers).
If set \(A\) is countably infinite, then \(A=\mathbb{N}.\)
Furthermore, we designate the cardinality of countably infinite sets as \(\aleph_0\) ("aleph null").
\(A=\mathbb{N}=\aleph_0 .\)
Countable
A set is countable if and only if it is finite or countably infinite.
Uncountably Infinite
A set that is NOT countable is uncountable or uncountably infinite.
Example \(\PageIndex{2}\)
\(\mathbb{Z}\) is countable.
 Initial thoughts

Thinking of how to match the natural numbers to the integers, I see how the even natural numbers could be used for the positive integers, like this:
\[2 \rightarrow 1 \qquad \qquad 4 \rightarrow 2 \qquad \qquad 6 \rightarrow 3 \qquad \qquad 8 \rightarrow 4 \qquad \mbox{ etc. by } f(n)=\frac{n}{2}.\]
However, I realize zero will need a preimage, so I can adjust the function a bit:
\[2 \rightarrow 0 \qquad \qquad 4 \rightarrow 1 \qquad \qquad 6 \rightarrow 2 \qquad \qquad 8 \rightarrow 3\qquad \mbox{ etc. by } f(n)=\frac{n2}{2}.\]
That takes care of the positive integers and zero.
For the negative integers, I need to use the odd natural numbers to get:
\[1 \rightarrow 1 \qquad \qquad 3 \rightarrow 2 \qquad \qquad 5 \rightarrow 3 \qquad \qquad \qquad 7 \rightarrow 4\qquad \mbox{ etc.} .\]
Now I need to come up with a function to accomplish this mapping to the negative integers, and after some thinking, I come up with \(f(n)=\frac{n+1}{2}.\)
These will need to fit together in a piecewise function, with one piece if \(n\) is even and the other piece if \(n\) is odd.  Proof
 Define \(f:\mathbb{N} \to \mathbb{Z}\) by \(f(n) = \begin{cases} \frac{n2}{2} & \text{if } n \mbox{ is even} \\ \frac{n+1}{2}& \text{if } n \mbox{ is odd} \end{cases}\)
\(f\) is welldefined:
Case 1: \(n\) is even. \(f(n)=\frac{n2}{2}\) and since \(n\) is even, \(n=2k\) for some integer \(k\), by definition of even.
Now, \(f(n)=\frac{2k2}{2}=k1\). Because the integers are closed under subtraction, \(k1 \in \mathbb{Z}\) so \(f(n) \in \mathbb{Z}.\)
Case 2: \(n\) is odd. \(f(n)=\frac{n+1}{2}\) and since \(n\) is odd, \(n=2j+1\) for some integer \(j\), by definition of odd.
Now, \(f(n)=\frac{2j+1+1}{2}=j1\). Because the integers are closed under addition and multiplication, \(j1 \in \mathbb{Z}\) so \(f(n) \in \mathbb{Z}.\)
By the Parity Property, \(n\) must be either even or odd, so we have shown for all natural numbers \(n\), \(f(n) \in \mathbb{Z},\) thus \(f\) is welldefined.
\(f\) is onetoone:
Let \(f(x_1)=f(x_2) \mbox{ for some } x_1,x_2 \in \mathbb{N}.\) Since \(f(x_1)=f(x_2)\), \(f(x_1)\mbox{ and }f(x_2)\) are either both nonnegative or both negative. If they are nonnegative, then \(x_1\mbox{ and }x_2\) are even and if they are negative, then \(x_1\mbox{ and }x_2\) are odd.
Case 1: \(f(x_1)\mbox{ and }f(x_2)\) are nonnegative, \(x_1\mbox{ and }x_2\) are even. \(\frac{x_12}{2}=\frac{x_22}{2}.\) Then \(x_12=x_22, \mbox{ so } x_1=x_2\) (by algebra).
Case 2:\(f(x_1)\mbox{ and }f(x_2)\) are negative, \(x_1\mbox{ and }x_2\) are odd. \(\frac{x_1+1}{2}=\frac{x_2+1}{2}.\) Then \(x_1+1=x_2+1, \mbox{ so } x_1=x_2\) (by algebra).
In both cases, if \(f(x_1)=f(x_2)\mbox{ then } x_1=x_2\) and so, by definition of onetoone, \(f\) is onetoone.
\(f\) is onto:
Let \(y \in \mathbb{Z}\). We must show there is an element in \(\mathbb{N}\) whose image is y.
Case 1: \(y\) is nonnegative; note: \(n\) is even. Choose \(n=2y+2.\) Since integers are closed under addition and multiplication, \(2y+2\) is an integer. Furthermore, since \(y \geq 0, \qquad \qquad 2y \geq 0\qquad \qquad 2y+2 >0 \mbox{ so }2y+2\in \mathbb{Z}^+\). Thus \(n \in \mathbb{N}.\)
\(f(n)=f(2y+2)= \frac{2y+22}{2}=y.\)
Case 2: \(y\) is negative; note: \(n\) is odd. Choose \(n=2y1\) Since integers are closed under subtraction and multiplication, \(2y1\) is an integer. Furthermore, since \(y < 0, \qquad \qquad 2y > 0, \qquad \qquad 2y1 > 1.\) The smallest odd integer greater than \(1\) is \(1\) , thus \(n \in \mathbb{N}.\)
\(f(n)=f(2y1)= \frac{2y1+1}{2}=\frac{2y}{2}=y.\)
By the Trichotomy Property, \(y\) is must be nonnegative or negative, so we have shown for an arbitrary element \(y,\) of the codomain, there exists an element in \(\mathbb{N}\) whose image is y and so, by definition of onto, \(f\) is onto.
Since \(f\) is a welldefined, onetoone, onto function, we have demonstrated a onetoone correspondence from \(\mathbb{N} \mbox{ to }\mathbb{Z}.\) Thus \(\mathbb{N}=\mathbb{Z}\) and therefore the set of integers, \(\mathbb{Z},\) is countable.
Theorem \(\PageIndex{2}\)
Any subset of a countable set is countable.
If \(S\) is countably infinite and \(A \subseteq S\) then \(A\) is countable.
 Proof

If \( A\) is an finite set, then it is countable. Consider the case that \( A \) is an infinite subset of \( S\). Since \(S\) is countably infinite, it can be enumerated: \(S = \{x_0, x_1, x_2, \ldots\}\). Let \(n_i\) be the \(i\)th smallest index such that \(x_{n_i} \in A\). Then \(A = \{x_{n_0}, x_{n_1}, x_{n_2}, \ldots\}\) and hence is countably infinite.
Corolary \(\PageIndex{3}\)
A set with an uncountable subset is uncountable.
Theorem \(\PageIndex{4}\)
\(\mathbb{Q}\) is countable.
 Sketch of a Proof

There is a nice proof you may have seen where all the fractions are listed in an endless matrix and it can be seen that a path can be drawn to cover all the fractions. This shows you can "line up" the rational numbers, and thus they can be "tagged" \(1, 2, 3, 4, 5, \ldots\) and so the set is countable.
Theorem \(\PageIndex{5}\)
\(\mathbb{R}\) is uncountable.
 Proof

We can show the set of real numbers in the interval \((0,1)\) are uncountable as follows:
Suppose the real numbers in the interval \((0,1)\) are countable. Then they can be written in a list, as the 1st, 2nd, etc.
Write this (infinite) list, and as it's written, we will create a number that is NOT on that list.
For example:
1st number: 0.345103592..... our number that we are creating 0.0
2nd number: 0.051023237..... our number that we are creating 0.00
3rd number: 0.840729312..... our number that we are creating 0.001
4th number: 0.859025839..... our number that we are creating 0.0011
5th number: 0.777888222..... our number that we are creating 0.00110
6th number: 0.001101111..... our number that we are creating 0.001100
7th number: 0.001100000..... our number that we are creating 0.0011001
Our scheme is to put a zero or a one in the \(i^{th}\) position depending on the digit in the \(i^{th}\) position of the \(i^{th}\) number in the list.
So, for the second number on the list, we see the second digit is a 5, and we choose a 0 for the second digit of our number being created.
So, for the third number on the list, we see the third digit is a 0, and we choose a 1 for the third digit of our number being created.
(We choose a 0 unless the digit we are comparing to is a 0 and then we choose a 1.)
Do you see that the number being created will never be on the list of real numbers?
More formally, if we describe the "wannabe" list of real numbers in the interval \((0,1)\) using subscripts for each digit:\(0.a_{11}a_{12}a_{13}a_{14}a_{15} \ldots \)
\(0.a_{21}a_{22}a_{23}a_{24}a_{25} \ldots \)
\(0.a_{31}a_{32}a_{33}a_{34}a_{35} \ldots \)
etc.
Then create \(d_n= \begin{cases} 1 & \text{if } a_{nn} \neq 0\ \\ 0 & \text{if } a_{nn}=0\end{cases}\)
\(d\) is the created number which will never be on the list.
It is impossible to put all the real numbers in the interval \((0,1)\) in a list (that number being created will always be left off the list), and thus that set of numbers is uncountable.
Since the interval \((0,1)\) which is a subset of \(\mathbb{R}\) is uncountable, then \(\mathbb{R}\) is also uncountable (Corollary 5.6.3).
This proof is known as Cantor's Diagonalization Process. Georg Cantor was a pioneer in the field of different sizes of infinite sets.
Transfinite Numbers
As mentioned earlier, \(\aleph_0\) is used to denote the cardinality of a countable set. Transfinite numbers are used to describe the cardinalities of "higher & higher" infinities.
\(\aleph_0=\mathbb{N}=\mathbb{Z}=\mathbb{Q}\) cardinality of countably infinite sets.
\(\aleph_1=\mathbb{R}=(0,1)= \scr{P}(\mathbb{N})\) cardinality of the "lowest" uncountably infinite sets; also known as "cardinality of the continuum".
\(\aleph_2=\scr{P}(\mathbb{R})= \scr{P}(\scr{P}(\mathbb{N}))\) cardinality of the next uncountably infinite sets
From this we see that \(2^{\aleph_0}=\aleph_1\).
Other strange math can be done with transfinite numbers such as \(\aleph_1 + \aleph_0 = \aleph_1.\)
The proof that a set cannot be mapped onto its power set is similar to the Russell paradox, named for Bertrand Russell.
The continuum hypothesis is the statement that there is no set whose cardinality is strictly between that of \(\mathbb{N} \mbox{ and } \mathbb{R}\). The continuum hypothesis actually started out as the continuum conjecture, until it was shown to be consistent with the usual axioms of the real number system (by Kurt Gödel in 1940), and independent of those axioms (by Paul Cohen in 1963).
Summary and Review
 A bijection (onetoone correspondence), a function that is both onetoone and onto, is used to show two sets have the same cardinality.
 An infinite set that can be put into a onetoone correspondence with \(\mathbb{N}\) is countably infinite.
 Finite sets and countably infinite are called countable.
 An infinite set that cannot be put into a onetoone correspondence with \(\mathbb{N}\) is uncountably infinite.
 \(\mathbb{Z} \mbox{ and } \mathbb{Q} \) are countably infinite sets.
 \(\mathbb{R}\) is an uncountably infinite set.
 \(\mathbb{N}= \aleph_0\)
 \(\mathbb{R}= \aleph_1\)
Exercises
Exercise \(\PageIndex{1}\label{ex:invfcn01}\)
 Solution

Exercise \(\PageIndex{2}\label{ex:invfcn02}\)
text needed
Exercise \(\PageIndex{3}\label{ex:invfcn03}\)
text needed
 Solution

text needed
Exercise \(\PageIndex{4}\label{ex:invfcn04}\)
text needed
Exercise \(\PageIndex{5}\label{ex:invfcn05}\)
text needed
 Solution

text needed
Exercise \(\PageIndex{6}\label{ex:invfcn06}\)
text needed
Exercise \(\PageIndex{7}\)
text needed
 Solution

text needed
Exercise \(\PageIndex{8}\label{ex:invfcn08}\)
text needed
Exercise \(\PageIndex{9}\label{ex:invfcn09}\)
text needed
 Solution

text needed
Exercise \(\PageIndex{10}\label{ex:invfcn10}\)
text needed
Exercise \(\PageIndex{11}\label{ex:invfcn11}\)
text needed
 Proof

text needed

Exercise \(\PageIndex{12}\label{ex:invfcn12}\)
text needed
Exercise \(\PageIndex{13}\)
text needed
 Proof

text needed
Exercise \(\PageIndex{14}\)
text needed