# Equivalence of Definitions of Ordered Pair

## Theorem

The following definitions of an ordered pair are equivalent:

### Informal Definition

An **ordered pair** is a two-element set together with an ordering.

In other words, one of the elements *is* distinguished above the other - it comes first.

Such a structure is written:

- $\tuple {a, b}$

and it means:

**first $a$, then $b$**.

### Kuratowski Formalization

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

- $\tuple {a, b} := \set {\set a, \set {a, b} }$

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

## Proof

### Equality of Ordered Pairs

From Equality of Ordered Pairs, we have that:

- $\set {\set a, \set {a, b} } = \set {\set c, \set {c, d} } \iff a = c, b = d$

hence showing that the Kuratowski formalization fulfils the requirement for equality.

### Existence of Cartesian Product

Let $A$ and $B$ be sets.

Suppose that either $A$ or $B$ is empty.

Then:

\(\ds A \times B\) | \(=\) | \(\ds \set {\tuple {a, b} : a \in A \land b \in B}\) | Definition of Cartesian Product | |||||||||||

\(\ds \) | \(=\) | \(\ds \O\) |

By the Axiom of the Empty Set $A \times B$ is a set.

Now suppose that $A$ and $B$ are both non-empty.

Let $a \in A$ and $b \in B$.

By Singleton of Element is Subset:

- $\set a \subseteq A$ and $\set b \subseteq B$

Therefore by Set Union Preserves Subsets:

- $\set {a, b} \subseteq A \cup B$

$A \cup B$ is a set by Union of Small Classes is Small.

Because $\set a \subseteq A \subseteq A \cup B$, it follows that:

- $\set a, \set {a, b} \in \powerset {A \cup B}$

where $\powerset {A \cup B}$ is the power set of $A \cup B$.

This a set by the Axiom of Powers.

Thus:

- $\set {\set a, \set {a, b} } \subseteq \powerset {A \cup B}$

and so by definition of the power set:

- $\set {\set a, \set {a, b} } \in \powerset {\powerset {A \cup B} }$

It has been shown that:

- $\set {\tuple {a, b}: a \in A \land b \in B} \subseteq \powerset {\powerset {A \cup B} }$

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

Thus it has been demonstrated that if $A$ and $B$ are non-empty, then 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$

## Sources

- 1964: W.E. Deskins:
*Abstract Algebra*... (previous) ... (next): Exercise $1.2: \ 12$ - 1972: A.G. Howson:
*A Handbook of Terms used in Algebra and Analysis*... (previous) ... (next): $\S 2$: Sets and functions: Graphs and functions