Exercise 3.1.3 (Commutativity and associativity of set union)

Question

Prove the remaining claims in Lemma 3.1.13.
ewline 
ewline
	extbf{Lemma 3.1.13.} 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.$

Khagan Gulusoy · Accepted Answer

\begin{proof} We complete the proof of Lemma 3.1.13.
\begin{enumerate}
    \item (associativity) By definition, to prove associativity, we should prove that if $x\in (A\cup B)\cup C$, then $x\in A\cup (B\cup C)$ and vice versa. 
ewline
    Part 1: $x\in (A\cup B)\cup C \implies x\in A\cup (B\cup C)$.
ewline
    The fact that $x\in (A\cup B)\cup C$ means that $x$ is in either $A\cup B$ or $C.$ We now look at these cases.
    \begin{enumerate}
        \item $(x\in A\cup B)$ If $x$ is in $A\cup B,$ we have two additional cases.
        \begin{itemize}
            \item $(x\in A)$ Then, by Axiom 3.4, it's true that:
            $$x\in A\cup (B\cup C).$$
            \item $(x\in B)$ Then, by Axiom 3.4, we have:
            $$x\in B\implies x\in B\cup C\implies x\in A\cup (B\cup C).$$
        \end{itemize}
        \item $(x\in C)$ Then, by Axiom 3.4, we have:
        $$x\in C\implies x\in B\cup C\implies x\in A\cup (B\cup C),$$
        as desired.
    \end{enumerate}
    Part 2: $x\in A\cup( B\cup C) \implies x\in (A\cup B)\cup C$.
ewline
    Follows similarly.

\item (commutativity) Suppose that $x \in A \cup B$ holds. By Definition 3.1.4, this means
    $$x \in A \quad 	ext{OR} \quad x \in B.$$
    From the basics of mathematical logic (see Appendix A), we know that $P$ or $Q$ is equivalent to $Q$ or $P$ for any statements $P, Q$. Thus, the above assertion is equivalent to
    $$x \in B \quad 	ext{OR} \quad x \in A.$$
    By Definition 3.1.4, we therefore have $x \in B \cup A$. The other direction, i.e, $x \in A \cup B$ implies $x \in A \cup B$, follows symmetrically. In other words, we have proven that
    $$\forall x: \quad x \in A \cup B \iff x \in B \cup A,$$
    meaning that $A \cup B = B \cup A$.

\item By transitivity of equality (\href{./exercise_3-1-1}{Exercise 3.1.1}) and commutativity of set union (previous part of this exercise), it suffices to show that $A \cup A = A$ and that $A \cup \emptyset = A$.
    \begin{description}
    \item[($A \cup A = A$)] From the basics of mathematical logic (see Appendix A), we know that the statement $P$ OR $P$ is equivalent to $P$ for any mathematical statement $P$. By Axiom 3.4, we thus get
    $$\forall x: x\in (A\cup A)\iff (x\in A)  	ext{ OR } (x\in A) \iff x\in A.$$
    In other words, $A \cup A = A$ by Definition 3.1.4.
    
    \item[($A \cup \emptyset = A$)] By Axiom 3.4,
    $$\forall x: x\in (A\cup \emptyset) \iff (x\in A) \ 	ext{OR}\ (x\in \emptyset).$$
    Since $x\in \emptyset$ is always false by Axiom 3.3, we can verify using some basics of mathematical logic that
    $$\forall x:x\in A\cup \emptyset \Longleftrightarrow x\in A .$$
    Thus, we have $A\cup \emptyset = A.$
    \end{description}

\end{enumerate}
\end{proof}

Exercise 3.1.3 (Commutativity and associativity of set union)

Answers

Comments

Exercise 3.1.3 (Commutativity and associativity of set union)

Answers

Comments

Add answer