Equivalence of Definitions of Set Equality

From ProofWiki
Jump to: navigation, search

Theorem

The following definitions of the concept of Set Equality are equivalent:

Definition 1

Two sets are equal if and only if they have the same elements.


This can be defined rigorously as:

$S = T \iff \paren {\forall x: x \in S \iff x \in T}$

where $S$ and $T$ are both sets.

Definition 2

Let $S$ and $T$ be sets.

Then $S$ and $T$ are equal if and only if:

$S$ is a subset of $T$

and

$T$ is a subset of $S$


Proof

Definition 1 implies Definition 2

Let $S = T$ by Definition 1.

Then:

\(\displaystyle S\) \(=\) \(\displaystyle T\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \left({x \in S}\right.\) \(\iff\) \(\displaystyle \left.{x \in T}\right)\) $\quad$ Definition of Set Equality $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \left({x \in S}\right.\) \(\implies\) \(\displaystyle \left.{x \in T}\right)\) $\quad$ Biconditional Elimination $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle S\) \(\subseteq\) \(\displaystyle T\) $\quad$ Definition of Subset $\quad$


Similarly:

\(\displaystyle S\) \(=\) \(\displaystyle T\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \left({x \in S}\right.\) \(\iff\) \(\displaystyle \left.{x \in T}\right)\) $\quad$ Definition of Set Equality $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \left({x \in T}\right.\) \(\implies\) \(\displaystyle \left.{x \in S}\right)\) $\quad$ Biconditional Elimination $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle T\) \(\subseteq\) \(\displaystyle S\) $\quad$ Definition of Subset $\quad$


Thus by the Rule of Conjunction:

$S \subseteq T \land T \subseteq S$

and so $S$ and $T$ are equal by Definition 2.

$\Box$


Definition 2 implies Definition 1

Let $S = T$ by Definition 2:

$S \subseteq T \land T \subseteq S$


First:

\(\displaystyle S\) \(\subseteq\) \(\displaystyle T\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \left({x \in S}\right.\) \(\implies\) \(\displaystyle \left.{x \in T}\right)\) $\quad$ Definition of Subset $\quad$

Then:

\(\displaystyle T\) \(\subseteq\) \(\displaystyle S\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \left({x \in T}\right.\) \(\implies\) \(\displaystyle \left.{x \in S}\right)\) $\quad$ Definition of Subset $\quad$


Thus by Biconditional Introduction:

$\forall x: \paren {x \in S \iff x \in T}$

and so $S$ and $T$ are equal by Definition 1.

$\blacksquare$


Sources