Set Theory Exercises

David Lu
July 25, 2018

Sets

1. Which of these sets are equal?
   {$x, y, z$}, {$z, y, z, x$}, {$y, x, y, z$}, {$y, z, x, y$}

2. List the elements of each set where $\mathbb{N}$ = {$1, 2, 3, ...$}.
   (a) $A =$ { $x \in \mathbb{N}$ | $3 < x < 9$}
   (b) $B =$ { $x \in \mathbb{N}$ | $x$ is even, $x < 11$}

3. Prove that $B \setminus A = B \cap \overline{A}$
   (The complement of a set $X$, $\overline{X}$ = {$x$ | $x \in \mathbb{U}$ and $x \notin X$})

4. Give some example sets that make the following statements true:
   (a) $A \cap B = A \cap C$ and $B \neq C$
   (b) $$D \cup E = D \cup F$ and $E = F$

5. Prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ (Set distributivity law)

6. Determine the validity of the following argument, using a Venn diagram:

• All my friends are musicians.
• Link is my friend.
• None of my neighbors are musicians.
  Therefore Link is not my neighbor.

7. Which of the following sets are identical?

$A = \{x | x^2 - 4x + 3 = 0\}$

$B = \{x | x^2 - 3x + 2 = 0\}$

$C = \{x | x \in \mathbb{N}, x < 3\}$

$D = \{x | x \in \mathbb{N}, x$ is odd, $x < 5\}$

$E = \{1, 2\}$

$F = \{1, 2, 1\}$

$G = \{3, 1\}$

$H = \{1, 1, 3\}$

8. Find the power set $\mathscr{P}(A)$ of $A = \{\{a, b\}, \{c\}, \{d, e, f\}\}$

---

Relations

Some examples:
If $A = \{1, 2\}$ and $B = \{a, b, c\}$, then:

$A \times B = \{\langle 1, a \rangle, \langle 1, b \rangle, \langle 1, c \rangle, \langle 2, a \rangle, \langle 2, b \rangle, \langle 2, c \rangle\}$

A binary relation $R$ from $A$ to $B$ is a subset of $A \times B$
If $\langle a, b \rangle \in R$, then we can write $Rab$ or $aRb$.
The former is typically preferred, since it allows us an easy convention for notating relationships with >2 relata, e.g. $Rabc$, and to notate the negation $\neg Rab$, using our logical vocabulary.

The inverse relation $R^{-1}$ is the relation from $B$ to $A$ which consists of the ordered pairs, which, when reversed, belong to $R$. In symbolic notation: $R^{-1} = \{\langle b, a \rangle | \langle a, b \rangle \in R\}$

1. Relations can be depicted by graphs. Draw a graph for the following relation $R$.
   $R = \{\langle 1, 2 \rangle, \langle 2, 2 \rangle, \langle 2, 4 \rangle, \langle 3, 2 \rangle, \langle 3, 4 \rangle, \langle 4, 1\rangle, \langle 4, 3 \rangle \}$

2. What does the inverse $R^{-1}$ look like?

3. Relations can also be represented as a table or two dimensional array. What would that look like? Construct one for $R$.

Relation Composition or product:
Suppose that we have three sets $A$, $B$, and $C$, a relation $R$ defined from $A$ to $B$, and a relation $S$ defined from $B$ to $C$. We can define a composition of $R$ and $S$, written $(R | S)$ (but sometimes $S \circ R$), as follows. If $a$ is an element of $A$ and $c$ is an element of $C$, then $(R | S)ac$ iff there exists some element $b$ in $B$ such that $Rab$ and $Sbc$. So we have a relation $R|S$ from $a$ to $c$ iff $a$ is $R$ related to $b$ and $b$ is $S$ related to $c$.

4. Let $A$ = {1, 2, 3, 4}, $R$ = {(1, 2), (1, 2), (2, 4), (3, 2)} ----- using () as angle brackets
   and $S$ = {(1, 4), (1, 3), (2, 3), (3, 1), (4, 1)}
   Find $R|S$.

Relations have many interesting properties. Some that we’re interested in include: reflexivity, symmetry, antisymmetry, transitivity, equivalence, and partial and total order.

5. Construct or name an example for each property.
   
   

6. Consider the following relations on the set $A$ = {1, 2, 3}.
   $R$ = {(1, 1), (1, 2), (1, 3), (3, 3)}
   $S$ = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
   $T$ = {(1, 1), (1, 2), (2, 2), (2, 3)}
   $\emptyset$ = empty relation
   $A \times A$ = universal relation on $A$

Determine whether or not each of the relations is (a) reflexive, (b) symmetric, © transitive, and (d) antisymmetric.

7. Let $l$ be any collection of sets. Is the subset relation, $\subseteq$, a partial order on $l$?

Unfamiliar notation: generalized set operation: $A_1 \cup A_2 \cup A_3 \cup ... \cup A_m = \bigcup^m_{i=1} R_i$

The transitive closure of a binary relation $R$ on set $A$ is the smallest relation on $A$ that contains $R$ and is transitive. If $R$ is transitive, then $R$ is the transitive closure.