有序数对

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

　
: $(\exists \ 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_} } 仍是有效的；在這種情況下陳述 (∀ _Y_1 ∈ _p_, ∀ _Y_2 ∈ _p_ : _Y_1 ≠ _Y_2 → (_x_ ∉ _Y_1 ∨ _x_ ∉ _Y_2)) 顯然是真的，因為不會有 _Y_1 ≠ _Y_2 的情況。

### 變體定義

上述有序對的定義是「充足」的，在它滿足有序對必須有的特徵性質（也就是：如果 (_a_,_b_)=(_x_,_y_) 則 _a_=_x_ 且 _b_=_y_）的意義上，但也是任意性的，因為有很多其他定義也是不更加複雜並且也是充足的。例如下列可能的定義

1. (_a_,_b_)reverse:= { {_b_}, {_a_,_b_} }
2. (_a_,_b_)short:= { _a_, {_a_,_b_} }
3. (_a_, _b_)01:= { {0,_a_}, {1,_b_} }

「逆」（reverse）對基本不使用，因為它比通用的 Kuratowski 對沒有明顯的優點（或缺點）。「短」（short）對有一個缺點，它的特徵性質的證明會比 Kuratowski 對的證明更加複雜（要使用正規公理）；此外，因為在集合論中數 2 有時定義為集合 {0, 1} = {{}, {0} }，這將意味著 2 是對 (0,0)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_≠_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_≠_b_。所以 {_c_} = {_a_}，即 _c=a_，且 {_c,d_} = {_a,b_}。

　
: : 並且如果 _d=a_，則 {_c,d_} = {_a,a_} = {_a_}≠{_a,b_}。所以 _d=b_。

　
: 所以同樣有 _a=c_ 且 _b=d_。

_當：_

　
: 反過來，如果 _a=c_ 並且 _b=d_，則顯然 {{_a_},{_a,b_}} = {{_c_},{_c,d_}}。所以 (_a,b_)K = (_c,d_)K。

 
**逆**對：
(_a,b_)reverse = {{_b_},{_a,b_}} = {{_b_},{_b,a_}} = (_b,a_)K。

　
: 如果 (_a,b_)reverse = (_c,d_)reverse，則 (_b,a_)K = (_d,c_)K。所以 _b=d_ 且 _a=c_。

　
: 反過來，如果 _a=c_ 和 _b=d_，則顯然 {{_b_},{_a,b_}} = {{_d_},{_c,d_}}。所以 (_a,b_)reverse = (_c,d_)reverse。

### Quine-Rosser 定義

Rosser（1953 年）擴展了蒯因的有序對定義。Quine-Rosser 的定義要求自然數的先決定義。設 $\mathbb {N} $ 是自然數的集合， $x\setminus \mathbb {N} $ 是 $\mathbb {N} $ 在 $x$ 內的相對差集，並定義：

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

φ(_x_) 包含在 _x_ 中所有自然數的後繼，和 _x_ 中的所有非數成員。特別是，φ(_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\}$

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

## 參考文獻

## 參見

* 笛卡兒積
* 二元關係