5.6: Infinite Sets and Cardinality

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 one-to-one correspondence between two sets is a bijection from one of those sets to the other. A bijection is a function that is one-to-one and onto.

 

Finite Sets 

Finite sets are either empty or have \(n\) elements.  If a set has \(n\) elements, there exists a one-to-one 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 one-to-one 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 non-empty set which cannot be put into a one-to-one 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 one-to-one 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 one-to-one 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 one-to-one 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 well-defined 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{n-2}{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 piece-wise 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{n-2}{2} & \text{if } n \mbox{ is even}  \\ -\frac{n+1}{2}& \text{if } n \mbox{ is odd} \end{cases}\)
\(f\) is well-defined:
Case 1: \(n\) is even.  \(f(n)=\frac{n-2}{2}\) and since \(n\) is even, \(n=2k\) for some integer \(k\), by definition of even.
Now, \(f(n)=\frac{2k-2}{2}=k-1\). Because the integers are closed under subtraction, \(k-1 \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}=-j-1\). Because the integers are closed under addition and multiplication, \(-j-1 \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 well-defined.

\(f\) is one-to-one:
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 non-negative or both negative.  If they are non-negative, 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 non-negative, \(x_1\mbox{  and  }x_2\) are even.  \(\frac{x_1-2}{2}=\frac{x_2-2}{2}.\)  Then \(x_1-2=x_2-2, \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 one-to-one, \(f\) is one-to-one. 

\(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 non-negative; 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+2-2}{2}=y.\) 

Case 2: \(y\) is negative; note: \(n\) is odd.  Choose \(n=-2y-1\) Since integers are closed under subtraction and multiplication, \(-2y-1\) is an integer.  Furthermore, since \(y < 0, \qquad \qquad -2y > 0, \qquad \qquad -2y-1 > -1.\) The smallest odd integer greater than \(-1\) is \(1\) , thus \(n \in \mathbb{N}.\) 
\(f(n)=f(-2y-1)= -\frac{-2y-1+1}{2}=\frac{2y}{2}=y.\) 

By the Trichotomy Property, \(y\) is must be non-negative 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 well-defined, one-to-one, onto function, we have demonstrated a one-to-one 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 (one-to-one correspondence), a function that is both one-to-one and onto, is used to show two sets have the same cardinality.
• An infinite set that can be put into a one-to-one correspondence with \(\mathbb{N}\) is countably infinite.
• Finite sets and countably infinite are called countable.
• An infinite set that cannot be put into a one-to-one 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:invfcn-01}\)

 

Solution

 

Exercise \(\PageIndex{2}\label{ex:invfcn-02}\)

text needed

Exercise \(\PageIndex{3}\label{ex:invfcn-03}\)

text needed

Solution

text needed

Exercise \(\PageIndex{4}\label{ex:invfcn-04}\)

text needed

Exercise \(\PageIndex{5}\label{ex:invfcn-05}\)

text needed

Solution

text needed

Exercise \(\PageIndex{6}\label{ex:invfcn-06}\)

text needed

Exercise \(\PageIndex{7}\)

text needed

Solution

text needed

Exercise \(\PageIndex{8}\label{ex:invfcn-08}\)

text needed

Exercise \(\PageIndex{9}\label{ex:invfcn-09}\)

text needed

Solution

text needed

Exercise \(\PageIndex{10}\label{ex:invfcn-10}\)

text needed

Exercise \(\PageIndex{11}\label{ex:invfcn-11}\)

text needed

Proof

text needed

 

Exercise \(\PageIndex{12}\label{ex:invfcn-12}\)

text needed

Exercise \(\PageIndex{13}\)

text needed

 

Proof

text needed

Exercise \(\PageIndex{14}\)

text needed