# Finite Sets and their Cardinalities

- Introduction
- Finite Sets and their Cardinalities
- Sums, Products, Powers and Finite Sets
- Injective and Surjective Mappings between Finite Sets
- Notes and References
- Download

## 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:

- Each finite (partially) ordered set has a maximal and a minimal element (see Theorem [#card-th-finite-maximum]).
- A set $A$ is infinite if and only if for each natural number $n$ there exists a subset $A_n$ of the set $A$ such that $|A_n| \geq n$ (see Theorem [#card-th-char-infinite]).
- The set $\mathbb{N}_0$ of the natural numbers is infinite (see Theorem [#card-th-n0-infinite]).
- We have $|A \cup B| + |A \cap B| = |A| + |B|$ for all finite sets $A$ and $B$ (see Theorem [#card-th-A-B-finite-card-A-cup-B]).
- We have $|A \times B| = |A| \cdot |B|$ for all finite sets $A$ and $B$ (see Theorem [#card-th-product-set]).
- We have $|{\cal F}(B, A)| = m^n$ where ${\cal F}(B, A)$ denotes the set of the functions $\alpha : B \rightarrow A$ from a finite set $B$ into a finite set $A$ with $|A| = m$ and $|B| = n$ (see Theorem [#card-th-exponent-set]).
- We have $|{\cal B}(A)| = n!$ where ${\cal B}(A)$ denotes the set of the bijective functions $\alpha : A \rightarrow A$ from a finite set $A$ onto itself with $|A| = n$ (see Theorem [#card-th-card-bijective-functions]).
- If $A$ and $B$ are two finite sets, then every mapping $\alpha : A \rightarrow B$ is injective if and only if it is bijective if and only if it is surjectie (see Theorem [#card-th-finite-bijective]).
- The so-called
*pigeonhole principle*(see Theorem [#card-th-pigeon]).

## 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

The pdf document is the full text including the proofs.

Current Version: 1.0.0 from January 2021