4.3 Set operations
In this section, we’ll continue to develop the correspondence between logic and set theory.
The logical connectors \(\land\) and \(\lor\) correspond to the set-theoretic notions of union (\(\cup\)) and intersection (\(\cap\)). The symbols are designed to provide a mnemonic for the correspondence; the set theory symbols are just rounded versions of those from logic.
Explicitly, if \(P(x)\) and \(Q(x)\) are open sentences, then the union of the corresponding truth sets \(S_P\) and \(S_Q\) is defined by \[ S_P \cup S_Q = \{ x \in U {\,:\,}P(x) \lor Q(x) \}. \]
Exercise 4.6 Suppose two sets \(A\) and \(B\) are given. Re-express the previous definition of “union” using their membership criteria, \(M_A(x) =\) “\(x \in A\)” and \(M_B(x) =\) “\(x \in B\).”
The union of more than two sets can be expressed using a big union symbol. For example, consider the family of real intervals defined by \(I_n = (n,n+1]\).38 There’s an interval for every integer \(n\). Also, every real number is in one of these intervals. The previous sentence can be expressed as \[ {\mathbb R}= \bigcup_{n\in{\mathbb Z}} I_n. \]
The intersection of two sets is conceptualized
as “what they have in common”
but the precise definition is found by considering conjunctions,
\[ A \cap B = \{ x \in U {\,:\,}x \in A \; \land \; x \in B \}. \]
There is also a “big” version of the intersection symbol. Using the same family of intervals as before, \[ \emptyset \; = \; \bigcap_{n\in{\mathbb Z}} I_n. \]
Of course the intersection of any distinct pair of these intervals is empty so the statement above isn’t particularly strong.
Negation in logic corresponds to complementation in set theory. The complement of a set \(A\) is usually denoted by \(\overline{A}\) (although some prefer a superscript \(c\) — as in \(A^c\)), this is the set of all things that aren’t in \(A\). In thinking about complementation, one quickly sees why the importance of working within a well-defined universal set is stressed. Consider the set of all math textbooks. Obviously the complement of this set would contain texts in English, engineering and evolution — but that statement is implicitly assuming that the universe of discourse is “textbooks.” It’s equally valid to say that a very long sequence of zeros and ones, a luscious red strawberry, and the number \(\sqrt{\pi}\) are not math textbooks and so these things are all elements of the complement of the set of all math textbooks.
What is really a concern for us is the issue of whether or not the complement of a set is well-defined; that is, can we tell for sure whether a given item is or is not in the complement of a set. This question is decidable exactly when the membership question for the original set is decidable. Many people think that the main reason for working within a fixed universal set is that we then have well-defined complements. The real reason that we accept this restriction is to ensure that both membership criteria, \(M_A(x)\) and \(M_{\overline{A}}(x)\), are decidable open sentences. As an example of the sort of strangeness that can crop up, consider that during the time that I, as the author of this book, was writing the last paragraph, this text was nothing more than a very long sequence of zeros and ones in the memory of my computer
Every rule that we learned in Section 2.3 has a set-theoretic equivalent. These set-theoretic versions are expressed using equalities (i.e. the symbol \(=\) in between two sets) which is actually a little bit funny if you think about it. We normally use \(=\) to mean that two numbers or variables have the same numerical magnitude, as in \(12^2 = 144\), we are doing something altogether different when we use that symbol between two sets, as in \(\{1,2,3\}= \{\sqrt{1},\sqrt{4},\sqrt{9}\}\), but people seem to be used to this so there’s no need to quibble
Exercise 4.8 Develop a useful definition for set equality. In other words, come up with a (quantified) logical statement that means the same thing as “\(A = B\)” for two arbitrary sets \(A\) and \(B\).
Exercise 4.9 What symbol in logic should go between the membership criteria \(M_A(x)\) and \(M_B(x)\) if \(A\) and \(B\) are equal sets?
The rules governing the interactions between the set theoretic operations are listed below:
Double complement: \(\overline{ \overline{ A}} = A\)
Intersection version:
| Commutative law | \(A\cap B = B\cap A\) |
| Associative law | \(A\cap(B\cap C) = (A\cap B)\cap C\) |
| Distributive law | \(A\cap(B\cup C) = (A\cap B)\cup(A\cap C)\) |
| De Morgan’s law | \(\overline{A \cap B}=\overline{A}\cup\overline{B}\) |
| Complementarity | \(A \cap \overline{A} = \emptyset\) |
| Identity law | \(A\cap U = A\) |
| Domination | \(A \cap \emptyset = \emptyset\) |
| Idempotence | \(A \cap A = A\) |
| Absorption | \(A\cap(A\cup B)= A\) |
Union version:
| Commutative law | \(A\cup B = B\cup A\) |
| Associative law | \(A\cup(B\cup C) = (A\cup B)\cup C\) |
| Distributive law | \(A\cup(B\cap C) = (A\cup B)\cap(A \cup C)\) |
| De Morgan’s law | \(\overline{A \cup B}=\overline{A}\cap\overline{B}\) |
| Complementarity | \(A\cup\overline{A}= U\) |
| Identity law | \(A\cup \emptyset = A\) |
| Domination | \(A \cup U = U\) |
| Idempotence | \(A \cup A = A\) |
| Absorption | \(A\cup(A\cap B) = A\) |
We are now in a position somewhat similar to when we jumped from proving logical assertions with truth tables to doing two-column proofs. We have two different approaches for showing that two sets are equal. We can do a so-called “element chasing” proof (to show \(A=B\), assume \(x \in A\) and prove \(x \in B\) and then vice versa). Or, we can construct a proof using the basic set equalities given above. Often the latter can take the form of a two-column proof.
Before we proceed much further in our study of set theory, it would be a good idea to give you an example. We’re going to prove the same assertion in two different ways — once via element chasing and once using the basic set theoretic equalities.
The statement we’ll prove is \(A \cup B \; = \; A \cup (\overline{A} \cap B)\).
First, by chasing elements:
Proof. Suppose \(x\) is an element of \(A \cup B\). By the definition of union we know that \[ x \in A \lor x \in B. \]
The conjunctive identity law and the fact that \(x \in A \lor x \notin A\) is a tautology gives us an equivalent logical statement: \[ (x \in A \lor x \notin A) \land (x \in A \lor x \in B). \]
Finally, this last statement is equivalent to \[ x \in A \lor (x \notin A \land x \in B) \] which is the definition of \(x \in A \cup (\overline{A} \cap B)\).
On the other hand, if we assume that \(x \in A \cup (\overline{A} \cap B)\), it follows that \[ x \in A \lor (x \notin A \land x \in B). \]
Applying the distributive law, disjunctive complementarity, and the identity law in sequence, we obtain \[\begin{gather*} x \in A \lor (x \notin A \land x \in B) \\ \cong (x \in A \lor x \notin A) \land (x \in A \lor x \in B) \\ \cong \top \land (x \in A \lor x \in B) \\ \cong x \in A \lor x \in B \end{gather*}\]
The last statement in this chain of logical equivalences provides the definition of \(x \in A \cup B\).
A two-column proof of the same statement looks like this:
There are some notions within set theory that don’t have any clear parallels in logic. One of these is essentially a generalization of the concept of “complements.” If you think of the set \(\overline{A}\) as being the difference between the universal set \(U\) and the set \(A,\) you are on the right track. The difference between two sets is written \(A \setminus B\) (sadly, sometimes this is denoted using the ordinary subtraction symbol \(A-B\)) and is defined by \[ A \setminus B = A \cap \overline{B}. \]
The difference, \(A \setminus B\), consists of those elements of \(A\) that aren’t in \(B\). In some developments of set theory, the difference of sets is defined first and then complementation is defined by \(\overline{A} = U \setminus A\).
The difference of sets (like the difference of real numbers) is not a commutative operation. In other words \(A \setminus B \neq B \setminus A\) (in general). It is possible to define an operation that acts somewhat like the difference, but that is commutative. The symmetric difference of two sets is denoted using a triangle (really a capital Greek delta) \[ A \triangle B = (A \setminus B) \cup (B\setminus A). \]
Exercise 4.10 Show that \(A \triangle B = (A \cup B) \setminus (A \cap B)\).
Come on! You read right past that exercise without even pausing!
What? You say you did try it and it was too hard?
Okay, just for you (and this time only) I’ve prepared an aid to help you through…
What follows is a two-column proof of the result you need to prove, but the lines of the proof are all scrambled. Make a copy and cut out all the pieces and then glue them together into a valid proof.
\[\begin{array}{|c|c|}\hline = (A \cap \overline{B}) \cup (B \cap \overline{A}) & \text{identity law} \\\hline = (A \cup B) \cap \overline{(A \cap B)} & \text{def. of relative difference} \\\hline (A \cup B) \setminus (A \cap B) & \text{Given} \\\hline = ((A \cap \overline{A}) \cup (A \cap \overline{B})) \cup ((B \cap \overline{A}) \cup (B \cap \overline{B})) & \text{distributive law} \\\hline = (A \setminus B) \cup (B \setminus A) & \text{def. of relative difference} \\\hline = (A \cap \overline{(A \cap B)}) \cup (B \cap \overline{(A \cap B)}) & \text{distributive law} \\\hline = A \triangle B & \text{def. of symmetric difference} \\\hline = (A \cap (\overline{A} \cup \overline{B}) \cup (B \cap (\overline{A} \cup \overline{B})) & \text{De Morgan's law} \\\hline = (\emptyset \cup (A \cap \overline{B})) \cup ((B \cap \overline{A}) \cup \emptyset) & \text{complementarity} \\\hline \end{array}\]
4.3.1 Exercises
Let \(A = \{1, 2, \{1, 2\}, b\}\) and let \(B=\{a, b, \{1, 2\} \}\). Find the following:
\(A \cap B\)
\(A \cup B\)
\(A \setminus B\)
\(B \setminus A\)
\(A \triangle B\)
In a standard deck of playing cards, one can distinguish sets based on face-value and/or suit. Let \(A, 2, \ldots 9, 10, J, Q\) and \(K\) represent the sets of cards having the various face-values. Also, let \(\heartsuit\), \(\spadesuit\), \(\clubsuit\) and \(\diamondsuit\) be the sets of cards having the possible suits. Find the following
\(A \cap \heartsuit\)
\(A \cup \heartsuit\)
\(J \cap (\spadesuit \cup \heartsuit)\)
\(K \cap \heartsuit\)
\(A \cap K\)
\(A \cup K\)
Figure 4.1 is a screenshot from the computational geometry program OpenSCAD (very hand for making models for 3-d printing…) In computational geometry, we use the basic set operations together with a few other types of transformations to create interesting models using simple components. Across the top of Figure 4.1, we see three sets of points in \({\mathbb R}^3\), a ball, a sort of 3-dimensional plus sign, and a disk. Let’s call the ball \(A\), the plus sign \(B\) and the disk \(C\). The nine shapes shown below them are made from \(A\), \(B\) and \(C\) using union, intersection and set difference. Identify them!
Figure 4.1: Screenshot of OpenSCAD.
Do element-chasing proofs (show that an element is in the left-hand side if and only if it is in the right-hand side) to prove each of the following set equalities.
\(\overline{A\cap B} \; = \; \overline{A}\cup\overline{B}\)
\(A\cup B \; = \; A\cup(\overline{A}\cap B)\)
\(A\triangle B \; = \; (A\cup B)\setminus(A\cap B)\)
\((A\cup B)\setminus C \; = \; (A\setminus C)\cup(B\setminus C)\)
For each positive integer \(n\), we’ll define an interval \(I_n\) by \[ I_n = [-n, 1/n). \] Find the union and intersection of all the intervals in this infinite family. \[ \bigcup_{n \in {\mathbb N}} I_n \quad = \] \[ \bigcap_{n \in {\mathbb N}} I_n \quad = \]
There is a set \(X\) such that, for all sets \(A\), we have \(X \triangle A = A\). What is \(X\)?
There is a set \(Y\) such that, for all sets \(A\), we have \(Y \triangle A = \overline{A}\). What is \(Y\)?
In proving a set-theoretic identity, we are basically showing that two sets are equal. One reasonable way to proceed is to show that each is contained in the other. Prove that \[A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\] by showing that \[A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)\] and \[(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C).\]
Prove that \[A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\] by showing that \[A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)\] and \[(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C).\]
Prove the set-theoretic versions of De Morgan’s laws using the technique discussed in the previous problems.
The previous technique (showing that \(A=B\) by arguing that \(A \subseteq B \; \land \; B \subseteq A\)) will have an outline something like
Proof. First we will show that \(A \subseteq B\).
Towards that end, suppose \(x \in A\). \[\vdots\] Thus \(x \in B\).Now, we will show that \(B \subseteq A\).
Therefore, \(A \subseteq B \; \land \; B \subseteq A\) and so we conclude that \(A=B\).
Suppose that \(x \in B\). \[\vdots\] Thus \(x \in A\).Formulate a proof that \(A \triangle B \; = \; (A \cup B) \setminus (A \cap B)\) that follows this outline.
The elements of \(I_n\) can also be distinguished as the solution sets of the inequalities \(n < x \leq n+1.\)↩