Equivalence of Definitions of Set Equality

From ProofWiki
(Redirected from Equality of Sets)
Jump to: navigation, search

Theorem

Then the following definitions 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 \left({\forall x: x \in S \iff x \in T}\right)$

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

Definition 2

Let $S$ and $T$ be sets.

Then $S$ and $T$ are equal iff:

$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\)                    
\(\displaystyle \implies\) \(\displaystyle \left({x \in S}\right.\) \(\iff\) \(\displaystyle \left.{x \in T}\right)\)          Definition of Set Equality          
\(\displaystyle \implies\) \(\displaystyle \left({x \in S}\right.\) \(\implies\) \(\displaystyle \left.{x \in T}\right)\)          Biconditional Elimination          
\(\displaystyle \implies\) \(\displaystyle S\) \(\subseteq\) \(\displaystyle T\)          Definition of Subset          


Similarly:

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


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\)                    
\(\displaystyle \implies\) \(\displaystyle \left({x \in S}\right.\) \(\implies\) \(\displaystyle \left.{x \in T}\right)\)          Definition of Subset          

Then:

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


Thus by Biconditional Introduction:

$\forall x: \left({x \in S \iff x \in T}\right)$

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

$\blacksquare$


Sources