unordered pair

The *unordered pair* of $x$ and $y$, denoted $\{x,y\}$, has the property that $\{x_1,y_1\} = \{x_2,y_2\}$ if and only if $x_1 = x_2$ and $y_1 = y_2$ or $x_1 = y_2$ and $y_1 = x_2$. In other words, the unordered pair $\{x,y\}$ is the same as the *ordered pair* $(x,y)$, except that presentation order does not matter.

A more transparent terminology calls an unordered pair a *pair set*, which allows a *pair* to unambiguously be an ordered pair (as is usual in current usage), however the *ordered/unordered* distinction is well entrenched in the literature.

Unordered pairs are commonly defined as subsets, as follows:

If $A$ is a set and $x$ and $y$ are elements of $A$, then the **unordered pair** or **pair set** $\{x,y\}$ is the subset of $A$ with the property that $z \in \{x,y\}$ if and only if $z = x$ or $z = y$. Note that $\{x,x\} = \{x\}$, a singleton.

In material set theory, we may apply this when $x$ and $y$ are not previously given as elements of any set $A$. In that case, the existence of the unordered pair is given by the axiom of pairing.

The set of all unordered pairs of elements of $A$ may be denoted $\big(\!\big({A \atop 2}\big)\!\big)$. Classically (using excluded middle), $\big(\!\big({A \atop 2}\big)\!\big)$ is the internal disjoint union $\big({A \atop 1}\big) \uplus \big({A \atop 2})$; in other words, every unordered pair is either a $1$-element set (a singleton) or a $2$-element set.

The unordered pair $\{x,y\}$ should not be confused with the ordered pair $(x,y)$. In particular, $\{x,y\} = \{y,x\}$, while $(x,y) \neq (y,x)$ (if $x \neq y$). In material set theory, $\{x,y\}$ has a direct definition, but $(x,y)$ must be coded in a complicated way (traditionally as $\big\{\{x\}, \{x,y\}\big\}$). On the other hand, ordered pairs are more natural in structural set theory.

However, the two are somewhat related:

- As just seen, the usual encoding of an ordered pair of pure sets as a pure set (due to Kuratowski) involves unordered pairs. Conversely, the set $\big(\!\big({A \atop 2}\big)\!\big)$ of unordered pairs of elements of $A$ may be constructed as a quotient set of the set $A^2$ of ordered pairs of elements of $A$ (by the equivalence relation generated by declaring that $(x,y) \sim (y,x)$).
- Just as unordered pairs (through the axiom of pairing) are needed to get anywhere in material set theory, so some axiom related to ordered pairs is needed to get anywhere in structural set theory. (In ETCS, this is the axiom of the (Cartesian) product; in SEAR, this is the axiom of tabulations.)

The term ‘pairing’ in the $n$Lab usually refers to *ordered* pairs.

Revised on January 16, 2011 02:50:59
by Toby Bartels
(75.117.106.4)