\[ \mathbb
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.\) For example, \(\\) can be put into a one-to-one correspondence with \(\\). 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.\)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\).
Cardinality is transitive (even for infinite sets). \[\mboxA,B,C, \qquad \qquad \mbox< if >|A|=|B| \mbox < and >|B|=|C| \mbox < then >|A|=|C|\]
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
Theorem \(\PageIndex<1>\) An infinite set and one of its proper subsets could have the same cardinality. An example: The set of integers \(\mathbb\) and its subset, set of even integers \(E = \<\ldots -4, -2, 0, 2, 4, \ldots\>.\) The function \(f: \mathbb \to E\) given by \(f(n) = 2 n\) is one-to-one and onto.
So, even though \(E \subset \mathbb,\) \(|E|=|\mathbb|.\)
(This is an example, not a proof. It can be shown that this function is well-defined and a bijection.)
A set \(A\) is countably infinite if and only if set \(A\) has the same cardinality as \(\mathbb\) (the natural numbers). If set \(A\) is countably infinite, then \(|A|=|\mathbb|.\) Furthermore, we designate the cardinality of countably infinite sets as \(\aleph_0\) ("aleph null"). \(|A|=|\mathbb|=\aleph_0 .\)
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.\]
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.\]
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.\)
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 \to \mathbb\) by \(f(n) = \begin \frac & \text n \mbox < is even>\\ -\frac& \text n \mbox < is odd>\end\)
\(f\) is well-defined:
Case 1: \(n\) is even. \(f(n)=\frac\) and since \(n\) is even, \(n=2k\) for some integer \(k\), by definition of even.
Now, \(f(n)=\frac=k-1\). Because the integers are closed under subtraction, \(k-1 \in \mathbb\) so \(f(n) \in \mathbb.\)
Case 2: \(n\) is odd. \(f(n)=-\frac\) and since \(n\) is odd, \(n=2j+1\) for some integer \(j\), by definition of odd.
Now, \(f(n)=-\frac=-j-1\). Because the integers are closed under addition and multiplication, \(-j-1 \in \mathbb\) so \(f(n) \in \mathbb.\)
By the Parity Property, \(n\) must be either even or odd, so we have shown for all natural numbers \(n\), \(f(n) \in \mathbb,\) 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.\) 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=\frac.\) 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=-\frac.\) 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\). We must show there is an element in \(\mathbb\) 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^+\). Thus \(n \in \mathbb.\)
\(f(n)=f(2y+2)= \frac=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.\)
\(f(n)=f(-2y-1)= -\frac=\frac=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\) 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 \mbox< to >\mathbb.\) Thus \(|\mathbb|=|\mathbb|\) and therefore the set of integers, \(\mathbb,\) 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 = \\). Let \(n_i\) be the \(i\)th smallest index such that \(x_ \in A\). Then \(A = \, x_, x_, \ldots\>\) and hence is countably infinite.
Corolary \(\PageIndex<3>\) A set with an uncountable subset is uncountable. Theorem \(\PageIndex<4>\)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>\)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^\) position depending on the digit in the \(i^\) position of the \(i^\) 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_a_a_a_a_ \ldots \)
\(0.a_a_a_a_a_ \ldots \)
\(0.a_a_a_a_a_ \ldots \)
etc.
Then create \(d_n= \begin 1 & \text a_ \neq 0\ \\ 0 & \text a_=0\end\)
\(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\) is uncountable, then \(\mathbb\) 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.
Solution
