Cartesian Product is Anticommutative

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S, T \ne \O$.


Then:

$S \times T = T \times S \iff S = T$


Corollary

$S \times T = T \times S \iff S = T \lor S = \O \lor T = \O$


Proof

Suppose $S \times T = T \times S$.

Then:

\(\ds x \in S\) \(\land\) \(\ds y \in T\)
\(\ds \leadstoandfrom \ \ \) \(\ds \tuple {x, y}\) \(\in\) \(\ds S \times T\) Definition of Cartesian Product
\(\ds \leadstoandfrom \ \ \) \(\ds \tuple {x, y}\) \(\in\) \(\ds T \times S\) by hypothesis
\(\ds \leadstoandfrom \ \ \) \(\ds x \in T\) \(\land\) \(\ds y \in S\) Definition of Cartesian Product

Thus it can be seen from the definition of set equality that $S \times T = T \times S \iff S = T$.


Note that if $S = \O$ or $T = \O$ then, from Cartesian Product is Empty iff Factor is Empty, $S \times T = T \times S = \O$ whatever $S$ and $T$ are, and the result does not hold.

$\blacksquare$


Also see


Sources

except that the case where either set is empty has been ignored
except that the case where either set is empty has been ignored
except that the case where either set is empty has been ignored
Retrieved from "https://proofwiki.org/w/index.php?title=Cartesian_Product_is_Anticommutative&oldid=660277"