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 \implies 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:

\(\displaystyle x \in S\) \(\land\) \(\displaystyle y \in T\)
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \tuple {x, y}\) \(\in\) \(\displaystyle S \times T\) Definition of Cartesian Product
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \tuple {x, y}\) \(\in\) \(\displaystyle T \times S\) by hypothesis
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle x \in T\) \(\land\) \(\displaystyle 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 \implies 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