Suppose that \(\mathscr{S}\) is a non-empty collection of sets. We define a relation \(\approx\) on \(\mathscr{S}\) by \(A \approx B\) if and only if there exists a one-to-one function \(f\) from \(A\) onto \(B\) (sometimes called a bijection). That is, \(A\) and \(B\) are in one-to-one correspondence.
The relation \(\approx\) is an equivalence relation on \(\mathscr{S}\).
Two sets that are in one-to-one correspondence are said to have the same cardinality. Thus, the equivalence classes under this equivalence relation capture the notion of having the same number of elements.
Let \(\N_0 = \emptyset\), and for \(k \in \N_+\), let \(\N_k = \{0, 1, \ldots k - 1\}\). Technically, a set \(A\) is finite if \(A \approx \N_k\) for some \(k \in \N\), in which case \(k\) is the cardinality of \(A\), and we write \(\#(A) = k\). Think of \(\N_k\) as a reference set with \(k\) elements; any other set with \(k\) elements must be equivalent to this one. Appropriately enough, a set is infinite if it's not finite. We will study the cardinality of finite sets in the next two sections on Counting Measure and Combinatorial Structures. In this section, we will concentrate primarily on infinite sets.
If \( S \) is a set, recall that \(\mathscr{P}(S)\) denotes the power set of \(S\) (the set of all subsets of \(S\)), and \(\{0, 1\}^S\) denotes the set of functions from \(S\) into \(\{0, 1\}\).
If \(S\) is a set then \(\mathscr{P}(S) \approx \{0, 1\}^S\).
The mapping that takes a set \(A \subseteq S\) into its indcator function \(\boldsymbol{1}_A\) is a bijection.
A set that is equivalent to the set of natural numbers \(\N\) is said to be countably infinite. A set that is either finite or countably infinite is said to be countable. Countable sets play a very important role in probability theory, as in many other branches of mathematics. Appropriately enough, a set that is not countable is said to be uncountable. We will soon see that there are such sets.
The set of even natural numbers \(E = \{0, 2, 4, \ldots\}\) is countable infinite, and the set of integers \(\Z\) is countable infinite.
A one-to-one mapping from \(\N\) onto \(E\) can be constructed by mapping \(n\) to \(2\,n\). A one-to-one mapping from \(\N\) onto \(\Z\) can be constructed by mapping the even natural numbers one-to-one onto the natural numbers via \(n \mapsto \frac{n}{2}\), and the odd natural numbers one-to-one onto the negative integers via \(n \mapsto -\frac{n + 1}{2}\).
Suppose that \(A\) is a set with at least two elements, and let \(S = A^\N\), the set of all functions from \(\N\) into \(A\). The elements of \(S\) can also be thought of as infinite sequences indexed by \(\N\) and taking values in \(A\). The set \(S\) is uncountable.
The proof is by contradiction, and uses a nice trick known as the diagonalization method. Suppose that \(S\) is countably infinite (it's clearly not finite), so that the elements of \(S\) can be enumerated: \(S = \{f_0, f_1, f_2, \ldots\}\). Let \(a\) and \(b\) denote distinct elements of \(A\) and define \(g: \N \to A\) by \(g(n) = b\) if \(f_n(n) = a\) and \(g(n) = a\) if \(f_n(n) \ne a\). Note that \(g \ne f_n\) for each \(n \in \N\), so \(g \notin S\). This contradicts the fact that \(S\) is the set of all functions from \(\N\) into \(A\).
Surely a set must be as least as large as any of its subsets, in terms of cardinality. On the other hand, it might also seem that the set of even natural numbers is only half the size of the set of all natural numbers, and that the set of integers is twice the size of the set of natural numbers. However, by a Exercise 3, the three sets have exactly the same size, in terms of cardinality. In this subsection, we will explore some interesting and somewhat paradoxical results that relate to subsets of infinite sets. Along the way, we will see that the countable infinity is the smallest
of the infinities.
If \(S\) is an infinite set then \(S\) has a countable infinite subset.
Select \(a_0 \in S\). It's possible to do this since \(S\) is infinite and therefore nonempty. Inductively, having chosen \(\{a_0, a_1, \ldots, a_{k-1}\} \subseteq S\), select \(a_k \in S \setminus \{a_0, a_1, \ldots, a_{k-1}\}\). Again, it's possible to do this since \(S\) is not finite. Manifestly, \(\{a_0, a_1, \ldots \}\) is a countably infinite subset of \(S\).
A set \(S\) is infinite if and only if \(S\) is equivalent to a proper subset of \(S\).
If \(S\) is finite, then \(S\) is not equivalent to a proper subset by the pigeonhole principle
. If \(S\) is infinite, then \(S\) has countably infinite subset \(\{a_0, a_1, a_2, \ldots\}\) by the previous exercise. Map \(\{a_0, a_1, a_2, \ldots\}\) one-to-one onto \(\{a_0, a_2, a_4, \ldots\}\) via the map \(a_n \mapsto a_{2\,n}\). For every other element \(x \in S \setminus \{a_0, a_1, a_2, \ldots\}\), map \(x\) to \(x\). Conclude that \(S\) is equivalent to \(S \setminus \{a_1, a_3, a_5, \ldots\}\).
When \(S\) was infinite in the previous exercise, not only did we map \(S\) one-to-one onto a proper subset, we actually threw away a countably infinite subset and still maintained equivalence. Similarly, we can add a countably infinite set to an infinite set \(S\) without changing the cardinality.
If \(S\) is an infinite set and \(B\) is a countable set, then \(S \approx S \cup B\).
Consider the most extreme case where \(B\) is countably infinite and disjoint from \(S\). Then \(S\) has a countably infinite subset \(A = \{a_0, a_1, a_2, \ldots\}\), and \(B = \{b_0, b_1, b_2, \ldots\}\). Map the even order terms of \(A\) one-to-one onto \(A\) via \(a_n \mapsto a_{n/2}\), and map the odd order terms of \(A\) one-to-one onto \(B\) via \(a_n \mapsto b_{(n-1)/2}\). For every element \(x \in S \setminus A\), map \(x\) to \(x\).
In particular, if \(S\) is uncountable and \(B\) is countable then \(S \cup B\) and \(S \setminus B\) have the same cardinality as \(S\), and in particular are uncountable.
In terms of the dichotomies finite-infinite and countable-uncountable, a set is indeed at least as large as a subset. First we need a preliminary result.
If \(S\) is countably infinite and \(A\) is an infinite subset of \(S\), then \(A\) is countably infinite.
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\). Argue that \(A = \{x_{n_0}, x_{n_1}, x_{n_2}, \ldots\}\) and hence is countably infinite.
Suppose that \(A \subseteq B\).
Note that (b) is the contrapositive of (a), and (d) is the contrapositive of (c).
We will look deeper at the general question of when one set is at least as big
than another, in the sense of cardinality. Not surprisingly, this will eventually lead to a partial order on the cardinality equivalence classes
First note that if there exists a function that maps a set \(A\) one-to-one into a set \(B\), then in a sense, there is a copy of \(A\) contained in \(B\). Hence \(B\) should be at least as large as \(A\).
Suppose that \(f: A \to B\) is one-to-one.
Note that \(f\) maps \(A\) one-to-one onto \(f(A)\), and \(f(A) \subseteq B\). Now use the Exercise 9.
On the other hand, if there exists a function that maps a set \(A\) onto a set \(B\), then in a sense, there is a copy of \(B\) contained in \(A\). Hence \(A\) should be at least as large as \(B\).
Suppose that \(f: A \to B\) is onto.
For each \(y \in B\), select a specific \(x \in A\) with \(f(x) = y\) (if you are persnickety, you may need to invoke the axiom of choice). Let \(C\) be the set of chosen points. Argue that \(f\) maps \(C\) one-to-one onto \(B\), and \(C \subseteq A\). Now use the Exercise 9.
The previous exercise also could be proved from the one before, since if there exists a function \(f\) mapping \(A\) onto \(B\), then there exists a function \(g\) mapping \(B\) one-to-one into \(A\). This duality is proven in the discussion of the axiom of choice. A simple and useful corollary of the previous two theorems is that if \(B\) is a given countably infinite set, then a set \(A\) is countable if and only if there exists a one-to-one function \(f\) from \(A\) into \(B\), if and only if there exists a function \(g\) from \(B\) onto \(A\).
If \(A_i\) is a countable set for each \(i\) in a countable index set \(I\), then \(\bigcup_{i \in I} A_i\) is countable.
Consider the most extreme case in which the index set \(I\) is countably infinite. There exists a function \(f_i\) that maps \(\N\) onto \(A_i\) for each \(i \in \N\). Let \(M = \{2^i 3^j: i \in \N, \; j \in \N\}\). Note that \(M\) is countably infinite. Define \(f: M \to \bigcup_{i \in I} A_i\) by \(f(2^i 3^j) = f_i(j)\). Then \(f\) is well-defined and is onto.
If \(A\) and \(B\) are countable then \(A \times B\) is countable.
There exists a function \(f\) that maps \(\N\) onto \(A\), and there exists a function \(g\) that maps \(\N\) onto \(B\). Again, let \(M = \{2^i 3^j: i \in \N, \; j \in \N\}\). Note that \(M\) is countably infinite. Define \(h: M \to A \times B\) by \(h(2^i 3^j) = (f(i), g(j))\). Then \(h\) is well-defined and is onto.
The last result could also be proven from the one before, by noting that
\[ A \times B = \bigcup_{a \in A} \{a\} \times B \]Both proofs work because the set \(M\) is essentially a copy of \(\N \times \N\), embedded inside of \(\N\). The last theorem generalizes to the statement that a finite product of countable sets is still countable. But, from Exercise 4, a product of infinitely many sets (with at least 2 elements each) will be uncountable.
The set of rational numbers \(\Q\) is countably infinite.
The sets \(\Z\) and \(\N_+\) are countably infinite. The set \(\Z \times \N_+\) is countably infinite. The function \(f: \Z \times \N_+ \to \Q\) given by \(f(m, n) = \frac{m}{n}\) is onto.
A real number is algebraic if it is the root of a polynomial function (of degree 1 or more) with integer coefficients. Rational numbers are algebraic, as are rational roots of rational numbers (when defined). Moreover, the algebraic numbers are closed under addition, multiplication, and division. A real number is transcendental if it's not algebraic. The numbers \(e\) and \(\pi\) are transcendental, but we don't know very many other transcendental numbers by name. However, as we will see, most (in the sense of cardinality) real numbers are transcendental.
The set of algebraic numbers \(\A\) is countably infinite.
Let \(\Z_0 = \Z \setminus \{0\}\) and let \(\Z_n = \Z^{n-1} \times \Z_0\) for \(n \in \N_+\). The set \(\Z_n\) is countably infinite for each \(n\). Let \(C = \bigcup_{n=1}^\infty \Z_n\). Think of \(C\) as the set of coefficients and note that \(C\) is countably infinite. Let \(P\) denote the set of polynomials of degree 1 or more, with integer coefficients. The function \((a_0, a_1, \ldots, a_n) \mapsto a_0 + a_1\,x + \cdots + a_n\,x^n\) maps \(C\) onto \(P\). A polynomial of degree \(n\) in \(P\) has at most \(n\) roots, by the fundamental theorem of algebra.
Now let's look at some uncountable sets.
The interval \([0, 10)\) is uncountable.
Let \(S\) denote the set of all functions from \(\N\) into \(\{0, 1, \ldots, 9\}\), thought of as infinite sequences. The set \(S\) is uncountable. Let \(N\) denote the set of all sequences in \(S\) that eventually end in all 9's. The set \(N\) is countably infinite. The set \(D = S \setminus N\) has the same cardinality as \(S\), and in particular is uncountable. The mapping \(f\) that takes a sequence in \(\boldsymbol{x} = (x_0, x_1, \ldots) \in D\) and returns the corresponding decimal expansion \(x_0.x_1\,x_2\ldots\) is one to one and onto \([0, 10)\).
The following sets have the same cardinality, and in particular all are uncountable:
You can find a linear function that maps an interval one-to-one onto another interval, as long as the two intervals are of the same type--that is, both bounded or unbounded, and both with the same type of closure. A closed (or half-closed) interval differs from its open counterpart by two (or one) points. The natural logarithm function \( \ln \) maps the interval \((0, \infty)\) one-to-one onto \(\R\). The tangent function \( \tan \) maps the interval \((-\frac{\pi}{2}, \frac{\pi}{2})\) one-to-one onto \(\R\). The irrational numbers can be obtained from the real numbers by removing the rational numbers (a countably infinite set), and similarly, the transcendental numbers can be obtained from the real numbers by removing the algebraic numbers (again a countably infinite set).
Suppose that \(\mathscr{S}\) is a nonempty collection of sets. We define the relation \(\preceq\) on \(\mathscr{S}\) by \(A \preceq B\) if and only if there exists a one-to-one function \(f\) from \(A\) into \(B\), if and only if there exists a function \(g\) from \(B\) onto \(A\). In light of the previous subsection, \(A \preceq B\) should capture the notion that \(B\) is at least as big as \(A\), in the sense of cardinality.
The relation \(\preceq\) is reflexive and transitive.
Thus, we can use the construction in the section on on Equivalence Relations to first define an equivalence relation on \(\mathscr{S}\), and then extend \(\preceq\) to a true partial order on the collection of equivalence classes. The only question that remains is whether the equivalence relation we obtain in this way is the same as the one that we have been using in our study of cardinality. Rephrased, the question is this: If there exists a one-to-one function from \(A\) into \(B\) and a one-to-one function from \(B\) into \(A\), does there necessarily exist a one-to-one function from \(A\) onto \(B\)? Fortunately, the answer is yes; the result is known as the Schröder-Bernstein Theorem, named for Ernst Schröder and Sergi Bernstein.
If \(A \preceq B\) and \(B \preceq A\) then \(A \approx B\).
Set inclusion \(\subseteq\) is a partial order on \(\mathscr{P}(A)\) (the power set of \(A\)) with the property that every subcollection of \(\mathscr{P}(A)\) has a supremum (namely the union of the subcollection). Suppose that \(f\) maps \(A\) one-to-one into \(B\) and \(g\) maps \(B\) one-to-one into \(A\). Define the function \(h: \mathscr{P}(A) \to \mathscr{P}(A)\) by \(h(U) = A \setminus g[B \setminus f(U)]\) for \(U \subseteq A\). Then \(h\) is increasing: if \(U \subseteq V\) then \(h(U) \subseteq h(V)\). From the fixed point theorem for partially ordered sets, there exists \(U \subseteq A\) such that \(h(U) = U\). Hence \(g[B \setminus f(U)] = A \setminus U\). Now define \(F: A \to B\) by \(F(x) = f(x)\) if \(x \in U\) and \(F(x) = g^{-1}(x)\) if \(x \in A \setminus U\). Then \(F\) is one-to-one and onto.
We will write \(A \prec B\) if \(A \preceq B\), but \(A \not \approx B\), That is, there exists a one-to-one function from \(A\) into \(B\), but there does not exist a function from \(A\) onto \(B\). Note that \(\prec\) would have its usual meaning if applied to the equivalence classes. That is, \([A] \prec [B]\) if and only if \([A] \preceq [B]\) but \([A] \ne [B]\). Intuitively, of course, \(A \prec B\) means that \(B\) is strictly larger than \(A\), in the sense of cardinality.
\(A \prec B\) in each of the following cases:
We close our discussion with the observation that for any set, there is always a larger set.
If \(S\) is a set then \(S \prec \mathscr{P}(S)\).
First, it's trivial to map \(S\) one-to-one into \(\mathscr{P}(S)\); just map \(x\) to \(\{x\}\). Suppose now that \(f\) maps \(S\) onto \(\mathscr{P}(S)\) and let \(R = \{x \in S: x \notin f(x)\}\). Since \(f\) is onto, there exists \(t \in S\) such that \(f(t) = R\). Note that \(t \in f(t)\) if and only if \(t \notin f(t)\).
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 \(\N\) and \(\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).
If \( S \) is uncountable, then there exists \( A \subseteq S \) such that \( A \) and \( A^c \) are uncountable.
There is an easy proof, assuming the continuum hypothesis. Under this hypothesis, if \( S \) is uncountable then \( [0, 1) \preceq S \). Hence there exists a one-to-one function \( f: [0, 1) \to S \). Let \( A = f[0, \frac{1}{2}) \). Then \( A \) is uncountable, and since \( f[\frac{1}{2}, 1) \subseteq A^c \), \( A^c \) is uncountable.
There is a more complicated proof just using the axiom of choice.