Like logic, the subject of sets is rich and interesting for its own sake. We will need only a few facts about sets and techniques for dealing with them, which we set out in this section and the next. We will return to sets as an object of study in chapters 4 and 5.

A set is a collection of objects; any one of the objects in a set is called a member or an element of the set. If $a$ is an element of a set $A$ we write $a\in A$.

Some sets occur so frequently that there are standard names and symbols for them. We denote the real numbers by $\R$, the rational numbers (that is, the fractions) by $\Q$, the integers by $\Z$ and the natural numbers (that is, the positive integers) by $\N$.

There is a natural relationship between sets and logic. If $A$ is a set, then $P(x)=$"$x\in A$'' is a formula. It is true for elements of $A$ and false for elements outside of $A$. Conversely, if we are given a formula $Q(x)$, we can form the truth set consisting of all $x$ that make $Q(x)$ true. This is usually written $\{x:Q(x)\}$ or $\{x\mid Q(x)\}$.

Example 1.5.1 If the universe is $\Z$, then $\{x:x>0\}$ is the set of positive integers and $\{x:\exists n\,(x=2n)\}$ is the set of even integers.

If there are a finite number of elements in a set, or if the elements can be arranged in a sequence, we often indicate the set simply by listing its elements.

Example 1.5.2 $\{1,2,3\}$ and $\{1,3,5,7,9,…\}$ are sets of integers. The second is presumably the set of all positive odd numbers, but of course there are an infinite number of other possibilities. In all but the most obvious cases, it is usually wise to describe the set ("the set of positive odd numbers, $\{1,3,5,7,9,…\}$'') or give a formula for the terms ("$\{1,3,5,7,9,\ldots,2i+1,\ldots\}$'').

Example 1.5.3 We indicate the empty set by $\emptyset$, that is, $\emptyset=\{\}$ is the set without any elements. Note well that $\emptyset\ne\{\emptyset\}$: the first contains nothing, the second contains a single element, namely the empty set.

The logical operations $\lnot, \land, \lor$ translate into the theory of sets in a natural way using truth sets. If $A$ is a set, define $$A^c=\{x: x\notin A\},$$ called the complement of $A$. If $B$ is a second set, define $$A\cap B=\{x:x\in A\land x\in B\},$$ called the intersection of $A$ and $B$, and $$A\cup B=\{x:x\in A\lor x\in B\},$$ called the union of $A$ and $B$.

Example 1.5.4 Suppose $U=\{1,2,3,\ldots,10\}$, $A=\{1,3,4,5,7\}$, $B=\{1,2,4,7,8,9\}$; then $A^c=\{2,6,8,9,10\}$, $A\cap B=\{1,4,7\}$ and $A\cup B=\{1,2,3,4,5,7,8,9\}$. Note that the complement of a set depends on the universe $U$, while the union and intersection of two sets do not.

We often wish to compare two sets. We say that $A$ is a subset of $B$ if $$\forall x (x\in A\implies x\in B),$$ and write $A\subseteq B$. This is not only a definition but a technique of proof. If we wish to show $A\subseteq B$ we may start with an arbitrary element $x$ of $A$ and prove that it must be in $B$. We say the sets $A$ and $B$ are equal if and only if $A\subseteq B$ and $B\subseteq A$, that is, $$\forall x (x\in A\iff x\in B).$$ So to show two sets are equal one must verify that a biconditional is satisfied, which often needs to be done in two parts, that is, the easiest way to show that $A=B$ often is to show that $A\subseteq B$ and $B\subseteq A$. If $A\subseteq B$ and $A\ne B$, we say $A$ is a proper subset of $B$ and write $A\subset B$.

Example 1.5.5 $\N\subset\Z\subset\Q\subset\R$.

Finally, we say that $A$ and $B$ are disjoint if $A\cap B=\emptyset$.

In section 1.1 we learned that logical operations are related by many tautologies, the study of which is called Boolean Algebra. These tautologies can be interpreted as statements about sets; here are some particularly useful examples.

Theorem 1.5.6 Suppose $A$, $B$ and $C$ are sets. Then

a) $A\cap B\subseteq A$,

b) $A\subseteq A\cup B$,

c) $A\cap(B\cup C)=(A\cap B)\cup (A\cap C)$,

d) $A\cup(B\cap C)=(A\cup B)\cap (A\cup C)$,

e) $(A\cap B)^c=A^c\cup B^c$,

f) $(A\cup B)^c=A^c\cap B^c$,

g) $A\subseteq B$ iff $B^c\subseteq A^c$.

Proof.
Suppose $P(x)=$"$x\in A$'', $Q(x)=$"$x\in B$'', $R(x)=$"$x\in C$''. To prove (a), suppose that $a\in A\cap B$. Then by definition, $P(a)\land Q(a)$ is true. Since $P(x)\land Q(x)\implies P(x)$ is a tautology, $P(a)$ is true, or $a\in A$. As noted above, this proves that $A\cap B\subseteq A$. Similarly, (c) follows since $P(x)\land(Q(x)\lor R(x))\iff (P(x)\land Q(x))\lor (P(x)\land R(x))$ is a tautology. All the other statements follow in the same manner.

$\square$

As in the case of logic, (e) and (f) are called De Morgan's laws. Theorem 1.5.6 certainly is not an exhaustive list of set identities, it merely illustrates a few of the more important ones.

If $a,b\in U$ we can form the ordered pair $(a,b)$. The fundamental property of ordered pairs is that $(a_1,b_1)=(a_2,b_2)$ if and only if $a_1=a_2$ and $b_1=b_2$. If $A$ and $B$ are sets, the set $$A\times B=\{(a,b): a\in A\land b\in B\}$$ is called the Cartesian product of $A$ and $B$.