1. Finite, Countable, and Uncountable Sets

Definition 2.1: A function (or mapping) from the set $A$ to the set $B$ is a rule, $f$, which associates each $x\in A$ with some $f(x)\in B$. The set $A$ is called the domain of $f$. The elements $f(x)$ are called the values of $f$. The set of all values of $f$ is called the range of $f$.

Definition 2.2: Let $f$ be a function from the set $A$ to the set $B$. When $E\subset A$, $f(E)$ is defined to be ${f(x)\mid x\in E}$. We call $f(E)$ the image of $E$ under $f$.

The range of $f$ is $f(A)$. When $f(A) = B$ we say that $f$ is onto

If $E\subset B$ then $f^{-1}(E)$ is defined to be ${x\in A\mid f(x)\in E}$. We call $f^{-1}(E)$ the inverse image of $E$ under $f$. For each $y\in B$ we define $f^{-1}(y) = f^{-1}({y})$. If each $y\in B$ has the property that $f^{-1}(y)$ is a singleton set (i.e. has exactly one element). Then we say $f$ is a one-to-one (more briefly 1-1) function. In other words $f$ is 1-1 provided that the following holds: if $x_1\neq x_2$ then $f(x_1)\neq f(x_2)$.

Definition 2.3: If there is a function from $A$ to $B$ that is both 1-1 and onto, then we say $A$ and $B$ can be put in 1-1 correspondence, or that $A$ and $B$ have the same cardinal number, or that $A$ and $B$ are equivalent. Symbolically, we denote this by writing $A\sim B$. The relation $\sim$ has three important properties, which together make it an equivalence relation.

• Reflexive: For any set $A$, $A\sim A$.
• Symmetric: If $A\sim B$, then $B\sim A$.
• Transitive: If $A\sim B$ and $B\sim C$, then $A\sim C$.

Definition 2.4: Let $n\in\mathbb{Z}^{+}$ and let $J_n = {1,2,\dots, n}$ (so $J_1 = {1}$, and by convention $J_0 = \emptyset$). Let $J = \mathbb{Z}^{+}$. For any set $A$ we say:

• $A$ is finite if $A$ is empty or $A\sim J_n$ for some $n\in J$.
• $A$ is infinite if it is not the case that $A$ is finite.
• $A$ is countable if $A\sim J$.
• $A$ is uncountable if $A$ is neither finite nor countable.
• $A$ is at most countable if $A$ is either finite or countable (i.e. when $A$ is not uncountable).

If $A$ is finite, then $A$ cannot be equivalent to one of its proper subsets. However, if $A$ is infinite this is quite possible. For example $\mathbb{Z}^{+}\sim\mathbb{N}\sim\mathbb{Z}$.

Definition 2.7 A sequence is a function with domain $\mathbb{Z}^{+}$. Where $f(n)=x_n$ we usually denote the sequence by ${x_n}$ or by $x_1,x_2,x_3,\dots$. The values of $f$ are called terms. If $x_n\in A$ for each $n\in \mathbb{Z}^{+}$, then we say that ${x_n}$ is a sequence in $A$.

It is sometimes more convenient to start the terms of a sequence with $x_0$ instead of $x_1$. Any countable set, $A$, can be “arranged in a sequence” by finding a 1-1 and onto function from $\mathbb{Z}^{+}$ to $A$.

Theorem 2.8: Every infinite subset of a countable set is countable.

By the previous theorem, we can say that countable sets represent the “smallest” kind of infinity.

Definition 2.9: Let $A$ and $\Omega$ be sets. Suppose that each $\alpha\in A$ is associated with some $E_\alpha \subset\omega$. The set of all such $E_\alpha$ will be denoted ${E_\alpha}$ and is sometimes called a collection or family of sets. The union of ${E_\alpha}$ is the set $S$ where $x\in S$ if and only if $x\in E_\alpha$ for some $\alpha\in A$. The intersection of ${E_\alpha}$ is the set $P$ where $x\in P$ if and only if $x\in E_\alpha$ for every $\alpha\in A$. The notations for union and intersection follow.

$S = \bigcup_{\alpha\in A}E_\alpha$ $P = \bigcap_{\alpha\in A}E_\alpha$

There are some variations on these notations found in your book, with which you should also familiarize yourself.

Remarks 2.11: Union and intersection are commutative, associative, and distributive. We state these for intersection, but all statements are still true when intersection and union are interchanged.

• Commutative: $A\cap B = B\cap A$
• Associative: $(A\cap B)\cap C = A\cap (B\cap C) = A\cap B\cap C$
• Distributive: $A\cap (B\cap C) = (A\cap B) \cap (A\cap C)$
• Distributive: $A\cap (B\cup C) = (A\cap B) \cup (A\cap C)$

A few more properties of intersection and union follow.

• $A\subset A\cup B$
• $A\cap B\subset A$
• $A\cup \emptyset = A$
• $A\cap \emptyset = \emptyset$
• If $A\subset B$, then $A\cup B = B$ and $A\cap B = A$.

Theorem 2.12: A countable union of (at most) countable sets is (at most) countable.

Theorem 2.13: Let $A$ be countable and $B_n$ be the set of all $n$-tuples from $A$. Then $B_n$ is also countable.

Corollary: The set $\mathbb{Q}$ is countable.

Theorem 2.14: Let $A$ be the set of sequences in ${0,1}$. Then $A$ is uncountable. The proof of this theorem is very important. Make sure you understand it thoroughly. Proof: By way of contradiction, assume that $A$ is countable. Then for each $n$ there is a sequence $s_n$ in ${0,1}$, and every sequence in ${0,1}$ is equal to $s_n$ for some $n$. Consider the following sequence ${x_n}$. We define the term $x_n$ to be equal to $1$ if the $n^\text{th}$ digit of the sequence $s_n$ is $0$, and $0$ otherwise. In other words ${x_n}$ always differs from the sequence $s_n$ in the $n^\text{th}$ digit. But then ${x_n}$ is a sequence in ${0,1}$ which cannot be equal to any $s_n$. This is a contradiction.