Cardinality
Contents
1.6. Cardinality#
In this section, we deal with questions concerning the size of a set. When do we say that two sets have same number of elements?
If we can find a one-to-one correspondence between two sets \(A\) and \(B\) then we can say that the two sets \(A\) and \(B\) have same number of elements.
In other words, if there exists a bijective function \(f : A \to B\), we say that \(A\) and \(B\) have same number of elements.
Definition 1.82 (Equivalent sets)
Two sets \(A\) and \(B\) are said to be equivalent (denoted as \(A \sim B\)) if there exists a bijective function \(f : A \to B\). When two sets are equivalent, we say that they have same cardinality.
Note that two sets may be equivalent yet not equal to each other.
Example 1.17 (Equivalent sets)
The set of natural numbers \(\Nat\) is equivalent to the set of integers \(\ZZ\). Consider the function \(f : \Nat \to \ZZ\) given by
\[\begin{split} f (n) = \left\{ \begin{array}{ll} (n - 1) / 2 & \mbox{if $n$ is odd};\\ -n / 2 & \mbox{if $n$ is even}. \end{array} \right. \end{split}\]It is easy to show that this function is bijective.
\(\Nat\) is equivalent to the set of even natural numbers \(E\). Consider the function \(f : \Nat \to E\) given by \(f(n) = 2n\). This is a bijective mapping.
\(\Nat\) is equivalent to the set of rational numbers \(\QQ\).
The sets \(\{a, b, c\}\) and \(\{1,4, 9\}\) are equivalent but not equal.
Theorem 1.23 (Cardinality as equivalence relation)
Let \(A, B, C\) be sets. Then:
\(A \sim A\).
If \(A \sim B\), then \(B \sim A\).
If \(A \sim B\), and \(B \sim C\), then \(A \sim C\).
Thus, it is an equivalence relation.
Proof. (1). Construct a function \(f : A \to A\) given by \(f (a) = a \Forall a \in A\). This is bijective. Hence \(A \sim A\).
(2). It is given that \(A \sim B\). Thus, there exists a function \(f : A \to B\) which is bijective. Thus, there exists an inverse function \(g : B \to A\) which is bijective. Thus, \(B \sim A\).
(3). It is given that \(A \sim B\) and \(B \sim C\). Thus, there exist two bijective functions \(f : A \to B\) and \(g : B \to C\). Define a function \( h : A \to C\) given by \( h = g \circ f\). Since composition of bijective functions is bijective , \(h\) is bijective. Thus, \(A \sim C\).
1.6.1. Cardinality and Natural Numbers#
We now look closely at the set of natural numbers \(\Nat = \{1,2,3,\dots\}\).
Definition 1.83
Any subset of \(\Nat\) of the form \(\{1,\dots, n\}\) is called a segment of \(\Nat\). \(n\) is called the number of elements in the segment or its cardinality.
Remark 1.15
Two segments \(\{1,\dots,m\}\) and \(\{1,\dots,n\}\) are equivalent only if \(m= n\).
Thus, a proper subset of a segment cannot be equivalent to the segment.
Definition 1.84
A set that is equivalent to a segment is called a finite set.
The cardinality or number of elements of a set which is equivalent to a segment is equal to the number of elements in the segment.
Remark 1.16
The empty set \(\EmptySet\) is also considered to be finite with zero elements.
Definition 1.85
A set that is not finite is called an infinite set.
It should be noted that so far we have defined number of elements only for sets which are equivalent to a segment.
Definition 1.86
A set \(A\) is called countable if it is equivalent to \(\Nat\), i.e., if there exists a bijective correspondence of \(\Nat\) with the elements of \(A\).
Definition 1.87
A countable set \(A\) is usually written as \(A = \{a_1, a_2, \dots\}\) which indicates the one-to-one correspondence of \(A\) with the set of natural numbers \(\Nat\). This notation is also known as the enumeration of \(A\).
Definition 1.88
An infinite set which is not countable is called an uncountable set.
With the definitions in place, we are now ready to study the connections between countable, uncountable and finite sets.
1.6.2. Infinite Sets#
Theorem 1.24
Every infinite set contains a countable subset.
Proof. Let \(A\) be an infinite set. Clearly, \(A \neq \EmptySet\). Pick an element \(a_1 \in A\). Consider the set \(A_1 \triangleq A \setminus \{a_1 \}\). Since \(A\) is infinite, hence \(A_1\) is nonempty. Pick an element \(a_2 \in A_1\). Clearly, \(a_2 \neq a_1\). Consider the set \(A_2 \triangleq A \setminus \{a_1, a_2 \}\). Again, by the same argument, since \(A\) is infinite, \(A_2\) is non-empty. We can pick \(a_3 \in A_2\). Proceeding in the same way we construct a set \(B \triangleq \{a_1, a_2, a_3, \dots \}\). The set is countable and by construction it is a subset of \(A\).
Theorem 1.25
Every subset of a countable set is either finite or countable. i.e. if \(A\) is countable and \(B \subseteq A\), then either \(B\) is finite or \(B \sim A\).
Proof. Let \(A\) be a countable set and \(B \subseteq A\).
If \(B\) is finite, then there is nothing to prove.
So we consider \(B\) as infinite and show that it is countable.
Since \(A\) is countable, hence \(A \sim \Nat\).
Thus, \(B\) is equivalent to a subset of \(\Nat\).
Without loss of generality, let us assume that \(B\) is a subset of \(\Nat\).
We now construct a mapping \(f : \Nat \to B\) as follows. Let \(b_1\) be the
least element of \(B\) (which exists due to the
well ordering principle).
We assign \(f(1) = b_1\).
Now, let \(b_2\) be the least element of \(B \setminus \{ b_1\}\).
We assign \(f(2) = b_2\).
Similarly, assuming that \(f(1) = b_1, f(2) = b_2, \dots , f(n) = b_n\) has
been assigned,
we assign \(f(n+1) = \) the least element of \(B \setminus \{b_1, \dots, b_n\}\).
This least element again exists due to the
well ordering principle.
This completes the definition of \(f\) using the
principle of mathematical induction.
It is easy to show that the function is bijective.
This proves that \(B \sim \Nat\).
We present different characterizations of a countable set.
Theorem 1.26 (Characterizations of countable sets)
Let \(A\) be an infinite set. The following are equivalent:
A is countable.
There exists a (partial) function \(f: \Nat \to A\) that is onto.
There exists a (total) function \(g : A \to \Nat\) that is one-one.
Proof. (1)\(\implies\) (2). Since \(A\) is countable, there exists a function \(f : \Nat \to A\) which is bijective. Choosing \(B = \Nat\), we get the result.
(2)\(\implies\) (3). We are given that there exists a (partial) function \(f: \Nat \to A\) that is onto. For some \(a \in A\), consider \(f^{-1}(a) = \{ b \in \Nat \ST f(b) = a \}\). Since \(f\) is onto, hence \(f^{-1}(a)\) is nonempty. Since \(f^{-1}(a)\) is a subset of natural numbers, it has a least element due to the well ordering principle. Further, if \(a_1, a_2 \in A\) are distinct, then \(f^{-1}(a_1)\) and \(f^{-1}(a_2)\) are disjoint and the corresponding least elements are distinct. Assign \(g(a) = \text{ least element of } f^{-1}(a) \Forall a \in A\). Such a function is well defined by construction. Clearly, the function is one-one.
(3)\(\implies\) (1). We are given that there exists a function \(g : A \to \Nat\) that is one-one. Clearly, \(A \sim g(A)\) where \(g(A) \subseteq \Nat\). Since \(A\) is infinite, hence \(g(A)\) is also infinite. Due to Theorem 1.25, \(g(A)\) is countable since it is the subset of a countable set \(\Nat\). Then, \(g(A) \sim \Nat\). Thus, \(A \sim g(A) \sim \Nat\) and \(A\) is countable.
Theorem 1.27 (Countable union of countable sets)
Let \(\{A_1, A_2, \dots \}\) be a countable family of sets where each \(A_i\) is a countable set. Then
is countable.
Proof. Let \(A_n = \{a_1^n, a_2^n, \dots\} \Forall n \in \Nat\). Further, let \(B = \{2^k 3^n : k, n \in \Nat \}\). Note that every element of \(B\) is a natural number, hence \(B \subseteq \Nat\). Since \(B\) is infinite, hence by Theorem 1.25 \(B\) is countable, i.e. \(B \sim \Nat\). We note that if \(b_1 = 2^{k_1} 3^{n_1}\) and \(b_2 = 2^{k_2} 3^{n_2}\), then \(b_1 = b_2\) if and only if \(k_1 = k_2\) and \(n_1 = n_2\). Now define a mapping \(f : \Nat \to A\) with \(\dom f = B\), given by \(f (2^k 3^n) = a^n_k\) (picking \(k\)-th element from \(n\)-th set). Clearly, \(f\) is well-defined and onto. Thus, using Theorem 1.26, \(A\) is countable.
Theorem 1.28
Let \(\{A_1, A_2, \dots, A_n \}\) be a finite collection of sets such that each \(A_i\) is countable. Then their Cartesian product \(A = A_1 \times A_2 \times \dots \times A_n\) is countable.
Proof. Let \(A_i = \{a_1^i, a_2^i, \dots\} \Forall 1 \leq i \leq n\). Choose \(n\) distinct prime numbers \(p_1, p_2, \dots, p_n\). Consider the set \(B = \{p_1^{k_1}p_2^{k_2} \dots p_n^{k_n} : k_1, k_2, \dots, k_n \in \Nat \}\). Clearly, \(B \subset \Nat\). Define a function \(f : A \to \Nat \) as
By fundamental theorem of arithmetic, every natural number has a unique prime factorization. Thus, \(f\) is one-one. Invoking Theorem 1.26, \(A\) is countable.
Theorem 1.29 (Cardinality of rational numbers)
The set of rational numbers \(\QQ\) is countable.
Proof. Let \(\frac{p}{q}\) be a positive rational number with \(p > 0\) and \(q > 0\) having no common factor. Consider a mapping \(f(\frac{p}{q}) = 2^p 3^q\). This is a one-one mapping into natural numbers. Hence invoking Theorem 1.26, the set of positive rational numbers is countable. Similarly, the set of negative rational numbers is countable. Invoking Theorem 1.27, \(\QQ\) is countable.
Theorem 1.30 (Cardinality of set of finite subsets)
The set of all finite subsets of \(\Nat\) is countable.
Proof. Let \(F\) denote the set of finite subsets of \(\Nat\). Let \(f \in F\). Then we can write \(f = \{n_1, \dots, n_k\}\) where \(k\) is the number of elements in \(f\). Consider the sequence of prime numbers \(\{p_n\}\) where \(p_n\) denotes \(n\)-th prime number. Now, define a mapping \(g : F \to \Nat\) as
The mapping \(g\) is one-one, since the prime decomposition of a natural number is unique. Hence invoking Theorem 1.26, \(F\) is countable.
Corollary 1.2
The set of all finite subsets of a countable set is countable.
1.6.3. Partial Order for Cardinality#
Definition 1.89 (Equivalence with subset)
We say that \(A \preceq B\) whenever there exists a (total) one-one function \(f : A \to B\). In other words, \(A\) is equivalent to a subset of \(B\).
In this sense, \(B\) has at least as many elements as \(A\).
Theorem 1.31
The relation \(\preceq\) satisfies following properties
Reflexivity: \(A \preceq A\) for all sets \(A\).
Transitivity: If \(A \preceq B\) and \(B \preceq C\), then \(A \preceq C\).
Antisymmetry: If \(A \preceq B\) and \(B \preceq A\), then \(A \sim B\).
Thus, \(\preceq\) is a partial order.
Proof. (1). We can use the identity function \(f (a ) = a \Forall a \in A\).
(2). Straightforward application of Theorem 1.1 that composition of injective functions is injective.
(3). Straightforward application of Schröder-Bernstein Theorem.
1.6.4. Power Sets#
Theorem 1.32 (Cardinality of power set)
If \(A\) is a set, then \(A \preceq \Power (A)\) and \(A \nsim \Power (A)\).
This result establishes that the power set of a set is larger than itself.
Proof. We first show that \(A \preceq \Power (A)\):
If \(A = \EmptySet\), then \(\Power(A) = \{ \EmptySet\}\) and the result is trivial.
So, lets consider non-empty \(A\).
We can choose \(f : A \to \Power(A)\) given by \(f (x) = \{ x\} \Forall x \in A\).
This is clearly a one-one (total) function leading to \(A \preceq \Power (A)\).
Next we show that \(A \nsim \Power (A)\):
For the sake of contradiction, lets us assume that \(A \sim \Power (A)\).
Then, there exists a bijective function \(g : A \to \Power(A)\).
Consider the set \(B = \{ a \in A \ST a \notin g(a) \}\).
Since \(B \subseteq A\), hence \(B \in \Power(A)\).
Since \(g\) is bijective, there exists \(a \in A\) such that \(g(a) = B\).
Now if \(a \in B\) then \(a \notin g(a) = B\).
And if \(a \notin B\), then \(a \in g(a) = B\).
This is impossible, hence \(A \nsim \Power(A)\).
1.6.5. Cardinal Numbers#
We now introduce a general definition for cardinality.
Definition 1.90 (Cardinal numbers)
For every set \(A\) a symbol (playing the role of a number) can be assigned that designates the number of elements in the set. This number is known as cardinal number of the set and is denoted by \(\card{A}\) or \(| A |\). It is also known as cardinality.
Note that the cardinal numbers are different from natural numbers, real numbers etc.
If \(A\) is finite, with \(A = \{a_1, a_2, \dots, a_n \}\), then \(\card{A} = n\).
We use the symbol \(\aleph_0\) to denote the cardinality of \(\Nat\).
By saying \(A\) has the cardinality of \(\aleph_0\), we simply mean that \(A \sim \Nat\).
If \(a\) and \(b\) are two cardinal numbers, then by \(a \leq b\), we mean that there exist two sets \(A\) and \(B\) such that \(\card{A} = a\), \(\card{B} = b\) and \(A \preceq B\).
By \(a < b\), we mean that \(A \preceq B\) and \(A \nsim B\).
\(a \leq b\) and \(b \leq a\) guarantees that \(a = b\).
Theorem 1.33 (Real numbers as power set of natural numbers)
\(\Power(\Nat) \sim \RR\).
Proof. We shall proceed as follows:
Establish a (total) injective mapping \(\RR \to \Power(\Nat)\).
Establish a (total) injective mapping \(\Power(\Nat) \to \RR\).
Claim that a bijective mapping between the two exists due to Schröder-Bernstein theorem.
\(\RR \to \Power(\Nat)\)
Define \(g : \RR \to \Power(\QQ)\) as
\[ g(r) = \{q \in \QQ \ST q < r \}. \]Note that \(g\) is injective. If \(r_1 < r_2\) then there is a rational number \(q\) such that \(r_1 < q < r_2\). Thus, \(g(r_1) \neq g(r_2)\).
Since, \(\QQ \sim \Nat\), hence there exists a bijection between \(\Power(\QQ)\) and \(\Power(\Nat)\).
Thus, there exists an injection from \(\RR\) to \(\Power(\Nat)\).
\(\Power(\Nat) \to \RR\)
Recall that \(2^{\Nat} \sim \Power(\Nat)\).
Thus, each subset of \(\Nat\) corresponds to a sequence \(x = \{ x_n \}\) in \(2^{\Nat}\).
Define a mapping \(h : 2^{\Nat} \to \RR\) as:
\[ h(x) = \sum_{n=1}^{\infty} \frac{x_n}{3^{n}} \]\(h\) maps each sequence \(x\) to a unique number \(y \in [0,1]\).
\(h\) is an injective mapping.
Definition 1.91 (Infinite cardinal number)
A cardinal number \(a\) satisfying \(\aleph_0 \leq a\) is known as infinite cardinal number.
Definition 1.92 (Cardinality of the continuum)
The cardinality of \(\RR\) denoted by \(\mathfrak{c}\) is known as the cardinality of the continuum.
Theorem 1.34 (Power sets and binary functions)
Let \(2 = \{ 0, 1 \}\). Then \(2^X \sim \Power (X) \) for every set \(X\).
We mention that the notation \(A^B\) means the set of all functions of type \(f : B \to A\).
Proof. \(2^X\) is the set of all functions \(f : X \to 2\). i.e. a function from \(X\) to \(\{ 0, 1 \}\) which can take only one the two values \(0\) and \(1\).
Define a mapping \(g : \Power (X) \to 2^X\) as follows. Let \(y \in \Power(X)\). Then \(g(y)\) is a function \(f : X \to \{ 0, 1 \}\) given by
The function \(g\) is bijective. Thus \(2^X \sim \Power(X)\).
Remark 1.17
We denote the cardinal number of \(\Power(X)\) by \(2^{\card{X}}\). Thus, \(\mathfrak{c} = 2^{\aleph_0}\).
Remark 1.18 (An ordering of cardinal numbers)
The following inequalities of cardinal numbers hold: