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