Set operations

Section 8.2 Set operations

The first two set operations we’ll discuss are union and intersection. Rather than having more discursive blurb, the authors should get on with it and just define them.

Definition 8.2.1.

Let \(A\) and \(B\) be sets. The union of \(A\) and \(B\text{,}\) denoted \(A \cup B\text{,}\) is the set of all elements in \(A\) or \(B\text{.}\)

\begin{align*} A \cup B &= \{x \so x\in A \text{ or } x \in B \} \end{align*}

A couple of things to note here. First — the symbol “\(\cup\)” is not the letter “u”. Second — we are using the word “or” in the definition in its inclusive mathematical sense. Indeed we could rewrite the above definition as

\begin{align*} (x\in A \cup B) & \iff (x \in A) \lor (x \in B) \end{align*}

We’ll draw some pictures to help illustrate things shortly. But first, another definition.

Definition 8.2.2.

Let \(A\) and \(B\) be sets. The intersection of \(A\) and \(B\text{,}\) denoted \(A \cap B\text{,}\) to be the set of elements that belong to both \(A\) and \(B\text{.}\)

\begin{align*} A \cap B &= \{ x \so x\in A \text{ and } x \in B \} \end{align*}

If the intersection \(A \cap B = \es\text{,}\) then we say that \(A\) and \(B\) are disjoint.

Again, the symbol “\(\cap\)” is not an upside-down letter “u”, and we are using the word “and” in this definition in its precise mathematical meaning. Just as we rewrote the definition of union, we can rewrite the definition of intersection as

\begin{align*} (x\in A \cap B) & \iff (x \in A) \land (x \in B) \end{align*}

Indeed there are many parallels between how the operators union and intersection act on sets and how the logical operators “or” and “and” act on mathematical statements. These parallel are reinforced by the similarity in notations.

Warning 8.2.3. The right notation in the right place..

Please be careful to not confuse set and logical operations. When \(A\) and \(B\) are sets, we cannot take their conjunction or disjunction: “\(A \lor B\)” “\(A\land B\)” do not make sense. Similarly, if \(P\) and \(Q\) are statements we cannot take their union or intersection: “\(P\cup Q\)” and “\(P \cap Q\)” do not make sense.

Example 8.2.4.

Let \(A = \{1,2,3,4 \}\text{,}\) \(B = \{p : p \mbox{ is prime} \}\text{,}\) \(C = \{5,7,9\}\) and \(D = \{\mbox{even positive integers}\}\text{.}\) Then

\begin{align*} A \cap B &= \set{2,3}\\ B \cap D &= \set{2}\\ A \cup C &= \set{1,2,3,4,5,7,9}\\ A \cap C &= \es \end{align*}

We can visualise the operations of union and intersection using a Venn diagram⁹⁴. These diagrams might seem like an obvious and simple idea, however it is much more recent than the cartesian plane. Venn diagrams are 19th century mathematics, while the cartesian plane is 17th century mathematics⁹⁵.

Remark 8.2.5. Long equations, sides, and short-hands.

Some of the results we want to prove (like the one coming shortly) involve showing that a long expression on one side of an equality is actually the same as the long expression on the other side. To ease both the writer and the reader of the resulting calculations, we refer to the expressions on either side⁹⁶ as “the left-hand side” and “the right-hand side”. In typical mathematician style, even this is too long and they are almost always contracted further to “LHS” and “RHS”. This shorthand allows us to avoid writing (and reading) chunks of text (with the associated potential errors), but, perhaps more importantly, allows us to indicate that one side of an equation remains fixed unchanged while we work on the other.

Here is a good example adapted from one in “The book of proof” by Richard Hammack ⁹⁷.

Example 8.2.6.

Let

\begin{align*} A &= \set{n \in \mathbb{Z} \;:\; 15|n}& B &= \set{n \in \mathbb{Z} \;:\; 3|n}& C &= \set{n \in \mathbb{Z} \;:\; 5|n} \end{align*}

Prove that \(A = B \cap C\text{.}\)

Scratchwork.

So — scratch work first. To prove the equality we need to show that the LHS is a subset of the RHS and vice versa. So we start by proving that \(A \subseteq B\cap C\text{.}\)

Let \(a \in A\text{,}\) so \(a\) is an integer divisible by 15.
Hence we can write \(a=15k\text{.}\)
We now need to show that \(a\in B\) and \(a\in C\text{,}\) so that \(a \in B\cap C\text{.}\)
Well, since \(a=15k\) we know that \(a=3(5k)\text{,}\) and because \(5k \in \mathbb{Z}\text{,}\) \(a\) is divisible by 3. Hence \(a \in B\text{.}\)
Similarly, since \(a=15k\) we know that \(a=5(3k)\text{,}\) and because \(3k \in \mathbb{Z}\text{,}\) \(a\) is divisible by 5. Hence \(a \in C\text{.}\)
Since \(a \in B\) and \(a\in C\text{,}\) we know that \(a\in B\cap C\text{.}\)

Thus \(A\subseteq B\cap C\text{.}\)

Now we must argue that \(B \cap C \subseteq A\text{.}\)

Let \(x\in B\cap C\text{.}\) Notice that we’re calling it \(x\) rather than \(b\) or \(c\) since that is a more neutral letter, while \(b\) or \(c\) suggest that the element might belong to \(B\) or \(C\) but not both.
Since \(x\in B \cap C\) we know that \(x\in B\) and that \(x\in C\text{.}\)
Because \(x\in B\text{,}\) \(x=3k\) for some integer \(k\text{.}\)
Similarly, because \(x\in C\text{,}\) we know that \(x=5\ell\) for some integer \(\ell\text{.}\) Notice that we did not write \(x=5k\) since we have already used \(k\) to express that \(x\) is divisible by 3.
This implies that \(x=3k=5\ell\text{,}\) and we are close to being done.
Since \(5\ell=3k\) we know that \(5\ell\) is divisible by 3. We’d like to show that \(\ell\) is a multiple by 3 (which would make sense because 3 and 5 are prime numbers⁹⁸). Perhaps the easiest way to do this is to investigate what happens if \(\ell\) is a multiple of 3 or not. There are 3 possibilities, \(\ell = 3j, 3j+1, 3j+2\text{,}\) for some integer \(j\) (we are using Euclidean division here).
- If \(\ell = 3j\) then \(5\ell = 15j\) which is precisely what we want.
- If \(\ell = 3j+1\) then \(5\ell = 15j+5 = 3(5j+1)+2\text{,}\) and so \(5\ell\) is not divisible by 3. But this contradicts the fact that \(x \in B\text{.}\)
- Similarly \(\ell = 3j+2\) then \(5\ell = 15j+10 = 3(5j+3)+1\text{,}\) and so \(5\ell\) is not divisible by 3. Again this contradicts the fact that \(x \in B\text{.}\)
Hence the only possibility is that \(\ell\) is a multiple of 3. Thus we can write \(x=5\ell = 5\cdot 3 \cdot j\) for some integer \(j\text{.}\)
Hence \(x\) is divisible by 15 and \(x\in A\text{.}\)

Thus \(B\cap C \subseteq A\text{.}\)

Oof! Everything is there, we just have to write it up nicely.

Solution.

Proof.

Let \(A,B,C\) be defined as above. We prove the equality by first proving that the LHS is a subset of the RHS and then vice-versa.

Let \(a \in A\text{.}\) Then \(a=15m\) for some \(m\in \mathbb{Z}\text{.}\) This means that \(a=3(5m)\) and \(a=5(3m)\text{.}\) Since both \(3m,5m \in \mathbb{Z}\text{,}\) it follows that \(a\in B\) and \(a\in C\text{.}\) Thus \(a\in B\cap C\) as required.
Now let \(x\in B\cap C\text{.}\) Then \(x=3k\) and \(x=5\ell\) for some integers \(k,\ell\text{,}\) so we must have that \(3k=5\ell\text{.}\) Since \(\ell \in \mathbb{Z}\) we know it can be written as \(\ell=3j, 3j+1\) or \(3j+2\) (by Euclidean division).
- If \(\ell=3j\) for some integer \(j\text{,}\) then \(x=5\ell=15j\) and so is a multiple of 15.
- If \(\ell=3j+1\) then \(x=15j+5 = 3(5j+1)+2\text{,}\) while if \(\ell=3j+2\) then \(x=15j+10 = 3(5j+3)+1\text{.}\) In either of these cases, we contradict our assumption that \(x\) is a multiple of 3.
Hence we must have that \(\ell=3j\text{.}\) Hence \(x=5\ell=5\cdot3j = 15(j)\) for some integer \(j\text{,}\) and so \(x\) is divisible by 15. Hence \(x\in A\) as required.

So we have shown that \(A=B\cap C\text{.}\)

Here is an alternative way to show that \(B \cap C \subseteq A\text{.}\) It relies on the fact that \(5 = 6-1\text{.}\)

Alternate proof.

Assume that \(x \in B \cap C\text{,}\) and so \(x \in B\) and \(x \in C\text{.}\) Then we know that there are \(k, \ell \in \mathbb{Z}\) so \(x=3k\) and \(x=5\ell\text{.}\) Thus we know that \(3k=5\ell\text{.}\) From this

\begin{align*} 3k \amp = 6\ell -\ell \amp \text{and thus}\\ \ell \amp = 6\ell-3k = 3(2\ell-k) \end{align*}

That is, \(\ell\) must be divisible by \(3\text{.}\) But now \(x = 5\ell = 15(2\ell-k)\) and so is divisible by 15. Thus \(x \in A\) as required.

Given two sets \(A,B\) we sometimes might need to construct a new set which contains all the elements of \(A\) that are not in \(B\text{.}\) This is the set-difference.

Definition 8.2.7.

Let \(A\) and \(B\) be sets. Then the difference, \(A - B\) (which is also written \(A \setminus B\)) is the elements in \(A\) that are not in \(B\)

\begin{align*} A - B &= \{ x \in A \so x \notin B \} \end{align*}

This new set is sometimes called the “relative complement of \(B\) in \(A\)”.

Another picture:

Example 8.2.8.

If we reuse the sets we just defined in the example Example 8.2.4 then,

\begin{align*} A - D &= \{1,3\}\\ C - A &= \{5,7,9\} \end{align*}

To define our next set operation we first need the univeral set \(U\text{.}\) This is the set from which we are taking objects to make our sets — it (essentially) tells us what domain we are working in. For many of our results \(U\) will be the set of natural numbers, for some other results \(U\) might be the set of reals. It depends on context. But given the universal set we can define our last operation.

Definition 8.2.9.

Given a universal set \(U\) and a set \(A \subset U\text{,}\) we define the complement of \(A\text{,}\) denoted \(\bar{A}\) to be the set of elements not in \(A\text{.}\)

\begin{align*} \bar{A} &= \{ x \in U | x \notin A\} \end{align*}

or equivalently:

\begin{gather*} x \in \bar{A} \iff x \not\in A \end{gather*}

Note

While it is a nice thing to say, “compl-I-ment” is not the same as “compl-E-ment”.
The complement acts on sets in much the same way that negation acts on logical statements. The complement of the complement is the original set:
\begin{equation*} \bar{\bar{A}}=A. \end{equation*}
We can express \(A - B\) using the complement as

\begin{equation*} A - B = A \cap \bar{B} \end{equation*}

Another descriptive picture:

Example 8.2.10.

Let \(U = \set{1,2,\dots,20}\text{,}\) \(A = \set{2,3,5,7,11,13,17,19}\) and \(B = \set{2,4,6,8,10,12,14,16,18,20}\text{.}\) Determine the following sets

\begin{gather*} \bar{B} \qquad A-B \qquad A \cap \bar{B} \qquad \bar{\bar{B}} \end{gather*}

Solution.

We can just chug through the definitions carefully to get

\begin{align*} \bar{B} &= \set{1,3,5,7,9,11,13,15,17,19}\\ A-B &= \set{3,5,7,11,13,17,19 }\\ A\cap\bar{B} &= \set{3,5,7,11,13,17,19 } = A - B\\ \bar{\bar{B}} &= B \end{align*}

John Venn was a 19th century English logician and mathematician. He introduced “Eulerian circles” (which later became to be known as Venn diagrams) in a paper “On the Diagrammatic and Mechanical Representation of Propositions and Reasoning”. He also built a machine to bowl cricket balls.

Or, if you look into the history a little more, 14th century.

This is, because mathematics is most commonly written sinistrodextrally (left-to-right). Though of course, we could use similar shorthand if we wrote dextrosinistrally or even boustrophedonically! It seems unlikely that anyone would write mathematics vertically. And yes, this footnote is here mostly just to use the word “boustrophedonically”.

www.people.vcu.edu/~rhammack/BookOfProof/

This proof can be made a bit more direct if we make use of the fact that every integer has a unique prime factorisation, but we haven’t proved that yet.

PLP: An introduction to mathematical proof

Search Results: