Cardinality

Abigail Huettig

16 Cardinality

Cardinality deals with the number of elements in a set. Based on the number of elements in a set, we can categorize it as either finite or infinite. If it is infinite, we can further categorize it as countable (denumerable) or uncountable.

Smith et al. tells a story of a shepherd with more sheep than he is able to count. Because the shepherd needs to know whether some sheep are missing or not, he devises a method that enables him to keep track without having to count them. He has a pebble for each sheep. As they come in one by one, he moves pebbles from one container to another one by one. If not all of the pebbles have been transferred over, he knows that he is missing some sheep [23].

In the story, the shepherd used a one-to-one correspondence between the pebbles and the sheep. When working with very large sets, the elements are like the sheep and the natural numbers, the pebbles. In other words, we form a one-to-one correspondence between the natural numbers and the elements of a set to determine the cardinality of a finite set.

Finite Sets

Equivalence
Using the ideas of one-to-one and onto functions, we can determine whether two finite sets are equivalent. This is not the same as equal. When two sets are equal, they have the exact same elements. Let’s look at the definition of equivalent sets from Smith et al. [23].

Definition III.9
Two sets $A$ and $B$ are equivalent if there exists a one-to-one function from $A$ onto $B$ . The sets are also said to be in one-to-one correspondence, and we write $A \approx B$ .

Recall that when we have a one-to-one function that we have a one-to-one correspondence between the elements of the domain and the elements of the range. An onto function is one where the range and codomain are equal sets. Combining these two ideas together, two sets are equivalent if there exists a function $f:A\rightarrow B$ where the elements of the domain have a one-to-one correspondence to the elements of the codomain. When referring to finite sets, the domain must have the same number of elements as the codomain. Let’s look at a problem that I have written and completed for this paper.

Example 34
Show that the sets

$A=\{1, 2, 3, 4, 5, ...\}$

and

$B=\{1, 8, 27, 64, 125, ...\}$

are equivalent.

Proof.
We need to find a function $f:A\rightarrow B$ that is one-to-one and onto $B$ . Just looking at the sets, it seems that we can define a function $f:A\rightarrow B$ as

$f(a)=a^3.$

Now we need to show that $f$ is one-to-one and onto $B$ . Let $f(a)=f(c)$ . It follows that

$\begin{align*} f(a)&=f(c)\\ a^3&=c^3\\ a&=c \end{align*}$

Thus, $f$ is one-to-one. Now, we need to show that $f$ is onto by showing that for every $b$ in $B$ there exists an $a$ in $A$ such that $f(a)=b.$ So, we have that

$\begin{align*} b&=f(a)\\ &=a^3\\ \sqrt[3]{b}&=a\\ \end{align*}$

Since for each element $b\in B$ there exists an element $a\in A$ such that $f(a)=b$ , $f$ is onto. Therefore, the sets $A$ and $B$ are equivalent.

Now that we understand what equivalent sets are, we are ready to discuss the idea of cardinality.

Cardinality
Let’s begin with a couple more definitions from Smith et al. [23].

Definition III.10
For each natural number $k$ , let $\mathbb{N}_k=\{1,2,3,...,k\}.$ A set $S$ is finite if $S=\emptyset$ or $S\approx \mathbb{N}_k$ for some $k\in \mathbb{N}$ .

Definition III.11
Let $S$ be a finite set.

If $S=\emptyset$ , then $S$ has cardinal number 0 (or cardinality 0). We write $\overline{S}=0$ .
If $S\approx \mathbb{N}_k$ for some natural number $k$ , then $S$ has cardinal number $k$ (or cardinality $k$ ), and we write $\overline{S}=k$ .

Simply, the cardinal number of a finite set is the number of elements in the set. Let’s look at another example that I wrote for this paper.

Example 35
Consider the sets

$A=\{1,2,3,4,5\}$

and

$B=\{1,8,27, 64, 125\}.$

Show that $B$ is a finite set and find its cardinality.

Solution
Using the same method that we used in example 34, we know that $A$ and $B$ are equivalent sets because we have a function $f:A\rightarrow B$ defined as

$f(a)= a^3$

that is a one-to-one function onto $B$ .

Notice that $A=\mathbb{N}_5$ which implies that $B\approx \mathbb{N}_5.$ So, by definitions III.10 and III.11, we know that $B$ is a finite set with cardinality 5.

This now brings us to the Pigeonhole Principle, a statement that is so intuitive yet so powerful.

Pigeonhole Principle
The Pigeonhole Principle is stated by Smith et al. as follows [23].

Theorem III.12 (Pigeonhole Principle)

Let $n,r\in \mathbb{N}$ and $f:\mathbb{N}_n\rightarrow \mathbb{N}_r$ . If $n>r$ , then $f$ is not one-to-one.

As this is called the pigeonhole principle, we will use pigeons and pigeonholes to help visualize what this is saying. Let $n$ be the number of pigeons and $r$ be the number of pigeonholes. Let $f:\mathbb{N}_n\rightarrow \mathbb{N}_r$ be the function of placing a pigeon into a pigeonhole. If the number of pigeons is greater than the number of pigeonholes, then at least one pigeonhole will contain more than one pigeon. Thus, there is not a one-to-one correspondence between pigeons and pigeonholes.

Smith et al. also provides the following corollary that comes from this principle [23].

Corollary III.12.1

If $A=n$ , $B=r$ , and $r<n$ , then there is no one-to-one function from $A$ to $B$ .

What this corollary is saying is that if the domain has more elements than the codomain, then it is not possible for a one-to-one mapping from the domain to the codomain to exist. This is because there will be at least two elements in the domain that map to the same element in the codomain, which is not a one-to-one mapping.Let’s now look at an exercise from Smith et al. that I completed for this paper [23].

Example 36
An English market town has a population of 21,307. Assuming that every resident has a first, middle, and last name, show that there are two residents with identical three-letter initials.

Proof.
Because there are 26 letters in the English alphabet, there are $26\times 26\times 26=17,576$ possible combinations for an individual’s initials. Let $A$ be the set of residents and $B$ be the set of possible initials. Because $A=21,307$ , $B=17,576$ , and $17,576<21,307$ , there is no one-to-one mapping from $A$ to $B$ by Corollary III.12.1. That is, there exist two people who are mapped to the same initials. Therefore, there are two residents with identical three-letter initials.

We have seen that the cardinality of a finite set is the number of elements contained in that set, but how does cardinality apply to infinite sets? That is what we are about to find out.

Infinite Sets

Denumerable Sets
An infinite set is simply a set that is not finite. Each infinite set is either denumerable or uncountable. Smith et al. provides the following definition for a denumerable set [23].

Definition III.13
The set $S$ is denumerable if $S\approx \mathbb{N}$ . For a denumerable set $S$ , we say $S$ has cardinal number $\aleph_0$ (or cardinality $\aleph_0$ ) and write $\overline{S}=\aleph_0.$

What this is saying is that an infinite set $S$ is denumerable if there is a one-to-one correspondence between the elements of $S$ and the natural numbers.

For example, the set of positive rational numbers is an infinite set that is denumerable, though intuitively it may seem otherwise. Georg Cantor devised a clever way for showing that the positive rational numbers have a one-to-one correspondence with the natural numbers and thus proved that the positive rational numbers are denumerable.

Proof.
We will use the following image taken from Smith et al. to explain the method Cantor used.

Start by writing the positive rational numbers in a matrix as shown above. The first row contains all positive rationals with a denominator of one, the second row contains all those with a denominator of two, and so on. The first column contains all positive rationals with a numerator of one, the second column contains all those with a numerator of two, and so on.

Then, draw diagonals in the manner that is shown above and create the one-to-one mapping below by following the diagonals and leaving out any duplicates (such as $\frac{2}{2}$ and $\frac{3}{3}$ since they are equal to $\frac{1}{1}$ ). This image is also taken from Smith et al.

As there is a one-to-one correspondence between the natural numbers and positive rational numbers, the positive rationals are denumerable.

Building off of the idea of denumerable sets, we have countable and uncountable sets. A countable set is not necessarily infinite, but a denumerable set is always countable, as we will see.

Countable and Uncountable Sets
The formal definitions of countable and uncountable sets are given by Smith et al. as follows [23].

Definition III.14
A set $S$ is countable if $S$ is finite or denumerable. We say $S$ is uncountable if $S$ is not countable.

We have seen that the positive rational numbers are denumerable and consequently, countable. But what about the interval of real numbers (0,1)? It may be surprising to know that this interval is uncountable, which was also proved by Cantor. The key to the proof is in showing that there is not a one-to-one correspondence between the natural numbers and this set of real numbers. It then follows that this infinite set is not denumerable and thus, uncountable. So, let’s look at how Cantor proved that $(0,1)$ is not denumerable [19].

Proof.
Let $f$ be a function such that $f:\mathbb{N}\rightarrow (0,1)$ . Let $n$ be a natural number and consider the following table.

The first row is the decimal expansion of $f(1)=\frac{1}{\sqrt{2}}$ . The second row is the decimal expansion of $f(2)=\frac{1}{\sqrt{3}}$ , and the third is $f(3)=\frac{1}{\sqrt{5}}$ . The fourth is $f(4)=\frac{1}{\sqrt{7}}$ , and the fifth is $f(5)=\frac{1}{\sqrt{11}}$ . The table continues on and on where the $nth$ row is the decimal expansion of $f(n)=y$ , where $y\in (0,1).$

What we want to determine is if $f$ is onto. That is, can every possible real number between 0 and 1 be placed in the table? Well, consider the same table where the digits along one of the diagonals are in bold.

Let’s add one to each of those bolded numbers and get a new decimal number, 0.88802…. Could this number be in the table somewhere? Well, this number cannot be equal to $f(1)$ because its first digit is one added to the first digit of $f(1)$ . Similarly, this number cannot be equal to $f(2)$ because its second digit is one added to the second digit of $f(2)$ . This continues on so that this number cannot equal $f(n)$ because its $nth$ digit is one added to the $nth$ digit of $f(n).$ So, there does not exist an $x$ in the domain of $f$ such that $f(x)=0.88802...$ .

This is not the only number that cannot be in the table. Any number we create by changing the digits along a diagonal will result in a number that cannot be in the table by similar reasoning. Thus, $f$ is not onto which implies that the set of all real numbers in the open interval (0,1) is not equivalent to the set of natural numbers. By Definition III.13, (0,1) is not denumerable. Since (0,1) is neither finite nor denumerable, it is uncountable by Definition III.14.

16 Cardinality

Finite Sets

Infinite Sets

License

Share This Book