In this short chapter, we will briefly review some basic set notation, proof methods, functions, and countability. The presentation of these topics is intentionally brief for two reasons: (1) the reader is likely familar with these topics, and (2) we include only the necessary material needed to start doing real analysis.
Sets, Numbers, and Proofs
Let \(S\) be a set. If \(x\) is an element of \(S\) then we write \(x \in S\), otherwise we write that \(x\notin S\). A set \(A\) is called a subset of \(S\) if each element of \(A\) is also an element of \(S\), that is, if \(a\in A\) then also \(a\in S\). To denote that \(A\) is a subset of \(S\) we write \(A\subset S\).
Now let \(A\) and \(B\) be subsets of \(S\). If \(A\subset B\) and \(B\subset A\) then \(A\) and \(B\) are said to be equal and we write that \(A=B\). The union of \(A\) and \(B\) is the set
\[
A\cup B=\{x\in S\;|\; x\in A\text{ or } x\in B\}
\]
and the intersection of \(A\) and \(B\) is the set
\[
A\cap B=\{x\in S\;|\; x\in A\text{ and } x\in B\}.
\]
A graphical representation of set unions and intersections are shown in Figure 1.1.
Set intersection \(A\cap B\) and union \(A\cup B\)
The empty set is the set that does not contain any elements and is denoted by \(\emptyset\). We note that \(\emptyset \subset S\) for any set \(S\). The sets \(A\) and \(B\) are disjoint if \(A\cap B = \emptyset\). The complement of \(A\) in \(S\) is the set
\[
S\backslash\hspace{-0.3em} A = \{x\in S \;|\; x\notin A\},
\]
in other words, \(S\backslash\hspace{-0.3em} A\) consists of the elements in \(S\) not contained in \(A\). We sometimes use the shorter notation \(A^c\) for \(S\backslash\hspace{-0.3em} A\) when it is clear that it is the complement of \(A\) relative to \(S\).
The Cartesian product of \(A\) and \(B\), denoted by \(A\times B\), is the set of ordered pairs \((a, b)\) where \(a\in A\) and \(b\in B\), in other words,
\[
A\times B = \{(a,b)\;|\; a\in A,\; b\in B\}.
\]
A partition of a set \(S\) is a set \(\Pi\) whose elements are subsets of \(S\) such that \(\Pi\) does not contain the empty set, the union of the elements of \(\Pi\) equals \(S\), and any two distinct elements of \(\Pi\) are disjoint.
Lastly, for any set \(S\), the power set of \(S\) is the set of all subsets of \(S\), and is denoted by \(\mathcal{P}(S)\).
Let \(A\) and \(B\) be subsets of a set \(S\). Show that
\[
(A\cup B)^c = A^c \cap B^c.
\]
We first show that \((A\cup B)^c \subset A^c \cap B^c\). If \(x\in (A\cup B)^c\) then by definition \(x\notin (A\cup B)\) and therefore \(x\notin A\) and \(x\notin B\). Thus, \(x\in A^c\) and \(x\in B^c\), that is, \(x\in A^c \cap B^c\).
Now suppose that \(x\in A^c\cap B^c\), that is, suppose that \(x \in A^c\) and \(x\in B^c\). Thus, \(x\notin A\) and \(x\notin B\) and thus \(x\notin (A\cup B)\). By definition, \(x\in (A\cup B)^c\) and this proves that \(A^c \cap B^c\subset (A\cup B)^c\).
We use the symbol \(\mathbb{N}\) to denote the set of natural numbers, that is,
\[
\mathbb{N} = \{1,2,3,4,\ldots\}.
\]
The set of integers is denoted by \(\mathbb{Z}\) so that
\[
\mathbb{Z} = \{\ldots,-3,-2,-1,0,1,2,3,\ldots\}.
\]
The set of rational numbers is denoted by
\[
\mathbb{Q} = \left\{\frac{p}{q}\;|\; p,q\in\mathbb{Z},\, q\neq 0\right\}.
\]
Notice that we have the following chain of set inclusions:
\[
\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q}.
\]
We now review the most commonly used methods of proof. To that end, recall that a logical statement is a declarative sentence that can be unambiguously decided to be either true or false. A theorem is a logical statement that has been proved to be true using a sequence of true statements and deductive reasoning. Many theorems are usually written as a conditional statement of the form if \(P\) then \(Q\) or symbolically \(P\Rightarrow Q\). The statement \(P\) is called the hypothesis or assumption and \(Q\) is called the conclusion. Below are the main techniques used to prove the statement \(P\Rightarrow Q\):
Direct Proof: To prove the statement \(P\Rightarrow Q\), assume that the statement \(P\) is true and show by combining axioms, definitions, and earlier theorems that \(Q\) is true. This should be the first method you attempt.
By Contraposition: Proving the statement \(P\Rightarrow Q\) by proving the logically equivalent statement \(\text{not Q\Rightarrow\text{ not } P\)}. Do not confuse this with proof by contradiction.
By Contradiction: To prove the statement \(P\Rightarrow Q\) by contradiction, one assumes that \(P\Rightarrow Q\) is false and then show that some contradiction results. Assuming that \(P\Rightarrow Q\) is false is to assume that \(P\) is true and \(Q\) is false. Using these to latter assumptions, one attempts to derive at a contradiction of the form \(R\) and not \(R\), where \(R\) is some statement. One disadvantage with proof by contradiction is that the logical contradiction that one is seeking \(R\) and not \(R\) is not known in advance so that the goal of the proof is unclear. Proof by contradiction frequently gets confused with proof by contraposition in the following way (do not do this): To prove that \(P\Rightarrow Q\), assume that \(P\) is true and suppose that \(Q\) is not true. After some work using only the assumption that \(Q\) is not true you show that \(P\) is not true and thus you say that there is a contradiction because you assumed that \(P\) is true. What you have really done is proved the contrapositive statement. Thus, if you believe that you are proving a statement by contradiction, take a close look at your proof to see if what you have is a proof by contraposition.
In the following example, we use both proof by contradiction and proof by contraposition.
Prove that if \(x\) and \(y\) are consecutive integers then \(x+y\) is odd.
Assume that \(x\) and \(y\) are consecutive integers (i.e. assume \(P\)) and assume that \(x+y\) is not odd (i.e. assume not \(Q\)). Since \(x+y\) is not odd then \(x+y \neq 2n+1\) for all integers \(n\). However, since \(x\) and \(y\) are consecutive, and assuming without loss of generality that \(x \lt y\), we have that \(x+y = 2x + 1\). Thus, we have that \(x+y \neq 2n+1\) for all integers \(n\) and also that \(x+y = 2x+1\). Since \(x\) is an integer we have reached a contradiction. Hence, if \(x\) and \(y\) are consecutive integers then \(x+y\) is odd.
Now we prove the statement by contraposition. Without loss of generality, suppose that \(x \lt y\). Assume that \(x+y\) is even. Then there exists an integer \(n\) such that \(x+y = 2n\) and therefore \(x = 2n - y\). Consequently,
\[
y - x = y - (2n-y) = 2(y-n).
\]
Hence, since \((y-n)\) is an integer, \(y-x \neq 1\) and consequently \(x\) and \(y\) are not consecutive integers.
In general, if the statement \(P \Rightarrow Q\) is true then the converse conditional statement \(Q\Rightarrow P\) is not necessarily true. For example, the converse conditional statement in Example 1.1.2 is if \(x+y\) is odd then \(x\) and \(y\) are consecutive integers is easily shown to be false (e.g., \(x=2\) and \(y=5\)). The conjoined statement \(P\Rightarrow Q\) and \(Q\Rightarrow P\), alternatively written as \(P\) if and only if \(Q\) or symbolically \(P \Leftrightarrow Q\), is called a biconditional statement. Thus, to prove that the biconditional statement \(P \Leftrightarrow Q\) is true one must prove that both \(P \Rightarrow Q\) and \(Q\Rightarrow P\) are true.
Let \(A\), \(B\), and \(C\) be subsets of a set \(S\). Prove that \((A\cup B) \subset C\) if and only if \(A\subset C\) and \(B\subset C\).
Exercises
Let \(A\) and \(B\) be subsets of a set \(S\). Show that \(A\subset B\) if and only if \(B^c \subset A^c\)
Find the power set of \(S=\{x,y,z,w\}\).
Let \(A=\{\alpha_1, \alpha_2, \alpha_3\}\) and let \(B=\{\beta_1, \beta_2\}\). Find \(A\times B\).
Let \(x\in\mathbb{Z}\). Prove that if \(x^2\) is even then \(x\) is even. Do not use proof by contradiction.
Prove that if \(x\) and \(y\) are even natural numbers then \(xy\) is even. Do not use proof by contradiction.
Prove that if \(x\) and \(y\) are rational numbers then \(x+y\) is a rational number. Do not use proof by contradiction.
Let \(x\) and \(y\) be natural numbers. Prove that \(x\) and \(y\) are odd if and only if \(xy\) is odd. Do not use proof by contradiction.
Mathematical Induction
Mathematical induction is a powerful proof technique that relies on the following property of \(\N\).
Every non-empty subset of \(\N\) contains a smallest element.
In other words, if \(S\) is a non-empty subset of \(\N\) then there exists \(a\in S\) such that \(a\leq x\) for all \(x\in S\). The smallest element of \(S\) is denoted by \(\min(S)\). Thus, \(\min(S) \in S\) and \(\min(S) \leq x\) for all \(x\in S\). We now state and prove the principle of Mathematical Induction.
Suppose that \(S\) is a subset of \(\N\) with the following properties:
\(1 \in S\)
If \(k\in S\) then also \(k+1 \in S\).
Then \(S=\N\).
Suppose that \(S\) is a subset of \(\N\) with properties (i) and (ii) and let \(T = \N\backslash\hspace{-0.3em} S\). Proving that \(S=\N\) is equivalent to proving that \(T\) is the empty set. Suppose then by contradiction that \(T\) is non-empty. By the well-ordering principle of \(\N\), \(T\) has a smallest element, say it is \(a\in T\). Because \(S\) satisfies property (i) we know that \(1\notin T\) and therefore \(a \gt 1\). Now since \(a\) is the least element of \(T\), then \(a-1\in S\) (we know that \(a-1 \gt 0\) because \(a \gt 1\)). But since \(S\) satisfies property (ii) then \((a-1)+1\in S\), that is, \(a\in S\). This is a contradiction because we cannot have both \(a\in T\) and \(a\in S\). Thus, \(T\) is the empty set, and therefore \(S=\N\).
Mathematical induction is frequently used to prove formulas or inequalities involving the natural numbers. For example, consider the validity of the formula
\begin{equation}\label{eqn:n-sum}
1 + 2 + 3 + \cdots + n = \tfrac{1}{2}n(n+1)
\end{equation}
where \(n\in\mathbb{N}\). In words, the identity \eqref{eqn:n-sum} says that the sum of all the integers from \(1\) to \(n\) equals \(\tfrac{1}{2}n(n+1)\). We use induction to show that this formula is true for all \(n\in \N\). Let \(S\) be the subset of \(\N\) consisting of the natural numbers that satisfy \eqref{eqn:n-sum}, that is,
\[
S = \{n\in\mathbb{N}\;|\; 1 + 2 + 3 + \cdots + n = \tfrac{1}{2}n(n+1) \}.
\]
If \(n=1\) then
\[
\tfrac{1}{2}n(n+1) = \tfrac{1}{2}(1+1) = 1.
\]
Thus, \(\tfrac{1}{2}n(n+1)\) is equal to the sum of all the integers from \(1\) to \(n=1\). Hence, \eqref{eqn:n-sum} is true when \(n=1\) and thus \(1\in S\). Now suppose that some \(k\in\N\) satisfies \eqref{eqn:n-sum}, that is, suppose that \(k\in S\). Then we may write that
\begin{equation}\label{induction-step}
1 + 2 + \cdots + k = \tfrac{1}{2}k(k+1).
\end{equation}
We will prove that the integer \(k+1\) also satisfies \eqref{eqn:n-sum}. To that end, adding \(k+1\) to both sides of \eqref{induction-step} we obtain
\[
1 + 2 + \cdots + k + (k+1) = \tfrac{1}{2}k(k+1) + (k+1).
\]
Now notice that we can factor \((k+1)\) from the right-hand side and through some algebraic steps we obtain that
\begin{align*}
1 + 2 + \cdots + k + (k+1) &= \tfrac{1}{2}k(k+1) + (k+1)\\
&= (k+1)[\tfrac{1}{2}k + 1]\\
& = \tfrac{1}{2}(k+1)(k+2).
\end{align*}
Hence, \eqref{eqn:n-sum} also holds for \(n=k+1\) and thus \(k+1\in S\). We have therefore proved that \(S\) satisfies properties (i) and (ii), and therefore by mathematical induction \(S=\N\), or equivalently that \eqref{eqn:n-sum} holds for all \(n\in\mathbb{N}\).
Use mathematical induction to show that \(2^n \leq (n+1)!\) holds for all \(n\in\N\).
Let \(r\neq 1\) be a constant. Use mathematical induction to show that
\[
1+r+r^2+\cdots + r^n = \frac{1-r^{n+1}}{1-r}
\]
holds for all \(n\in\N\).
Prove that if \(x \gt -1\) then \((1+x)^n \geq 1+nx\) for all \(n\in\N\).
The statement is trivial for \(n=1\). Assume that for some \(k\in\N\) it holds that \((1+x)^k \geq 1+kx\). Since \(x \gt -1\) then \(x+1 \gt 0\) and therefore
\begin{align*}
(1+x)^k (1+x) &\geq (1+kx)(1+x)\\[2ex]
&= 1 + (k+1)x + kx^2\\[2ex]
&\geq 1+ (k+1)x.
\end{align*}
Therefore, \((1+x)^{k+1} \geq 1 + (k+1)x\), and the proof is complete by induction.
There is another version of mathematical induction called the Principle of Strong Induction which we now state.
Suppose that \(S\) is a subset of \(\N\) with the following properties:
\(1 \in S\)
If \(\{1,2,\ldots,k\} \subset S\) then also \(k+1 \in S\).
Then \(S=\N\).
Do you notice the difference between induction and strong induction? It turns out that the two statements are equivalent, in other words, if \(S\) satisies either one of properties (i)-(ii) of induction or strong induction then we may conclude that \(S=\N\). The upshot with strong induction is that one is able to use the stronger condition that \(\{1,2,\ldots,k\}\subset S\) to prove that \(k+1\in S\).
Exercises
Prove that \(n \lt 2^n\) for all \(n\in\mathbb{N}\).
Prove that \(2^n \lt n!\) for all \(n\geq 4\), \(n\in\N\).
Use induction to prove that if \(S\) has \(n\) elements then \(\mathcal{P}(S)\) has \(2^n\) elements. Hint: If \(S\) is a set with \(n+1\) elements, for instance \(S=\{x_1, x_2, \ldots, x_n, x_{n+1}\}\), then argue that \(\mathcal{P}(S) = \mathcal{P}(\tilde{S})\cup \mathcal{T}\) where \(\tilde{S}=S\backslash\hspace{-0.3em}\{x_{n+1}\}\) and \(\mathcal{T}\) consists of subsets of \(S\) that contain \(x_{n+1}\). How many sets are in \(\mathcal{P}(\tilde{S})\) and how many are in \(\mathcal{T}\)? And what is \(\mathcal{P}(\tilde{S})\cap \mathcal{T}\)? Explain carefully.
Functions
Let \(A\) and \(B\) be sets. A function from \(A\) to \(B\) is a rule that assigns to each element \(x\in A\) one element \(y\in B\). The set \(A\) is called the domain of \(f\) and \(B\) is called the co-domain of \(f\). We usually denote a function with the notation \(f:A\rightarrow B\), and the assignment of \(x\) to \(y\) is written as \(y = f(x)\). We also say that \(f\) is a mapping from \(A\) to \(B\), or that \(f\) maps \(A\) into \(B\). The element \(y\) assigned to \(x\) is called the image of \(x\) under \(f\). The range of \(f\), denoted by \(f(A)\), is the set
\[
f(A) = \{y\in B\;|\; \exists\; x\in A,\; y = f(x)\}.
\]
In the above definition of \(f(A)\), we use the symbol \(\exists\) as a short-hand for there exsits. By definition, \(f(A)\subset B\) but in general we do not have that \(f(A) = B\), in other words, the range of a function is generally a strict subset of the function's co-domain.
Consider the mapping \(f:\mathbb{Q}\rightarrow\mathbb{Z}\) defined by
\[
f(x) = \begin{cases} 1, & x\geq 0\\[2ex] -1, & x \lt 0.\end{cases}
\]
The image of \(x=1/2\) under \(f\) is \(f(1/2) = 1\). The range of \(f\) is \(f(\rat) = \{1,-1\}\).
Consider the function \(f:\mathbb{N}\rightarrow\mathcal{P}(\mathbb{N})\) defined by
\[
f(n) = \{1,2,\ldots,n\}.
\]
The set \(S=\{2,4,6,8,\ldots,\}\) of even numbers is an element of the co-domain \(\mathcal{P}(\mathbb{N})\) but is not in the range of \(f\). As another example, the set \(\mathbb{N}\in\mathcal{P}(\mathbb{N})\) itself is not in the range of \(f\).
Function's whose range is equal to it's co-domain are given a special name.
A function \(f:A\rightarrow B\) is said to be a surjection if for any \(y\in B\) there exists \(x\in A\) such that \(f(x) = y\).
In other words, \(f:A\rightarrow B\) is a surjection if \(f(A) = B\).
The function \(f:\rat\rightarrow\rat\) defined by \(f(x) = x^2\) is not a surjection. For example, \(y=-1\) is clearly not in the range of \(f\) since \(f(x) = x^2 \neq -1\) for all \(x\in\rat\). On the other hand, \(y=\frac{121}{64}\) is in the range of \(f\) since \(f(11/8) = \frac{121}{64}\). Is \(y=2\) in the range of \(f\)?
Consider the function \(f:\mathcal{P}(\mathbb{N})\rightarrow\mathbb{N}\) defined by
\[
f(S) = \min (S).
\]
Prove that \(f\) is a surjection.
To prove that \(f\) is a surjection, we must show that for any element \(y\in\mathbb{N}\) (the co-domain), there exists \(S\in\mathcal{P}(\mathbb{N})\) (the domain) such that \(f(S) = y\). Consider then an arbitrary \(y\in \mathbb{N}\). Let \(S=\{y\}\) and thus clearly \(S\in\mathcal{P}(\mathbb{N})\). Moreover, it is clear that \(\min(S) = y\) and thus \(f(S) = \min(S) = y\). This proves that \(f\) is a surjection.
Notice that in Example 1.3.5, given any \(y\in\mathbb{N}\) there are many sets \(S\in\mathcal{P}(\mathbb{N})\) such that \(f(S) = y\). This leads us to the following definition.
A function \(f:A\rightarrow B\) is said to be an injection if no two distinct elements of \(A\) are mapped to the same element in \(B\), in other words, for any \(x_1, x_2\in A\), if \(x_1\neq x_2\) then \(f(x_1) \neq f(x_2)\).
In other words, \(f\) is an injection if whenever \(f(x_1) = f(x_2)\) then necessarily \(x_1=x_2\).
The function \(f:\rat\rightarrow\rat\) defined by \(f(x) = x^2\) is not an injection. For example, \(f(-2) = f(2) = 4\).
Consider again the function \(f:\mathbb{N}\rightarrow\mathcal{P}(\mathbb{N})\) defined by
\[
f(n) = \{1,2,\ldots,n\}.
\]
This function is an injection. Indeed, if \(f(n) = f(m)\) then \(\{1,2,\ldots,n\} = \{1,2,\ldots, m\}\) and therefore \(n=m\). Hence, whenever \(f(n) = f(m)\) then necessarily \(n=m\) and this proves that \(f\) is an injection.
Consider the function \(f:\mathcal{P}(\mathbb{N})\rightarrow\mathbb{N}\) defined by
\[
f(S) = \min (S)
\]
Is \(f\) an injection?
Consider the function \(f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}\) defined by
\[
f(n) = (2n^2, n+1)
\]
Show that \(f\) is an injection.
A function \(f:A\rightarrow B\) is said to be a bijection if it is a surjection and an injection.
Suppose that \(f:P\rightarrow Q\) is an injection. Prove that the function \(\tilde{f}:P \rightarrow f(P)\) defined by \(\tilde{f}(x) = f(x)\) for \(x\in P\) is a bijection.
By construction, \(\tilde{f}\) is a surjection. If \(\tilde{f}(x) = \tilde{f}(y)\) then \(f(x) = f(y)\) and then \(x=y\) since \(f\) is an injection. Thus, \(\tilde{f}\) is an injection and this proves that \(\tilde{f}\) is a bijection.
Prove that \(f:\rat\backslash\hspace{-0.3em}\{0\}\rightarrow\rat\backslash\hspace{-0.3em}\{0\}\) defined by \(f(\tfrac{p}{q}) = \tfrac{q}{p}\) is a bijection, where \(\gcd(p,q)=1\).
Suppose that \(f:A\rightarrow B\) is a bijection and define the function \(g:B\rightarrow A\) as follows: for \(b\in B\) let \(g(b)\) be the (necessarily unique) element in \(A\) such that \(f(g(b)) = b\). Notice that by definition, \(g(f(a)) = a\). The function \(g\) is called the inverse of \(f\) and we write instead \(g = f^{-1}\). It is not hard to show that \(g\) is a bijection and that \(g^{-1} = f\).
Given functions \(f:A\rightarrow B\) and \(g:B\rightarrow C\), the composition of \(g\) and \(f\) is the function \((g\circ f): A\rightarrow C\) defined as \((g\circ f)(a) = g(f(a))\).
If \(f:A\rightarrow B\) and \(g:B\rightarrow C\) are injections (surjections) then the composition \((g\circ f): A\rightarrow C\) is an injection (surjection).
Assume that \(f:A\rightarrow B\) and \(g:B\rightarrow C\) are injections. To prove that \((g\circ f)\) is an injection, suppose that \((g\circ f)(x_1) = (g\circ f)(x_2)\). Then by definition of \((g\circ f)\), it follows that \(g(f(x_1)) = g(f(x_2))\). Now since \(g\) is an injection then necessarily \(f(x_1) = f(x_2)\) and since \(f\) is an injection then necessarily \(x_1=x_2\). Thus if \((g\circ f)(x_1) = (g\circ f)(x_2)\) then \(x_1=x_2\) and this proves that \((g\circ f)\) is an injection.
Now suppose that \(f\) and \(g\) are surjections. To prove that \((g\circ f):A\rightarrow C\) is a surjection, let \(z\in C\) be arbitrary. Since \(g\) is a surjection, there exists \(y\in B\) such that \(g(y) = z\). Since \(f\) is a surjection, there exists \(x\in A\) such that \(y=f(x)\). Thus, for \(x\in A\) we have that \((g\circ f)(x) = g(f(x)) = g(y) = z\). Hence, for arbitrary \(z\in C\) there exists \(x\in A\) such that \((g\circ f)(x) = z\) and this proves that \((g\circ f)\) is a surjection.
The following result is then an immediate application of Theorem 1.3.14 and the definition of a bijection.
The composition of two bijections is a bijection.
Exercises
Consider the function \(f:\mathbb{N}\rightarrow\mathbb{Q}\) defined as \(f(n) = \frac{1}{n}\). Is \(f\) an injection? Is \(f\) a surjection?
Consider the function \(f:\mathbb{N}\times\mathbb{N}\rightarrow \mathbb{N}\) defined as \(f(n, m) = nm\). Is \(f\) an injection? Is \(f\) a surjection?
Consider the function \(f:\rat\rightarrow\rat\) defined as \(f(x) = (x-2)(x-6)\). Is \(f\) an injection? If \(f\) a surjection?
Let \(f:\N\rightarrow\mathbb{Z}\) be the function defined as
\[
f(n) = \begin{cases} \frac{n}{2},& \text{ if \(n\) is even,}\\[2ex] -\frac{(n-1)}{2},&\text{ if \(n\) is odd.}\end{cases}
\]
Prove that \(f\) is a bijection.
The sign of a rational number \(x\in\mathbb{Q}\) is defined as \(\text{sgn}(x) = x / |x|\) if \(x\neq 0\), where \(|x|\) is the absolute value of \(x\), and \(\text{sgn}(0) = 1\). For example, \(\text{sgn}(-3) = -1\) and \(\text{sgn}(2) = 1\). Prove that the function \(f:\mathbb{Z}\rightarrow \{-1, 1\}\times\N\) defined as
\[
f(x) = (\text{sgn}(x), |x| + 1)
\]
is a bijection.
Countability
A non-empty set \(S\) is said to be finite if there is a bijection from \(\{1,2,\ldots,n\}\) onto \(S\) for some \(n\in \N\). In this case, we say that \(S\) contains \(n\) elements and we write \(|S|=n\). If \(S\) is not finite then we say that \(S\) is infinite.
Let \(f:P\rightarrow Q\) be an injection. If \(P\) is an infinite set then \(f(P)\) is an infinite set.
The proof is by contraposition. Suppose that \(f(P)\) is a finite set containing \(n\) elements. Then there exists a bijection \(g:\{1,2,\ldots,n\}\rightarrow f(P)\). The function \(\tilde{f}:P\rightarrow f(P)\) defined as \(\tilde{f}(x) = f(x)\) for \(x\in P\) is a bijection (Example 1.3.12) and therefore \((\tilde{f}^{-1}\circ g): \{1,2,\ldots,n\}\rightarrow P\) is a bijection. Thus \(P\) is a finite set and completes the proof.
We now introduce the notion of a countable set.
Let \(S\) be a set.
The set \(S\) is countably infinite if there is a bijection from \(\N\) onto \(S\).
The set \(S\) is countable if \(S\) is either finite or countably infinite.
The set \(S\) is uncountable if \(S\) is not countable.
Roughly speaking, a set \(S\) is countable if the elements of \(S\) can be listed or enumerated in a systematic manner. To see how, suppose that \(S\) is countably infinite and let \(f:\mathbb{N}\rightarrow S\) be a bijection. Then the elements of \(S\) can be listed as
\[
S = \{f(1), f(2), f(3), f(4), \ldots\}.
\]
Hence, although sets have no predetermined order, the elements of a countable set can be ordered.
The set \(S\) of odd natural numbers is countable. Recall that \(n\in\mathbb{N}\) is an odd positive integer if \(n=2k-1\) for some \(k\in\mathbb{N}\). A bijection \(f:\N\rightarrow S\) from \(\N\) to \(S\) is \(f(k)=2k-1\). The function \(f\) can be interpreted as a listing of the odd natural numbers in the natural way:
\[
S = \{f(1), f(2), f(3), \ldots\} = \{1, 3, 5, \ldots\}.
\]
The natural numbers \(S=\mathbb{N}\) are countable. A bijection \(f:\mathbb{N}\rightarrow S\) is \(f(n) = n\), i.e., the identity mapping.
The set of integers \(\mathbb{Z}\) is countable. A bijection \(f\) from \(\N\) to \(\mathbb{Z}\) can be defined by listing the elements of \(\mathbb{Z}\) as follows:
\[
\begin{matrix}
\N: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \ldots \\[2ex]
& \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \ldots\\[2ex]
\mathbb{Z}: & 0 & 1 & -1 & 2 & -2 & 3 & -3 & \ldots
\end{matrix}
\]
To be more precise, \(f\) is the function
\[
f(n) = \begin{cases} \frac{n}{2},& \text{ if \(n\) is even,}\\[2ex] -\frac{(n-1)}{2},&\text{ if \(n\) is odd.}\end{cases}
\]
It is left as an exercise to show that \(f\) is indeed a bijection.
The set \(\N\times\N\) is countable. There are many bijections from \(\N\) to \(\N\times\N\) but a particularly interesting one is the function defined as follows. Consider the family of lines
\[
L_k = \{(x,y)\in\N\times\N\,|\, y = -x + k + 1\}
\]
for \(k\in\N\). There are \(k\) points on the line \(L_k\), namely \((j, k+1-j)\) for \(1\leq j \leq k\), and we say that \((j, k+1-j)\) is the \(j\)th point on the line \(L_k\). The point \((x,y)\in\N\times\N\) is contained in the line \(L_k\) where \(k = x+y-1\). Thus, one way to enumerate the points in \(\N\times\N\) is to assign to each \((x, y)\in L_k\) the number \(\rho(x,y)\) obtained by adding all points on the lines \(L_1, \ldots, L_{k-1}\) and adding the position of \((x,y)\) on line \(L_k\), namely \(x\). Thus,
\begin{align*}
\rho(x,y) &= 1 + 2 + \ldots + (k-1) + x\\
&= \frac{1}{2}(k-1)k + x\\
&= \frac{1}{2}(x+y-2)(x+y-1) + x.
\end{align*}
The function \(\rho\) is called the Cantor pairing function. Alternatively, we use a modified version of \(\rho\) which we call \(\tau:\N\times\N\rightarrow\N\) and defined as
\[
\tau(x,y) =
\begin{cases}
\rho(x,y), & \text{if}\;(x+y-1)\;\text{is odd},\\[2ex]
\rho(y, x), & \text{if}\;(x+y-1)\;\text{is even}.
\end{cases}
\]
We now find a formula for the inverse of \(\tau\) which we call the Cantor snake. To write down the formula for \(\tau^{-1}\), we first let for each \(n\in\N\)
\[
m = \text{floor}\left(\frac{-1 + \sqrt{1 + 8(n-1)}}{2}\right)
\]
and we note that \(m\geq 0\) is the smallest integer such that \(\frac{1}{2}m(m+1) \lt n\). We then set \(p(n) = n - \frac{1}{2}m(m+1)\) a then
\begin{align*}
\tau^{-1}(n) =
\begin{cases}
(p(n), -p(n) + m + 2), & \text{ if } m \text{ is even }\\[2ex]
(-p(n) + m + 2, p(n)), & \text{ if } m \text{ is odd. }
\end{cases}
\end{align*}
We note that the point \((x,y) = \tau^{-1}(n)\) is on the line \(L_k\) with \(k = m + 1\). The range of \(\tau^{-1}\) is
\[
\tau^{-1}(\N) = \{(1, 1), (2, 1), (1, 2), (1, 3), (2, 2), (3, 1), \ldots \}.
\]
The sequence of pairs \((x, y)\in\N\times\N\) generated by \(\tau^{-1}\) for \(1\leq n\leq 55\) are shown in Figure 1.2.
The image of the Cantor snake
Suppose that \(f:T\rightarrow S\) is a bijection. Prove that \(T\) is countable if and only if \(S\) is countable.
Suppose that \(T\) is countable. Then by definition there exists a bijection \(g:\N\rightarrow T\). Since \(g\) and \(f\) are bijections, the composite function \((f\circ g):\N\rightarrow S\) is a bijection. Hence, \(S\) is countable.
Now suppose that \(S\) is countable. Then by definition there exists a bijection \(h:\N\rightarrow S\). Since \(f\) is a bijection then the inverse function \(f^{-1}:S\rightarrow T\) is also a bijection. Therefore, the composite function \((f^{-1}\circ h):\N\rightarrow T\) is a bijection. Thus, \(T\) is countable.
As the following theorem states, countability, or lack thereof, can be inherited via set inclusion.
Let \(S\) and \(T\) be sets and suppose that \(T\subset S\).
If \(S\) is countable then \(T\) is also countable.
If \(T\) is uncountable then \(S\) is also uncountable.
To prove (i), let \(S\) be a countable set and let \(f:S\rightarrow \N\) be a bijection. Define the mapping \(\tilde{f}:T\rightarrow f(T)\) by \(\tilde{f}(x) = f(x)\). By Example 1.3.12, \(\tilde{f}\) is a bijection. Therefore, since \(f(T)\) is a subset of \(\N\), and thus countable, then \(T\) is countable. The proof of (ii) is left as an exercise.
Let \(S\) be the set of odd natural numbers. In Example 1.4.3, we proved that the odd natural numbers are countable by explicitly constructing a bijection from \(\N\) to \(S\). Alternatively, since \(\N\) is countable and \(S\subset \N\) then by Theorem 1.4.8 \(S\) is countable. More generally, any subset of \(\N\) is countable.
If \(S\) is known to be a finite set then by Definition 1.4.2 \(S\) is countable, while if \(S\) is infinite then \(S\) may or may not be countable (we have yet to encounter an uncountable set but soon we will). To prove that a given infinite set \(S\) is countable we could use Theorem 1.4.8 if it is applicable but otherwise we must use Definition 1.4.2, that is, we must show that there is a bijection from \(S\) to \(\N\), or equivalently from \(\N\) to \(S\). However, suppose that we can only prove the existence of a surjection \(f\) from \(\N\) to \(S\). The problem might be that \(f\) is not an injection and thus not a bijection. However, the fact that \(f\) is a surjection from \(\N\) to \(S\) somehow says that \(S\) is no larger than \(\N\) and gives evidence that perhaps \(S\) is countable. Could we use a surjection \(f:\N\rightarrow S\) to construct a bijection \(g:\N\rightarrow S\)? Or, what if instead we had an injection \(g:S\rightarrow\N\); could we use \(g\) to construct a bijection \(f:S\rightarrow \N\)? The following theorem says that it is indeed possible to do both.
Let \(S\) be a set.
If there exists an injection \(g:S\rightarrow\N\) then \(S\) is countable.
If there exists a surjection \(f:\N\rightarrow S\) then \(S\) is countable.
(i) Let \(g:S\rightarrow\N\) be an injection. Then the function \(\tilde{g}:S\rightarrow g(S)\) defined by \(\tilde{g}(s) = g(s)\) for \(s\in S\) is a bijection. Since \(g(S)\subset \N\) then \(g(S)\) is countable. Therefore, \(S\) is countable also.
(ii) Now let \(f:\N\rightarrow S\) be a surjection. For \(s\in S\) let \(f^{-1}(s) = \{ n\in\N\;|\; f(n) = s\}\). Since \(f\) is a surjection, \(f^{-1}(s)\) is non-empty for each \(s\in S\). Consider the function \(h:S\rightarrow \N\) defined by \(h(s) = \min f^{-1}(s)\). Then \(f(h(s)) = s\) for each \(s\in S\). We claim that \(h\) is an injection. Indeed, if \(h(s) = h(t)\) then \(f(h(s)) = f(h(t))\) and thus \(s = t\), and the claim is proved. Thus, \(h\) is an injection and then by (i) we conclude that \(S\) is countable.
We must be careful when using Theorem 1.4.10; if \(f:\N\rightarrow S\) is known to be an injection then we cannot conclude that \(S\) is countable and similarly if \(f:S\rightarrow\N\) is known to be a surjection then we cannot conclude that \(S\) is countable.
In this example we will prove that the union of countable sets is countable. Hence, suppose that \(A\) and \(B\) are countable. By definition, there exist bijections \(f:\N\rightarrow A\) and \(g:\N\rightarrow B\). Consider the function \(h:\N\rightarrow A\cup B\) defined as follows:
\[
h(n) = \begin{cases} f((n+1)/2), & \text{if \(n\) is odd,}\\[2ex] g(n/2), & \text{if \(n\) is even.}\end{cases}
\]
We claim that \(h\) is a surjection (Loosely speaking, if \(A=\{a_1,a_2,\ldots,\}\) and \(B=\{b_1,b_2,\ldots,\}\), then the function \(h\) lists the elements of \(A\cup B\) as \(A\cup B = \{a_1, b_1, a_2, b_2, a_3, b_3, \ldots,\}\).). To see this, let \(x\in A\cup B\). If \(x\in A\) then \(x = f(k)\) for some \(k\in\N\). Then \(h(2k-1)=f(k)=x\). If on the other hand \(x\in B\) then \(x=g(k)\) for some \(k\in \N\). Then \(h(2k) = g(k)=x\). In either case, there exists \(n\in \N\) such that \(h(n) = x\), and thus \(h\) is a surjection. By Theorem 1.4.10, the set \(A\cup B\) is countable.
This example can be generalized as follows. Let \(A_1, A_2, A_3,\ldots,\) be countable sets and let \(S=\bigcup_{k=1}^\infty A_k\). Then \(S\) is countable. To prove this, we first enumerate the elements of each \(A_k\) as follows:
\begin{align*}
A_1 &= \{a_{1,1}, a_{1,2}, a_{1,3}, \ldots\}\\
A_2 &= \{a_{2,1}, a_{2,2}, a_{2,3}, \ldots\}\\
A_3 &= \{a_{3,1}, a_{3,2}, a_{3,3}, \ldots\}\\
\cdots & \qquad\cdots\qquad \cdots
\end{align*}
Formally, we have surjections \(f_k:\N\rightarrow A_k\) for each \(k\in\N\). Consider the mapping \(\varphi:\N\times\N \rightarrow S\) defined by
\[
\varphi(m,n) = a_{m,n} = f_m (n).
\]
It is clear that \(\varphi\) is a surjection. Since \(\N\times\N\) is countable, there is a surjection \(\phi:\N\rightarrow\N\times\N\), and therefore the composition \((\varphi\circ\phi):\N\rightarrow S\) is a surjection. Therefore, \(S\) is countable.
The following theorem is perhaps surprising.
The set of rational numbers \(\mathbb{Q}\) is countable.
Let \(\mathbb{Q}_{ \gt 0}\) be the set of all positive rational numbers and let \(\mathbb{Q}_{ \lt 0}\) be the set of all negative rational numbers. Clearly, \(\mathbb{Q} = \mathbb{Q}_{ \lt 0}\cup \{0\}\cup \mathbb{Q}_{ \gt 0}\), and thus it is enough to show that \(\mathbb{Q}_{ \lt 0}\) and \(\mathbb{Q}_{ \gt 0}\) are countable. In fact, we have the bijection \(h:\mathbb{Q}_{ \gt 0}\rightarrow\mathbb{Q}_{ \lt 0}\) given by \(h(x) = -x\), and thus if we can show that \(\mathbb{Q}_{ \gt 0}\) is countable then this implies that \(\mathbb{Q}_{ \lt 0}\) is also countable. In summary, to show that \(\mathbb{Q}\) is countable it is enough to show that \(\mathbb{Q}_{ \gt 0}\) is countable. To show that \(\mathbb{Q}_{ \gt 0}\) is countable, consider the function \(f:\N\times\N\rightarrow\mathbb{Q}_{ \gt 0}\) defined as
\[
f(p,q) = \frac{p}{q}.
\]
By definition, any rational number \(x\in\mathbb{Q}_{ \gt 0}\) can be written as \(x = \frac{p}{q}\) for some \(p, q \in\N\). Hence, \(x = f(p,q)\) and thus \(x\) is in the range of \(f\). This shows that \(f\) is a surjection. Now, because \(\N\times\N\) is countable, there is a surjection \(g:\N\rightarrow\N\times\N\) and thus \((f\circ g):\N\rightarrow\mathbb{Q}_{ \gt 0}\) is a surjection. By Theorem 1.4.10, this proves that \(\mathbb{Q}_{ \gt 0}\) is countable and therefore \(\mathbb{Q}\) is countable.
We end this section with Cantor's theorem named after mathematician Georg Cantor (1845-1918). Cantor is considered as the creator of set theory. Originally interested in analytical problems having as their root problems in physics, and in particular in characterizing solutions to equations describing heat conduction, Cantor discovered that infinite sets come in many possible sizes. One of Cantor's fascinating discoveries, which initially were very controversial at the time, led to the following theorem \cite{GC:91}.
For any set \(S\), there is no surjection of \(S\) onto the power set \(\mathcal{P}(S)\).
Suppose by contradiction that \(f:S\rightarrow\mathcal{P}(S)\) is a surjection. By definition, for each \(a\in S\), \(f(a)\) is a subset of \(S\). Consider the set
\[
\mathcal{C} = \{a\in S\;|\; a \notin f(a)\}.
\]
Since \(\mathcal{C}\) is a subset of \(S\) then \(\mathcal{C}\in\mathcal{P}(S)\). Since \(f\) is a surjection, there exists \(x\in S\) such that \(\mathcal{C} = f(x)\). One of the following must be true: either \(x \in \mathcal{C}\) or \(x\notin \mathcal{C}\). If \(x\in \mathcal{C}\) then \(x\notin f(x)\) by definition of \(\mathcal{C}\). But \(\mathcal{C}=f(x)\) and thus we reach contradiction. If \(x\notin \mathcal{C}\) then by definition of \(\mathcal{C}\) we have \(x\in f(x)\). But \(\mathcal{C}=f(x)\) and thus we reach a contradiction. Hence, neither of the possibilities are true, and thus we have reached an absurdity. Hence, we conclude that there is no such surjection \(f\).
Cantor's theorem implies that \(\mathcal{P}(\N)\) is uncountable. Indeed, if we take \(S=\N\) in Cantor's Theorem then there is no surjection from \(\N\) to \(\mathcal{P}(\N)\), and thus certainly no bijection from \(\N\) to \(\mathcal{P}(\N)\). In summary:
The set \(\mathcal{P}(\N)\) is uncountable.
Exercises
Let \(P\) and \(Q\) be infinite sets. Prove that if \(f:Q\rightarrow P\) is a bijection then \(Q\) is uncountable if and only if \(P\) is uncountable. Do not use proof by contradiction.
In this exercise you will provide another proof that \(\N\times\N\) is countable.
Prove that \(3^n\) is odd for each \(n\in\N\).
Consider the function \(f:\N\times\N\rightarrow\N\) defined as \(f(p, q) = 2^p 3^q\). Prove that \(f\) is an injection. Hint: Use part (a) in some way.
Explain how part (b) proves that \(\N\times\N\) is countable.
Prove that if \(A\) and \(B\) are countably infinite then \(A\times B\) is countable.
Recall that a sequence \(a=\{a_k\}_{k=1}^\infty\) of numbers is an infinite list
\[
a = (a_1, a_2, a_3, a_4, \ldots )
\]
where each element \(a_k\) is a number (We will cover sequences in detail but you are already familiar with them from calculus.). Let \(Q\) be the set of sequences whose elements are either \(0\) or \(1\), in other words,
\[
Q = \left\{\{a_k\}_{k=1}^\infty\;|\; a_k = 0 \text{ or } a_k = 1 \right\}.
\]
For example, the following sequences are elements of the set \(Q\):
\begin{align*}
a &= (0, 0, 0, 0, 0, 0, \ldots) \in Q\\
b &= (1, 0, 1, 0, 1, 0, \ldots)\in Q\\
c &= (0, 0, 1, 1,0, 0, \ldots)\in Q\\
d &= (1,1,1,1,1,1,\ldots) \in Q
\end{align*}
Give two non-trivial examples of functions from \(\N\) to \(Q\).
Consider the function \(f:Q\rightarrow\mathcal{P}(\N)\) defined as
\[
f(a) = \{k\in\N \;|\; a_k = 1\}
\]
where \(\mathcal{P}(\N)\) is the power set of \(\N\). Hence, \(f\) takes a sequence \(a\in Q\) and outputs the indices where \(a\) is equal to \(1\). For example:
\begin{align*}
f(0,0,0,0,0,0,0,0,\ldots) &= \emptyset \\[2ex]
f(1,0,1,0,1,0,1,0,\ldots ) &= \{1, 3, 5, 7, \ldots \}\\[2ex]
f(0,0,1,1,0,0,0,0,\ldots) &= \{3, 4\}\\[2ex]
f(1,1,1,1,1,1,1,1,\ldots) & = \{1,2,3,4,5,6,\ldots\} = \N
\end{align*}
Prove that \(f:Q\rightarrow\mathcal{P}(\N)\) is a bijection.
Combine part (b), Exercise 1.4.1, and Cantor's theorem to thoroughly explain whether \(Q\) is countable or uncountable.
