Chapter 1 - Set Theory

1.2 Equivalence of Sets. The Power of a Set

Main:	Index
Previous:	1.1 Sets and Functions
Next:	1.3 Ordinal Sets and Ordinal Numbers

Results

There are two types of infinite sets: countable sets such as $\N$, and uncountable sets such as $(0,1)$. By definition, the elements of a set are unique.



Every subset of a countable set is countable.

Proof.
Let $A$ be countable, with elements $a_1, a_2, \ldots,$ and let $B$ be a subset of $A$. Among the elements $a_1, a_2, \ldots,$ let $a_{n_1}, a_{n_2},\ldots$ be those in the set $B$. If the set of numbers $n_1, n_2, \ldots$ has a largest number, then $B$ is finite. Otherwise $B$ is countable with correspondence $i\leftrightarrow a_{n_i}$.



The union of a finite or countable number of countable sets $A_1, A_2,\ldots$ is itself countable.




Every infinite set has a countable subset.

Proof.
Let $M$ be an infinite set and $a_1$ any element of $M$. Being infinite, $M$ contains an element $a_2$ distinct from $a_1$, and element $a_3$ distinct from $a_1$ and $a_2$, and so on. Continuing this process we get a countable subset $$ A = \{a_1, a_2,\ldots, a_n,\ldots\} $$ of the set $M$.


Two sets $M$ and $N$ are said to be equivalent, $M\sim N$, if there exists a one-to-one correspondence between the elements of $M$ and $N$.




Every infinite set is equivalent to one of its proper subsets.

Proof.
According to Theorem 3, any infinite set $M$ contains a countable subset: $$ A = \{a_1, a_2,\ldots, a_n,\ldots\}, $$ and partition $A$ into two countable subsets. $$ A_1 = \{a_1, a_3, a_5, \ldots\}, \quad A_2 = \{a_2, a_4, a_6, \ldots\}. $$ Obviously, we can establish a one-to-one correspondence between the countable sets $A$ and $A_1$ with $a_n\leftrightarrow a_{2n-1}$. This correspondence can be extended to a one-to-one correspondence between the sets $A\cup(M-A) = M$ and $A_1\cup(M-A) = M - A_2$ by simply assigning $x$ itself to each element $x\in M-A$. But $M-A_2$ is a proper subset of $M$.


The set of real numbers in the closed unit interval $[0,1]$ is uncountable.




Given any set $M$, let $\mathscr{M}$ be the set whose elements are all possible subsets of $M$. Then the power of $\mathscr{M}$ is greater than the power of the original set $M$.



Given two sets $A$ and $B$, suppose $A$ contains a subset $A_1$ equivalent to $B$, while $B$ contains a subset $B_1$ equivalent to $A$. Then $A$ and $B$ are equivalent.

Problem 1

A set with an uncountable subset is itself uncountable.

Proof.
A set $A$ is countable if there is a one-to-one correspondence between the elements of $A$ and $\N$, or in other words, if there exists an injective function $f: A\rightarrow \N$.

Let us call the set $A$ and the subset $S$ and assume $S$ is uncountable. Let us assume for contradiction that $A$ is countable, so there exists an injective function $f: A\rightarrow \N$. Since $S\subset A$, we can define the function $g(x) = \{f(x)\;|\; x\in S\}$ which is an injective function $g:S\rightarrow\N$. But this is impossible since $S$ is uncountable. Hence, $A$ must be uncountable.

Alternative Proof.
The statement we want to prove is: if the set $S\subset A$ is uncountable, then $A$ is uncountable.

The contrapositive statement is: if $A$ is countable, then $S\subset A$ is a countable. This follows from Theorem 1. It follows that if $S\subset A$ is uncountable, then $A$ is uncountable.

Problem 2

Let $M$ be any infinite set and $A$ any countable set. Prove that $M\sim M\cup A$.

Proof.
Assume first that $M$ is a countable. By Theorem 2, $M\cup A$ is countable, so $M\sim M\cup A$.

Assume now that $M$ is uncountable. Since $M$ is an uncountable subset of $M\cup A$, then $M\cup A$ is uncountable by Problem 1, so $M\sim M\cup A$.

Problem 3

Prove that the following sets are countable. As shown in Example 4, the set of rational numbers $\Q$ is countable.

a) The set of all numbers with two distinct decimal expansions (like $0.5000\ldots$ and $0.4999\ldots$).

Proof.
Let us call the set of numbers with two distinct decimal expansions $D$.

Any number with two distinct decimal expansions has a representation that terminates with an infinite number of 0s, which means there are a finite number of non-zero decimals. This in turn means that it can be represented as a fraction and is therefore rational. Since there are rational numbers that do not have two distinct decimal expansions, such as $1/3$ or $4/7$, the set $D$ is a proper subset of $\Q$. For every $n\in\N$, $n + 1/2 \in D$ so it is an infinite set.

We assume for contradiction that $D$ is uncountable. Since it is a proper subset of $\Q$, then by Problem 1, $\Q$ must be uncountable. This is a contradiction, so we conclude that $D$ is a countable set.

b) The set of all rational points in the plane (points with rational coordinates).

Proof.
Since $\Q$ is a countable set, we can write $\Q = \{q_1, q_2, q_3, \ldots\}$. If we fix $q_1$ we get the following set: $$ Q_1 = \{(q_1, p)\;|\; p\in\Q\}, $$ which are all rational points in the plane with $q_1$ in the $x$ position. We can create a one-to-one correspondence with $\Q$ by simply setting $p\leftrightarrow (q_1, p)$ for each $p\in\Q$, which shows that $Q_1$ is countable. For every $q_i\in\Q$ we define the following sets which are countable by the same argument. $$ Q_i = \{(q_i, p)\;|\; p\in\Q\}, $$ We can now define the following union which are all rational points in the plane: $$ \mathcal{Q} = \bigcup_{n=1}^\infty Q_n, $$ which is a countable union of countable sets. By Theorem 2, $\mathcal{Q}$ is a countable set.

c) The set of all rational intervals (intervals with rational endpoints).

Proof.
Define $\mathscr{Q}_1$ to be the set of all open intervals with rational endpoints. $$ \mathscr{Q}_1 = \{(p,q)\;|\; p,q\in\Q\}. $$ Using $\mathcal{Q}$ from (b), we can create a bijection from $\mathcal{Q}$ to $\mathscr{Q}_1$ by setting $(p,q)\leftrightarrow(p,q)$ which shows that $\mathscr{Q}_1$ is a countable set.

In a similar way, we can define the following three sets of half-open and closed intervals $$ \mathscr{Q}_2 = \{[p,q)\;|\; p,q\in\Q\}. $$ $$ \mathscr{Q}_3 = \{(p,q]\;|\; p,q\in\Q\}. $$ $$ \mathscr{Q}_4 = \{[p,q]\;|\; p,q\in\Q\}. $$ which are all countable sets by the same argument as for $\mathscr{Q}_1$. We have four countable sets, and by Theorem 2 their union is a countable set.



Will use a theorem not mentioned in the book.


A finite cartesian product of countable sets is countable.




d) The set of all polynomials with rational coefficients.
(Note: this has to be the set of all finite polynomials with rational coefficients, otherwise it isn't true. Will also try to prove this without cartesian ).

Proof.
Finite polynomials with rational coefficients are on the following form $$ p_0 + p_1x + p_2x^2 + p_3x^3 + \ldots + p_nx^n $$ where $p_i\in\Q$ for all $i$. We define the set of all rational polynomials as follows: $$ P = \{p_0 + p_1x + \ldots + p_nx^n\;|\; p_0,p_1,\ldots, p_n\in\Q\} $$ For any rational polynomial, we can create the following bijection. $$ p_0 + p_1x + p_2x^2 + \ldots + p_nx^n \leftrightarrow (p_0, p_1, p_2, \ldots, p_n)\in\Q\times\Q\times\Q\times\ldots\times\Q = \textbf{Q}^n. $$ Since $\Q$ is countable and this is a finite cartesian product, then by Theorem A.1, $\textbf{Q}^n$ is countable. Since we have a bijection between $P$ and $\textbf{Q}^n$, it follows that $P$ is countable.

Problem 4

A number $\alpha$ is said to be algebraic if it is a root of a polynomial equation with rational coefficients. Prove that the set of all algebraic numbers is countable.

Proof.
From the fundamental theorem of algebra, any non-constant $n$th degree polynomial can be factored into $n$ first degree polynomials, $$ p_0 + p_1x + p_2x^2 + p_3x^3 + \ldots + p_nx^n = r_n(x-r_0)(x-r_1)\ldots(x-r_{n-1}) $$ where $p_0,\ldots, p_n\in\Q$ and $r_0,\ldots,r_n\in\C$. Define $R$ as the set of all roots of polynomials with rational coefficients. $$ R = \{r_n(x-r_0)(x-r_1)\ldots(x-r_{n-1})\;|\; r_0, r_1, r_2, \ldots, r_n\in\C\} $$ Using the fundamental theorem, we can create a one-to-one correspondence from the set of all polynomials $P$ to the set of all roots $R$, since the roots are uniquely determined by the coefficients. $$ (p_0, p_1, p_2, \ldots, p_n) \leftrightarrow (r_0, r_1, r_2, \ldots, r_n) \leftrightarrow r_n(x-r_0)(x-r_1)\ldots(x-r_{n-1}) $$ Since we have a bijection from the countable set $P$ to $R$, the set $R$ is countable. To find the set of all algebraic numbers, we take the union of all sets $r\in (r_0, r_1, r_2, \ldots, r_n)$ and call it $\mathcal{A}$. $$ \mathcal{A} = \bigcup_{r\in R} r. $$ Since this is a countable union of countable sets, the set of all algebraic numbers $\mathcal{A}$ is countable by Theorem 2.

Problem 5

We introduce the following Lemma.

Lemma
If $M$ is an uncountable set and $A\subset M$ is a countable set, then $M-A$ is uncountable.

Proof.
Assume $M$ is uncountable and $A\subset M$ is countable. Assume for contradiction that $M-A$ is countable. Since $A$ and $M-A$ are countable, then by Theorem 2, $A\cup(M-A) = M$ is countable. But this is a contradiction, since $M$ is uncountable. Hence, $M-A$ must be countable.
Comment: $A\cup(M-A) = M$ since $A\subset M$. This was used in the proof of Theorem 4.



Prove the existence of uncountably many transcedental numbers, i.e. numbers which are not algebraic.

Proof.
Define the set of transcedental numbers as $\R$ minus the algebraic numbers: $\mathcal{T} = \R - \mathcal{A}$. By Theorem 5, $[0,1]$ is uncountable, and since $[0,1]\subset\R$ then by Problem 1, $\R$ is uncountable.

Since $\R$ is uncountable and $\mathcal{A}\subset\R$ is countable, then $\mathcal{T}=\R-\mathcal{A}$ is uncountable by the previous Lemma. Therefore there are uncountably many transcedental numbers.

Problem 6

Prove that the set of all real functions (more generally, functions taking the values in a set containing at least two elements) defined on a set $M$ is of power geater than the power of $M$. In particular, prove that the power of the set of all real functions (continuous and discontinuous) defined in the interval $[0, 1]$ is greater than $c$.

Hint: Use the fact that the set of all characteristic functions/identity functions (i.e functions taking only the values 0 and 1) on $M$ is equivalent to the set of all subsets of $M$.



Claim: The set of all real functions defined on a set $M$ is of power geater than the power of $M$.

Proof.
For any subset $A\subset M$ we can define the corresponding identity function $\1_A(x)$, such that $$ \1_A(x) = \left\{ \begin{matrix} 1 & x\in A, \\ 0 & x\not\in A. \end{matrix} \right. $$ If we define $\mathscr{M} = \{A \,|\, A\subset M\}$ we get a one-to-one correspondence $\mathscr{M} = \{A \,|\, A\subset M\}\leftrightarrow \{\1_A \,|\, A\subset M\}$ which shows that these sets are equivalent: $\mathscr{M}\sim \{\1_A \,|\, A\subset M\}$. By Theorem 6, $\mathscr{M}$ has a power greater than $M$ and since it is equivalent to $\mathscr{M}$, so does the set of indicatior functions which is a subset of all possible functions.


Claim: The set of all real functions defined on a set $[0,1]$ is of power geater than the continuum $c$.

Proof.
The set $[0,1]$ is uncountable and has the power of the continuum. But by the previous result, the set of real functions defined on $[0,1]$ has a greater power.

Problem 7

Give an indirect proof of the equivalence of the closed interval $[a, b]$, the open interval $(a,b)$ and the half-open interval $[a, b)$ or $(a, b]$.

Proof.
Repeated use of the Theorem 7 (Cantor-Bernstein). Assume $c,d\in\R$ such that $a < c < d < b$. Now we define the intervals $(c,d)\subset[a, b]$ and $[c,d]\subset(a, b)$. Since $(c, d)\sim (a, b)$ and $[c, d]\sim[a, b]$, then by Theorem 7, $[a, b]\sim (a, b)$. The same argument can be used to show that all the intervals are equivalent.

Problem 8

Prove that the union of a finite or countable number of sets, each of power $c$ is itself of power $c$.

Proof.
Let $A_1, A_2, A_3, \ldots$ be sets of power $c$. Since intervals of type $[a, b)$ also have power $c$, we can construct a bijection between the sets $A_i$ and the interval $[i-1, i)$ for $i\in\N$.

For $A_1$ there is a bijection with $[0, 1)$ and for $A_2$ there is a bijection with $[1, 2)$. It follows that we get a bijection from $A_1\cup A_2$ to $[0, 2)$, and since $[0, 2)$ has power $c$, so does $A_1\cup A_2$.

We will use proof by induction. Assume $A_1\cup\ldots A_k$ has a bijection to $[0, k)$ which means both sets have power $c$. There is a bijection between $A_{k+1}$ and $[k, k+1)$. The union $A_1\cup\ldots\cup A_k\cup A_{k+1}$ has power $c$ since it has a bijection with $[0, k+1)$.

By induction the countable union $$ \bigcup_{n=1}^\infty A_n $$ has power $c$. The finite case follows by setting $A_m = \emptyset$ for all $m\geq N$ for some $N\in\N$.





Will use a theorem not mentioned in the book.


If there exists an injection $f$: $A\rightarrow B$ and an injection $g: B\rightarrow A$, then there exists a bijection $h: A\rightarrow B$.

Problem 9

We will prove that the following three sets have power of $c$.

(a) The set of all infinite sequences of positive integers.

Proof.
Let $\mathcal{S}$ be the set of infinite sequences. We can create a bijection between $\mathcal{S}$ and $[0,1]$. We do this by finding an injection in both directions. For the sequence $$ d_1, d_2, d_3, \ldots $$ we could define the number $0.d_1d_2d_3\ldots\in[0,1]$, but this is not unique, since $$ 1, 2, 3, 0, 0, \ldots $$ $$ 12, 3, 0, 0, \ldots $$ $$ 1, 23, 0, 0, \ldots $$ $$ 123, 0, 0, \ldots $$ would all point to $0.123000\ldots$. Instead, we define $b_i$ to be the binary representation of $d_i$ and replace $,$ with $2$. This will give an injection from the set $\mathcal{S}\rightarrow[0,1]$. $$ 1, 2, 3, 0, 0, \ldots \rightarrow 0.12102112020\ldots $$ $$ 12, 3, 0, 0, \ldots \rightarrow 0.11002112020\ldots $$ $$ 1, 23, 0, 0, \ldots \rightarrow 0.12101112020\ldots $$ $$ 123, 0, 0, \ldots \rightarrow 0.11110112020\ldots $$ Now to find an injection from $[0,1]$ to $\mathcal{S}$. This can be done by simply setting $$ 0.d_1d_2d_3\ldots \rightarrow d_1, d_2, d_3, \ldots. $$ By Theorem A.2 (Schröder-Bernstein), there exists a bijection between $[0,1]$ and $\mathcal{S}$ which means they are equivalent sets and $\mathcal{S}$ has the power $c$.

(b) The set of all ordered $n$-tuples of real numbers.

Proof.
Will show that we can make an injection from $(x_1, \ldots, x_n)\rightarrow\R$ and from $\R\rightarrow(x_1, \ldots, x_n)$ where $x_i\in\R$ and then apply Theorem A.2.

Injection $\R\rightarrow(x_1, \ldots, x_n)$. For any $x\in\R$ just place this in the first spot and set all others to 0: $(x, 0, \ldots, 0)$ and we have an injection.

Injection $(x_1, \ldots, x_n)\rightarrow\R$. In this case the numbers $x_i$ are on the form $$ x_i = d^i.d_1^id_2^id_3^i\ldots. $$ For the integral part, we use the binary $b^i$ of $d^i$ and separate the different numbers with 2, as we did in part (a). Then for the decimals, we run through each in turn, so we get: $$ b^12b^22\ldots 2b^n.d_1^1d_1^2\ldots d_1^nd_2^1d_2^2\ldots d_2^nd_3^1\ldots $$ which creates an injection.

By injection both ways, we have a bijection by Theorem A.2. This shows that the set of $n$-tuples has the same power as $\R$; the continuum $c$.

(c) The set of all infinite sequences of real numbers.

This proof seems to be based on some more advanced set theoretic concepts. Will skip for now.

Problem 10

Develop a contradiction inherent in the notion of the 'set of all sets which are not members of themselves'.

Define this set as: $$ X = \{A\,|\, A\not\in A\}. $$

This is a set of sets, such as $Y = \{B, C, D\}$. In this case $Y\not\in Y$ so $Y\in X$.

From the hint we will try to answer if $X$ is in $X$. Assume that $X\not\in X$. By the membership condition $X\not\in X\Rightarrow X\in X$ which is a contradiction. If we assume $X\in X$, this cannot be true since $X$ is the set of all sets that don't contain themselves so we violate the membership condition $A\not\in A$. Another contradiction. As such, this set cannot exist.