# 1.1: Sets and Operations on Sets. Quantifiers

- Page ID
- 19021

## Sets and Operations on Sets

A *set* is a collection of objects of any specified kind. Sets are usually denoted by capitals. The objects belonging to a set are called its *elements* or *members*. We write \(x \in A\) if \(x\) is a member of \(A\), and \(x \notin A\) if it is not.

\(A = \{a, b, c, ...\}\) means that \(A\) consists of the elements \(a, b, c, ... \). In particular, \(A = \{a, b\}\) consists of \(a\) and \(b\); \(A = \{p\}\) consists of \(p\) alone. The *empty* or *void* set, \(\emptyset\), has *no* elements. Equality (\(=\)) means *logical identity.*

If all members of \(A\) are also in \(B\), we call \(A\) a* **subset* of \(B\) (and \(B\) is a *superset* of \(A\)), and write \(A \subseteq B\) or \(B \supseteq A\). It is an axiom that *the sets *\(A\) *and *\(B\) *are equal* (\(A = B\)) *if they have the same members, *i.e.,

\[A \subseteq B \hskip 8pt and \hskip 8pt B \subseteq A.\]

If, however, \(A \subseteq B\) but \(B \nsubseteq A\) (i.e., B has some elements not in A), we call \(A\) a proper subset of \(B\) and write \(A \subset B\) or \(B \supset A\). “\(\subseteq\)” is called the inclusion relation.

Set equality is not affected by the order in which elements appear. Thus \({a, b} = {b, a}\). Not so for ordered pairs \((a, b)\). For such pairs,

\[(a, b) = (x, y) \hskip 8pt \text{iff} \hskip 8pt a = x \hskip 8pt and \hskip 8pt b = y,\]

but not if \(a = y\) and \(b = x\). Similarly, for *ordered n-tuples*,

\[(a_{1}, a_{2}, ... , a_{n}) = (x_{1}, x_{2}, ... , x_{n}) \hskip 8pt \text{iff} \hskip 8pt a_{k} = x_{k}, k = 1, 2, ... , n.\]

We write \({x | P(x)}\) for "the set of all \(x\) satisfying the condition \(P(x)\)." Similarly, \({(x, y) | P(x, y)}\) is the set of all *ordered pairs *for which \(P(x, y)\) holds; \({x \in A | P(x)}\) is the set of those \(x\) *in* \(A\) for which \(P(x)\) is true.

For any sets \(A\) and \(B\), we define their *union* \(A \cup B\), *intersection* \(A \cap B\), *difference* \(A = B\), and *Cartesian product* (or *cross product*) \(A \times B\), as follows:

\(A \cup B\) is the set of all members of \(A\) and \(B\) taken *t**ogether*:

\[\{x | x \in A \hskip 2pt or \hskip 2pt x \in B\}.\]

\(A \cap B\) is the set of all *common* elements of \(A\) and \(B\):

\[\{x \in A | x \in B\}.\]

\(A - B\) consists of those \(x \in A\) that are *not* in \(B\):

\[\{x \in A | x \notin B\}.\]

\(A \times B\) is the set of all *ordered pairs* \((x, y)\), with \(x \in A\) and \(y \in B\):

\[\{(x, y) \ x \in A, y \in B\}.\]

Similarly, \(A_{1} \times A_{2} \times ... \times A_{n}\) is the set of all *ordered n-tuples* \((x_{1}, ... , x_{n})\) such that \(x_{k} \in A_{k}, k = 1, 2, ... , n\). We write \(A^{n}\) for \(A \times A \times ... \times A\) (\(n\) factors).

\(A\) and \(B\) are said to be *disjoint* iff \(A \cap B\ = \emptyset\) (no common elements). Otherwise, we say that \(A\) *meets* \(B\) (\(A \cap B \neq \emptyset\)). Usually all sets involved are subsets of a "*master set*" \(S\), called the *space.* Then we write \(-X\) for \(S - X\), and call \(-X\) the *complement* of \(X\) ( in \(S\)). Various other notations are likewise in use.

Let \(A = \{1, 2, 3\}, B = \{2, 4\}\). Then

\[A \cup B = \{1, 2, 3, 4\}, \hskip 8pt A \cap B - \{2\}, \hskip 8pt A - B = \{1, 3\},\]

\[A \times B = \{(1, 2), (1, 4), (2, 2), (2, 4), (3, 2), (3, 4)\}.\]

If \(N\) is the set of all *naturals* (positive integers), we could also write

\[A = \{x \in N | x < 4\}.\]

- \(A \cup A = A; A \cap A = A\);
- \(A \cup B = B \cup A, A \cap B = B \cap A\);
- \((A \cup B) \cup C = A \cup (B \cup C); (A \cap B) \cap C = A \cap (B \cap C)\);
- \((A \cup B) \cap C = (A \cap C) \cup (B \cap C)\);
- \((A \cap B) \cup C = (A \cup C) \cap (B \cup C)\).

**Proof**-
The proof of (d) is sketched out in Problem 1. The rest is left to the reader.

Because of (c), we may omit brackets in \(A \cup B \cup C\) and \(A \cap B \cap C\); similarly for four or more sets. More generally, we may consider whole *families* of sets, i.e., collections of many (possibly infinitely many) sets. If \(\mathcal{M}\) is such a family, we define its *union*, \(\bigcup\mathcal{M}\), to be the set of all elements \(x\), each belonging to *at least one* set of the family. The intersection of \(\mathcal{M}\), denoted \(\bigcap\mathcal{M}\), consists of those \(x\) that belong to all sets of the family *simultaneously*. Instead, we also write

\[\bigcup \{X | X \in \mathcal{M}\} \hskip 8pt \text{and} \hskip 8pt \bigcap \{X | X \in \mathcal{M}\}, \hskip 8pt \text{respectively.}\]

Often we can *number* the sets of a given family:

\[A_{1}, A_{2}, ... , A_{n}, ...\]

More generally, we may denote all sets of a family \(\mathcal{M}\) by some letter (say, \(X\)) with indices \(i\) attached to it (the indices may, but *need not,* be numbers). The family \(\mathcal{M}\) then is denoted by \(\{X_{i}\}\) or \(\{X_{i} | i \in I\), where \(i\) is a variable index ranging over a suitable set \(I\) of indices ("index notation"). In this case, the union and intersection of \(\mathcal{M}\) are denoted by such symbols as

\[\bigcup\{X_{i} | i \in I\} = \bigcup\limits_{i} X_{i} = \bigcup X_{i} = \bigcup\limits_{i \in I} X_{i};\]

\[\bigcap\{X_{i} | i \in I\} = \bigcap\limits_{i} X_{i} = \bigcap X_{i} = \bigcap\limits_{i \in I} X_{i};\]

If the indices are *integers*, we may write

\[\bigcup\limits_{n = 1}^{m} X_{n}, \bigcup\limits_{n = 1}^{\infty} X_{n}, \bigcup\limits_{n = k}^{m} X_{n}, \text{etc.}\]

For any sets \(S\) and \(A_{i}\) \((i \in I)\), the following are true:

\[(i) \hskip 5pt S - \bigcup_{i} A_{i} = \bigcap_{i}(S - A); \hskip 12pt (ii) \hskip 5pt S - \bigcap_{i}A_{i} = \cup_{i}(S - A_{i}).\]

(If \(S\) is the entire space, we may write \(-A_{i}\) for \(S - A_{i}\), \(-\bigcup A_{i}\) for \(S - \bigcup A_{i}\), etc.

Before proving these laws, we introduce some useful notation.

## Logical Quantifiers

From logic we borrow the following abbreviations.

"\((\forall x \in A)\)..." means "For each member \(x\) of \(A\), it is true that . . ."

"\((\exists x \in A)\)..." means "There is at least one \(x\) in \(A\) such that . . ."

"\((\exists! x \in A)\)..." means "There is a *unique* \(x\) in \(A\) such that . . ."

The symbols "\((\forall x \in A)\)" and "\((\exists x \in A)\)" are called the *universal* and *existential quantifiers*, respectively. If confusion is ruled out, we simply write "\((\forall x)\)," "\((\exists x)\)," and "\((\exists! x)\)" instead. For example, if we agree that \(m\), and \(n\) denote *naturals*, then

\["(\forall n)(\exists m) \hskip 5pt m > n"\]

means "For each natural \(n\), there is a natural \(m\) such that \(m > n\)." We give some more examples.

Let \(\mathcal{M} = \{A_{i} | i \in I\}\) be an indexed set family. By definition, \(x \in \bigcup A_{i}\) means that \(x\) is in *at least one* of the sets \(A_{i}\); in symbols,

\[(\exists i \in I) \hskip 5pt x \in A_{i}.\]

Thus we note that

\[x \in \bigcup_{i \in I} A_{i} \hskip 5pt \text{iff} \hskip 5pt [(\exists i \in I) x \in A_{i}].\]

Similarly,

\[x \in \bigcap_{i} A_{i} \hskip 5pt \text{iff} \hskip 5pt [(\forall i \in I) x \in A_{i}].\]

Also note that \(x \notin \bigcup A_{i}\) iff \(x\) is in *none* of the \(A_{i}\), i.e.,

\[(\forall i) \hskip 5pt x \notin A_{i}.\]

Similarly, \(x \notin \bigcap A_{i}\) iff \(x\) fails to be in *some* \(A_{i}\). i.e.,

\[(\exists i) \hskip 5pt x \notin A_{i}. \hskip 5pt (Why?)\]

We now use these remarks to prove Theorem 2(i). We have to show that \(S - \bigcup A_{i}\) has the same elements as \(\bigcap(S - A_{i})\), i.e., that \(x \in S - \bigcup A_{i}\) iff \(x \in \bigcap(S - A_{i})\). But, by our definitions, we have

\[\begin{equation} \begin{split} x \in S - \bigcup A_{i} &\iff [x \in S, x \notin \bigcup A_{i}] \\ &\iff (\forall i)[x \in S, x \notin A_{i}] \\ &\iff (\forall i) x \in S - A_{i} \\ &\iff x \in \bigcap(S - A_{i}), \end{split} \end{equation}\]

as required.

One proves part (ii) of Theorem 2 quite similarly. (Exercise!)

We shall now dwell on quantifiers more closely. Sometimes a formula \(P(x)\) holds not for all \(x \in A\), but only for those with an additional property \(Q(x)\).

This will be written as

\[(\forall x \in A | Q(x)) \hskip 5pt P(x),\]

where the vertical stroke stands for "such that." For example, if \(N\) is again the naturals, then the formula

\[(\forall x \in N | x > 3) \hskip 5pt x \geq 4\]

means "for each \(x \in N\) *such that* \(x \geq 4\)." In other words, for naturals, \(x > 3 \implies x \geq 4\) (the arrow stands for "implies"). Thus (1) can also be written as

\[(\forall x \in N) \hskip 5pt x > 3 \implies x \geq 4.\]

In mathematics, we often have to form the *negation* of a formula that starts with one or several quantifiers. It is noteworthy, then, that *each universal quantifier is replaced by an existential one (and vice versa),* followed by the negation of the subsequent part of the formula. For example, in calculus, a real number \(p\) is called the *limit* of a sequence \(x_{1}, x_{2}, ... , x_{n}, ...\) iff the following is true:

For every real \(\epsilon > 0\), there is a natural \(k\) (depending on \(\epsilon\)) such that, for all natural \(n > k\), we have \(|x_{n} - p| < \epsilon|\).

If we agree that lower case letters (possibly with subscripts) denote real numbers, and that \(n\), \(k\) denote naturals \((n, k \in \mathbb{N})\), this sentence can be written as

\[(\forall \epsilon > 0)(\exists k)(\forall n > k) \hskip 5pt |x_{n} - p| < \epsilon.\]

Here the expressions "\((\forall \epsilon > 0)\)" and "\((\forall n > k)\)" stand for "\((\forall \epsilon | \epsilon > 0)\)" and "\((\forall n | n > k)\)," respectively (such self-explanatory abbreviations will also be used in other similar cases).

Now, since (2) states that "for all \(\epsilon > 0\)" something (i.e., the rest of (2)) is true, the negation of (2) starts with "*there is an* \(\epsilon > 0\)" (for which the rest of the formula *fails*). Thus we start with "\((\exists \epsilon > 0)\)," and form the negation of what follows, i.e., of

\[(\exists k)(\forall n > k) \hskip 5pt |x_{n} - p| < \epsilon.\]

This negation, in turn, starts with "\((\forall k)\)," etc. Step by step, we finally arrive at

\[(\exists \epsilon > 0)(\forall k)(\exists n > k) \hskip 5pt |x_{n} - p| \geq \epsilon.\]

Note that here* the choice of \(n > k\) may depend on k.* To stress it, we often write \(n_{k}\) for \(n\). Thus the negation of (2) finally emerges as

\[(\exists \epsilon > 0)(\forall k)(\exists n_{k} > k) \hskip 5pt |x_{n_{k}} - p| \geq \epsilon.\]

The *order* in which the quantifiers follow each other is *essential.* For example, the formula

\[(\forall n \in N)(\exists m \in N) \hskip 5pt m > n\]

("each \(n \in N\) is exceeded by some \(m \in N\)") is true, but

\[(\exists m \in N)(\forall n \in N) \hskip 5pt m > n\]

is false. However, two *consecutive* universal quantifiers (or two *consecutive* existential ones) may be interchanged. We briefly write

\["(\forall x, y \in A)" \text{ for } "(\forall x \in A)(\forall y \in A),"\]

and

\["(\exists x, y \in A)" \text{ for } "(\exists x \in A)(\exists y \in A)," \text{ etc.}\]

*does not* imply the existence of an \(x\) for which \(P(x)\) is true. It is only meant to imply that *there is no \(x\) in \(A\) for which \(P(x)\) fails.*

The latter is true even if \(A = \emptyset\); we then say that "\((\forall x \in A) \hskip 5pt P(x)\)" is *vacuously true.* For examplek the formula \(\emptyset \subseteq B\), i.e.,

\[(\forall x \in \emptyset) \hskip 5pt x \in B\]

*is always true (vacuously).*