One of the set traits that will be useful to us in distinguishing between algebraic structures is *cardinality*.

#####
Definition1.3.1

A set is *finite* if it contains a finite number of elements; otherwise, it's *infinite*. The *cardinality* of a finite set \(S\) is the number of elements in \(S\text{;}\) we denote the cardinality of \(S\) by \(|S|\text{.}\) When \(S\) is infinite, we may write \(|S|=\infty\text{.}\)

Note that in the above definition, we omitted the definition of the cardinality of an infinite set. This is because defining the cardinality of an infinite set is a more complicated endeavor, and one which is, in the most general context, beyond the scope of this class. For us it will suffice to distinguish between two types of infinite sets: *countably infinite* sets and *uncountable* (or *uncountably infinite*) sets.

#####
Definition1.3.3

A set \(S\) is said to be *countably infinite* if there exists a bijection from \(S\) to \(\Z\) (equivalently, if there exists a bijection from \(\Z\) to \(S\)). It is said to be *countable* if it is finite or countably infinite, and *uncountable* (or *uncountably infinite*) if it is not countable.

Here are some straightforward examples to get us started:

#####
Example1.3.4

- \(|\{a,b\}|=2\text{.}\)
- \(|\emptyset|=0\text{.}\)
- Clearly, \(\Z\) itself is countably infinite.

Perhaps surprisingly, a proper subset of a set can have the same cardinality as its superset, as the following example shows.

#####
Example1.3.6

We claim that \(\Z^+\) is countably infinite. Indeed, consider the function \(f:\Z^+ \to \Z\) defined by \(f(n)=(-1)^n \lfloor n/2 \rfloor\text{,}\) where \(\lfloor x \rfloor\) denotes the greatest integer less than or equal to \(x\text{,}\) for each \(x\in \R\text{.}\) The fact that \(f\) is a bijection is demonstrated (though not proven) by the following visual representation, where each number maps via \(f\) to the value directly to the right of it:

\(1\) |
\(0\) |

\(1\) |
\(1\) |

\(2\) |
\(-1\) |

\(3\) |
\(2\) |

\(4\) |
\(-2\) |

\(\vdots\) |
\(\vdots\) |

Note that this means that \(\Z\) and its proper subset \(\Z^+\) have the same cardinality, that is, the same “size”!

We summarize here examples of countably and uncountably infinite sets. (On pp. 5–6 of [1], Fraleigh sketches proofs of the facts that \(\Q\) is countable and that the interval \((0,1)\) in \(\R\) is uncountable. The proof then that \(\R\) is uncountable follows from Theorem 1.3.7, below.)

Countably infinite sets: \(\Z\text{,}\) \(\Z^+\text{,}\) \(\Z^-\text{,}\) \(\Z^*\text{,}\) \(\Q\text{,}\) \(\Q^+\text{,}\) \(\Q^-\text{,}\) \(\Q^*\text{,}\) \(\N\)

Uncountably infinite sets: \(\R\text{,}\) \(\R^+\text{,}\) \(\R^-\text{,}\) \(\R^*\text{,}\) \(\C\text{,}\) \(\C^*\text{,}\) the interval \((0,1)\) in \(\R\)

The key idea here for us is that if two sets are essentially “the same,” then they must have the same “size.” Thus, we see that there is some fundamental difference between the sets \(\Z\) and \(\R\) (in fact, there are many such differences). On the other hand, cardinality alone won't allow us to distinguish structurally between the sets \(\Z\) and \(\Z^+\text{.}\)

We end our preliminary chapter with the following theorem and a corollary of it (which can be proved using induction on \(n\)). We omit the proofs of the first two statements.

#####
Theorem1.3.7

Let \(A\) and \(B\) be sets.

If \(A\subseteq B\) and \(A\) is infinite [uncountable] then so is \(B\text{.}\)

If \(A\subseteq B\) and \(B\) is finite [countable] then so is \(A\text{.}\)

If \(|A|=m\lt \infty\) and \(|B|=n\lt \infty\text{,}\) then \(|A\times B|=mn\text{.}\) More generally, if \(n>1\) is an integer and \(A_1, A_2, \ldots, A_n\) are sets with \(|A_i|=k_i\lt \infty\) for each \(i=1,2,\ldots, n\text{,}\) then \(|A_1 \times A_2 \times \cdots \times A_n|=k_1k_2\cdots k_n\text{.}\)

Let \(A\) and \(B\) be countable sets. Then \(A \times B\) is countable. More generally, if \(n>1\) be an integer and \(A_1,A_2,\ldots, A_n\) are countable sets, then \(A_1\times A_2\times \cdots \times A_n\) is countable.

##### Proof

You prove the first statement in Part 3 in your homework. The second statement in Part 3 follows using induction on the number of sets.

To prove the first statement in Part 4: Assume that \(A\) and \(B\) are both countably infinite. Since \(\Z^+\) is countably infinite, we can index the elements of \(A\) and of \(B\) by \(\Z^+\text{,}\) writing

\begin{equation*}
A=\{a_1,a_2,\ldots\} \text{ and } B=\{b_1,b_2,\ldots\}.
\end{equation*}
Notice that the table

\((a_1,b_1)\) |
\((a_1,b_2)\) |
\((a_1,b_3)\) |
\(\cdots\) |

\((a_2,b_1)\) |
\((a_2,b_2)\) |
\((a_2,b_3)\) |
\(\cdots\) |

\((a_3,b_1)\) |
\((a_3,b_2)\) |
\((a_3,b_3)\) |
\(\cdots\) |

\(\vdots\) |
\(\vdots\) |
\(\vdots\) |
\(\ddots\) |

contains every element of \(A\times B\text{.}\) We can then list the elements of \(A\times B\) by listing the elements in progressive upper-right to lower-left diagonals, starting with \((a_1,b_1)\) and moving to the right along the top row: that is, we can write

\begin{equation*}
A\times B=\{(a_1,b_1),(a_1,b_2),(a_2,b_1),(a_2,b_3),(a_2,b_2),(a_3,b_1),\ldots\}.
\end{equation*}
This implicitly yields a bijection from \(\Z^+\) to \(A\times B\text{;}\) thus, \(A\times B\) is countably infinite, and hence countable.

The proof in the case that one or both \(A\) and \(B\) are finite is similar; the corresponding table in that case will simply have either only finitely many rows or finitely many columns, or both.

The second statement in Part 4 follows using induction on the number of sets.