A.1: Cardinality-additional info

Basic Theory

Definitions

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$. The relation $\approx$ is an equivalence relation on $\mathscr{S}$. That is, for all $A, \, B, \, C \in \mathscr{S}$,

1. $A \approx A$, the reflexive property
2. If $A \approx B$ then $B \approx A$, the symmetric property
3. If $A \approx B$ and $B \approx C \ $ then $A \approx C$, the transitive property

Proof

a. The identity function $I_A$ on $A$, given by $I_A(x) = x$ for $x \in A$, maps $A$ one-to-one onto $A$. Hence $A \approx A$.

b. If $A \approx B$ then there exists a one-to-one function $f$ from $A$ onto $B$. But then $f^{-1}$ is a one-to-one function from $B$ onto $A$, so $B \approx A$.

c. Suppose that $A \approx B$ and $B \approx C$. Then there exists a one-to-one function $f$ from $A$ onto $B$ and a one-to-one function $g$ from $B$ onto $C$. But then $g \circ f$ is a one-to-one function from $A$ onto $C$, so $A \approx C$.

A one-to-one function $f$ from $A$ onto $B$ is sometimes called a bijection. Thus if $A \approx B$ then $A$ and $B$ are in one-to-one correspondence and are said to have the same cardinality. The equivalence classes under this equivalence relation capture the notion of having the same number of elements.

Let $\mathbb{N}_0 = \emptyset$, and for $k \in \mathbb{N}_+$, let $\mathbb{N}_k = \{0, 1, \ldots k - 1\}$. As always, $\mathbb{N} = \{0, 1, 2, \ldots\}$ is the set of all natural numbers.

Suppose that $A$ is a set.

1. $A$ is finite if $A \approx \mathbb{N}_k$ for some $k \in \mathbb{N}$, in which case $k$ is the cardinality of $A$, and we write $\#(A) = k$.
2. $A$ is infinite if $A$ is not finite.
3. $A$ is countably infinite if $A \approx \mathbb{N}$.
4. $A$ is countable if $A$ is finite or countably infinite.
5. $A$ is uncountable if $A$ is not countable.

In part (a), think of $\mathbb{N}_k$ as a reference set with $k$ elements; any other set with $k$ elements must be equivalent to this one. 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. In part (d), a countable set is one that can be enumerated or counted by putting the elements into one-to-one correspondence with $\mathbb{N}_k$ for some $k \in \mathbb{N}$ or with all of $\mathbb{N}$. An uncountable set is one that cannot be so counted. Countable sets play a special role in probability theory, as in many other branches of mathematics. Apriori, it's not clear that there are uncountable sets, but we will soon see examples.

Preliminary Examples

If $S$ is a set, recall that $\mathscr{P}(S)$ denotes the power set of $S$ (the set of all subsets of $S$). If $A$ and $B$ are sets, then $A^B$ is the set of all functions from $B$ into $A$. In particular, $\{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$.

Proof

The mapping that takes a set $A \in \mathscr{P}(S)$ into its indicator function $\boldsymbol{1}_A \in \{0, 1\}^S$ is one-to-one and onto. Specifically, if $A, \, B \in \mathscr{P}(S)$ and $\bs{1}_A = \bs{1}_B$, then $A = B$, so the mapping is one-to-one. On the other hand, if $f \in \{0, 1\}^S$ then $f = \bs{1}_A$ where $A = \{x \in S: f(x) = 1\}$. Hence the mapping is onto.

Next are some examples of countably infinite sets.

The following sets are countably infinite:

1. The set of even natural numbers $E = \{0, 2, 4, \ldots\}$
2. The set of integers $\mathbb{Z}$

Proof

a. The function $f: \mathbb{N} \to E$ given by $f(n) = 2 n$ is one-to-one and onto.

b. The function $g: \mathbb{N} \to \mathbb{Z}$ given by $g(n) = \frac{n}{2}$ if $n$ is even and $g(n) = -\frac{n + 1}{2}$ if $n$ is odd, is one-to-one and onto.

At one level, it might seem that $E$ has only half as many elements as $\mathbb{N}$ while $\mathbb{Z}$ has twice as many elements as $\mathbb{N}$. as the previous result shows, that point of view is incorrect: $\mathbb{N}$, $E$, and $\mathbb{Z}$ all have the same cardinality (and are countably infinite). The next example shows that there are indeed uncountable sets.

If $A$ is a set with at least two elements then $S = A^\mathbb{N}$, the set of all functions from $\mathbb{N}$ into $A$, is uncountable.

Proof

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: \mathbb{N} \to A$ by $g(n) = b$ if $f_n(n) = a$ and $g(n) = a$ if $f_n(n) \mathbb{N}e a$. Note that $g \mathbb{N}e f_n$. for each $n \in \mathbb{N}$, so $g \mathbb{N}otin S$. This contradicts the fact that $S$ is the set of allfunctions from $\mathbb{N}$ into $A$.

Subsets of Infinite Sets

Surely a set must be as least as large as any of its subsets, in terms of cardinality. On the other hand, by example (4), the set of natural numbers $\mathbb{N}$, the set of even natural numbers $E$ and the set of integers $\mathbb{Z}$ all have exactly the same cardinality, even though $E \subset \mathbb{N} \subset \mathbb{Z}$. 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.

Proof

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$.

Proof

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 result. Define the function $f: S \to S$ by $f \left(a_n\mathbb{R}ight) = a_{2 n}$ for $n \in \mathbb{N}$ and $f(x) = x$ for $x \in S \setminus \{a_0, a_1, a_2, \ldots\}$. Then $f$ maps $S$ one-to-one onto $S \setminus \{a_1, a_3, a_5, \ldots\}$.

When $S$ was infinite in the proof of the previous result, 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$.

Proof

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\}$ by the result above, and $B$ can be enumerated, so $B = \{b_0, b_1, b_2, \ldots\}$. Define the function $f: S \to S \cup B$ by $f\left(a_n\mathbb{R}ight) = a_{n/2}$ if $n$ is even, $f\left(a_n\mathbb{R}ight) = b_{(n-1)/2}$ if $n$ is odd, and $f(x) = x$ if $x \in S \setminus \{a_0, a_1, a_2, \ldots\}$. Then $f$ maps $S$ one-to-one onto $S \cup B$.

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 \subseteq S$ then $A$ is countable.

Proof

It suffices to show that if $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$. Then $A = \{x_{n_0}, x_{n_1}, x_{n_2}, \ldots\}$ and hence is countably infinite.

Suppose that $A \subseteq B$.

1. If $B$ is finite, then $A$ is finite.
2. If $A$ is infinite, then $B$ is infinite.
3. If $B$ is countable, then $A$ is countable.
4. If $A$ is uncountable, then $B$ is uncountable.

Proof

a. This is clear from the definition of a finite set.

b. This is the contrapositive of (a).

c. If $A$ is finite, then $A$ is countable. If $A$ is infinite, then $B$ is infinite by (b) and hence is countably infinite. But then $A$ is countably infinite by (9).

d. This is the contrapositive of (c).

Comparisons by one-to-one and onto functions

We will look deeper at the general question of when one set is at least as big as 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.

1. If $B$ is finite then $A$ is finite.
2. If $A$ is infinite then $B$ is infinite.
3. If $B$ is countable then $A$ is countable.
4. If $A$ is uncountable then $B$ is uncountable.

Proof

Note that $f$ maps $A$ one-to-one onto $f(A)$. Hence $A \approx f(A)$ and $f(A) \subseteq B$. The results now follow from (10):

a. If $B$ is finite then $f(A)$ is finite and hence $A$ is finite.

b. If $A$ is infinite then $f(A)$ is infinite and hence $B$ is infinite.

c. If $B$ is countable then $f(A)$ is countable and hence $A$ is countable.

d. If $A$ is uncountable then $f(A)$ is uncountable and hence $B$ is uncountable.

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.

1. If $A$ is finite then $B$ is finite.
2. If $B$ is infinite then $A$ is infinite.
3. If $A$ is countable then $B$ is countable.
4. If $B$ is uncountable then $A$ is uncountable.

Proof

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. Then $f$ maps $C$ one-to-one onto $B$, so $C \approx B$ and $C \subseteq A$. The results now follow from (11):

a. If $A$ is finite then $C$ is finite and hence $B$ is finite.

b. If $B$ is infinite then $C$ is infinite and hence $A$ is infinite.

c. If $A$ is countable then $C$ is countable and hence $B$ is countable.

d. If $B$ is uncountable then $C$ is uncountable and hence $A$ is uncountable.

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.

Proof

Consider the most extreme case in which the index set $I$ is countably infinite. Since $A_i$ is countable, there exists a function $f_i$ that maps $\mathbb{N}$ onto $A_i$ for each $i \in \mathbb{N}$. Let $M = \left\{2^i 3^j: (i, j) \in \mathbb{N} \times \mathbb{N}\mathbb{R}ight\}$. Note that the points in $M$ are distinct, that is, $2^i 3^j \mathbb{N}e 2^m 3^n$ if $(i, j), \, (m, n) \in \mathbb{N} \times \mathbb{N}$ and $(i, j) \mathbb{N}e (m, n)$. Hence $M$ is infinite, and since $M \subset \mathbb{N}$, $M$ is countably infinite. The function $f$ given by $f\left(2^i 3^j\mathbb{R}ight) = f_i(j)$ for $(i, j) \in \mathbb{N} \times \mathbb{N}$ maps $M$ onto $\bigcup_{i \in I} A_i$, and hence this last set is countable.

If $A$ and $B$ are countable then $A \times B$ is countable.

Proof

There exists a function $f$ that maps $\mathbb{N}$ onto $A$, and there exists a function $g$ that maps $\mathbb{N}$ onto $B$. Again, let $M = \left\{2^i 3^j: (i, j) \in \mathbb{N} \times \mathbb{N} \mathbb{R}ight\}$ and recall that $M$ is countably infinite. Define $h: M \to A \times B$ by $h\left(2^i 3^j\mathbb{R}ight) = \left(f(i), g(j)\mathbb{R}ight)$. Then $h$ maps $M$ onto $A \times B$ and hence this last set is countable.

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 $\mathbb{N} \times \mathbb{N}$, embedded inside of $\mathbb{N}$. The last theorem generalizes to the statement that a finite product of countable sets is still countable. But, from (5), a product of infinitely many sets (with at least 2 elements each) will be uncountable.

The set of rational numbers $\mathbb{Q}$ is countably infinite.

Proof

The sets $\mathbb{Z}$ and $\mathbb{N}_+$ are countably infinite and hence the set $\mathbb{Z} \times \mathbb{N}_+$ is countably infinite. The function $f: \mathbb{Z} \times \mathbb{N}_+ \to \mathbb{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 $\mathbb{A}$ is countably infinite.

Proof

Let $\mathbb{Z}_0 = \mathbb{Z} \setminus \{0\}$ and let $\mathbb{Z}_n = \mathbb{Z}^{n-1} \times \mathbb{Z}_0$ for $n \in \mathbb{N}_+$. The set $\mathbb{Z}_n$ is countably infinite for each $n$. Let $C = \bigcup_{n=1}^\infty \mathbb{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$, and hence $P$ is countable. For $p \in P$, let $A_p$ denote the set of roots of $p$. A polynomial of degree $n$ in $P$ has at most $n$ roots, by the fundamental theorem of algebra, so in particular $A_p$ is finite for each $p \in P$. Finally, note that $\mathbb{A} = \bigcup_{p \in P} A_p$ and so $\mathbb{A}$ is countable. Of course $\mathbb{N} \subset \mathbb{A}$, so $\mathbb{A}$ is countably infinite.

Now let's look at some uncountable sets.

The interval $[0, 1)$ is uncountable.

Proof

Recall that $\{0, 1\}^{\mathbb{N}^+}$ is the set of all functions from $\mathbb{N}^+$ into $\{0, 1\}$, which in this case, can be thought of as infinite sequences or bit strings: $$\{0, 1\}^{\mathbb{N}^+} = \left\{\bs{x} = (x_1, x_2, \ldots): x_n \in \{0, 1\} \text{ for all } n \in \mathbb{N}^+\right\}$$ By (5), this set is uncountable. Let $N = \left\{\bs{x} \in \{0, 1\}^{\mathbb{N}_+}: x_n = 1 \text{ for all but finitely many } n\mathbb{R}ight\}$, the set of bit strings that eventually terminate in all 1s. Note that $N = \bigcup_{n=1}^\infty N_n$ where $N_n = \left\{\bs{x} \in \{0, 1\}^{\mathbb{N}_+}: x_k = 1 \text{ for all } k \ge n\mathbb{R}ight\}$. Clearly $N_n$ is finite for all $n \in \mathbb{N}_+$, so $N$ is countable, and therefore $S = \{0, 1\}^{\mathbb{N}_+} \setminus N$ is uncountable. In fact, $S \approx \{0, 1\}^{\mathbb{N}_+}$. The function $$\bs{x} \mapsto \sum_{n = 1}^\infty \frac{x_n}{2^n}$$ maps $S$ one-to-one onto $[0, 1)$. In words every number in $[0, 1)$ has a unique binary expansion in the form of a sequence in $S$. Hence $[0, 1) \approx S$ and in particular, is uncountable. The reason for eliminating the bit strings that terminate in 1s is to ensure uniqueness, so that the mapping is one-to-one. The bit string $x_1 x_2 \cdots x_k 0 1 1 1\cdots$ corresponds to the same number in $[0, 1)$ as the bit string $x_1 x_2 \cdots x_k 1 0 0 0\cdots$.

The following sets have the same cardinality, and in particular all are uncountable:

1. $\mathbb{R}$, the set of real numbers.
2. Any interval $I$ of $\mathbb{R}$, as long as the interval is not empty or a single point.
3. $\mathbb{R} \setminus Q$, the set of irrational numbers.
4. $\mathbb{R} \setminus \mathbb{A}$, the set of transcendental numbers.
5. $\mathscr{P}(\mathbb{N})$, the power set of $\mathbb{N}$.

Proof

a. The mapping $x \mapsto \frac{2 x - 1}{x (1 - x)}$ maps $(0, 1)$ one-to-one onto $\mathbb{R}$ so $(0, 1) \approx \mathbb{R}$. But $(0, 1) = [0, 1) \setminus \{0\}$, so $(0, 1] \approx (0, 1) \approx \mathbb{R}$, and all of these sets are uncountable by the previous result.

b. Suppose $a, \, b \in \mathbb{R}$ and $a \lt b$. The mapping $x \mapsto a + (b - a) x$ maps $(0, 1)$ one-to-one onto $(a, b)$ and hence $(a, b) \approx (0, 1) \approx \mathbb{R}$. Also, $[a, b) = (a, b) \cup \{a\}$, $(a, b] = (a, b) \cup\{b\}$, and $[a, b] = (a, b) \cup \{a, b\}$, so $(a, b) \approx [a, b) \approx (a, b] \approx [a, b]\approx \mathbb{R}$. The function $x \mapsto e^x$ maps $\mathbb{R}$ one-to-one onto $(0, \infty)$, so $(0, \infty) \approx \mathbb{R}$. For $a \in \mathbb{R}$, the function $x \mapsto a + x$ maps $(0, \infty)$ one-to-one onto $(a, \infty)$ and the mapping $x \mapsto a - x$ maps $(0, \infty)$ one to one onto $(-\infty, a)$ so $(a, \infty) \approx (-\infty, a) \approx (0, \infty) \approx \mathbb{R}$. Next, $[a, \infty) = (a, \infty) \cup \{a\}$ and $(-\infty, a] = (-\infty, a) \cup \{a\}$, so $[a, \infty) \approx (-\infty, a] \approx \mathbb{R}$.

c. $\Q$ is countably infinite, so $\mathbb{R} \setminus \Q \approx \mathbb{R}$.

d. Similarly, $\A$ is countably infinite, so $\mathbb{R} \setminus \mathbb{A} \approx \mathbb{R}$.

e. If $S$ is countably infinite, then by the previous result and (a), $\mathscr{P}(S) \approx \mathscr{P}(\mathbb{N}_+) \approx \{0, 1\}^{\mathbb{N}_+} \approx [0, 1)$.

The Cardinality Partial Order

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.

Proof

For $A \in \mathscr{S}$, the identity function $I_A: A \to A$ given by $I_A(x) = x$ is one-to-one (and also onto), so $A \preceq A$. Suppose that $A, \, B, \, C \in \mathscr{S}$ and that $A \preceq B$ and $B \preceq C$. Then there exist one-to-one functions $f: A \to B$ and $g: B \to C$. But then $g \circ f: A \to C$ is one-to-one, so $A \preceq C$.

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$.

Proof

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: $$\begin{align} U \subseteq V & \implies f(U) \subseteq f(V) \implies B \setminus f(V) \subseteq B \setminus f(U) \\ & \implies g[B \setminus f(V)] \subseteq g[B \setminus f(U)] \implies A \setminus g[B \setminus f(U)] \subseteq A \setminus g[B \setminus f(U)] \end{align}$$ From the fixed point theorem for partially ordered sets, there exists $U \subseteq A$ such that $h(U) = U$. Hence $U = A \setminus g[B \setminus f(U)]$ and therefore $A \setminus U = g[B \setminus f(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$.

$f$ maps $U$ one-to-one onto $f(U)$; $g$ maps $B \setminus f(U)$ one-to-one onto $A \setminus U$

Next we show that $F$ is one-to-one. Suppose that $x_1, \, x_2 \in A$ and $F(x_1) = F(x_2)$. If $x_1, \, x_2 \in U$ then $f(x_1) = f(x_2)$ so $x_1 = x_2$ since $f$ is one-to-one. If $x_1, \, x_2 \in A \setminus U$ then $g^{-1}(x_1) = g^{-1}(x_2)$ so $x_1 = x_2$ since $g^{-1}$ is one-to-one. If $x_1 \in U$ and $x_2 \in A \setminus U$. Then $F(x_1) = f(x_1) \in f(U)$ while $F(x_2) = g^{-1}(x_2) \in B \setminus f(U)$, so $F(x_1) = F(x_2)$ is impossible.

Finally we show that $F$ is onto. Let $y \in B$. If $y \in f(U)$ then $y = f(x)$ for some $x \in U$ so $F(x) = y$. If $y \in B \setminus f(U)$ then $x = g(y) \in A \setminus U$ so $F(x) = g^{-1}(x) = y$.

We will write $A \prec B$ if $A \preceq B$, but $A \mathbb{N}ot \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] \mathbb{N}e [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:

1. $A$ and $B$ are finite and $\#(A) \lt \#(B)$.
2. $A$ is finite and $B$ is countably infinite.
3. $A$ is countably infinite and $B$ is uncountable.

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)$.

Proof

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 \mathbb{N}otin 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 \mathbb{N}otin 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 $\mathbb{N}$ 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).

If $S$ is uncountable, then there exists $A \subseteq S$ such that $A$ and $A^c$ are uncountable.

Proof

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\left[0, \frac{1}{2}\mathbb{R}ight)$. Then $A$ is uncountable, and since $f\left[\frac{1}{2}, 1\mathbb{R}ight) \subseteq A^c$, $A^c$ is uncountable.

There is a more complicated proof just using the axiom of choice.