One of the set traits that will be useful to us in distinguishing between algebraic structures is cardinality.
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{.}\)
Of course, vertical bars are used to denote other mathematical concepts; for instance, if \(x\) is a real number, \(|x|\) usually denotes the absolute value of \(x\text{.}\) You must determine from context, and from the nature of the expression within the bars, what vertical bars mean in a particular context.
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.
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:
It turns out that countably infinite sets have the same cardinality as one another, while a countably infinite set and an uncountable set have different cardinalities. Intuitively, you can think of two countably infinite sets as having the same “size,” and a countable set and an uncountable set as having different “sizes”; however, this is a risky way of framing things, since it can make some results seem counterintuitive when you're used to dealing only with finite sets (see, for instance, Example 1.3.6). Luckily, exploring the cardinality of infinite sets isn't the focus of this class.
Perhaps surprisingly, a proper subset of a set can have the same cardinality as its superset, as the following example shows.
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.
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.
It is not true that any countable product of countable (or even finite) sets is countable. Indeed, even the set \(\{0,1\}\times \{0,1\}\times \cdots\) is uncountable. (If you want to get into the gory details of this, the key is that there is a bijection from this set to the power set of the natural numbers, which Cantor's Theorem tells us is uncountable. You are welcome to jump down this rabbit hole by googling “Cantor's Theorem,” if you desire, but know that you will not be responsible for that material in class.)