Saturday, 7 October 2023

Tao Analysis I - 3.1.3

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