有序对

在数学中，有序对是两个对象的搜集，使得可以区分出其中一个是“第一个元素”而另一个是“第二个元素”（第一个元素和第二个元素也叫做左投影和右投影）。带有第一个元素$a$和第二个元素$b$的有序对通常写为$(a,b)$。

符号$(a,b)$也表示在实数轴上的开区间；在有歧义的场合可使用符号$\langle a,b\rangle$。

## 一般性

设$(a_1,b_1)$和$(a_2,b_2)$是两个有序对。则有序对的特征或定义性质为：

$$(a_1, b_1) = (a_2, b_2) \leftrightarrow (a_1 = a_2 \land b_1 = b_2)$$

有序对可以有其他有序对作为投影。所以有序对使得能够递归定义有序n-元组（n项的列表）。例如，有序三元组$(a,b,c)$可以定义为$(a,(b,c))$，一个对嵌入了另一个对。这种方法也反映在计算机编程语言中，就是从嵌套的有序对构造元素的列表。例如，列表 (1 2 3 4 5)变成了(1, (2, (3, (4, (5, {} )))))。Lisp编程语言使用这种列表作为基本数据结构。

有序对的概念对于定义笛卡尔积和关系是至关重要的。

## 有序对的集合论定义

诺伯特·维纳在1914年提议了有序对的第一个集合论定义：

$$(x,y) \equiv_{def} \{\{\{x\},\emptyset\},\{\{y\}\}\}$$

他注意到这个定义将允许《数学原理》中所有类型只透过集合便能表达。（在《数学原理》中，所有元数的关系都是原始概念。）

### 标准Kuratowski定义

在公理化集合论中，有序对(a,b)通常定义为库拉托夫斯基对：

$$(a,b)_K \equiv_{def} \{\{a\},\{a,b\}\}$$

陈述“$x$是有序对$p$的第一个元素”可以公式化为

$$\forall \ Y \in p : x \in Y$$

而陈述“$x$是$p$的第二个元素”为

$$(\exist \ Y \in p : x \in Y) \land (\forall \ Y_1 \in p, \forall \ Y_2 \in p : Y_1 \neq Y_2 \rightarrow (x \notin Y_1 \lor x \notin Y_2))$$

注意这个定义对于有序对$p=(x,x)=\{\{x\},\{x,x\}\}=\{\{x\},\{x\}\}=\{\{x\}\}$仍是有效的；在这种情况下陈述（$\forall Y_1 \in p, \forall Y_2\in p : Y_1 \neq Y_2 \rightarrow (x\not\in Y_1 \lor x \not\in Y_2)$）显然是真的，因为不会有$Y_1 \neq Y_2$的情况。

### 变体定义

上述有序对的定义是“充足”的，在它满足有序对必须有的特征性质（也就是：如果$(a,b)=(x,y)$则$a=x$且$b=y$）的意义上，但也是任意性的，因为有很多其他定义也是不更加复杂并且也是充足的。例如下列可能的定义

- $$(a,b)_{\text{reverse}} := \{ \{b\}, \{a,b\} \}$$
- $$(a,b)_{\text{short}} := \{ a, \{a,b\} \}$$
- $$(a,b)_{01} := \{ \{0,a\} , \{1,b\} \}$$

“逆”（reverse）对基本不使用，因为它比通用的Kuratowski对没有明显的优点（或缺点）。“短”（short）对有一个缺点，它的特征性质的证明会比Kuratowski对的证明更加复杂（要使用正规公理）；此外，因为在集合论中数2有时定义为集合$\{0,1\}= \{ \{\} , \{0\} \}$，这将意味着2是对$(0,0)_{\text{short}}$。

### 证明有序对的特征性质

Kuratowski对：

证明：$(a,b)_K = (c,d)_K$当且仅当$a=c$且$b=d$。

仅当：

如果$a=b$，则$(a,b)_K= \{ \{a\}, \{a,a\} \} = \{\{a\}\}$，且$(c,d)_K = \{ \{c\}, \{c,d\} \} = \{\{a\}\}$。所以$\{c\} = \{a\} = \{c,d\}$，或$c=d=a=b$。

如果$a\neq b$，则$\{\{a\}, \{a,b\}\} = \{\{c\},\{c,d\}\}$。

如果$\{c,d\} = \{a\}$，则$c=d=a$或$\{\{c\},\{c,d\}\} = \{\{a\}, \{a,a\}\} = \{\{a\}, \{a\}\} = \{ \{a\} \}$。但这样$\{\{a\}, \{a, b\}\}$就会等于$\{\{a\}\}$，继而$b = a$，跟先前的假设矛盾。

如果$\{c\} = \{a,b\}$，则$a=b=c$，这矛盾于$a\neq b$。所以$\{c\} = \{a\}$，即$c=a$，且$\{c,d\} = \{a,b\}$。

并且如果$d=a$，则$\{c,d\} = \{a,a\} = \{a\}\neq\{a,b\}$。所以。

所以同样有$a=c$且$b=d$。

当：

反过来，如果$a=c$并且$b=d$，则显然$\{\{a\},\{a,b\}\} = \{\{c\},\{c,d\}\}$。所以$(a,b)_K = (c,d)_K$。

逆对：

$(a,b)_{\text{reverse}} = \{\{b\},\{a,b\}\} = \{\{b\},\{b,a\}\} = (b,a)_K$。

如果$(a,b)_{\text{reverse}} = (c,d)_{\text{reverse}}$，则$(b,a)_K = (d,c)_K$。所以$b=d$且$a=c$。

反过来，如果$a=c$和$b=d$，则显然$\{\{b\},\{a,b\}\} = \{\{d\},\{c,d\}\}$。所以$(a,b)_{\text{reverse}} = (c,d)_{\text{reverse}}$。

### Quine-Rosser定义

Rosser（1953年）扩展了蒯因的有序对定义。Quine-Rosser的定义要求自然数的先决定义。设$\N$是自然数的集合，$x \setminus \N$是$\N$在$x$内的相对差集，并定义：

$$\varphi(x) = (x \setminus \N) \cup \{n+1 : n \in (x \cap \N) \}$$

$\varphi(x)$包含在$x$中所有自然数的后继，和$x$中的所有非数成员。特别是，$\varphi(x)$不包含数0，所以对于任何集合$A$和$B$，$\phi(A) \not= \{0\} \cup \phi(B)$。

以下是有序对$(A,B)$的定义：

$$(A, B) = \{\varphi(a) : a \in A\} \cup \{\varphi(b) \cup \{0\} : b \in B \}.$$

提取这个对中那些不包含0的所有元素，然后再还原$\varphi$的作用，就得出了$A$。类似的，$B$可以通过提取这个对的包含0的所有元素来复原。

有序对的这个定义有个显著的优点。在类型论和从类型论派生出的集合论如新基础中，这个对与它的投影有相同的类型（所以术语叫做“类型齐平”有序对）。因此一个函数（定义为有序对的集合），有只比序对的投影的类型高1的类型。对蒯因集合论中有序对的广泛的讨论请参见Holmes (1998)。

### Morse定义

Morse（1965年）提出的Morse-Kelley集合论可以自由的使用真类。Morse定义有序对的方法，使得它的投影可以是真类或者集合。（Kuratowski定义不允许这样）。它首先像Kuratowski的方式那样，定义投影为集合的有序对。接着，他重定义对 (x,y)为

$$(x, y) = (\{0\} \times s(x)) \cup (\{1\} \times s(y))$$

这里的笛卡尔积是指由Kuratowski对组成的集合并且

$$s(x) = \{\emptyset \} \cup \{\{t\} | t \in x\}$$

这便允许了定义以真类为投影的有序对。