Pairing and Cartesian Products

Ordered Pairs

Definition

An ordered pair $(a, b)$ is a mathematical structure that:

1. Contains exactly two elements
2. Has a specified order: first component $a$, second component $b$

Key Property

$(a, b) = (c, d) \iff a = c \land b = d$

This distinguishes ordered pairs from sets: $\{a, b\} = \{b, a\}$ but $(a, b) \neq (b, a)$ (unless $a = b$).

Kuratowski Definition (Encoding)

We can define ordered pairs purely in terms of sets:

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

Verification: If $(a, b) = (c, d)$, then $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$.

• If $a = b$, then $\{\{a\}, \{a, b\}\} = \{\{a\}\}$, so $\{c\} = \{a\}$, hence $c = a = b$.
• If $a \neq b$, then $\{a\} \in \{\{c\}, \{c, d\}\}$ requires $\{a\} = \{c\}$, so $a = c$.
  • Then $\{a, b\} = \{a, d\}$, and since $a \neq b$, we have $b = d$.

Cartesian Product

Definition

The Cartesian product of sets $A$ and $B$ is:

$A \times B = \{(a, b) : a \in A \land b \in B\}$

Examples

• $\{1, 2\} \times \{a, b\} = \{(1, a), (1, b), (2, a), (2, b)\}$
• $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ (the Euclidean plane)
• $\{x\} \times A = \{(x, a) : a \in A\}$

Cardinality

For finite sets:

$|A \times B| = |A| \cdot |B|$

Properties of Cartesian Products

Non-commutativity

$A \times B \neq B \times A \text{ in general}$

Unless $A = B$ or one of them is empty.

Distributivity over Union

$A \times (B \cup C) = (A \times B) \cup (A \times C)$ $(A \cup B) \times C = (A \times C) \cup (B \times C)$

Distributivity over Intersection

$A \times (B \cap C) = (A \times B) \cap (A \times C)$ $(A \cap B) \times C = (A \times C) \cap (B \times C)$

Interaction with Empty Set

$A \times \emptyset = \emptyset = \emptyset \times A$

n-tuples

Definition

An n-tuple $(a_1, a_2, \ldots, a_n)$ generalises ordered pairs.

We can encode n-tuples using nested pairs:

$(a_1, a_2, \ldots, a_n) = (a_1, (a_2, (\ldots, (a_{n-1}, a_n)\ldots)))$

n-fold Cartesian Product

$A^n = \underbrace{A \times A \times \cdots \times A}_{n \text{ times}} = \{(a_1, \ldots, a_n) : a_i \in A\}$

Examples

• $\mathbb{R}^2$: the plane (2D coordinates)
• $\mathbb{R}^3$: 3D space
• $\mathbb{Z}^n$: integer lattice in $n$ dimensions

Disjoint Union (Coproduct)

Motivation

The union $A \cup B$ is not ideal for “combining” sets because:

• If $A$ and $B$ overlap, we lose information about origin
• We cannot distinguish $a \in A \cap B$ from $a \in A$ vs $a \in B$

Definition

The disjoint union (or coproduct, or sum) of $A$ and $B$ is:

$A + B = (\{0\} \times A) \cup (\{1\} \times B)$

Each element is “tagged” with its origin.

Examples

• $\{a, b\} + \{b, c\} = \{(0, a), (0, b)\} \cup \{(1, b), (1, c)\}$
• Even though $b$ appears in both, $(0, b) \neq (1, b)$

Cardinality

$|A + B| = |A| + |B|$

This holds without restriction (unlike union, where $|A \cup B| = |A| + |B| - |A \cap B|$).

---

Summary

• Ordered pairs $(a, b)$ satisfy $(a, b) = (c, d) \iff a = c \land b = d$
• Cartesian product $A \times B = \{(a, b) : a \in A, b \in B\}$
• $|A \times B| = |A| \cdot |B|$ and $|A + B| = |A| + |B|$
• Disjoint union $A + B$ tags elements to preserve origin information