On Cardinality of Sets: UCI Math 13 Notes for Students

Here I’d like to make precise some notions that we’ve talked about in class, provide proofs of results that have been mentioned but remained dangling without proof, and give some examples and counter-examples. A few times I shall wave hands or base an argument on purely intuitive grounds in view of the lack of sophisticated mathematical machinery that is required to make these arguments precise (such as, for instance, some basic notions of topology and measure theory).

Let’s recall first basic definitions:

Given a set S, if S is a finite set (in this case this is a purely intuitive notion), then the cardinality of S, denoted \|S\|, is the number of elements in the set S. So, for instance, if S = \left\{a_1, a_2,\dots,a_n\right\}, then \|S\| = n. In particular, if S = \emptyset, then \|S\| = 0.

To define cardinality for a set containing infinitely many elements (again, a notion which is purely intuitive, but see the end of this post) is a hard and messy business. So, instead we shall define what it means for two (nonempty) sets S and T to have the same cardinality.

Definition: We say that sets S and T have the same cardinality, and write \|S\| = \|T\|, provided that there exists a bijection (a map which is one-to-one and onto) f: S\rightarrow T.

Lemma 1: Equality as defined for cardinalities is an equivalence relation. That is, for all sets S, T, W one has

  1. \|S\| = \|S\|.
  2. If \|S\| = \|T\|, then \|T\| = \|S\|.
  3. If \|S\| = \|T\| and \|T\| = \|W\| then \|S\| = \|W\|.

As an exercise, prove Lemma 1. The proof is straightforward. For (1) consider the identity map. For (2) keep in mind that a bijective map (a map that is 1-to-1 and onto) has a bijective inverse (prove this). For (3) prove that a composition of bijective maps is again a bijective map.

Lemma 2: If S and T are finite sets, then \|S\| = \|T\| if and only if they have the same number of elements.

Proof: Suppose that S consists of n\geq 0 elements and T consists of m \geq 0 elements.

If n = m, denote the elements of S by s_1, \dots, s_n and the elements of T by t_1,\dots, t_n. Then let f: S\rightarrow T by given by f = \left\{(s_j, t_j)\in S\times T: 1\leq j \leq n\right\}.

In the other direction, assume that \|S\| = \|T\|. Assume, without loss of generality, that n < m. By definition, there exists a function f which is onto from S to T. Hence f, when viewed as a set of ordered pairs, must contain at least m ordered pairs, with no repeating first coordinates. But the first coordinates take as values elements of S, of which there are only n, which is strictly less than m. Can’t be!

This completes the proof.

Essentially this theorem tells us that the definition in terms of a bijective function, and that in terms of number of elements (for finite sets) agree.

Notation: From now on we shall write |\cdot | for \|\cdot\|, not to be confused with the absolute value.

Definition: Given sets S and T, we say that |S| > |T| if there does not exist an onto map f: T\rightarrow S. We say that |S| \geq T provided that there exists an onto map f: S\rightarrow T.

Remark: If f: S\rightarrow T is one-to-one, then |T| \geq |S|. This is easy to prove: since f: S\rightarrow T is one-to-one (but nothing is being said about onto), let R be the range of f in T, then f: S\rightarrow R is one-to-one and onto. If it so happens that R = T, then by definition f is one-to-one and onto T, hence |S| = |T|.

Suppose that R\neq T (that is, the range of f is smaller than all of T), then, since f: S\rightarrow R is one-to-one and onto, f has an inverse g: R\rightarrow S. Now fix some s\in S (that is, pick some s\in S and let it be fixed for the rest of our discussion). Define the function h: T\rightarrow S as follows:

h(t) = \left\{\begin{array}{lcr} g(t) & \text{ if } & t\in R\\ s & \text{ if } & t\notin R\end{array}\right.

Then h: T\rightarrow S is onto, hence by definition |T| \geq |S|.

Lemma 3: If S is an infinite set and T is a finite set then |S| > |T|.

Proof: This is left as an exercise. Again, the idea of infinity is purely intuitive here.

Definition: A set S is said to be countable provided that |S| = |\mathbb{N}|. A set S is said to be uncountable if it is not countable.

Definition: A nonempty set S is said to be totally ordered provided that there exists a relation < on S such that for no element x\in S do we have x < x and for all elements x,y\in S either x < y or y < x and, further, for all x, y, z \in S, if x < y and y < z, then x < z.A totally ordered set is said to be well ordered provided that for any (nonempty) subset T\subset S, there exists t\in T such that for all x \in T one has t < x. That is, every subset has a least element.

Definition: We say that S is finitely well ordered provided that S is well ordered and carries the additional property that, for all s\in S, the set \left\{t\in S: t < s\right\}, that is, the set of all elements of S which are less than s, is finite. In other words, if one orders S by < , then there are finitely many elements preceding any s \in S.

Remark: \mathbb{N} is finitely well ordered (easily checked).

Remark: The condition of being finitely well ordered is independent of the condition of being well ordered (i.e., is not a consequence of the well-ordering). To see this, take \mathbb{N} and add to it the element \infty. In this case \infty doesn’t mean “infinity” – it’s only a label for an element. So, let S = \mathbb{N}\cup\left\{\infty\right\} and extend < defined on \mathbb{N} to S by declaring that x < \infty for all x\in \mathbb{N}. Then clearly S is well ordered, but is not finitely well ordered, since there are infinitely many elements less than the element \infty.

Theorem 1: Suppose that S is a finitely well ordered set. Then S is countable.

Proof: Let S be finitely well ordered. We shall define a bijection f: S\rightarrow \mathbb{N} inductively as follows. Let s_1 be the least element of S. Then let f(1) = s_1. In general, for n\geq 2 let s_n be the least element of S\setminus\left\{s_1, \dots, s_{n-1}\right\}. So essentially s_n is the n^\text{th} smallest element. Define f(n) = s_n.

Now, that f is a function is easily proved: for any given n, one cannot have f(n) = s and f(n) = t with s\neq t, for if s\neq t, then by the total order of S either s < t or t < s. In which case only one of them can be the least element of a subset, hence f(n) cannot equal both simultaneously.

That f is onto is a bit more subtle. Suppose that s \in S. Since S is finitely well ordered, we know that there are only finitely many elements preceding s. So list them: s_1 < s_2 < \cdots < s_k < s such that there doesn’t exist t\in S with s_k < t < s. That is,  s is the next smallest element after s_k. But then, by definition of f, we clearly have f(k+1) = s. So f is onto.

That f is one-to-one is not at all hard to check. Suppose f(n) = f(m). But then by the total ordering on S, we must have n = m.

This shows that f is a bijection from S onto \mathbb{N}, hence |S| = |N|. This completes the proof.

Remark: The converse of Theorem 1 is false. That is, if S is countable, one cannot conclude that S is finitely well ordered. For instance, take S = \mathbb{N}\cup\left\{\infty\right\} as in the previous remark. Now consider f: \mathbb{N}\rightarrow S such that f(1) = \infty and for k \geq 2, f(k) = k-1. One can check that f is a bijection, so S is countable. But as we’ve already seen, S is not finitely well ordered.

Lemma 4: Any subset of a finitely well ordered set is itself finitely well ordered.

Proof: Prove this as an exercise.

Theorem 2: Every subset of \mathbb{N} is either finite or countable.

Proof: Suppose that S\subset\mathbb{N}. Suppose that S is not finite. Then S is infinite and, furthermore, is finitely well ordered by Lemma 4. Hence, by Theorem 1, S is countable.

Theorem 3: A finite Cartesian product

S = \underbrace{\mathbb{N}\times\mathbb{N}\times\cdots\times\mathbb{N}}_{k-\text{times}}

is countable.

Proof: Consider the map f: S\rightarrow \mathbb{N} given by f: (s_1, s_2,\dots,s_k)\mapsto p_1^{s_1}p_2^{s_2}\cdots p_k^{s_k} where p_j stands for the j^\text{th} prime. Check, as an exercise, that this function is one-to-one.

Now, it is obvious that the function is not onto (for instance, there is nothing that maps to 1). But that’s not a problem. Let R\subset \mathbb{N} be the range of this function. But then f is one-to-one and onto its range R. Hence |R| = |S|. On the other hand, by Theorem 2 we know that R is countable, so |R| = |\mathbb{N}|. Finally by Lemma 1 we conclude that |S| = |\mathbb{N}|. Hence S is countable.

Remark: In general a finite Cartesian product of countable sets is again countable. Simply replace \mathbb{N} with countable sets S_1, S_2, \dots, S_k, and enumerate each set S_j = \left\{s_1^j, s_2^j, \dots\right\}. Then obviously

|S_1\times S_2\times\cdots\times S_k| = |\underbrace{\mathbb{N}\times\mathbb{N}\times\cdots\times\mathbb{N}}_{k-\text{times}}|

Now use Theorem 3.

We shall soon see that an infinite Cartesian product of countable sets is not necessarily countable. Next we ask: well, what about the union of countable sets? Are finite unions of countable sets remain countable? Are infinite unions of countable sets remain countable?

The answer to the first question is – yes. The answer to the second question is complicated by the notion of infinity. That is – what do we mean by an infinite union? As it turns out, if we have a countable collection of sets, then their union (called countable union) is countable. If, however, we have an uncountable collection of sets, then their union is not necessarily countable.

Let us first prove that a finite, or a countable union of countable sets is countable.

Theorem 4: Suppose that \left\{S_1, S_2, S_3, \dots, S_n,\dots\right\} is a countable collection of countable sets (that is, each S_j is countable and, furthermore, there are only countably many of these sets. Then their union,

\bigcup_{n = 1}^\infty S_n

is countable.

Proof: Let T_1 = S_1. Let T_2 = S_2\setminus S_1, let T_3 = S_3\setminus(S_1\cup S_2), and in general,

for n\geq 2, let T_n = S_n\setminus(S_1\cup S_2\cup\cdots\cup S_{n-1}).

It may seem strange why we’re doing this. But notice that (prove this as an exercise):

\bigcup_{n=1}^\infty T_n = \bigcup_{n=1}^\infty S_n

and, furthermore,

T_i\cap T_j = \emptyset whenever i \neq j

This is very convenient. By the first assertion, to prove that \bigcup_{n = 1}^\infty S_n is countable, it will suffice to prove that \bigcup_{n=1}^\infty T_n is countable. This task is made easier by the fact that T_n’s are pairwise disjoint (that is, no two of them intersect).

Since each T_n is obviously countable (since it is equal to S_n minus possibly some elements, and each S_n is countable by hypothesis), we can list the elements of T_n as t_1, t_2, t_3,\dots and so on. To emphasise that these elements belong to T_n and not, say, T_k, let us list them as t_1^n, t_2^n, t_3^n, \dots. So each T_n can be written as

T_n = \left\{t_1^n, t_2^n, \dots\right\}

Hence if we set T = \bigcup_{n=1}^\infty T_n, then each element of T is of the form t_i^j, where j indicates which of the T_n’s it belongs to, and i indicates its index inside T_j. Now consider f: T\rightarrow \mathbb{N}\times\mathbb{N} given by

f(t_i^j) = (i, j)

You can prove as an exercise that f is a function, and is one-to-one. It is not necessarily onto \mathbb{N}\times\mathbb{N}, but that’s OK. Let R be the range of f in \mathbb{N}\times\mathbb{N}. Then f is one-to-one and onto R. So |T| = |R|. On the other hand, R\subset \mathbb{N}\times\mathbb{N}, hence by the previous result, R is countable. Thus by transitivity, we must also have that T is countable. And we’re done.

Notice that we needed T_n’s to be pairwise disjoint, since otherwise f would not be a well-defined function.

Theorem 5: The sets \mathbb{Z}, \mathbb{Q} are countable.

Proof: Since \mathbb{Z} = \left\{-1, -2, -3, \dots \right\}\cup\left\{0\right\}\cup\left\{1,2,3,\dots\right\}, then by Theorem 4 \mathbb{Z} is countable. Now on to \mathbb{Q}: If p/q is in reduced form (that is, p and q have no common divisors other than the number \pm 1), then we can represent p/q as the ordered pair (p, q). Hence \mathbb{Q}_{>0}, the subset of \mathbb{Q} of positive fractions, can be represented as a subset of \mathbb{N}\times \mathbb{N}, hence countable. Similarly for \mathbb{Q}_{< 0}. So

\mathbb{Q} = \mathbb{Q}_{> 0}\cup\left\{0\right\}\cup\mathbb{Q}_{< 0},

hence \mathbb{Q} is countable, being a union of countable sets.

Lemma 5: Let B = \left\{0, 1\right\}. Now let

\tilde{B} = \underbrace{B\times B\times\cdots}_{\mathbb{N}-\text{times}}

That is, we take the cross product of infinitely many copies of B, countably many times. We claim that \tilde{B} is not countable. One can visualise \tilde{B} is the set of \infty-tubles (i_1, i_2, i_3, \dots), where each i_k carries the value of either 0 or 1. Essentially, these are infinite binary strings.

Proof: Suppose that \tilde{B} is countable. Enumerate its elements as b_1, b_2, b_3, \dots. Now construct an infinite binary string b as follows: b = (j_1, j_2, j_3, \dots) by letting j_1 be the opposite of the first entry in b_1, j_2 is the opposite of the second entry in b_2, j_3 is the opposite of the third entry in b_3, and so on (by the opposite we mean: if the entry is 0, then we take 1 as its opposite, and if the entry is 1, we take 0 as its opposite). Now, since b is an infinite binary string, certainly b\in \tilde{B}. However, b is different from each of b_1, b_2, b_3, \dots (since the entry in the jth place of b is different from the entry in the jth place of b_j, just by how we constructed b in the first place).

But this is a contradiction, since we assumed that b_1, b_2, b_3,\dots was an enumeration of \tilde{B} (that is, every element of \tilde{B} is one of those). So, \tilde{B} is uncountable.

Theorem 6: \mathbb{R}, the set of all real numbers, is uncountable.

Proof 1: Let \tilde{B} be as above. Consider f: \tilde{B}\rightarrow [0, 1] (where [0, 1] is the positive unit interval in \mathbb{R}), given as follows:

f((j_1,j_2,j_3,\dots)) = \sum_{n = 1}^\infty \frac{j_n}{2^n}

where, remember, (j_1, j_2, j_3, \dots) is an infinite binary string. So each j_k is either 0 or 1. The sum above converges, since it is not greater than the geometric series

\sum_{n=1}^\infty \frac{1}{2^n}

and the element that it converges to is not greater than 1. Hence f is a well-defined function and, furthermore, is one-to-one. But then, by the remark following Lemma 2, |\mathbb{R}|\geq |[0, 1]|\geq |\tilde{B}| and \tilde{B} is uncountable, as we saw above. Hence \mathbb{R} is uncountable.

Proof 2: (One needs elements of measure theory to make this proof precise – we’ll simply proceed via intuiiton). Suppose that \mathbb{R} is countable. But then [0, 1] must also be countable. Enumerate [0, 1] = \left\{s_1, s_2, s_3, \dots\right\}. Let \epsilon > 0 be fixed. Let

I_n = (s_n - \frac{\epsilon}{2^{n+1}}, s_n + \frac{\epsilon}{2^{n+1}})

But then

[0, 1] \subset \bigcup_{n=1}^\infty I_n

Now let L denote the length function, that is, for any interval I we let L(I) be the length of I. For convenience, set

U = \bigcup_{n=1}^\infty I_n

We take for granted that U is actually an interval. We take the following for granted too, but it is intuitively obvious, as the length of the whole thing is smaller than or equal to the sum of the lengths of its constituent parts:

L(U) \leq \sum_{n=1}^\infty L(I_n) = \sum_{n=1}^\infty \frac{\epsilon}{2^n} = \epsilon\sum_{n=1}^\infty \frac{1}{2^n} = \epsilon

On the other hand, since [0, 1]\subset U, we must have L(I)\leq L(U). But L(I) = 1. So from above we get L(I) \leq \epsilon. But \epsilon was arbitrary, so we can take it as small as we please. In particular, we may let \epsilon = 1/2. Then we get 1 \leq 1/2, a clear contradiction! So [0, 1] is not countable and hence \mathbb{R} is uncountable.

Theorem 7: If I is any interval in \mathbb{R}, then |I| = |\mathbb{R}|.

Proof: First let us suppose that I is an open interval, finite interval. Write I = (a, b). Consider the map f: (a, b)\rightarrow (-\pi/2, \pi/2) given by

f(x) = \frac{\pi}{b-a}(x-a) - \frac{\pi}{2}

It is easy to verify that f is one-to-one and onto. So |(a, b)| = |(-\pi/2, \pi/2)|. Now consider the map h: (-\pi/2, \pi/2)\rightarrow\mathbb{R} given by h(x) = \tan(x). Then you can verify that this map is one-to-one and onto, hence |(-\pi/2, \pi/2)| = |\mathbb{R}|, and so, for any open interval (a, b), we have |(a, b)| = |\mathbb{R}|.

Now suppose that I is a finite closed interval. Write I = [a, b]. But then (a, b)\subset [a, b], and so |\mathbb{R}| = |(a, b)| \leq |[a, b]| \leq |\mathbb{R}|, and so |\mathbb{R}| = |I|.

Similar proofs work for intervals of the form [a, \infty), (a, \infty), (-\infty, b), (-\infty, b].

I think I want to stop here. I do recommend looking over the following article in Wikipedia, especially now since you understand basic things about cardinalities: Continuum Hypothesis

This entry was posted on Sunday, November 15th, 2009 at 00:13 and is filed under For My Students, Math 13 Fall 09, Mathematics Lecture Notes. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “On Cardinality of Sets: UCI Math 13 Notes for Students”

  1. gina Says:
    November 22, 2009 at 02:06 | Reply

    Hi Will, Where does cardinality fall under Tucker’s hints?

    1. Be able to state definitions. With readable sentences.
    2. Tautologies.
    3. Addition.
    4. Multiplication.
    5. Product spaces.
    6. Functions.
    7. Equivalence relations.
    8. Equivalence classes.
    9. The integers.
    10. The axiom of induction, what it means and how to use it in doing a proof.
    11. Less than,
    12. Be able to state one or more reasons for every statement of a proof.

    thanks!

    • akcuoma Says:
      November 23, 2009 at 00:27 | Reply

      Well, this is supplementary material to what we’ve covered in class. So, as far as the exam is concerned: you’re only responsible for the stuff that was covered in class.

Leave a Reply