Cardinality

Maggie Schildt

16 Cardinality

We have mentioned in a previous section, the concept of infinite sets, and one might think that this means that the size is also infinite but that is where cardinality comes in. Cardinality is what we refer to when trying to define the size of an infinite set. we can also use cardinality to count the size of a finite set as well. When we consider the size of a set we aren’t thinking of big or little, we consider size by the count of how many elements are in the set. The elements are defined by the set, this means they can be natural, rational, integers, or real numbers.

Some might think “why does cardinality of an infinite or finite set matter?” what mathematicians say to this is cardinality allows us to compare sets and define relations between sets. To give a real world example cardinality is extremely important to the data modeling used in businesses, and without knowing how to determine cardinality we would be unable to create data models in the real world and for that matter be able to analyze any data brought in.

Lets now consider the cardinality for finite and infinite sets in greater detail by addressing them individually.

14.1 Finite Sets

We already know that cardinality means the size of a set and if a set is finite then the size of the set is just the number of elements in the set which can, tediously, be counted by hand. We can denote the cardinality of a set by $|P|=|\mathbb{N_{n}}$ for some $n\in \mathbb{N}$ , given set $P$ . For example if $P=\left\lbrace a,b,c\right\rbrace$ then we can say $|P|=3$ . The other option is if a set $P$ is empty then cardinality will be 0 because there are no elements in $P$ . Instead of a formal definition for cardinality we will introduce the properties of a finite set in terms of cardinality [23].

Theorem: Fundamental Properties of Finite Sets

Suppose A and B are finite sets.

Every subset of set $A$ is finite, and has cardinality less than or equal to the cardinality of $A$ .
$A\cup B$ is finite, and the cardinality of $A\cup B$ is equal to the cardinality of $A+B$ minus the cardinality of $A\cap B$ .
$A\times B$ is finite, and the cardinality of $A\times B$ is equal to the cardinality of $A$ multiplied by the cardinality of $B$ .

Now recall when we discussed functions and the concepts of one-to-one and onto. There are times where $f:A\rightarrow B$ with $|A|=m$ and $|B|=n$ the cardinality of the set of $f$ is $|f|=n^{m}$ [25]. Now this works very well for finite sets that are a one-to-one correspondence but from our previous section on functions we know not all functions are one-to-one or onto. With this in mind we introduce the pigeon hole principle [25].

Theorem: The Pigeonhole Principle

Let $A$ and $B$ be finite sets. if $|A|>|B|$ and $f:A\rightarrow B$ , then there exists distinct elements $a_{1},a_{2}\in A$ such that $f(a_{1})=f(a_{2})$ .

This means for two elements in $A$ there is only one element in $B$ . This just goes to show that sets do not need to be equal under a function. We can consider set equality by introducing the definition of equality [30].

Definition. Set Equality

Two sets are equal if, and only if, for all $x\in A$ then $x\in B$ .

Given this definition we can prove that two sets are equal through the use of cardinality. Lets consider the proof below.

Example:

True or False: Let $A$ and $B$ be finite sets with $|A|=|B|$ , if $A\subseteq B$ then $A=B$ .

True, if $|A|=|B|$ then $A$ and $B$ have the same number of elements. Since we are given that $A\subseteq B$ and we know $|A|=|B|$ then $A$ is not a proper subset of $B$ and thus $A=B$ .

Here we can see that we do not need to prove both $A\subseteq B$ and $B\subseteq A$ in order to prove $A=B$ , we can use cardinality instead. Now it’s important to note that this is only for finite sets since an infinite set can be a subset of another with the same cardinality but that does not mean they are equal. We will look at some examples of this in the next section, Infinite Sets.

14.2 Infinite Sets

We have already explored what cardinality is and how we can apply it to finite sets so lets begin the topic of cardinality for infinite sets by first giving the definition [30].

Definition.

Let $A$ and $B$ be infinite sets. We say that $|A|=|B|$ if there exists an onto function $f:A\rightarrow B$ .

Using cardinality we can categorize infinite sets as either countable of uncountable sets. If we think about our number families as sets we have sets such as real numbers $\mathbb{R}$ , rational numbers $\mathbb{Q}$ , integers $\mathbb{Z}$ , natural numbers $\mathbb{N}$ . We define an infinite set $A$ to be countable if $|A|=|\mathbb{N}$ which means that set $A$ has a one-to-one correspondance with set $\mathbb{N}$ , counter to this, if a set $A$ has a cardinality such that $|A|>|\mathbb{N}|$ then we say that $A$ is uncountable. Now when a list can be established for the objects to be counted in a set we say the set is enumerable. We have an established definition for both enumerable finite sets and enumerable infinite sets below [30].

Definition.

A set $A$ is finite if and only if the elements of $A$ can be enumerated in a terminating list as $A=\left\lbrace a_{1}, a_{2}, a_{3},...,x_{n}\right\rbrace$ .

Thus we can say that all finite sets are enumerable [30].

Definition.

A set $A$ is countably infinite if and only if the elements of $A$ can be enumerated in an endless list as $A=\left\lbrace a_{1}, a_{2}, a_{3},...\right\rbrace$ .

Now not every infinitely countable set is enumerable, if a set $A$ has cardinality such that $|A|=|\mathbb{N}$ then $A$ is what we call denumerable. This may seem a bit all over the place with countability and enumerable and denumerable sets. Lets examine some true or false logic statements to get some clarity.

If a set $A$ is denumerable, then $A$ is countable. This is true because a denumerable set must be both countable and infinite [20].
If a set $A$ is not denumerable, then $A$ is uncountable. This is false because $A$ can still be countable even if it is not denumerable. The definition for countable sets states that a set can either be finite or denumerable [20].
If a set $A$ is enumerable, then $A$ is countable. This is true because a countable set must either be enurmerable or denumerable and all enumerable sets must then be countable.

Let’s now consider one example before we continue on.

Example:

Prove that the set $\left\lbrace n:n\in \mathbb{N}\ and\ n>6\right\rbrace$ is denumerable [20].

Proof: Assume that set $P=\left\lbrace n:n\in \mathbb{N}\ and\ n>6\right\rbrace$ then there is a function $f:\mathbb{N}\rightarrow P$ where $f(x)=x+6$ . Let $f(x)=f(y)$ then $x+6=y+6y$ , now if we subtract $-6$ from both sides and we find $x=y$ thus we can say $f$ is one-to-one. Next, let there be $n\in A$ such that for $(n-6)\in \mathbb{N}$ it follows that $f(n-6)=n-6+6=n$ thus we can conclude that $f$ is onto so $f$ is a bijection or one-to-one correspondence which means $f$ is denumerable and $P\approx\mathbb{N}$ .

It took some amazing brain power to be able to establish these ideas for sizing infinite sets, we can credit a lot of what we have seen in this section to Georg Cantor who established the idea of uncountable infinites, began to establish the idea that infinite sets can be different sizes and thus qualify some to be considered countable and others as uncountable [33]. Cantor also coined the “Cantor’s set” seen below.

This illustration shows the breakdown of the infinite set within the interval from 0 to 1. This discovery led to Cantor’s Diagonal Argument over the countable nature of the interval $(0,1)$ . The argument proves that the set of all real numbers on the interval $(0,1)$ is uncountable. We can see the argument supporting Cantor’s conclusion here.

Example:

Prove that the set $(0,1)$ is uncountable [20].

Proof: Let the set $(0,1)=S$ and assume $S$ is countable such that $f:\mathbb{N} \rightarrow S$ has a one-to-one correspondence. We are then able to produce the following sequences.

$\begin{equation*} \begin{split} x_{1}&=0.x_{11}x_{12}x_{13}x_{14}...\\ x_{2}&=0.x_{21}x_{22}x_{23}x_{24}...\\ x_{3}&=0.x_{31}x_{32}x_{33}x_{34}...\\ x_{4}&=0.x_{41}x_{42}x_{43}x_{44}...\\ x_{n}&=0.x_{n1}x_{n2}x_{n3}x_{n4}... \end{split} \end{equation*}$

We can observe that $x_{ni}$ symbolizes a decimal between 0 and 9 that form a real number with a decimal expansion $x = 0.x_{1}x_{2}x_{3}...$ . The digits are determined by the following rule.

$\begin{equation*} x_{i}= \begin{cases} 3 \quad \text{if} \ x_{ii} \ \neq 3\\ 5 \quad \text{if} \ x_{ii} \ = 3 \end{cases} \end{equation*}$

Each expansion is unique and this means that the real number $x$ cannot be equal to any decimal expansion. This is because the expansion of $x$ is not the same as the $i$ th term in the decimal expansion $x_{i}$ for $i\geq 1$ . Therefore there is a real number $x\in S$ that is not included, this contradicts the assumption that $f$ has a one-to-one correspondence. If $f$ had a one to one correspondence then every element in $\mathbb{N}$ would map to an $x\in S$ . Since this is not true then not every element between $0$ and $1$ can be accounted for and thus we must conclude that the set $(0,1)$ is uncountable.

16 Cardinality

License

Share This Book