Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section4.3Set 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 \begin{equation*} S_P \cup S_Q \; = \{ x \in U \suchthat P(x) \lor Q(x) \}. \end{equation*}

Exercise4.3.1

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]\). 1  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 \begin{equation*} \Reals \; = \; \bigcup_{n\in\Integers} I_n. \end{equation*}

The intersection of two sets is conceptualized as “what they have in common” but the precise definition is found by considering conjunctions, \begin{equation*} A \cap B \; = \; \{ x \in U \suchthat x \in A \; \land \; x \in B \}. \end{equation*}

Exercise4.3.2

With reference to two open sentences \(P(x)\) and \(Q(x)\), define the intersection of their truth sets, \(S_P \cap S_Q\).

There is also a “big” version of the intersection symbol. Using the same family of intervals as before, \begin{equation*} \mbox{\(\emptyset\)} \; = \; \bigcap_{n\in\Integers} I_n. \end{equation*}

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 Chapter 2 (see Table 2.3.4) 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 sense in quibbling.

Exercise4.3.3

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

Exercise4.3.4

What symbol in Logic should go between the membership criteria \(M_A(x)\) and \(M_B(x)\) if \(A\) and \(B\) are equal sets?

In Table 4.3.5 the rules governing the interactions between the set theoretic operations are collected.

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 in Table 4.3.5. Often the latter can take the form of a two-column proof.

\begin{minipage}{.35\textwidth} \Intersection \version \begin{minipage}{.35\textwidth} \Union \version
Commutative
laws \begin{minipage}{.35\textwidth} \\(A \cap B = B \cap A\) \begin{minipage}{.35\textwidth} \\(A \cup B = B \cup A\)
Associative
laws \begin{minipage}{.35\textwidth} \\(A \cap (B \cap C)\) \\(= (A \cap B) \cap C\) \begin{minipage}{.35\textwidth} \\(A \cup (B \cup C)\) \\(= (A \cup B) \cup C\)
Distributive
laws \begin{minipage}{.35\textwidth} \\(A \cap (B \cup C) =\) \\((A \cap B) \cup (A \cap C)\) \begin{minipage}{.35\textwidth} \\(A \cup (B \cap C) =\) \\((A \cup B) \cap (A \cup C)\)
DeMorgan's
laws \begin{minipage}{.35\textwidth} \\(\overline{A \cap B}\) \\(= \; \overline{A} \cup \overline{B}\) \begin{minipage}{.35\textwidth} \\(\overline{A \cup B}\) \\(= \; \overline{A} \cap \overline{B}\)
Double
complement \begin{minipage}{.35\textwidth} \\(\overline{\overline{A}} \; = \; A\) \begin{minipage}{.35\textwidth} \same
Complementarity \begin{minipage}{.35\textwidth} \\(A \cap \overline{A} \; = \; \emptyset\) \begin{minipage}{.35\textwidth} \\(A \cup \overline{A} \; = \; U\)
Identity
laws \begin{minipage}{.35\textwidth} \\(A \cap U = A\) \begin{minipage}{.35\textwidth} \\(A \cup \emptyset = A\)
Domination \begin{minipage}{.35\textwidth} \\(A \cap \emptyset = \emptyset\) \begin{minipage}{.35\textwidth} \\(A \cup U = U\)
Idempotence \begin{minipage}{.35\textwidth} \\(A \cap A = A\) \begin{minipage}{.35\textwidth} \\(A \cup A = A\)
Absorption \begin{minipage}{.35\textwidth} \\(A \cap (A \cup B) = A\) \begin{minipage}{.35\textwidth} \\(A \cup (A \cap B) = A\)
Table4.3.5Basic set theoretic equalities.

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 from Table 4.3.5.

The statement we'll prove is \(A \cup B \; = \; A \cup (\overline{A} \cap B)\).

First, by chasing elements:

Proof

A two-column proof of the same statement looks like this:

Proof

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 \begin{equation*} A \setminus B = A \cap \overline{B}. \end{equation*}

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) \begin{equation*} A \triangle B = (A \setminus B) \cup (B\setminus A). \end{equation*}

Exercise4.3.6

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…

On the next page 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.

So, no more excuses, just do it!

\(= (A \cap \overline{B}) \cup (B \cap \overline{A})\) identity law
\(= (A \cup B) \cap \overline{(A \cap B)}\) def. of relative difference
\((A \cup B) \setminus (A \cap B)\) Given
\(= ((A \cap \overline{A}) \cup (A \cap \overline{B})) \cup ((B \cap \overline{A}) \cup (B \cap \overline{B}))\) distributive law
\(= (A \setminus B) \cup (B \setminus A)\) def. of relative difference
\(= (A \cap \overline{(A \cap B)}) \cup (B \cap \overline{(A \cap B)})\) distributive law
\(= A \triangle B\) def. of symmetric difference
\(= (A \cap (\overline{A} \cup \overline{B}) \cup (B \cap (\overline{A} \cup \overline{B}))\) DeMorgan's law
\(= (\emptyset \cup (A \cap \overline{B})) \cup ((B \cap \overline{A}) \cup \emptyset)\) complementarity

Subsection4.3.1Exercises

  1. Let \(A = \{1, 2, \{1, 2\}, b\}\) and let \(B=\{a, b, \{1, 2\} \}\). Find the following:

    1. \(A \cap B\) \hint{ \(\{ b, \{1, 2\} \}\) }

    2. \(A \cup B\) \hint{ \(\{1, 2, a, b, \{1, 2\} \}\) }

    3. \(A \setminus B\) \hint{ \(\{ 1, 2 \}\) }

    4. \(B \setminus A\) \hint{ \(\{ a \}\) }

    5. \(A \triangle B\) \hint{ \(\{ 1, 2, a \}\) }

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

    1. \(A \cap \heartsuit\) \hint{This is just the ace of hearts.}

    2. \(A \cup \heartsuit\) \hint{All of the hearts and the other three aces}

    3. \(J \cap (\spadesuit \cup \heartsuit)\) \hint{ These two cards are known as the one-eyed jacks.}

    4. \(K \cap \heartsuit\) \hint{The king of hearts, a.k.a. the suicide king.}

    5. \(A \cap K\) \hint{\(\emptyset\) }

    6. \(A \cup K\) \hint{Eight cards: all four kings and all four aces.}

  3. The following is a screenshot from the computational geometry program OpenSCAD (very hand for making models for 3-d printing…) In computational geometry we use the basice set operations together with a few other types of transformations to create interesting models using simple components. Across the top of the image below we see 3 sets of points in \(\Reals^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!

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

    1. \(\overline{A\cap B} \; = \; \overline{A}\cup\overline{B}\)

    2. \(A\cup B \; = \; A\cup(\overline{A}\cap B)\)

    3. \(A\triangle B \; = \; (A\cup B)\setminus(A\cap B)\)

    4. \((A\cup B)\setminus C \; = \; (A\setminus C)\cup(B\setminus C)\)

    \begin{gather*} x \in \overline{A\cap B}\\ \iff \; {\lnot}(x \in A\cap B)\\ \iff \; {\lnot}(x \in A \; \land \; x \in B)\\ \iff \; {\lnot}(x \in A) \; \lor \; {\lnot}(x \in B)\\ \iff \; x \in \overline{A} \; \lor \; x \in \overline{B}\\ \iff \; x \in \overline{A} \cup \overline{B} \end{gather*}

  5. For each positive integer \(n\), we'll define an interval \(I_n\) by \begin{equation*} I_n = [-n, 1/n). \end{equation*} Find the union and intersection of all the intervals in this infinite family. \begin{equation*} \bigcup_{n \in \Naturals} I_n = \end{equation*} \begin{equation*} \bigcap_{n \in \Naturals} I_n = \end{equation*} \hint{To better understand what is going on, first figure out what the first three or four intervals actually are. \begin{equation*} I_1 \; = \; \underline{} \end{equation*} \begin{equation*} I_2 \; = \; \underline{} \end{equation*} \begin{equation*} I_3 \; = \; \underline{} \end{equation*} \begin{equation*} I_4 \; = \; \underline{} \end{equation*} Any negative real number \(r\) will be in the intersection only if \(r \geq -1\). Certainly \(0\) is in the intersection since it is in each of the intervals. Are there any positive numbers in the intersection? In order to be in the union a real number just needs to be in one of the intervals. }

  6. There is a set \(X\) such that, for all sets \(A\), we have \(X \triangle A = A\). What is \(X\)?

  7. There is a set \(Y\) such that, for all sets \(A\), we have \(Y \triangle A = \overline{A}\). What is \(Y\)? \hint{One of the answers to the last two questions is \(\emptyset\) and the other is \(U\). Decide which is which.}

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

  9. 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)\). \hint{This exercise, as well as the previous one, is really just about converting set-theoretic statements into their logical equivalents, applying some rules of logic that we've already verified, and then returning to a set-theoretic version of things.}

  10. Prove the set-theoretic versions of DeMorgan's laws using the technique discussed in the previous problems.

  11. The previous technique (showing that \(A=B\) by arguing that \(A \subseteq B \; \land \; B \subseteq A\)) will have an outline something like

    Proof
    Formulate a proof that \(A \triangle B \; = \; (A \cup B) \setminus (A \cap B)\) that follows this outline. \hint{The definition of \(A \triangle B\) is \((A\setminus B) \cup (B\setminus A)\). The definition of \(X \setminus Y\) is \(X \cap \overline{Y}\). Restating things in terms of \(\cap\) and \(\cup\) (and complementation) should help. So your first few lines should be:
    Suppose \(x \in A \triangle B\). Then, by definition, \(x \in (A\setminus B) \cup (B\setminus A)\). So, \(x \in (A \cap \overline{B}) \cup (B \cap \overline{A})\). \(\vdots\)
    }