Finite and Infinite Sets

Before we look deeper into various combinatorics topics - we will need to establish a basic foundation on what a set is and some operations that are commonly used with sets. We loosely define a set below.

 Definition: A Set $A$ is a collection of elements. If there are a finite number of elements $m$ in $A$ then $A$ is said to be a Finite Set and the Size of $A$ is denoted as $\lvert A \rvert = m$. If there are an infinite number of elements in $A$ then $A$ is said to be an Infinite Set.

It is common to use an uppercase letter to denote a set.

For small finite sets, we can often describe the set by writing the elements within curly braces separated by commas. For example, the set $A$ of integers between $1$ and $5$ inclusive can be written as:

(1)
\begin{align} A = \{ 1, 2, 3, 4, 5 \} \end{align}

So clearly, the numbers $1$, $2$, $3$, $4$, and $5$ are in $A$.

 Definition: The element $x$ is said to be Contained in the set $A$ or is a Member of $A$ written $x \in A$ if $x$ is in $A$. If $x$ is not in the set $A$ then we write $x \not \in A$.

In the example above, we see that $2$ is in $A$ and so we can write $2 \in A$. However, the number $6$ is not an integer between $1$ and $5$ inclusive and so $6 \not \in A$.

For large finite sets and infinite sets, we cannot reasonably write every element down. Instead, we use the more appropriate set-builder notation which describes what elements are contained in the set. For example, consider a set $B$ which contains all integers between $1$ and $1000$ inclusive. It is unreasonable to write down all $1000$ elements of this set. Instead, we can compact that notation to simply writing:

(2)
\begin{align} B = \{ x : x \: \mathrm{is \: an \: integer \: and } \: 1 \leq x \leq 1000 \} \end{align}

The notation above should be read as "$B$ is the set of elements $x$ such that $x$ is an integer and $1$ is less than or equal to $x$ which is less than or equal to $1000$. It is now clear what exactly is in $B = \{ 1, 2, ..., 1000 \}$.

Of course, we should mention a rather trivial set - one which contains no elements.

 Definition: The set that contains no elements is called the Empty Set and is denoted as $\emptyset = \{ \}$.

As we mentioned earlier though, not all sets are finite. In the examples above, sets $A$ and $B$ were finite and it's not hard to see that $\lvert A \rvert = 5$ and $\lvert B \rvert = 1000$. Now let's consider another set $C$ whose elements are real numbers between $0$ and $1$ inclusive. Using set-builder notation, we can write this as:

(3)
\begin{align} C = \{ x : x \: \mathrm{is \: a \: real \: number \: and} \: 0 \leq x \leq 1 \} \end{align}

For nonempty finite sets of real numbers, we will always have a smallest and largest element of the set which we define below:

 Definition: If $A$ is a set of real numbers then the element $x \in A$ is said to be the Minimum of $A$ if $x \leq y$ for all $y \in A$. The element $x \in A$ is said to be the Maximum of $A$ if $y \leq x$ for all $y \in A$.

For the sets $A$ and $B$ in the previous examples, we have that the minimum of $A$ is $1$ and the maximum of $A$ is $5$ while the minimum of $B$ is $1$ and the maximum of $B$ is $1000$.

The definition above brings us to our first result on sets in which every nonempty finite set has a minimum and maximum.

 Lemma 1: If $A$ is a nonempty finite set of real numbers then there exists elements $x, z \in A$ such that $x \leq y \leq z$ for all $y \in A$.
• Proof: Let $A$ be a nonempty finite set. Then there exists a positive integer $m$ such that $\lvert A \rvert = m$, that is, $A$ has $m$ elements. We can write the set $A$ as:
(4)
\begin{align} \quad A = \{x_1, x_2, ..., x_m \} \end{align}
• Let $B = \{ y \in A : y < x \: \mathrm{for \: all \: x \in A}$, i.e., the set of all real numbers in $A$ that are less than every element in $A$. This set $B$ must be empty since $y \in A$ and $y < x_1$, $y < x_2$, …, $y < x_m$ cannot all be true since $y = x_n$ for some $n = 1, 2, ..., m$. Therefore there exists an element, say $x_1 \in A$ such that $x_1 \leq x$ for all $x \in A$ - i.e., the minimum of $A$. An analogous argument can be used to prove that every nonempty finite set $A$ of real numbers contains a maximum too. $\blacksquare$

It is important to note that the converse of the theorem above is not necessarily true - that is if a set has a minimum and/or maximum then it is not necessarily finite.

## Some Examples of Common Sets

We will often use some special notation to denote some common sets which we list below.

Notation Description
$\mathbb{R}$ The set of all real numbers.
$\mathbb{C}$ The set of all complex numbers.
$\mathbb{Q}$ The set of all rational numbers.
$\mathbb{Z}$ The set of all integers.
$\mathbb{N}$ The set of natural numbers $\{ 1, 2, ... \}$ for which we exclude $0$.
$D(f)$ The domain of a function $f$.
$R(f)$ The range of a function $f$.