Discrete Mathematics : Sets

Contents

• Concepts
• Element Argument

Concepts

What is a set?

A set is a collection of related items

Examples:

• $A = \{ 1, 2, 3, 4, 5 \}$
• $P = \{ 2, 3, 5, 7, 11, 13, 17, \ldots \}$
• $S$ is a set of square numbers
• $B = \{ m \in \mathbb{Z} ~|~ m = 7n + 100 \text{ for some } n \in \mathbb{Z}\}$

Subsets

• Subset. $A \subseteq B \Leftrightarrow \forall x, \text{ if } x \in A \text{ then } x \in B$
• Not subset. $A \nsubseteq B \Leftrightarrow \exists x \text{ such that } x \in A \text{ and } x \not\in B$
• Proper subset. $A \subset B \Leftrightarrow$
  1. $A \subseteq B$
  2. $\exists x \text{ such that } x \in B \text{ and } x \not\in A$

Examples:

• Let $A = \{1\}$ and $B = \{1,\{1\}\}$.
  1. $(a)$ Is $A \subseteq B?$
  2. $(b)$ Is $A \subset B?$
• Let $A = \{m \in \mathbb{Z} ~|~ m = 6r + 12 \text{ for some } r \in \mathbb{Z} \}$ and $B = \{n \in \mathbb{Z} ~|~ n = 3s \text{ for some } s \in \mathbb{Z} \}$.
  1. $(a)$ Prove that $A \subseteq B$.
  2. $(b)$ Disprove that $B \subseteq A$.

Set equality

• Given sets $A$ and $B$, $A$ equals $B$, written $A = B$, if, and only if, every element of $A$ is in $B$ and every element of $B$ is in $A$.
• $A = B \Leftrightarrow A \subseteq B$ and $B \subseteq A$.

Examples:

• $A = \{m \in \mathbb{Z} ~|~ m = 2a \text{ for some integer } a \}$
  $B = \{n \in \mathbb{Z} ~|~ n = 2b - 2 \text{ for some integer } b \}$
  Is $A = B$?

Venn diagrams

• Relationship between a small number of sets can be represented by pictures called Venn diagrams
• Venn diagram for $A \subseteq B$
  
• Venn diagram for $A \not\subseteq B$
  

Examples:

• Write a Venn diagram representing sets of numbers: $\mathbb{N}, \mathbb{W}, \mathbb{Q}, \mathbb{R}$.

Operations on sets

Let $A$ and $B$ be subsets of a universal set $U$.

1. The union of $A$ and $B$, denoted $A \cup B$, is the set of all elements that are in at least one of $A$ or $B$.
   $A \cup B = \{ x \in U ~|~ x \in A \text{ or } x \in B \}$
2. The intersection of $A$ and $B$, denoted $A \cap B$, is the set of all elements that are common to both $A$ and $B$.
   $A \cap B = \{ x \in U ~|~ x \in A \text{ and } x \in B \}$
3. The difference of $B$ minus $A$ (or relative complement of $A$ in $B$), denoted $B - A$, is the set of all elements that are in $B$ and not $A$.
   $B - A = \{ x \in U ~|~ x \in B \text{ and } x \not\in A \}$
4. The complement of $A$, denoted $A'$, is the set of all elements in $U$ that are not in $A$.
   $A' = \{ x \in U ~|~ x \not\in A \}$

Examples:

• Let the universal set $U = \{a, b, c, d, e, f, g\}$.
  Let $A = \{a, c, e, g\}$ and $B = \{d, e, f, g\}$.
  Find $A \cup B$, $A \cap B$, $B - A$, and $A'$.

Operations on sets

Given real numbers $a$ and $b$ with $a \le b$:

• $(a, b) = \{ x \in \mathbb{R} ~|~ a < x < b \}$
  $[a, b] = \{ x \in \mathbb{R} ~|~ a \le x \le b \}$
  $(a, b] = \{ x \in \mathbb{R} ~|~ a < x \le b \}$
  $[a, b) = \{ x \in \mathbb{R} ~|~ a \le x < b \}$
• The symbols $\infty$ and $-\infty$ are used to indicate intervals that are unbounded either on the right or on the left:
  $(a, \infty) = \{ x \in \mathbb{R} ~|~ x > a \}$
  $[a, \infty) = \{ x \in \mathbb{R} ~|~ x \ge a \}$
  $(-\infty, b) = \{ x \in \mathbb{R} ~|~ x < b \}$
  $(-\infty, b] = \{ x \in \mathbb{R} ~|~ x \le b \}$

Examples:

• $A = (-1, 0] = \{x \in \mathbb{R} ~|~ -1 < x \le 0 \}$
  $B = [0, 1) = \{x \in \mathbb{R} ~|~ 0 \le x < 1 \}$.
  Find $A \cup B$, $A \cap B$, $B - A$, and $A'$.

Operations on sets

Given sets $A_0, A_1, A_2, \ldots$ that are subsets of a universal set $U$ and given a nonnegative integer $n$,

• $\cup_{i=0}^{n} A_i = \{ x \in U ~|~ x \in A_i \text{ for at least one } i = 0, 1, 2, \ldots, n \}$
• $\cup_{i=0}^{\infty} A_i = \{ x \in U ~|~ x \in A_i \text{ for at least one whole number } i \}$
• $\cap_{i=0}^{n} A_i = \{ x \in U ~|~ x \in A_i \text{ for all } i = 0, 1, 2, \ldots, n \}$
• $\cap_{i=0}^{\infty} A_i = \{ x \in U ~|~ x \in A_i \text{ for all whole numbers } i \}$

Examples:

• For each positive integer $i$, let
  $A_i = \{ x \in \mathbb{R} ~|~ -\frac{1}{i} < x < \frac{1}{i} \} = \left( -\frac{1}{i}, \frac{1}{i} \right)$
  Find $A_1 \cup A_2 \cup A_3$ and $A_1 \cap A_2 \cap A_3$
  Find $\cup_{i=0}^{\infty} A_i$ and $\cap_{i=0}^{\infty} A_i$

Empty set

Empty set, denoted by $\phi$, is a set with no elements.

Examples:

• $\{1, 3\} \cap \{2, 4\} = \phi$
• $\{ x \in \mathbb{R} ~|~ x^2 = -1 \} = \phi$
• $\{ x \in \mathbb{R} ~|~ 3 < x < 2 \} = \phi$

Disjoint sets

• Two sets are called disjoint if, and only if, they have no elements in common.
• $A$ and $B$ are disjoint $\Leftrightarrow A \cap B = \phi$

Examples:

• Let $A = \{ 1, 3, 5 \}$ and $B = \{ 2, 4, 6 \}$. Are $A$ and $B$ disjoint?

Mutually disjoint sets

• Sets $A_1, A_2, A_3, \ldots$ are mutually disjoint (or pairwise disjoint or nonoverlapping) if, and only if, no two sets $A_i$ and $A_j$ with distinct subscripts have any elements in common.
• For all $i, j = 1, 2, 3, \ldots$
  $A_i \cap A_j = \phi$ whenever $i \not= j$.

Examples:
Are the following sets mutually disjoint?

• $A_1 = \{ 3, 5 \}$, $A_2 = \{ 1, 4, 6 \}$, and $A_3 = \{ 2 \}$.
• $B_1 = \{ 2, 4, 6 \}$, $B_2 = \{ 3, 7 \}$, and $B_3 = \{ 4, 5 \}$.

Partition of a set

• A finite or infinite collection of nonempty sets $\{A_1, A_2, A_3, \ldots \}$ is a partition of a set $A$ if, and only if,
  1. $A$ is the union of all the $A_i$
  2. The sets $A_1, A_2, A_3, \ldots$ are mutually disjoint.

Examples:

• Let $A = \{ 1, 2, 3, 4, 5, 6 \}$, $A_1 = \{ 1, 2 \}$, $A_2 = \{ 3, 4 \}$, and $A_3 = \{ 5, 6 \}$. Is $\{ A_1, A_2, A_3 \}$ a partition of $A$?
• Let $\mathbb{Z}$ be the set of all integers and let
  $T_0 = \{n \in \mathbb{Z} ~|~ n = 3k, \text{ for some integer } k\},$
  $T_1 = \{n \in \mathbb{Z} ~|~ n = 3k + 1, \text{ for some integer } k\},$
  $T_2 = \{n \in \mathbb{Z} ~|~ n = 3k + 2, \text{ for some integer } k\},$
  Is $\{T_0, T_1, T_2\}$ a partition of $\mathbb{Z}$?

Power set

• Given a set $A$, the power set of $A$, denoted $P(A)$, is the set of all subsets of $A$.

Examples:

• Find the power set of the set $\{x, y\}$. That is, find $P(\{x, y\})$.

Ordered $n$-tuple

• Ordered $n$-tuple, $(x_1, x_2, \ldots, x_n)$, consists of $x_1, x_2, \ldots, x_n$ together with the ordering.
• Ordered pair = ordered 2-tuple
  Ordered triple = ordered 3-tuple
• Two ordered $n$-tuples $(x_1, x_2, \ldots, x_n)$ and $(y_1, y_2, \ldots, y_n)$ are equal if, and only if, $x_1 = y_1, x_2 = y_2, \ldots, x_n = y_n$.
  $(x_1, x_2, \ldots, x_n) = (y_1, y_2, \ldots, y_n) \Leftrightarrow x_1 = y_1, \ldots, x_n = y_n$.

Examples:

• Is $(1, 2, 3, 4) = (1, 2, 4, 3)$?
• Is $\left( 3, (-2)^2, \frac{1}{2} \right) = \left(\sqrt{9}, 4, \frac{3}{6} \right)$?
• Is $((1, 2), 3) = (1, 2, 3)$?

Cartesian product

• Given sets $A_1, A_2, \ldots, A_n$, the Cartesian product of $A_1, A_2, \ldots, A_n$ denoted $A_1 \times A_2 \times \cdots \times A_n$, is the set of all ordered $n$-tuples $(a_1, a_2, \ldots, a_n)$ where $a_1 \in A_1, a_2 \in A_2, \ldots, a_n \in A_n$.
• $A_1 \times A_2 \times \cdots \times A_n$
  $= \{ (a_1, a_2, \ldots, a_n) ~|~ a_1 \in A_1, a_2 \in A_2, \ldots, a_n \in A_n \}.$

Examples:

• Let $A_1 = \{ x, y \}$, $A_2 = \{ 1, 2, 3 \}$, and $A_3 = \{ a, b \}$. Find:
  $(a)$ $A_1 \times A_2$,
  $(b)$ $(A_1 \times A_2) \times A_3$, and
  $(c)$ $A_1 \times A_2 \times A_3$.

Properties of sets

• Inclusion of intersection: For all sets $A$ and $B$,
  $A \cap B \subseteq A$ and $A \cap B \subseteq B$.
• Inclusion in union: For all sets $A$ and $B$,
  $A \subseteq A \cup B$ and $B \subseteq A \cup B$.
• Transitive property of subsets: For all sets $A$, $B$, and $C$,
  if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Procedural versions of set definitions

Let $X$ and $Y$ be subsets of a universal set $U$ and suppose $x$ and $y$ are elements of $U$.

• $x \in X \cup Y \Leftrightarrow x \in X$ or $x \in Y$
• $x \in X \cap Y \Leftrightarrow x \in X$ and $x \in Y$
• $x \in X - Y \Leftrightarrow x \in X$ and $x \not\in Y$
• $x \in X' \Leftrightarrow x \not\in X$
• $(x, y) \in X \times Y \Leftrightarrow x \in X$ and $y \in Y$

Set identities

Element Argument

Type 1: Prove that a set is a subset of another

• Let sets $X$ and $Y$ be given. To prove that $X \subseteq Y$,
  1. suppose that $x$ is a particular but arbitrarily chosen element of $X$.
  2. show that $x$ is an element of $Y$.

Type 2: Prove that two sets are equal

• Let sets $X$ and $Y$ be given. To prove that $X = Y$,
  1. Prove that $X \subseteq Y$.
  2. Prove that $Y \subseteq X$.

Type 3: Prove that a set equals the empty set

• To prove that a set $X$ is equal to the empty set $\phi$, prove that $X$ has no elements.
• To do this, suppose $X$ has an element and derive a contradiction.

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Proof

We need to prove:

1. $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$
2. $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$

1. Prove that $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$.
Suppose $x \in A \cup (B \cap C)$.
$x \in A$ or $x \in B \cap C$     $(\because \text{defn. of union})$

• Case 1. $[x \in A.]$
  $x \in A \cup B$     $(\because \text{defn. of union})$
  $x \in A \cup C$     $(\because \text{defn. of union})$
  $x \in (A \cup B) \cap (A \cup C)$     $(\because \text{defn. of intersection})$
• Case 2. $[x \in B \cap C.]$
  $x \in B$ and $x \in C$     $(\because \text{defn. of intersection})$
  $x \in A \cup B$     $(\because \text{defn. of union})$
  $x \in A \cup C$     $(\because \text{defn. of union})$
  $x \in (A \cup B) \cap (A \cup C)$     $(\because \text{defn. of intersection})$

2. Prove that $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$.
Suppose $x \in (A \cup B) \cap (A \cup C)$.
$x \in A \cup B$ and $x \in A \cup C$     $(\because \text{defn. of intersection})$

• Case 1. $[x \in A.]$
  $x \in A \cup (B \cap C)$     $(\because \text{defn. of union})$
• Case 2. $[x \not\in A.]$
  $x \in A$ or $x \in B$     $(\because \text{defn. of union})$
  $x \in B$     $(\because x \not\in A)$
  $x \in A$ or $x \in C$     $(\because \text{defn. of union})$
  $x \in C$     $(\because x \not\in A)$
  $x \in B \cap C$     $(\because \text{defn. of intersection})$
  $x \in A \cup (B \cap C)$     $(\because \text{defn. of union})$

$(A \cup B)' = A' \cap B'$

Proof

We need to prove:

1. $(A \cup B)' \subseteq A' \cap B'$
2. $A' \cap B' \subseteq (A \cup B)'$

1. Prove that $(A \cup B)' \subseteq A' \cap B'$.
   Suppose $x \in (A \cup B)'$.
   $x \not\in A \cup B$     $(\because \text{defn. of complement})$
   It is false that ($x$ is in $A$ or $x$ is in $B$).
   $x$ is not in $A$ and $x$ is not in $B$     $(\because \text{De Morgan's law of logic})$
   $x \not\in A$ and $x \not\in B$
   $x \in A'$ and $x \in B'$     $(\because \text{defn. of complement})$
   $x \in (A' \cap B')$     $(\because \text{defn. of intersection})$
   Hence, $(A \cup B)' \subseteq A' \cap B'$     $(\because \text{defn. of subset})$
2. Prove that $A' \cap B' \subseteq (A \cup B)'$.
   Suppose $x \in A' \cap B'$.
   $x \in A'$ and $x \in B'$     $(\because \text{defn. of intersection})$
   $x \not\in A$ and $x \not\in B$     $(\because \text{defn. of complement})$
   $x$ is not in $A$ and $x$ is not in $B$
   It is false that ($x$ is in $A$ or $x$ is in $B$)     $(\because \text{De Morgan's law of logic})$
   $x \not\in A \cup B$
   $x \in (A \cup B)'$     $(\because \text{defn. of complement})$
   Hence, $A' \cap B' \subseteq (A \cup B)'$     $(\because \text{defn. of subset})$

$A \cap B = A$ and $A \cup B = B$

Proof

Part $(a)$: We need to prove:

1. $A \cap B \subseteq A$
2. $A \subseteq A \cap B$

Part $(b)$: We need to prove:

1. $A \cup B \subseteq B$
2. $B \subseteq A \cup B$

Part $(a)$.

1. Proof that $A \cap B \subseteq A$.
   $A \cap B \subseteq A$     $(\because \text{inclusion of intersection})$
2. Proof that $A \subseteq A \cap B$.
   Suppose $x \in A$
   $x \in B$     $(\because A \subseteq B)$
   $x \in A$ and $x \in B$
   $x \in A \cap B$     $(\because \text{defn. of intersection})$

Part $(b)$.

1. Proof that $A \cup B \subseteq B$.
   Suppose $x \in A \cup B$
   $x \in A$ or $x \in B$     $(\because \text{defn. of union})$
   If $x \in A$, then $x \in B$     $(\because A \subseteq B)$
   $x \in B$     $(\because \text{Modus Ponens and division into cases})$
2. Proof that $B \subseteq A \cup B$.
   $B \subseteq A \cup B$     $(\because \text{inclusion in union})$

$E \subseteq A$

Proof

Proof by contradiction.

• Suppose there exists a set $E$ with no elements and a set $A$ such that $E \not\subseteq A$.
• $\exists x$ such that $x \in E$ and $x \not\in A$     $(\because \text{defn. of a subset})$
• But there can be no such element since $E$ has no elements.
• Contradiction!
• Hence, if $E$ is a set with no elements and $A$ is any set, then $E \subseteq A$.

Only one empty set

Proof

• Suppose $E_1$ and $E_2$ are both sets with no elements.
• $E_1 \subseteq E_2$     $(\because \text{previous proposition})$
• $E_2 \subseteq E_1$     $(\because \text{previous proposition})$
• Thus, $E_1 = E_2$

$A \cap \phi = \phi$

Proof

Proof by contradiction.

• Suppose there is an element $x$ such that $x \in A \cap \phi$
• $x \in A$ and $x \in \phi$     $(\because \text{defn. of intersection})$
• $x \in \phi$
• Impossible because $\phi$ cannot have any elements
• Hence, the supposition is incorrect.
• So, $A \cap \phi = \phi$

If $A \subseteq B$ and $B \subseteq C'$, then $A \cap C = \phi$

Proof

Proof by contradiction.

• Suppose there is an element $x$ such that $x \in A \cap C$
• $x \in A$ and $x \in C$     $(\because \text{defn. of intersection})$
• $x \in A$
• $x \in B$     $(\because x \in A \text{ and } A \subseteq B)$
• $x \in C'$     $(\because x \in B \text{ and } B \subseteq C')$
• $x \not\in C$     $(\because \text{defn. of complement})$
• $x \in C$ and $x \not\in C$
• Contradiction!
• Hence, the supposition is incorrect.
• So, $A \cap C = \phi$

Proof by counterexample: $(A - B) \cup (B - C) = A - C$

Disproof

False!
$(A - B) \cup (B - C) \not= A - C$

• Draw Venn diagrams
• Counterexample 1: $A = \{ 1 \}$, $B = \phi$, $C = \{ 1 \}$
• Counterexample 2: $A = \phi$, $B = \{ 1 \}$, $C = \phi$

Proof by induction: $|\text{PowerSet}(X)| = 2^n$

Proof

Let $P(n)$ denote "Any set with $n$ elements has $2^n$ subsets."

• Basis step. $P(0)$ is true.
  The only set with zero elements is the empty set. The only subset of the empty set is itself. Hence, $2^0 = 1$.
• Induction step. Suppose that $P(k)$ is true for any $k \ge 0$.
  i.e., "Any set with $k$ elements has $2^k$ subsets."
  Now, we want to show that $P(k+1)$ is true.
  i.e., "Any set with $k+1$ elements has $2^{k+1}$ subsets."
  Suppose set $X$ has $k+1$ elements including element $a$.
  #subsets of $X$
  $=$ #subsets of $X$ without $a$ + #subsets of $X$ with $a$
  $=$ #subsets of $(X - \{ a \})$ + #subsets of $X$ with $a$
  $=$ #subsets of $(X - \{ a \})$ + #subsets of $(X - \{ a \})$
       $(\because$ 1:1 correspondence$)$
  $= 2 \cdot$ #subsets of $(X - \{ a \})$
  $= 2 \cdot 2^k$
  $= 2^{k+1}$
  Hence, $P(k+1)$ is true.

1:1 correspondence: Any subset $A$ of $X - \{a\}$ can be matched up with a subset $B$, equal to $A \cup \{a\}$, of $X$ that contains $a$.

Algebraic proof: $(A \cup B) - C = (A - C) \cup (B - C)$

Proof

• $(A \cup B) - C$
  $= (A \cup B) \cap C'$     $(\because \text{set difference law})$
  $= C' \cap (A \cup B)$     $(\because \text{commutative law})$
  $= (C' \cap A) \cup (C' \cap B)$     $(\because \text{distributive law})$
  $= (A \cap C') \cup (B \cap C')$     $(\because \text{commutative law})$
  $= (A - C) \cup (B - C)$     $(\because \text{set difference law})$

Algebraic proof: $A - (A \cap B) = A - B$

Proof

• $A - (A \cap B)$
  $= A \cap (A \cap B)'$     $(\because \text{set difference law})$
  $= A \cap (A' \cup B')$     $(\because \text{De Morgan's law})$
  $= (A \cap A') \cup (A \cap B')$     $(\because \text{distributive law})$
  $= \phi \cup (A \cap B')$     $(\because \text{complement law})$
  $= (A \cap B') \cup \phi$     $(\because \text{commutative law})$
  $= A \cap B'$     $(\because \text{identity law})$
  $= A - B$     $(\because \text{set difference law})$