Tutorial: Cardinality

Adaptive game version

What is an adaptive game tutorial? ▶

Basics

Intuitively, the cardinality of a set refers to the number of elements in the set.

Cardinality of a finite set
If $A$ is a finite set, then its cardinality is the number of elements in the set:

$n(A) = $ Number of elements in $A$. Alternative notation You will often see the cardinality $n(A)$ of $A$ written as $|A|$. Thus,

$|A| = $ Number of elements in $A$. However, we will stick to the notation $n(A)$ here.

Suggested video on cardinality of finite sets: Video by The Infinite Looper

Examples

1. \t %%Let $P = \{x, y, z, t\}$. \gap[20] \t \\ \t Then $n(P) = 4$. \gap[40] $P$ contains 4 elements. \\ \t \\ 2. \t %%Let $Q = \{x \mid x \text{ is a negative integer greater than } -5 \}$. \gap[20] \\ \t So $Q = \{ -1, -2, -3, -4 \}$, %%and $n(Q) = 4$.

Some for you

Note #[If $A$ is not finite, then we will just say that the $A$ has infinite cardinality. (Actually, some infinite sets are "larger" than others in a very precise sense not discussed here, and sets with infinite cardinality can be assigned particular "infinite cardinal numbers."][Si $A$ no es finito, entonces diremos simplemente que el conjunto $A$ tiene cardinalidad infinita. (En realidad, algunos conjuntos infinitos son "más grandes" que otros en un sentido muy preciso que no se trata aquí, y a los conjuntos con cardinalidad infinita se les puede asignar "números cardinales infinitos" en particular.]#

Suggested video on sets with infinite cardinality: Video by Computer Science Mathematics

Sets are often built from simpler sets using set operations, so we need to find out how to calculate the cardinality of things like unions, intersections and cartesian products.

The cardinality of a union

#[Here we consider the question: How do you calculate $n(A \cup B)$ from a knowledge of $n(A)$ and $n(B)$?][A continuación consideramos la pregunta: ¿Cómo se calcula $n(A \cup B)$ a partir de un conocimiento de $n(A)$ y $n(B)$?]#

%%Q #[That's easy! $A \cup B$ is obtained by combining the elements of $A$ and $B$, so $n(A \cup B)$ should equal $n(A) + n(B)$, right?][¡Eso as fácil! $A \cup B$ se obtiene combinando los elementos de $A$ y $B$, por lo que $n(A \cup B)$ debe ser igual a $n(A) + n(B)$, ¿verdad?]#
%%A #[Not quite! What if $A$ and $B$ have elements in common? Then adding $n(A)$ and $n(B)$ would count those elements twice! For instance, take][¡No exactamente! ¿Qué pasa si $A$ y $B$ tienen elementos en común? Luego, ¡sumar $n(A)$ y $n(B)$ contaría esos elementos dos veces! Por ejemplo, sea]#

#[Then $A \cup B = \{a,b,c,d,e\}$ has only 5 elements, whereas $n(A) = n(B) = 4 + 4 = 8$. The reason the sum gives the wrong answer is that it counts the three elements in $A \cap B = \{b, c, d\}$, twice, so to correct the answer we need to subtract this number:][Entonces $A \cup B = \{a,b,c,d,e\}$ tiene solo 5 elementos, mientras que $n(A) = n(B) = 4 + 4 = 8$. La razón por la que la suma da la respuesta incorrecta es que cuenta los tres elementos en $A \cap B = \{b, c, d\}$, dos veces, por lo que para corregir la respuesta necesitamos restar este número:]#

$n(A \cup B)$ \t ${}= 4 + 4 - 3$ \t #[Add $n(A)$ to $n(B)$ and then subtract $n(A \cap B)$][Sumar $n(A)$ y $n(B)$ y luego restar $n(A \cap B)$]#. \\ \t ${}= n(A) + n(B) - n(A \cap B)$

#[and we have discovered a formula for the cardinailty of the union of two sets!][y ¡hemos descubierto una fórmula para la cardinalidad de la unión de dos conjuntos!]#

Cardinality of a union
If $A$ and $B$ are finite sets, then

Cardinality of a union

Special case: If $A$ and $B$ are disjoint sets (that is, $A \cap B = \emptyset$), then

Cardinality of a disjoint union

#[Note][Nota]# We can rewrite the formula for a union by solving for $n(A \cap B)$:

Cardinality of an intersection

Suggested video on cardinality of a union: Video by MathsSmart

Examples

1. %%Let $A = \{a,b,c,d\}$ and $B = \{b,c,d,e\}$. Then

$n(A \cup B)$ \t ${}= n(A) + n(B) - n(A \cap B)$ \\ \t ${}= 4 + 4 - 3 = 5$.

2. %%Let $A = \{a,b,c,d\}$ and $B = \{e,f,g\}$. Then $A$ and $B$ are disjoint, and

$n(A \cup B)$ \t ${}= n(A) + n(B)$ \\ \t ${}= 4 + 3 = 7$.

3. %%If $n(A) = 6, n(B) = 7,$ %%and $n(A \cup B) = 12$, %%then

$n(A \cap B)$ \t ${}= n(A) + n(B) - n(A \cup B)$ \\ \t ${}= 6 + 7 - 12 = 1$.

#[Visualizing the cardinality of a union][Visualizar la cardinalidad de una unión]#:

#[Not disjoint][No desunidos]#:

$A = \{a,b,c,d\}$ and $B = \{b,c,d,e\}$.

$n(A) = 4; \quad n(A \cap B) = 3; \quad n(B) = 4 $
$n(A \cup B) = 4 + 4 - 3 = 5$

#[Disjoint][Desunidos]#:

$A = \{a,b,c,d\}$ and $B = \{e,f,g\}$.

$n(A) = 4; \quad n(A \cap B) = 0; \quad n(B) = 3$
$n(A \cup B) = 4 + 3 = 7$

Some for you

The cardinality of a complement

#[In the %%prevsectut we saw that the complement $A'$ of the set $A$ is the set of all elements in a designated universal set* $S$ not in $A$.][En el %%prevsectut vimos que el complemento $A'$ del conjunto $A$ es el conjunto de todos los elementos en un designado conjunto universal* $S$ no en $A$.]#
* #[In %%prevsectut we took $S$ to consist of all the elements in the sets under discussion.][En %%prevsectut tomamos $S$ para consistir en todos los elementos en los conjuntos baja consideración.]#

Cardinality of a complement
If $S$ is a finite universal set and $A$ is a subset of $S$, then

$n(A\prime) = n(S) - n(A)$. #[Equivalently][Equivalentemente]#,

$n(A) = n(S) - n(A\prime)$.

Examples

1. %%Let $S = \{a,b,c,d\}$ %%and $A = \{a,b,c\}$. Then

$n(A\prime) = n(S) - n(A) = 4 - 3 = 1$.

#[Visualizing the cardinality of a complement][Visualizar la cardinalidad de un complemento]#:

$S$

$\overbrace{\qquad \qquad \qquad \qquad \qquad \qquad}$

$S = \{a,b,c,d\} \quad A = \{a, b, c\}$
$n(A\prime) = n(S) - n(A) = 4 - 3 = 1$.
$n(A) = n(S) - n(A\prime) = 4 - 1 = 3$.

2. #[In a box of 50 pieces of chocolate, 20 contain Turkish delight ($T$), 12 use use dark chocolate ($D$), and 6 either contain Turkish delight or use dark chocolate. How many neither contain Turkish delight nor use dark chocolate?][En una caja de 50 piezas de chocolate, 20 contienen delicias turcas ($T$), 12 usan chocolate oscuro ($D$) y 6 contienen delicias turcas o usan chocolate oscuro. ¿Cuántos no contienen delicias turcas ni usan chocolate oscuro?]#
#[Answer][Respuesta]# #[The number that neither contain Turkish delight nor use dark chocolate is][El número que no contienen delicias turcas ni usan chocolate oscuro es]#

$n(T \cup D)' = n(S) - n(T \cup D)$.

#[Here][Aquí]#, $n(S) = 50$, #[and][y]# $n(T \cup D) = n(T) + n(D) - n(T \cap D) = 20 - 12 - 6 = 26$. Thus

$n(T \cup D)' = 50 - 26 = 24$.

Some for you

The cardinality of a cartesian product

To find a formula for $n(A \times B)$, consider the following simple example we looked at in the %%prevsectutb %%Let $A = \{a,b\}$ %%and $B = \{1,2,3\}$, Then

$A \times B = \{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\}$. We visualized this product as the following $2 \times 3$ grid:

So we conclude that the number of elements in the product is $n(A) \times n(B) = 2 \times 3 = 6$. In general:

Cardinality of a cartesian product
If $A$ and $B$ are finite sets, then

$n(A \times B) = n(A)n(B)$.

Suggested video on cardinality of cartesian products: Video by Don't Memorise

Examples

%%Let $A = \{a,b\}$ %%and $B = \{1,2,3\}$. Then
$n(A \times B) = n(A)n(B) = 2 \times 3 = 6$.
In the %%prevsectutb we saw that, if an experiment consists of two steps with individual sets of outcomes $A$ for the first step and $B$ for the second, then the set of outcomes for the two-step experiment is $A \times B$. Thus, the number of possible outcomes in such an experiment is $n(A \times B) = n(A)n(B)$. This obsservation is knowns as the multiplication principle which we will learn more about in the %%nextsectut.
In particular (see the %%prevsectutb) if we toss a coin twice in succession, observing which side faces up each time, then the set of possible outcomes is $S = \{$%%H, %%T$\} \times \{$%%H, %%T$\}$. Thus, the number of possible outcomes is

Some for you

Now try some of the exercises in Section 7.2 in Finite Mathematics and Applied Calculus.