Exercise 3.1.3
Prove the remaining claims in Lemma 3.1.12.
Let's write out Lemma 3.1.12.
Lemma 3.1.12 If $a$ and $b$ are objects, then $\{a,b\}=\{a\} \cup \{b\}$. If $A$, $B$, $C$ are sets, then the union operation is commutative (i.e., $A \cup B = B \cup A$) and associative (i.e., $(A \cup B) \cup C = A \cup (B \cup C)$). Also, we have $A \cup A = A \cup \emptyset = \emptyset \cup A = A$.
The textbook provides a proof that union is associative. We'll prove the remaining claims.
Show $\{a,b\}=\{a\} \cup \{b\}$
Axiom 3.4 defining pair sets tells us that the only elements of $\{a,b\}$ are $a$ and $b$. That is
$$x \in \{a,b\} \iff (x=a \lor x=b)$$
Axiom 3.4 defining singletons tells us
$$\begin{align}x \in \{a\} &\iff x=a \\ \\ x \in \{b\} &\iff x=b\end{align}$$
Axiom 3.5 defines pairwise union as follows
$$x \in (A \cup B) \iff ((x \in A) \lor (x \in B))$$
Thus
$$x \in (\{a\} \cup \{b\}) \iff ((x \in \{a\}) \lor (x \in \{b\}))$$
This is equivalent to the following (Axiom 3.4),
$$x \in (\{a\} \cup \{b\}) \iff ((x = a) \lor (x=b))$$
And by Axiom 3.4 again,
$$x \in (\{a\} \cup \{b\}) \iff ((x = a) \lor (x=b)) \iff x \in \{a,b\}$$
We have shown $\{a,b\}=\{a\} \cup \{b\}$. $\square$
Union is Commutative $A \cup B = B \cup A$
We want to prove $A \cup B = B \cup A$.
By Axiom 3.5 which defines pairwise union we have
$$x \in (A \cup B) \iff ((x \in A) \lor (x \in B))$$
Because logical disjunction $\lor$ is commutative, we have
$$((x \in A) \lor (x \in B)) \iff ((x \in B) \lor (x \in A))$$
By Axiom 3.5, we also have
$$x \in (B \cup A) \iff ((x \in B) \lor (x \in A))$$
These three statements give us
$$x \in (A \cup B) \iff x \in (B \cup A)$$
That is, $A \cup B = B \cup A$. $\square$
Show $A \cup A = A \cup \emptyset = \emptyset \cup A = A$
We have already shown that pairwise union is commutative, so we don't need to show again that
$$A \cup \emptyset = \emptyset \cup A \; \square$$
Let's use Axiom 3.5 which defines union to write
$$x \in (A \cup A) \iff ((x \in A) \lor (x \in A))$$
We can simplify the RHS,
$$x \in (A \cup A) \iff (x \in A)$$
This is simply stating that
$$A \cup A = A \; \square$$
All that remains is to show $A \cup \emptyset = A$. Let's again use Axiom 3.5 which defines union to write
$$x \in (A \cup \emptyset) \iff ((x \in A) \lor (x \in \emptyset))$$
Since there is no $x \in \emptyset$ by Axiom 3.3 which defines the empty set, we can simplify the RHS,
$$x \in (A \cup \emptyset) \iff (x \in A)$$
This is simply stating that
$$A \cup \emptyset = A \; \square$$
No comments:
Post a Comment