有序对

在数学中，有序对是两个对象的搜集，使得可以区分出其中一个是“第一个元素”而另一个是“第二个元素”（第一个元素和第二个元素也叫做左投影和右投影）。带有第一个元素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）多值隱
查论编