Finite Sets and their Cardinalities

The present unit is part of the following walks

Introduction

Please note that the text on this web page gives a summary of the Unit Finite Sets and their Cardinalities. A full text including the proofs is available as a separate pdf-document at the end of this page.

The present unit is the first unit of the walk The Cardinality of Sets.

You will learn the meaning of the following terms:

The main results of this unit are:

Finite Sets and their Cardinalities

We will explain some elementary properties of the cardinality of finite sets:

Definition. (a) The set $A$ is called finite if we have $A = \emptyset$ or if there exists a natural number $n \geq 1$ such that the sets $A$ and $\{1, \ldots, n\}$ are equivalent.

(b) If $A = \emptyset$, then we say that the set $A$ has $0$ elements, and we write $|A| = 0$.

(c) If the sets $A$ and $\{1, \ldots, n\}$ are equivalent for some natural number $n \geq 1$, then we say that the set $A$ has $n$ elements, and we write $|A| = n$.

(d) For a finite set $A$ the value $|A|$ is called the cardinality of the set $A$.

(e) If the set $A$ is finite, then we also write $|A| < \infty$.

(f) If the set $A$ is not finite, then the set $A$ is called infinite. In this case we write $|A| = \infty$.

French / German. Finite set = Ensemble fini = Endliche Menge. Cardinality = Cardinalité = Mächtigkeit. Infinite Set = Ensemble infini = Unendliche Menge.

Theorem. Let $A$ be a set, let $b$ be an element not contained in the set $A$, and let $B := A \mathbin{\dot{\cup}} \{b\}$.

Then the set $A$ is finite if and only if the set $B$ is finite. In this case, we have

$$
|B| = |A| + 1.
$$

Theorem. Let $B$ be a finite set, and let $A$ be a subset of the set $B$.

(a) The set $A$ is finite, and we have $|A| \leq |B|$.

(b) We have

$$
|A| = |B| \mbox{ if and only if } A = B.
$$

Theorem. Let $A$ and $B$ be two finite sets. If the set $A$ is a proper subset of the set $B$, then we have $|A| < |B|$. In particular, the sets $A$ and $B$ are not equivalent.

Theorem. Let $A$ be a finite set with $|A| = n$ for a natural number $n$, and let $m$ be a further natural number with $m \leq n$.

Then there exists a subset $B$ of the set $A$ such that $|B| = m$.

Theorem. Let $A = (A, \leq)$ be a non-empty finite (partially) ordered set. Then the set $A$ has a maximal and a minimal element.

Theorem. Let $A$ be a set. Then the following conditions are equivalent:

(i) The set $A$ is infinite, that is, $|A| = \infty$.

(ii) For each natural number $n$ there exists a finite subset $A_n$ of the set $A$ such that $|A_n| = n$.

(iii) For each natural number $n$ there exists a finite subset $A_n$ of the set $A$ such that $|A_n| \geq n$.

Theorem. The set $\mathbb{N}_0$ of the natural numbers is infinite.

Sums, Products, Powers and Finite Sets

We will compute the cardinality of the sets $A \cap B$, $A \cup B$, $A \setminus B$, $A \times B$, ${\cal F}(A, B)$ (set of the functions from a set $A$ into a set $B$) and ${\cal B}(A)$ (set of the bijective functions from a set $A$ onto itself). It will turn out that these cardinalities are strongly related to the sums, products and powers of natural numbers.

Theorem. Let $A$ and $B$ be two finite sets.

If the sets $A$ and $B$ are disjoint, then the set $A \mathbin{\dot{\cup}} B$ is finite, and we have

$$
|A \mathbin{\dot{\cup}} B| = |A| + |B|.
$$

Theorem. Let $B$ be a finite set, and let $A$ be a subset of the set $B$.

Then the sets $A$ and $B \setminus A$ are finite, and we have

$$
|B| = |A| + |B \setminus A|.
$$

Theorem. Let $A$ and $B$ be two finite sets.

Then the union $A \cup B$ is finite, and we have

$$
|A| + |B| = |A \cup B| + |A \cap B|.
$$

Definition. Let $A$ be a finite set of natural numbers such that $|A| = n$ for a natural number $n$.

(a) If $A = \emptyset$, that is, if $n = 0$, then we set

$$
\sum_{x \in A} x := 0.
$$

(b) Suppose that $n \geq 1$, let $\alpha : \{1, \ldots, n\} \rightarrow A$ be a bijective mapping from the set $\{1, \ldots, n\}$ onto the set $A$, and let

$$
a_i := \alpha(i) \mbox{ for all } i =1, \ldots, n.
$$

Then we set

$$
\sum_{x \in A} x := \sum_{i=1}^n \alpha(i) = \sum_{i=1}^n a_i.
$$

Theorem. (a) Let $A$ and $B$ be two finite sets.

Then the set $A \times B$ is finite, and we have

$$
| A \times B | = |A| \cdot |B|.
$$

(b) Let $A_1, \ldots, A_n$ be $n$ finite sets. Then we have

$$
\Big| \prod_{i=1}^n A_i \Big| = \prod_{i=1}^n |A_i|.
$$

Theorem. Let $A$ and $B$ be two finite sets with $|A| = m$ and $|B| = n$ for two natural numbers $m$ and $n$. Then the set

$$
{\cal F}(B, A) := \big\{ \alpha : B \rightarrow A \mid \alpha \mbox{ function} \big\}
$$

is finite, and we have

$$
| {\cal F}(B, A) | = m^n.
$$

Theorem. Let $A$ be a finite set with $n$ elements for a natural number $n$, and let ${\cal B}(A)$ be the set of the bijective functions from the set $A$ onto itself. Then we have

$$
|{\cal B}(A)| = n!.
$$

Injective and Surjective Mappings between Finite Sets

We will explain some important properties of functions between finite set:

Theorem. Let $A$ and $B$ be two finite sets, and let $\alpha : A \rightarrow B$ be a mapping from the set $A$ into the set $B$.

(a) Suppose that the mapping $\alpha : A \rightarrow B$ is injective. Then we have

$$
|A| \leq |B| \mbox{ and } |A| = |B| \mbox{ if and only if } \alpha : A \rightarrow B \mbox{ is bijective}.
$$

(b) Suppose that the mapping $\alpha : A \rightarrow B$ is surjective. Then we have

$$
|A| \geq |B| \mbox{ and } |A| = |B| \mbox{ if and only if } \alpha : A \rightarrow B \mbox{ is bijective}.
$$

Theorem. Let $A$ and $B$ be two finite sets, and let $\alpha : A \rightarrow B$ be a mapping from the set $A$ into the set $B$. If $|A| = |B|$, then the following conditions are equivalent:

(i) The mapping $\alpha : A \rightarrow B$ is injective.

(ii) The mapping $\alpha : A \rightarrow B$ is surjective.

(iii) The mapping $\alpha : A \rightarrow B$ is bijective.

Theorem. (Pigeonhole Principle) Let $f : A \rightarrow B$ be a function from a finite set $A$ into a finite set $B$. If $|B| < |A|$, then the function $f : A \rightarrow B$ is not injective, that is, there exist two elements $x$ and $y$ of the set $A$ such that $f(x) = f(y)$.

French / German. Pigeonhole Principle = Principe des Tiroirs = Schubfachprinzip.

Notes and References

A list of textbooks about set theory is contained in Unit [Literature about Set Theory].

Do you want to learn more? The next step is the definition of the so-called well-ordered sets. They are an important tool for the definition of infinite cardinal numbers. Well-ordered set will be explained in Unit [Well-ordered Sets – in preparation].

Download

Finite Sets and their Cardinalities

math_garden_card_finite_setsDownload

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021