Kuratowski Formalization of Ordered Pair

Theorem

The concept of an ordered pair can be formalized by the definition:

$\left({a, b}\right) = \left\{{\left\{{a}\right\}, \left\{{a, b}\right\}}\right\}$

This formalization justifies the existence of ordered pairs in Zermelo-Fraenkel set theory.

This automatically justifies the definitions of an ordered tuple and the cartesian product of two sets.

Furthermore, the cartesian product of two non-empty sets is non-empty.

Proof

Equality of Ordered Pairs

From Equality of Ordered Pairs, we have that:

$\left\{{\left\{{a}\right\}, \left\{{a, b}\right\}}\right\} = \left\{{\left\{{c}\right\}, \left\{{c, d}\right\}}\right\} \iff a = c, b = d$

hence showing that this formalization fulfils the requirement for equality.

Existence of Cartesian Product

Let $A$ and $B$ be non-empty sets, and let $a \in A$ and $b \in B$.

Then $\left\{{a}\right\} \subseteq A$ and $\left\{{b}\right\} \subseteq B$.

Therefore $\left\{{a, b}\right\} \subseteq A \cup B$ where $\cup$ denotes union.

Because $\left\{{a}\right\} \subseteq A \cup B$, it follows that:

$\left\{{a}\right\}, \left\{{a, b}\right\} \in \mathcal P \left({A \cup B}\right)$

where $\mathcal P \left({A \cup B}\right)$ is the power set of $A \cup B$.

Thus:

$\left\{{\left\{{a}\right\}, \left\{{a, b}\right\}}\right\} \subseteq \mathcal P \left({A \cup B}\right)$

and so by definition of power set:

$\left\{{\left\{{a}\right\}, \left\{{a, b}\right\}}\right\} \in \mathcal P \left({\mathcal P \left({A \cup B}\right)}\right)$

Applying the axiom of specification and the axiom of extension, the unique set $A \times B$ is created which consists exactly of ordered pairs $\left({a, b}\right)$ such that $a \in A$ and $b \in B$.

Thus it has been demonstrated that the cartesian product $A \times B$ exists and is non-empty.

Finally, in Subset of Cartesian Product it is demonstrated that every set of ordered pairs is a subset of the cartesian product of two sets.

$\blacksquare$

Source of Name

This entry was named for Kazimierz Kuratowski.

This formalization was established in collaboration with Norbert Wiener.

Comment

The only reason for this formulation of ordered pairs is so their existence can be justified in the strictures of the axiomatic set theory, in particular Zermelo-Fraenkel set theory. Once that has been demonstrated, there is no need to invoke it again.

The fact that this formulation allows that:

$\left({a, b}\right) = \left({c, d}\right) \iff a = c, b = d$

is its stated aim.

The fact that $\left\{{a, b}\right\} \in \left({a, b}\right)$ is an unfortunate side-effect brought about by means of the definition.

It would be possible to add another axiom to ZF or ZFC specifically to allow for ordered pairs to be defined, and in some systems of axiomatic set theory this is what is done.

Also see

• Finite Cartesian Product of Non-Empty Sets is Non-Empty

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 6$: Ordered Pairs
• Steven A. Gaal: Point Set Topology (1964)... (previous)... (next): Introduction to Set Theory: $1$. Elementary Operations on Sets