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. $\square$

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\}$''). $\square$

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.
$\square$

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$. Finally, it
is occasionally useful to have a notation for the **difference** of $A$ and $B$:
$$
A\backslash B=\{x:x\in A \land x\notin B\} = A\cap B^c.
$$
Note that this operation is not commutative: $A\backslash B$ and
$B\backslash A$ are usually quite different.

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. $\square$

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$. $\square$

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. $\qed$

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

Example 1.5.7 If $A=\{r,s,t\}$, $B=\{\$,\%\}$, then $$ A\times B=\{(r,\$),(r,\%),(s,\$),(s,\%),(t,\$),(t,\%)\}. $$ $\square$

Example 1.5.8 $\R\times \R=\R^2$ is the plane. $\R\times \R\times \R=\R^3$ is 3-dimensional space. $\square$

**René Descartes.** Descartes
(1596–1650) was perhaps the most able mathematician of his time
(though he may have to share top billing with Pierre de Fermat, a busy
lawyer who did mathematics on the side for fun). Despite his ability
and his impact on mathematics, Descartes was really a scientist and
philosopher at heart. He made one great contribution to mathematics,
*La géométrie*, and then concentrated his energies elsewhere.

*La géométrie* did not even appear on its own, but as an
appendix to his most famous work, *Discours de la méthode pour
bien conduire sa raison et chercher la vérité dans les sciences*
("Discourse on the method of reasoning well and seeking truth in the
sciences''). Descartes is remembered as the father of coordinate or
analytic geometry, but his uses of the method were much closer in
spirit to the great Greek geometers of antiquity than to modern usage.
That is, his interest really lay in geometry; he viewed the
introduction of algebra as a powerful tool for solving geometrical
problems. Confirming his view that geometry is central, he went to
some lengths to show how algebraic operations (for example, finding
roots of quadratic equations) could be interpreted
geometrically.

In contrast to modern practice, Descartes had no interest in
graphing an arbitrary relation in two variables—in the whole of
*La géométrie*, he did not plot any new curve
from its equation. Further, ordered pairs do not play any role in the
work; rectangular coordinates play no special role (Descartes used
oblique coordinates freely—that is, his axes were not constrained to
meet at a right angle); familiar formulas for distance, slope,
angle between lines, and so on, make no appearance; and negative
coordinates, especially negative abscissas, are little used and poorly
understood. Ironically, then, there is little about the modern notion
of Cartesian coordinates that Descartes would recognize.

Despite all these differences in emphasis and approach, Descartes' work ultimately made a great contribution to the theory of functions. The Cartesian product may be misnamed, but Descartes surely deserves the tribute.

## Exercises 1.5

**Ex 1.5.1**
For the given universe $U$ and the given sets $A$ and $B$, find
$A^c$, $A\cap B$ and $A\cup B$.

a) $U=\{1,2,3,4,5,6,7,8\}$, $A=\{1,3,5,8\}$, $B=\{2,3,5,6\}$

b) $U=\R$, $A=(-\infty, 2]$, $B=(-1, \infty)$

c) $U=\Z$, $A=\{n: \hbox{$n$ is even}\}$, $B=\{n: \hbox{$n$ is odd}\}$

d) $U=\Q$, $A=\emptyset$, $B=\{q: q>0\}$

e) $U=\N$, $A=\N$, $B=\{n: \hbox{$n$ is even}\}$

f) $U=\R$, $A=(-\infty, 0]$, $B= [-2, 3)$

g) $U=\N$, $A=\{n:n\le 6\}$, $B=\{1,2,4,5,7,8\}$

h) $U=\R\times\R$, $A=\{(x,y):x^2+y^2\le 1\}$, $B=\{(x,y):x\ge0,y\ge0\}$.

**Ex 1.5.2**
Prove the parts of Theorem 1.5.6
not proved in the text.

**Ex 1.5.3**
Suppose $U$ is some universe of discourse.

a) What is $\{x: x=x\}$?

b) What is $\{x: x\ne x\}$?

**Ex 1.5.4**
Prove carefully from the definition of
"$\subseteq$'' that for any set $A$, $\emptyset\subseteq A$.

**Ex 1.5.5**

a) If $A=\{1,2,3,4\}$ and $B=\{x,y\}$, what is $A\times B$?

b) If $A$ has $m$ elements and $B$ has $n$ elements, how many elements are in $A\times B$?

c) Describe $A\times \emptyset$. Justify your answer.

d) What name do we give the set $(0, \infty)\times (0, \infty)\subset \R^2$?

e) What kind of geometric figure is $[1,2]\times [1,2]\subset \R^2$?

**Ex 1.5.6**
If $A$ and $B$ are sets, show $A\subseteq B$ iff $A\cap
B^c=\emptyset$ iff $A^c\cup B=U$. (What are the
corresponding logical statements?)

**Ex 1.5.7**
Suppose $A$, $B$, $C$ and $D$ are sets.

a) Show $(A\times B)\cap (C\times D)= (A\cap C)\times (B\cap D)$.

b) Does (a) hold with $\cap$ replaced by $\cup$?

**Ex 1.5.8**
Suppose we say a set $S$ is **normal** if $S\notin S$. (You probably have
encountered only normal sets, e.g., the *set* of reals is not a
particular real.) Consider $N=\{S: \hbox{$S$ is a normal set}\}$. Is
$N$ a normal set? (This is called Russell's Paradox. Examples like this helped make set theory a mathematical
subject in its own right. Although the concept of a set at first seems
straightforward, even trivial, it emphatically is not.)