Skip to main content
Logo image

Discrete Math for Shockers

John Hammond

Section 2.2 Application: Set Equivalences

This section explores how we can apply the equivalences of logical statements to the set properties we explored in Section 1.2. It is no coincidence that those set properties look nearly identical to the logical equivalences! Instead of using Venn Diagrams, in this section we’ll use equivalences to verify statements about sets.

Subsection

Definition 2.2.1. Set operations defined via logic.

Let \(A \and B\) be sets.
  1. Subset: \(A \subseteq B \iff (x \in A) \to (x \in B)\)
  2. Union: \(x \in A \cup B \iff x \in A \lor x \in B\)
  3. Intersection: \(x \in A \cap B \iff x \in A \land x \in B\)
  4. Complement: \(x \in A \setminus B \iff x \in A \land x \not\in B\)
  5. Equality: \(A = B\) if and only if \(A \subseteq B\) and \(B \subseteq A\text{.}\)
Now that we have formally defined set properties in terms of our logical operations, we can now use our logical equivalences to formally prove statements about sets. We’ll start with this basic statement we first introduced as Theorem 1.2.7

Example 2.2.2.

Prove that if \(S\) is any set:
  1. \(\displaystyle \emptyset \subseteq S\)
  2. \(\displaystyle S \subseteq S\)
Solution.
  1. The logical statement we’re trying to prove is \((x \in \emptyset) \to (x \in S)\)
    Assume that \(x \in \emptyset\text{.}\) This is false, since nothing is in the empty set. That means that the conditional statement \((x \in \emptyset) \to (x\in S)\) is vacuously true, since the conditional \(F \to p\) is always true. Thus \(\emptyset \subseteq S\text{.}\)
  2. The logical statement we’re trying to prove is \((x \in S) \to (x\in S)\)
    Assume that \(x \in S\text{.}\) Then \(x \in S\) is trivially true. Thus \(S \subseteq S\text{.}\)
In the next example and the exercises, as you work through each proof, begin by picking one side of the equation, and writing out the logical statement according to Definition 2.2.1. Then ask yourself what logical equivalence 2.1.5 (De Morgan’s Law? Associativity? Commutitivity? Distribution?), you could apply.
Take it one line at a time.

Example 2.2.3.

Prove the following identities:
  1. \(\displaystyle A \cup \emptyset = A\)
  2. \(\displaystyle A \subseteq (A \cup B)\)
  3. \(\displaystyle A \cap (A \cup B) = A\)
  4. \(\displaystyle \overline{A \cup B} = \overline{A} \cap \overline{B}\)
Video / Answer.
Solution.
We’ll prove the first via an “if and only if” argument:
\begin{align*} x\in A \cup \emptyset \amp \iff x \in A \lor x\in \emptyset\\ \amp \iff x\in A \lor F\\ \amp \iff x\in A \end{align*}
thus \(A \cup \emptyset = A\text{.}\)
As noted above, take it one line at a time. As you review the example and check your solutions to exercises below, make sure that you understand each line. How did we get from the previous line to this one? Once you understand, move to the next. Don’t be afraid to take it slow!

Exercises Exercises

Let \(A, B, \and C\) be sets. Prove the following identities:

1.

Prove \(A \cup (B \cup C) = (A \cup B) \cup C\)
Solution.
Assume \(x\in A \cup (B \cup C)\text{,}\) then:
\begin{align*} x\in A \cup (B \cup C) \amp\equiv (x \in A) \lor (x \in B \cup C)\\ \amp\equiv (x \in A) \lor ((x \in B) \lor (x \in C))\\ \amp\equiv x \in A \lor x \in B \lor x \in C\\ \amp\equiv (x \in A \lor x \in B) \lor x \in C\\ \amp\equiv (x \in A \cup B) \lor x \in C\\ \amp\equiv x \in (\in A \cup B) \cup C \end{align*}
and so \(A \cup (B\cup C) = (A \cup B) \cup C\text{.}\)

2.

Prove \(\overline{\overline{A}} = A\)
Solution.
Assume \(x \in \overline{\overline{A}}\) then we have
\begin{align*} x \in \overline{\overline{A}} \amp \equiv \neg(x \in \overline{A})\\ \amp \equiv \neg(\neg (x \in A))\\ \amp \equiv x \in A \end{align*}
and so \(\overline{\overline{A}} = A\text{.}\)

3.

Prove \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
Solution.
Here we convert the expression of sets into a logical statement and apply the distributive law for logical statements.
Assume that \(x \in A \cup (B\cap C)\text{,}\) then:
\begin{align*} x \in A \cup (B \cap C) \amp \equiv x \in A \lor (x \in B \cap C) \\ \amp \equiv x \in A \lor (x\in B \land x \in C)\\ \amp \equiv (x \in A \lor x\in B) \land (x \in A \lor \in C)\\ \amp \equiv (x \in A \cup B) \land (x \in A \cup C)\\ \amp \equiv x \in (A \cup B) \cap (A \cup C) \end{align*}
and therefore \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{.}\)

4.

Prove \(\overline{A \cap B} = \overline{A} \cup \overline{B}\)
Solution.
Our strategy is to first convert the statement into a logical statement and then apply DeMorgan’s law for logical statements.
Assume \(x\in \overline{A \cap B}\text{.}\) Then:
\begin{align*} \neg (x \in A\cap B) \amp \equiv \neg (x \in A \land x \in B) \\ \amp \equiv \neg (x \in A) \lor \neg (x \in B)\\ \amp \equiv x \in \overline{A} \lor x \in \overline{B} \end{align*}
and so \(\overline{A \cap B} = \overline{A} \cup \overline{B}\text{.}\)

5.

Prove \(A \subseteq B\) if and only if \(\overline{B} \subseteq \overline{A}\)
Solution.
Here our “trick” is to use the fact the the contrapositive is equivalent to the conditional.
Assume \(A \subseteq B\text{.}\) This means that \(x\in A \to x \in B\text{.}\)
\begin{align*} x\in A \to x \in B \amp \equiv \neg(x\in B) \to \neg(x \in A) \\ \amp \equiv x \in \overline{B} \to x \in \overline{A} \end{align*}
and thus \(\overline{B} \subseteq \overline{A}\text{.}\)
<Prev^TopNext>