How to measure the size of a set? It is easy for sets with finite elements, but how about sets with infinite elements? We have used ‘infinite’ several times in previous posts, as we all have a rough idea about what infinity means. In this post, we will give strict definition and other discussions concerning finite and infinite sets. Notice that \mathbb{N} has already been assumed.

1. Finite set

When we say a set is finite, we normally presume the existence of the amount. For example, the set \{a,b,c,d\} is finite because it has four elements;  the set ‘Chinese citizens’ is also finite as the amount, or say the total number of its elements, is finite, even though huge. We summarize this in a mathematical way as:

A set A is finite if it’s empty, or there exists a positive number N \in \mathbb{N} such that we can find a bijection between A and \{1,2,\ldots, N\}.

Here, N is the amount of elements of A, which is a basic characteristic of this set. We call it the cardinality (势) of A. The cardinality of a set is also called the cardinal number (序数). Informally, cardinality is the size of sets.

For a finite set, after defining the function (bijection), we are actually arranging the set. f(n) is called the nth element under this function. Therefore, each element might be in different positions under different functions. However, the size for finite sets is fixed, which is guaranteed by the following theorem:

Theorem 1: The cardinality is unique for finite sets.

2. Countable set

A set is infinite if it is not finite. More specifically, a set is infinite if one cannot find a positive number N \in \mathbb{N} such that there exists a bijection between A and \{1,2,\ldots, N\}.

In the above definition, N is a finite natural number. It makes sense since \mathbb{N} is assumed being well defined. Another point of view is for a finite set, after the arrangement by some function (bijection), there is a last element, Nth element.. For example, for the set {a,b,c,d}, we can arrange it in the manner of ‘a,b,c,d’, where ‘d’ is the last (4th) element; or we can arrange it as ‘d,b,a,c’, where ‘c’ is the 4th element. No matter how one arrange these element, the last one is always the 4th one. In another word, the cardinality of this set is 4.

For an infinite set, the property doesn’t hold. Take \mathbb{N} itself as an example. There is no biggest natural number. However, we can still list them as ‘1,2,3,…’. Another example is \mathbb{Z}. We can list all the integers in this way: ‘0,1,-1,2,-2,3,-3,…’. Therefore, each integer has an unique position in this list, and one can find out the number for any given position. It is like one can count these numbers one by one, even though there is no stop. We think these infinite sets are still not that bad to study. Some other ones are even ‘worse’, like \mathbb{R}. There is no way to list all real numbers down.

A set is countable if it is finite, or there is a bijection between it and \mathbb{N}. For the second case, we call this set countable infinite.

Example 1: \mathbb{Q} is countable. 

Example 2: \{A_{\alpha}\}_{\alpha \in \mathfrak{A}} is a countable family of sets, where A_{\alpha} is countable for each \alpha \in \mathfrak{A}. Then \displaystyle \bigcup_{\alpha \in \mathfrak{A}} A_{\alpha} is countable.

3. Uncountable sets

A set is uncountable (infinite) if it is not countable (neither finite nor countable infinite).

Example 3: \mathbb{R} is uncountable.

An useful technique to prove a set being uncountable is to prove there is a bijection between this set and \mathbb{R}.

Example 4: \mathcal{P}(\mathbb{N}) (the power set of \mathbb{N}) is uncountable. 

Example 5: 2^{\mathbb{N}}:=\{2^n|n \in \mathbb{N}\} is uncountable.

3. Cardinal numbers of infinite sets

Now back to the original question. The answer is to compare their cardinal numbers. We say two sets are of the same size (cardinality), if their cardinal numbers are the same.

  • The cardinal number of a finite set are easily equal to the number of its elements, which is the cardinality.

However, it is not so clear for infinite sets. (we haven’t define cardinality and cardinal numbers for infinite sets yet.) A famous example is to compare the sizes of \mathbb{N} and \mathbb{N}-\{1\}. Seems like the second set is one element less than the first set. But does the first set really has more elements than the second set? By define f(n)=n+1, I can find ‘as many elements as there are’ in the first set. Moreover, let’s look at the following concern.

  • All countable infinite sets should have the same ‘size’. This is clear since bijection has transitivity. If both f:A \to \mathbb{N} and g: B \to \mathbb{N} are bijections, then g^{-1} \circ f: A \to B is also a bijection.

Hence, we define the cardinal number of countable infinite sets as \aleph_0.

  • For uncountable sets, there might be different sizes, and things become very complicated here. We define the cardinal number of \mathbb{R} as \aleph. Of course, for any set, if there is a bijection between it and \mathbb{R}, its cardinal number is also \aleph.

For cardinal numbers greater than \aleph, you can refer to here.

4. Summary

So far, we have defined the cardinal number for finite sets, countable infinite sets, and some uncountable sets. To compare the cardinalities of two sets, we use functions. For two sets A and B:

  • Their cardinalities are comparable. (See Well Ordering Principle)
  • There have the same cardinality if there is a bijection from A to B.
  • The cardinality of A is less than or equal to the cardinality of B, if there is an injection from A to B. Additionally, it is strictly less than if there is no injection from B to A (therefore no bijection between A and B).
Advertisements