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)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)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)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:
- 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$. |