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


Similarly:

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

Then:

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