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 together:
\[\{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).