Set theory is concerned with elements, certain collections of elements called sets and a concept of membership. For each element \(x\) and each set \(X\text{,}\) exactly one of the following two statements holds:

1. \(x\) is a member of \(X\text{.}\)

2. \(x\) is not a member of \(X\text{.}\)

It is important to note that membership cannot be ambiguous.

When \(x\) is an element and \(X\) is a set, we write \(x\in X\) when \(x\) is a member of \(X\text{.}\) Also, the statement \(x\) belongs to \(X\) means exactly the same thing as \(x\) is a member of \(X\text{.}\) Similarly, when \(x\) is not a member of \(X\text{,}\) we write \(x\notin X\) and say \(x\) does not belong to \(X\text{.}\)

Certain sets will be defined explicitly by listing the elements. For example, let \(X=\{a,b,d,g,m\}\text{.}\) Then \(b\in X\) and \(h\notin X\text{.}\) The order of elements in such a listing is irrelevant, so we could also write \(X=\{g,d,b,m,a\}\text{.}\) In other situations, sets will be defined by giving a rule for membership. As examples, let \(\posints\) denote the set of positive integers. Then let \(X=\{n\in\posints:5\le n\le 9\}\text{.}\) Note that \(6,8\in X\) while \(4,10,238\notin X\text{.}\)

Given an element \(x\) and a set \(X\text{,}\) it may at times be tedious and perhaps very difficult to determine which of the statements \(x\in X\) and \(x\notin X\) holds. But if we are discussing sets, it must be the case that exactly one is true.

When \(X\) and \(Y\) are sets, the cartesian product of \(X\) and \(Y\text{,}\) denoted \(X\times Y\), is defined by \begin{equation*} X\times Y=\{(x,y): x\in X \text{ and } y\in Y\} \end{equation*} For example, if \(X=\{a,b\}\) and \(Y=[3]\text{,}\) then \begin{equation*} X\times Y=\{(a,1),(b,1),(a,2),(b,2),(a,3),(b,3)\}. \end{equation*} Elements of \(X\times Y\) are called ordered pairs. When \(p=(x,y)\) is an ordered pair, the element \(x\) is referred to as the first coordinate of \(p\) while \(y\) is the second coordinate of \(p\text{.}\) Note that if either \(X\) or \(Y\) is the empty set, then \(X\times Y=\emptyset\text{.}\)

Cartesian products can be defined for more than two factors. When \(n\ge 2\) is a positive integer and \(X_1,X_2,\dots,X_n\) are non-empty sets, their cartesian product is defined by \begin{equation*} X_1\times X_2\times\dots\times X_n=\{(x_1,x_2,\dots,x_n): x_i\in X_i \text{ for } i = 1,2,\dots,n\} \end{equation*}

A subset \(R\subseteq X\times Y\) is called a binary relation on \(X\times Y\text{,}\) and a binary relation \(R\) on \(X\times Y\) is called a function from \(X\) to \(Y\) when for every \(x\in X\text{,}\) there is exactly one element \(y\in Y\) for which \((x,y)\in R\text{.}\)

Many authors prefer to write the condition for being a function in two parts:

1. For every \(x\in X\text{,}\) there is some element \(y\in Y\) for which \((x,y)\in R\text{.}\)

2. For every \(x\in X\text{,}\) there is at most one element \(y\in Y\) for which \((x,y)\in R\text{.}\)

The second condition is often stated in the following alternative form: If \(x\in X\text{,}\) \(y_1,y_2\in Y\) and \((x,y_1),(x,y_2)\in R\text{,}\) then \(y_1=y_2\text{.}\)

In many settings (like calculus), it is customary to use letters like \(f\text{,}\) \(g\) and \(h\) to denote functions. So let \(f\) be a function from a set \(X\) to a set \(Y\text{.}\) In view of the defining properties of functions, for each \(x\in X\text{,}\) there is a unique element \(y\in Y\) with \((x,y)\in f\text{.}\) And in this case, the convention is to write \(y=f(x)\text{.}\) For example, if \(f=R_1\) is the function in Example B.4, then \(2=f(4)\) and \(f(3) =1\text{.}\)

The shorthand notation \(f:X\rightarrow Y\) is used to indicate that \(f\) is a function from the set \(X\) to the set \(Y\text{.}\)

In calculus, we study functions defined by algebraic rules. For example, consider the function \(f\) whose rule is \(f(x) = 5x^3-8x+7\text{.}\) This short hand notation means that \(X=Y=\reals\) and that \begin{equation*} f=\{(x,5x^3-8x+7):x\in\reals\} \end{equation*} In combinatorics, we sometimes study functions defined algebraically, just like in calculus, but we will frequently describe functions by other kinds of rules. For example, let \(f:\posints\rightarrow\posints\) be defined by \(f(n) = |n/2|\) if \(n\) is even and \(f(n)=3|n|+1\) when \(n\) is odd.

A function \(f:X\rightarrow Y\) is called an injection from \(X\) to \(Y\) when for every \(y\in Y\text{,}\) there is at most one element \(x\in X\) with \(y=f(x)\text{.}\)

When the meaning of \(X\) and \(Y\) is clear, we just say \(f\) is an injection. An injection is also called a \(1\)–\(1\) function (read this as “one to one”) and this is sometimes denoted as \(f:X\injection Y\text{.}\)

A function \(f:X\rightarrow Y\) is called a surjection from \(X\) to \(Y\) when for every \(y\in Y\text{,}\) there is at least one \(x\in X\) with \(y=f(x)\text{.}\)

Again, when the meaning of \(X\) and \(Y\) is clear, we just say \(f\) is a surjection. A surjection is also called an onto function and this is sometimes denoted as \(f:X\surjection Y\text{.}\)

A function \(f\) from \(X\) to \(Y\) which is both an injection and a surjection is called a bijection. Alternatively, a bijection is referred to as a \(1\)–\(1\text{,}\) onto function, and this is sometimes denoted as \(f:X \bijection Y\). A bijection is also called a \(1\)–\(1\)-correspondence.

A set \(X\) is said to be finite when either (1) \(X=\emptyset\text{;}\) or (2) there exists positive integer \(n\) and a bijection \(f:[n]\bijection X\text{.}\) When \(X\) is not finite, it is called infinite. For example, \(\{a,\emptyset,(3,2),\posints\}\) is a finite set as is \(\posints\times\emptyset\text{.}\) On the other hand, \(\posints\times \{\emptyset\}\) is infinite. Of course, \([n]\) and \(\bfn\) are finite sets for every \(n\in\posints\text{.}\)

In some cases, it may take some effort to determine whether a set is finite or infinite. Here is a truly classic result.

Here's a famous example of a set where no one knows if the set is finite or not.

This conjecture is known as the Twin Primes Conjecture. Guaranteed \(\text{A} ++\) for any student who can settle it!

When \(X\) is a finite non-empty set, the cardinality of \(X\text{,}\) denoted \(|X|\) is the unique positive integer \(n\) for which there is a bijection \(f:[n]\bijection X\text{.}\) Intuitively, \(|X|\) is the number of elements in \(X\text{.}\) For example, \begin{equation*} |\{(6,2), (8,(4,\emptyset)), \{3,\{5\}\}\}|=3. \end{equation*} By convention, the cardinality of the empty set is taken to be zero, and we write \(|\emptyset|=0\text{.}\)

We note that the statement in Proposition B.11 is an example of “operator overloading”, a technique featured in several programming languages. Specifically, the times sign \(\times\) is used twice but has different meanings. As part of \(X\times Y\text{,}\) it denotes the cartesian product, while as part of \(|X|\times |Y|\text{,}\) it means ordinary multiplication of positive integers. Programming languages can keep track of the data types of variables and apply the correct interpretation of an operator like \(\times\) depending on the variables to which it is applied.

We also have the following general form of Proposition B.11: \begin{equation*} |X_1\times X_2\times\dots\times X_n|= |X_1|\times |X_2|\times\dots\times |X_n| \end{equation*}

In set theory, it is common to deal with statements involving one or more elements from the universe as variables. Here are some examples:

1. For \(n\in\posints\text{,}\) \(n^2-6n+8=0\text{.}\)

2. For \(A\subseteq[100]\text{,}\) \(\{2,8,25,58,99\}\subseteq A\text{.}\)

3. For \(n\in \ints\text{,}\) \(|n|\) is even.

4. For \(x\in \reals\text{,}\) \(1+1=2\text{.}\)

5. For \(m,n\in \posints\text{,}\) \(m(m+1)+2n\) is even.

6. For \(n\in \posints\text{,}\) \(2n+1\) is even.

7. For \(n\in \posints\) and \(x\in\reals\text{,}\) \(n+x\) is irrational.

These statements may be true for some values of the variables and false for others. The fourth and fifth statements are true for all values of the variables, while the sixth is false for all values.

Implications are frequently abbreviated using with a double arrow \(\Longrightarrow\text{;}\) the quantifier \(\forall\) means “for all” (or “for every”); and the quantifier \(\exists\) means “there exists” (or “there is”). Some writers use \(\wedge\) and \(\vee\) for logical “and” and “or”, respectively. For example, \begin{equation*} \forall A,B\subseteq[4]\quad \bigl((1,2\in A) \wedge |B|\ge 3)\bigr) \Longrightarrow\bigl((A\subseteq B)\vee (\exists n\in A\cup B, n^2=16)\bigr) \end{equation*} The double arrow \(\iff\) is used to denote logical equivalence of statements (also “if and only if”). For example \begin{equation*} \forall A\subseteq[7]\quad A\cap\{1,3,6\}\neq\emptyset\iff A\nsubseteq\{2,4,5,7\} \end{equation*} We will use these notational shortcuts except for the use of \(\wedge\) and \(\vee\text{,}\) as we will use these two symbols in another context: binary operators in lattices.

We define a binary operation \(\times\text{,}\) called multiplication, on the set of natural numbers. When \(m\) and \(n\) are natural numbers, \(m\times n\) is also called the product of \(m\) and \(n\text{,}\) and it sometimes denoted \(m*n\) and even more compactly as \(mn\text{.}\) We will use this last convention in the material to follow. Let \(n\in \nonnegints\text{.}\) We define

1. \(n0=0\text{,}\) and
2. \(n(k+1)=nk +n\text{.}\)

Note that \(10=0\) and \(01=00+0=0\text{.}\) Also, note that \(11=10+1=0+1=1\text{.}\) More generally, from (ii) and Lemma B.19, we conclude that if \(m,n\neq0\text{,}\) then \(mn\neq0\text{.}\)

The commutative law requires some preliminary work.

We now define a binary operation called exponentiation which is defined only on those ordered pairs \((m,n)\) of natural numbers where not both are zero. The notation for exponentiation is non-standard. In books, it is written \(m^n\) while the notations \(m**n\text{,}\) \(m\wedge n\) and \(\exp(m,n)\) are used in-line. We will use the \(m^n\) notation for the most part.

When \(m=0\text{,}\) we set \(0^n=0\) for all \(n\in\nonnegints\) with \(n\neq0\text{.}\) Now let \(m\neq0\text{.}\) We define \(m^n\) by (i) \(m^0=1\) and (ii) \(m^{k+1}=mm^k\text{.}\)

A binary relation \(R\) on a set \(X\) is just a subset of the cartesian product \(X\times X\text{.}\) In discussions of binary relations, the notation \((x,y)\in R\) is sometimes written as \(xRy\text{.}\)

A binary relation \(R\) is:

1. reflexive if \((x,x)\in R\) for all \(x\in X\text{.}\)
2. antisymmetric if \(x=y\) whenever \((x,y)\in R\) and \((y,x)\in R\text{,}\) for all \(x,y\in X\text{.}\)
3. transitive if \((x,y)\in R\) and \((y,z)\in R\) imply \((x,z)\in R\text{,}\) for all \(x,y,z\in X\text{.}\)

A binary relation \(R\) on a set \(X\) is called a partial order on \(X\) when it is reflexive, antisymmetric, and transitive. Traditionally, symbols like \(\le\) and \(\subseteq\) are used to denote partial orders. As an example, recall that if \(X\) is a family of sets, we write \(A\subseteq B\) when \(A\) is a subset of \(B\text{.}\)

When using the ordered pair notation for binary relations, to indicate that a pair \((x,y)\) is not in the relation, we simply write \((x,y)\notin R\text{.}\) When using the alternate notation, this is usually denoted by using the negation symbol from logic and writing \(\lnot (xRy)\text{.}\) Most of the special symbols used to denote partial orders come with negative versions, e.g., \(x\not\le y\text{,}\) \(x\nsubseteq y\text{.}\)

A partial order is called a total order on \(X\) when for all \(x,y\in X\text{,}\) \((x,y)\in R\) or \((y,x)\in R\text{.}\) For example, if \begin{equation*} X=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} \end{equation*} then \(\subseteq\) is a total order on \(X\text{.}\)

When \(\le\) is a partial order on a set \(X\text{,}\) we write \(x\lt y\) when \(x\le y\) and \(x\neq y\text{.}\)

Let \(m,n\in \nonnegints\text{.}\) Define a binary relation \(\le\) on \(\nonnegints\) by setting \(m\le n\) if and only if there exists a natural number \(p\) so that \(m+p=n\text{.}\)

Note that if \(m,n\in\nonnegints\text{,}\) then \(m\lt n\) if and only if there exists a natural number \(p\neq 0\) so that \(m+p=n\text{.}\)

A binary relation \(R\) is symmetric if \((x,y)\in R\) implies \((y,x)\in R\) for all \(x,y\in X\text{.}\)

A binary relation \(R\) on a set \(X\) is called an equivalence relation when it is reflexive, symmetric, and transitive. Typically, symbols like, \(=\text{,}\) \(\cong\text{,}\) \(\equiv\) and \(\sim\) are used to denote equivalence relations. An equivalence relation, say \(\cong\text{,}\) defines a partition on the set \(X\) by setting \begin{equation*} \langle x\rangle =\{y\in X: x\cong y\}. \end{equation*} Note that if \(x,y\in X\) and \(\langle x\rangle\cap\langle y\rangle \neq\emptyset\text{,}\) then \(\langle x\rangle=\langle y\rangle\text{.}\) The sets in this partition are called equivalence classes.

When using the ordered pair notation for binary relations, to indicate that a pair \((x,y)\) is not in the relation, we simply write \((x,y)\notin R\text{.}\) When using the alternate notation, this is usually denoted by using the negation symbol from logic and writing \(\lnot (xRy)\text{.}\) Many of the special symbols used to denote equivalence relations come with negative versions: \(x\neq y\text{,}\) \(x\ncong y\text{,}\) \(x\nsim y\text{,}\) etc.

Define a binary relation \(\cong\) on the set \(Z=\nonnegints \times\nonnegints\) by \begin{equation*} (a,b)\cong (c,d)\quad\textit{iff}\quad a+d=b+c. \end{equation*}

Now that we know that \(\cong\) is an equivalence relation on \(Z\text{,}\) we know that \(\cong\) partitions \(Z\) into equivalence classes. For an element \((a,b)\in Z\text{,}\) we denote the equivalence class of \((a,b)\) by \(\langle (a,b)\rangle\text{.}\)

Let \(\ints\) denote the set of all equivalence classes of \(Z\) determined by the equivalence relation \(\cong\text{.}\) The elements of \(\ints\) are called integers.

For the remainder of this chapter, most statements will be given without proof. Students are encouraged to fill in the details.

We define a binary operation \(+\) on \(\ints\) by the following rule: \begin{equation*} \langle(a,b)\rangle+\langle(c,d)\rangle = \langle(a+c,b+d)\rangle. \end{equation*} Note that the definition of addition is made in terms of representatives of the class, so we must pause to make sure that \(+\) is well defined, i.e., independent of the particular representatives.

In what follows, we use a single symbol, like \(x\text{,}\) \(y\) or \(z\) to denote an integer, but remember that each integer is in fact an entire equivalence class whose elements are ordered pairs of natural numbers.

Next, we define a second binary operation called multiplication, and denoted \(x\times y\text{,}\) \(x*y\) or just \(xy\text{.}\) When \(x=\langle(a,b)\rangle\) and \(y=\langle(c,d)\rangle\text{,}\) we define: \begin{equation*} xy =\langle(a,b)\rangle\langle(c,d)\rangle= \langle(ac+bd, ad+bc)\rangle. \end{equation*}

The integer \(\langle(0,0)\rangle\) has a number of special properties. Note that for all \(x\in\ints\text{,}\) \(x+\langle(0,0)\rangle= x\) and \(x\langle(0,0)\rangle=\langle(0,0)\rangle\text{.}\) So most folks call \(\langle(0,0)\rangle\) zero and denote it by \(0\text{.}\) This is a terrible abuse of notation, since we have already used the word zero and the symbol \(0\) to denote a particular natural number.

But mathematicians, computer scientists and even real people do this all the time. We use the same word and even the same phrase in many different settings expecting that the listener will make the correct interpretation. For example, how many different meanings do you know for You're so bad?

If \(x=\langle(a,b)\rangle\) is an integer and \(y= \langle(b,a)\rangle\text{,}\) then \(x+y=\langle(a+b,a+b)\rangle=0\text{.}\) The integer \(y\) is then called the additive inverse of \(x\) and is denoted \(-x\text{.}\) The additive inverse of \(x\) is also called minus \(x\). The basic property is that \(x + (-x) = 0\text{,}\) for every \(x\in \ints\text{.}\)

We can now define a new binary operation, called subtraction and denoted \(-\text{,}\) on \(\ints\) by setting \(x-y= x+(-y)\text{.}\) In general, subtraction is neither commutative nor associative. However, we do have the following basic properties.

Next, we define a total order on \(\ints\) by setting \(x\le y\) in \(\ints\) when \(x=\langle(a,b)\rangle\text{,}\) \(y=\langle(c,d) \rangle\) and \(a+d \le b+c\) in \(\nonnegints\text{.}\)

For multiplication, the situation is more complicated.

Now consider the function \(f:\nonnegints\longrightarrow \ints\) defined by \(f(n) = \langle(n,0)\rangle\text{.}\) It is easy to show that \(f\) is an injection. Furthermore, it respects addition and multiplication, i.e., \(f(n+m)=f(n)+f(m)\) and \(f(nm)=f(n)f(m)\text{.}\) Also, note that if \(x\in \ints\text{,}\) then \(x>0\) if and only if \(x=f(n)\) for some \(n\in \nonnegints\text{.}\) So, it is customary to abuse notation slightly and say that \(\nonnegints\) is a “subset” of \(\ints\text{.}\) Similarly, we can either consider the set \(\posints\) of positive integers as the set of natural numbers that are successors, or as the set of integers that are greater than \(0\text{.}\)

When \(n\) is a positive integer and \(0\) is the zero in \(\ints\text{,}\) we define \(0^n=0\text{.}\) When \(x\in\ints\text{,}\) \(x\neq 0\) and \(n\in\nonnegints\text{,}\) we define \(x^n\) inductively by (i) \(x^0=1\) and \(x^{k+1}=xx^k\text{.}\)

A full discussion of this would take us far away from a discrete math class, but let's at least provide the basic definitions. A subset \(S\subset \rats\) of the rationals is called a cut (also, a Dedekind cut), if it satisfies the following properties:

1. \(\emptyset\neq S\neq \rats\text{,}\) i.e, \(S\) is a proper non-empty subset of \(\rats\text{.}\)

2. \(x\in S\) and \(y\lt x\) in \(\rats\) implies \(y\in S\text{,}\) for all \(x,y\in \rats\text{.}\)

3. For every \(x\in S\text{,}\) there exists \(y\in S\) with \(x\lt y\text{,}\) i.e., \(S\) has no greatest element.

Cuts are also called real numbers, so a real number is a particular kind of set of rational numbers. For every rational number \(q\text{,}\) the set \(\bar{q}= \{p\in \rats: p\lt q\}\) is a cut. Such cuts are called rational cuts. Inside the reals, the rational cuts behave just like the rational numbers and via the map \(h(q)=\bar{q}\text{,}\) we abuse notation again (we are getting used to this) and say that the rational numbers are a subset of the real numbers.

But there are cuts which are not rational. Here is one: \(\{p\in \rats: p\le 0\}\cup \{p\in \rats: p^2\lt 2\}\text{.}\) The fact that this cut is not rational depends on the familiar proof that there is no rational \(q\) for which \(q^2=2\text{.}\)

The operation of addition on cuts is defined in the natural way. If \(S\) and \(T\) are cuts, set \(S+T=\{s+t:s\in S, t\in T\}\text{.}\) Order on cuts is defined in terms of inclusion, i.e., \(S\lt T\) if and only if \(S\subsetneq T\text{.}\) A cut is positive if it is greater than \(\bar{0}\text{.}\) When \(S\) and \(T\) are positive cuts, the product \(ST\) is defined by \begin{equation*} ST= \bar{0}\cup\{st:s\in S, t\in T, s\ge0, t\ge 0\}. \end{equation*} One can easily show that there is a real number \(r\) so that \(r^2=\bar{2}\text{.}\) You may be surprised, but perhaps not, to learn that this real number is denoted \(\sqrt2\text{.}\)

There are many other wonders to this story, but enough for one day.

In the first part of this appendix, we put number systems on a firm foundation, but in the process, we used an intuitive understanding of sets. Not surprisingly, this approach is fraught with danger. As was first discovered more than 100 years ago, there are major conceptual hurdles in formulating consistent systems of axioms for set theory. And it is very easy to make statements that sound “obvious” but are not.

Here is one very famous example. Let \(X\) and \(Y\) be sets and consider the following two statements:

1. There exists an injection \(f:X\rightarrow Y\text{.}\)

2. There exists a surjection \(g:Y\rightarrow X\text{.}\)

If \(X\) and \(Y\) are finite sets, these statements are equivalent, and it is perhaps natural to surmise that the same is true when \(X\) and \(Y\) are infinite. But that is not the case.

Here is the system of axioms popularly known as ZFC, which is an abbreviation for Zermelo-Fraenkel plus the Axiom of Choice. In this system, the notion of set and the membership operator \(\in\) are undefined. However, if \(A\) and \(B\) are sets, then exactly one of the following statements is true: (i) \(A\in B\) is true; (ii) \(A\in B\) is false. When \(A\in B\) is false, we write \(A\notin B\text{.}\) Also, there is an equivalence relation \(=\) defined on sets.

A good source of additional (free) information on set theory is the collection of Wikipedia articles. Do a web search and look up the following topics and people:

1. Zermelo-Fraenkel set theory.

2. Axiom of Choice.

3. Peano postulates.

4. Georg Cantor, Augustus De Morgan, George Boole, Bertrand Russell and Kurt Gödel.