EF Complement, union, and intersection

Section 9.4 Complement, union, and intersection

First, it is often convenient to restrict the scope of the discussion.

universal set: 🔗
a set that contains all objects currently under consideration

We will consider all of the following set operations to be performed within a universal set

U .

In particular, suppose

A, B \subseteq U .

🔗

Subsection 9.4.1 Universal and relative complement

🔗

complement: 🔗
the set of elements of $U$ which are not in $A$
$A^{c}$: 🔗

🔗
the complement of $A$ (in $U$ ), so that

$A^{c} = {x \in U | x \notin A}$
relative complement: 🔗
if $A, B \subseteq U,$ the complement of $A$ in $B$ is the set of elements of $B$ which are not in $A$
$B ∖ A$: 🔗

🔗
the complement of $A$ in $B,$ so that

$B ∖ A = {x \in B | x \notin A}$

A Venn diagram of a (universal) set complement. — 🔗
Figure 9.4.1. Venn diagrams of universal and relative set complements.

A Venn diagram of a relative set complement. — 🔗
Figure 9.4.1. Venn diagrams of universal and relative set complements.

🔗

Note 9.4.2.

🔗

Another common notation for relative complement is

B - A .

However, this conflicts with the notation for the algebraic operation of subtraction in certain contexts, so we will prefer the notation

B ∖ A .

🔗

Example 9.4.3. Some examples of relative complement involving number sets.

🔗

🔗
Suppose $B = {1, 2, 3, 4, 5, 6}$ and $A = {1, 3, 5} .$ Then $B ∖ A = {2, 4, 6} .$
🔗
The complement of the set of rational numbers $Q$ inside the set of real numbers $R$ is called the set of irrational numbers, and we write $I = R ∖ Q$ for this set. If you are thinking of real numbers in terms of their decimal expanions, the irrational numbers are precisely those that have nonterminating, nonrepeating decimal expansions.

🔗

Subsection 9.4.2 Union, intersection, and disjoint sets

🔗

union: 🔗
the combined collection of all elements in a pair of sets
$A \cup B$: 🔗

🔗
the union of sets $A$ and $B,$ so that

$A \cup B = {x \in U | x \in A or x \in B (or both)}$
intersection: 🔗
the collection of only those elements common to a pair of sets
$A \cap B$: 🔗

🔗
the intersection of $A$ and $B,$ so that

$A \cap B = {x \in U | x \in A and x \in B}$

A Venn diagram of a set union. — 🔗
Figure 9.4.4. Venn diagrams of set union and intersection.

A Venn diagram of a set intersection. — 🔗
Figure 9.4.4. Venn diagrams of set union and intersection.

🔗

Note 9.4.5.

🔗

A union contains every element from both sets, so it contains both sets as subsets:

A, B \subseteq A \cup B .

🔗

On the other hand, every element in an intersection is in both sets, so the intersection is a subset of both sets:

A \cap B \subseteq A, B .

🔗

Example 9.4.6.

🔗

For subsets

A = {1, 2, 3, 4}

and

B = {3, 4, 5, 6}

N,

we have

\begin{aligned} A \cup B & = {1, 2, 3, 4, 5, 6}, & A \cap B & = {3, 4} . \end{aligned}

🔗

Example 9.4.7.

🔗

Consider the following subsets of

N .

\begin{aligned} E & = {n \in N | n even} & P & = {n \in N | n prime, n \neq 0} \\ O & = {n \in N | n odd} & T & = {3 n | n \in N} = {0, 3, 6, 9, \dots} \end{aligned}

🔗

Then,

\begin{aligned} E \cup O & = N, & E \cap P & = {2}, & E \cap T & = {6 n | n \in N}, \\ E \cap O & = \emptyset, & O \cap P & = P ∖ {2}, & O \cap T & = {6 n + 3 | n \in N} . \end{aligned}

🔗

disjoint sets: 🔗
sets that have no elements in common, i.e. sets $A, B$ such that $A \cap B = \emptyset$
disjoint union: 🔗
a union $A \cup B$ where $A$ and $B$ are disjoint
$A ⊔ B$: 🔗
the disjoint union of sets $A$ and $B$

🔗
Figure 9.4.8. A Venn diagram of a disjoint set union.

🔗

Example 9.4.9.

🔗

Sets

E, O

from Example 9.4.7 are disjoint, and

N = E ⊔ O .

🔗

Remark 9.4.10.

🔗

A \subseteq U,

then we can express

U

as a disjoint union

U = A ⊔ A^{c} .

Similarly, if

U = A ⊔ B,

then we must have

B = A^{c} .

🔗

Subsection 9.4.3 Rules for set operations

🔗

Proposition 9.4.11. Rules for Operations on Sets.

🔗

Suppose

A, B, C

are subsets of a universal set

U .

Then the following set equalities hold.

Properties of the universal set.
🔗
1. 🔗
  $A \cup U = U$
2. 🔗
  $A \cap U = A$
Properties of the empty set.
🔗
1. 🔗
  $A \cup \emptyset = A$
2. 🔗
  $A \cap \emptyset = \emptyset$
Duality of universal and empty sets.
🔗
1. 🔗
  $U^{c} = \emptyset$
2. 🔗
  $\emptyset^{c} = U$
Double complement.
🔗
${(A^{c})}^{c} = A$
Idempotence.
🔗
1. 🔗
  $A \cup A = A$
2. 🔗
  $A \cap A = A$
Commutativity.
🔗
1. 🔗
  $A \cup B = B \cup A$
2. 🔗
  $A \cap B = B \cap A$
Associativity.
🔗
1. 🔗
  $(A \cup B) \cup C = A \cup (B \cup C)$
2. 🔗
  $(A \cap B) \cap C = A \cap (B \cap C)$
Distributivity.
🔗
1. 🔗
  $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
2. 🔗
  $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
3. 🔗
  $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$
4. 🔗
  $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$
DeMorgan’s Laws.
🔗
1. 🔗
  ${(A \cup B)}^{c} = A^{c} \cap B^{c}$
2. 🔗
  ${(A \cap B)}^{c} = A^{c} \cup B^{c}$

🔗

Proof of Rule 9.a.

Recall that to prove this set equality, we need to show both

\begin{aligned} {(A \cup B)}^{c} & \subseteq A^{c} \cap B^{c}, & A^{c} \cap B^{c} & \subseteq {(A \cup B)}^{c} . \end{aligned}

Show ${(A \cup B)}^{c} \subseteq A^{c} \cap B^{c}$ .

We need to show

x \in {(A \cup B)}^{c} \Rightarrow x \in A^{c} \cap B^{c} .

x \in {(A \cup B)}^{c}

then by definition of complement,

x \in U

but

x \notin A \cup B .

Then

x \notin A

must be true, since if

x

were in

A

then it would also be in

A \cup B .

Similarly,

x \notin B

must also be true. So

x \in A^{c}

and

x \in B^{c};

i.e.

x \in A^{c} \cap B^{c} .

Show $A^{c} \cap B^{c} \subseteq {(A \cup B)}^{c}$ .

We need to show

x \in A^{c} \cap B^{c} \Rightarrow x \in {(A \cup B)}^{c} .

x \in A^{c} \cap B^{c}

then by definition of intersection, both

x \in A^{c}

and

x \in B^{c}

are true.; i.e.

x \notin A

and

x \notin B .

Since

A \cup B

is all elements of

U

which are in one (or both) of

A, B,

we must have

x \notin A \cup B .

Thus

x \in {(A \cup B)}^{c} .

🔗

Proofs of the other rules.

These are left to you, the reader, in the Exercise 9.9.1.

🔗

Remark 9.4.12.

🔗

Compare the set operation rules of the proposition above with the Rules of Propositional Calculus.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 9.4 Complement, union, and intersection