Exercise 3.1.1 (Set equality)

Question

Show that the definition of equality in Definition 3.1.4 is reflexive, symmetric, and transitive.

Il-Young Son · Accepted Answer

Reflexive and symmetric properties follows directly from definition.  For transitivity, consider the sets $A$, $B$, and $C$ and suppose $A=B$ and $B=C$.  We first show that $x\in A\implies x\in C$ (i.e., $A\subseteq C$).  By definition of equality, we have the following chain of implications $x\in A\implies x\in B$ and $x\in B \implies x\in C$. Thus, $A\subseteq C$. Conversely, if $x\in C$ then by definition of equality we have another chain of implications, $x\in C\implies x\in B\implies x\in A$ and thus $x\in C\implies x\in A$ (i.e., $C\subseteq A$).  Thus, $A=C$ (by Proposition 3.1.18).

Khagan Gulusoy · Answer

\begin{proof} 
We verify the three axioms of equality for objects (cf. page 329). To do so, we will rely on the fundamental results from logic (cf. "Appendix: the basics of mathematical logic") and on Definition 3.1.4, which more formally states that two sets $A$ and $B$ are equal if and only if
$$\forall x: x \in A \implies x \in B \quad 	ext{ AND } \quad \forall x: x \in B \implies x \in A.$$
\begin{enumerate}
    \item 	extit{(reflexive)} By Definition 3.1.4, to prove that $A = A,$ we should demonstrate that:
    $$\forall a: a \in A \implies  a \in A \quad 	ext{ AND } \quad \forall a: a\in A \implies a\in A.$$
    Since $a \in A \implies a \in A$ is always true, and since two true statements joined by the logical AND operator result in a true statement, the above statement is always true (cf. page 312).
    
    \item 	extit{(symmetric)} Suppose that $A=B$, i.e, by Definition 3.1.4 we have
    $$\forall a: a \in A \implies a \in B \quad 	ext{ AND } \quad \forall b: b \in B \implies b \in A.$$
    To prove that $B=A$, by Definition 3.1.4, we must demonstrate
    $$\forall b: b \in B \implies b \in A \quad 	ext{ AND } \quad \forall a:  a \in A \implies a \in B.$$
    But the latter expression is equivalent to the assumption $A=B$ since we can simply swap the two statements around the logical AND operator (cf. page 309).
    
    \item 	extit{(transitivity)} Since $A=B$ and $B=C,$ by definition we have:
    $$\forall x: x \in A \implies x \in B \quad 	ext{ AND } \quad \forall x: x \in B \implies x \in A.\qquad (1)$$
    $$\forall x: x \in B \implies x \in C \quad 	ext{ AND } \quad \forall x: x \in C \implies x \in B.\qquad (2)$$
    Using (1), (2), we get:
    $$\forall x: x\in C\implies x\in B\implies x\in A.$$
    Using (2), (1), we get:
    $$\forall x: x \in A \implies x \in B\implies x\in C.$$
    Recall that implication is transitive, i.e, if $P \implies Q$ and $Q \implies R$, then $P \implies R$ (cf. Section A2). Therefore, we get
    $$\forall x: x \in A \implies x \in C \quad 	ext{ AND } \quad \forall x: x \in C \implies x \in A.$$
    Since every element $x$ of $C$ is an element of $A,$ and every element of $A$ is an element of $C,$ $A = C.$
\end{enumerate}
\end{proof}

Exercise 3.1.1 (Set equality)

Answers

Comments

Comments

Exercise 3.1.1 (Set equality)

Answers

Comments

Comments

Add answer