有序對

在數學中，有序對是兩個對象的搜集，使得可以區分出其中一個是「第一個元素」而另一個是「第二個元素」（第一個元素和第二個元素也叫做左投影和右投影）。帶有第一個元素$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\}$$

這便允許了定義以真類為投影的有序對。