有序對

在數學中，有序對是兩個對象的搜集，使得可以區分出其中一個是「第一個元素」而另一個是「第二個元素」（第一個元素和第二個元素也叫做左投影和右投影）。帶有第一個元素a和第二個元素b的有序對通常寫為(a, b)。

符號(a, b)也表示在實數軸上的開區間；在有歧義的場合可使用符號 $\langle a,b\rangle$ 。

一般性

設(a₁, b₁)和(a₂, b₂)是兩個有序對。則有序對的特徵或定義性質為：

(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₁ ∈ p, ∀ Y₂ ∈ p : Y₁ ≠ Y₂ → (x ∉ Y₁ ∨ x ∉ Y₂))顯然是真的，因為不會有Y₁ ≠ Y₂的情況。

變體定義

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

(a,b)_reverse:= { {b}, {a,b} }
(a,b)_short:= { a, {a,b} }
(a, b)₀₁:= { {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年）^[1]擴展了蒯因的有序對定義。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)。^[2]

Morse定義

Morse（1965年）^[3]提出的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\}

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

參考文獻

^ J. Barkley Rosser, 1953. Logic for Mathematicians. McGraw-Hill.
^ Holmes, Randall (1998) Elementary Set Theory with a Universal Set （頁面存檔備份，存於互聯網檔案館）. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this monograph via the web. Copyright is reserved.
^ Morse, Anthony P., 1965. A Theory of Sets. Academic Press

參見

[1] J. Barkley Rosser, 1953. Logic for Mathematicians. McGraw-Hill.

[2] Holmes, Randall (1998) Elementary Set Theory with a Universal Set （頁面存檔備份，存於互聯網檔案館）. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this monograph via the web. Copyright is reserved.

[3] Morse, Anthony P., 1965. A Theory of Sets. Academic Press

[1]

[2]

[3]

閱論編集合論
公理	選擇可數依賴外延無窮配對冪集正則性併集馬丁公理公理模式替代分類
運算	笛卡兒積德摩根定律交集冪集補集對稱差併集
概念方法	勢基數（大基數）類可構造全集（英語：Constructible universe）連續統假設對角論證法元素有序對多元組集合族力迫一一對應序數超限歸納法文氏圖
集合類型	可數集空集有限集合（繼承有限集合）模糊集無限集合遞歸集合子集傳遞集合不可數集泛集（英語：Universal set）
理論	可替代的集合論集合論樸素集合論康托爾定理策梅洛廣義（英語：General set theory）《數學原理》新基礎策梅洛-弗蘭克馮諾伊曼-博內斯-哥德爾 Morse–Kelley（英語：Morse–Kelley set theory）克里普克–普拉特克（英語：Kripke–Platek set theory）塔斯基–格羅滕迪克（英語：Tarski–Grothendieck set theory）
悖論（英語：Paradoxes of set theory）問題	羅素悖論蘇斯林問題 ZFC系統無法確定的命題列表
集合論者	亞伯拉罕·弗蘭克爾伯特蘭·羅素恩斯特·策梅洛格奧爾格·康托爾約翰·馮·諾伊曼庫爾特·哥德爾盧菲特·澤德保羅·貝爾奈斯（英語：Paul Bernays）保羅·寇恩理查德·戴德金托馬什·耶赫威拉德·蒯因

各種函數
$x \mapsto f (x)$
不同定義域和陪域
$X$ → $\mathbb {B}$ , $\mathbb {B}$ → $X$ , $\mathbb {B} ^{n}$ → $\mathbb {B}$ $X$ →（英語：integer-valued function） $\mathbb {Z}$ , $\mathbb {Z} ^{+}$ → $X$ $X$ →（英語：real-valued function） $\mathbb {R}$ , $\mathbb {R}$ → $X$ , $\mathbb {R} ^{n}$ →（英語：function of several real variables） $X$ $X$ →（英語：complex-valued function） $\mathbb {C}$ , $\mathbb {C}$ → $X$ , $\mathbb {C} ^{n}$ →（英語：Function of several complex variables） $X$
函數類/性質
常值恆等線性多項式有理代數解析光滑連續可測單射滿射雙射
構造
限制複合 λ 逆
推廣
偏（英語：Partial function）多值隱
閱論編