有序對

在數學中，有序對是兩個對象的搜集，使得可以區分出其中一個是「第一個元素」而另一個是「第二個元素」（第一個元素和第二個元素也叫做左投影和右投影）。帶有第一個元素$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\}\}$仍是有效的；在這種情況下陳述（$\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$）的意義上，但也是任意性的，因為有很多其他定義也是不更加複雜並且也是充足的。例如下列可能的定義

1. $(a,b)_{\text{reverse}}:=\{\{b\},\{a,b\}\}$
2. $(a,b)_{\text{short}}:=\{a,\{a,b\}\}$
3. $(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的定義要求自然數的先決定義。設$\mathbb {N}$是自然數的集合，$x\setminus \mathbb {N}$是$\mathbb {N}$在$x$內的相對差集，並定義：

$\varphi (x)=(x\setminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {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\}$

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

參見

• 笛卡兒積
• 二元關係