nLab
unordered pair

Unordered pairs

Idea

The unordered pair of xx and yy, denoted {x,y}\{x,y\}, has the property that {x 1,y 1}={x 2,y 2}\{x_1,y_1\} = \{x_2,y_2\} if and only if x 1=x 2x_1 = x_2 and y 1=y 2y_1 = y_2 or x 1=y 2x_1 = y_2 and y 1=x 2y_1 = x_2. In other words, the unordered pair {x,y}\{x,y\} is the same as the ordered pair (x,y)(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.

Definition

Unordered pairs are commonly defined as subsets, as follows:

If AA is a set and xx and yy are elements of AA, then the unordered pair or pair set {x,y}\{x,y\} is the subset of AA with the property that z{x,y}z \in \{x,y\} if and only if z=xz = x or z=yz = y. Note that {x,x}={x}\{x,x\} = \{x\}, a singleton.

In material set theory, we may apply this when xx and yy are not previously given as elements of any set AA. 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 AA may be denoted ((A2))\big(\!\big({A \atop 2}\big)\!\big). Classically (using excluded middle), ((A2))\big(\!\big({A \atop 2}\big)\!\big) is the internal disjoint union (A1)(A2)\big({A \atop 1}\big) \uplus \big({A \atop 2}); in other words, every unordered pair is either a 11-element set (a singleton) or a 22-element set.

Relation to ordered pairs

The unordered pair {x,y}\{x,y\} should not be confused with the ordered pair (x,y)(x,y). In particular, {x,y}={y,x}\{x,y\} = \{y,x\}, while (x,y)(y,x)(x,y) \neq (y,x) (if xyx \neq y). In material set theory, {x,y}\{x,y\} has a direct definition, but (x,y)(x,y) must be coded in a complicated way (traditionally as {{x},{x,y}}\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 ((A2))\big(\!\big({A \atop 2}\big)\!\big) of unordered pairs of elements of AA may be constructed as a quotient set of the set A 2A^2 of ordered pairs of elements of AA (by the equivalence relation generated by declaring that (x,y)(y,x)(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 nnLab usually refers to ordered pairs.

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