查看“有序对”的源代码

在[[数学]]中，'''有序对'''是两个对象的[[类 (数学)|搜集]]，使得可以区分出其中一个是“第一个元素”而另一个是“第二个元素”（第一个元素和第二个元素也叫做'''左投影'''和'''右投影'''）。带有第一个元素''a''和第二个元素''b''的有序对通常写为(''a'', ''b'')。

符号(''a'', ''b'')也表示在[[实数轴]]上的[[区间|开区间]]；在有歧义的场合可使用符号<math>\langle a,b\rangle</math>。

== 一般性 ==

设(''a''<sub>1</sub>, ''b''<sub>1</sub>)和(''a''<sub>2</sub>, ''b''<sub>2</sub>)是两个有序对。则有序对的特征或定义性质为：
:<math>(a_1, b_1) = (a_2, b_2) \leftrightarrow (a_1 = a_2 \land b_1 = b_2)</math>

有序对可以有其他有序对作为投影。所以有序对使得能够递归定义有序[[多元组|''n''-元组]]（''n''项的列表）。例如，有序三元组 (''a,b,c'')可以定义为(''a'', (''b,c''))，一个对嵌入了另一个对。这种方法也反映在计算机编程语言中，就是从嵌套的有序对构造元素的列表。例如，列表 (1 2 3 4 5)变成了(1, (2, (3, (4, (5, {} )))))。[[LISP|Lisp编程语言]]使用这种列表作为基本数据结构。

有序对的概念对于定义[[笛卡尔积]]和[[关系 (数学)|关系]]是至关重要的。

== 有序对的集合论定义 ==

[[诺伯特·维纳]]在1914年提议了有序对的第一个集合论定义：
:<math>(x,y) \equiv_{def} \{\{\{x\},\emptyset\},\{\{y\}\}\}</math>
他注意到这个定义将允许《[[数学原理]]》中所有类型只透過集合便能表达。（在《数学原理》中，所有[[元数]]的[[关系 (数学)|关系]]都是原始概念。）

=== 标准Kuratowski定义 ===
在[[公理化集合论]]中，有序对(''a'',''b'')通常定义为[[库拉托夫斯基]]对：
:<math>(a,b)_K \equiv_{def} \{\{a\},\{a,b\}\}</math>
陈述“''x''是有序对''p''的第一个元素”可以公式化为
: <math>\forall \ Y \in p : x \in Y</math>
而陳述“''x''是''p''的第二个元素”为
: <math>(\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))</math>

注意这个定义对于有序对''p'' = (''x'',''x'') = { {''x''}, {''x'',''x''} } = { {''x''}, {''x''} } = { {''x''} }仍是有效的；在这种情况下陈述(∀ ''Y''<sub>1</sub> ∈ ''p'', ∀ ''Y''<sub>2</sub> ∈ ''p'' : ''Y''<sub>1</sub> ≠ ''Y''<sub>2</sub> → (''x'' {{unicode|∉}} ''Y''<sub>1</sub> ∨ ''x'' {{unicode|∉}} ''Y''<sub>2</sub>))顯然是真的，因为不会有''Y''<sub>1</sub> ≠ ''Y''<sub>2</sub>的情况。

=== 变体定义 ===
上述有序对的定义是“充足”的，在它满足有序对必须有的特征性质（也就是：如果(''a'',''b'')=(''x'',''y'')则''a''=''x''且''b''=''y''）的意义上，但也是任意性的，因为有很多其他定义也是不更加复杂并且也是充足的。例如下列可能的定义
# (''a'',''b'')<sub>reverse</sub>:= { {''b''}, {''a'',''b''} }
# (''a'',''b'')<sub>short</sub>:= { ''a'', {''a'',''b''} }
# (''a'', ''b'')<sub>01</sub>:= { {0,''a''}, {1,''b''} }

“逆”（reverse）对基本不使用，因为它比通用的Kuratowski对没有明显的优点（或缺点）。“短”（short）对有一個缺點，它的特征性质的证明會比Kuratowski对的证明更加复杂（要使用[[正规公理]]）；此外，因为在集合论中数2有时定义为集合{ 0, 1 } = { {}, {0} }，这将意味着2是对 (0,0)<sub>short</sub>。

=== 证明有序对的特征性质 ===
'''Kuratowski'''对：
证明：(''a,b'')<sub>K</sub> = (''c,d'')<sub>K</sub>当且仅当''a''=''c''且''b''=''d''。

''僅當：''
:如果''a''=''b''，则 (''a,b'')<sub>K</sub> = {{''a''}, {''a,a''}} = { {''a''} }，且 (''c,d'')<sub>K</sub> = {{''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''}}就會等於<nowiki>{{</nowiki>''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'')<sub>K</sub> = (''c,d'')<sub>K</sub>。


'''逆'''对：
(''a,b'')<sub>reverse</sub> = {{''b''},{''a,b''}} = {{''b''},{''b,a''}} = (''b,a'')<sub>K</sub>。

:如果 (''a,b'')<sub>reverse</sub> = (''c,d'')<sub>reverse</sub>，则 (''b,a'')<sub>K</sub> = (''d,c'')<sub>K</sub>。所以''b=d''且''a=c''。

:反过来，如果''a=c''和''b=d''，则顯然{{''b''},{''a,b''}} = {{''d''},{''c,d''}}。所以 (''a,b'')<sub>reverse</sub> = (''c,d'')<sub>reverse</sub>。

=== Quine-Rosser定义 ===
[[J. Barkley Rosser|Rosser]]（1953年）<ref>[[J. Barkley Rosser]], 1953. ''Logic for Mathematicians''. McGraw-Hill.</ref>扩展了[[蒯因]]的有序对定义。Quine-Rosser的定义要求[[自然数]]的先决定义。设<math>\N</math>是自然数的集合，<math>x \setminus \N</math>是<math>\N</math>在<math>x</math>內的相對差集，並定義：

:<math>\varphi(x) = (x \setminus \N) \cup \{n+1 : n \in (x \cap \N) \}</math>

φ(''x'')包含在''x''中所有自然数的后继，和''x''中的所有非数成员。特别是，φ(''x'')不包含数0，所以对于任何集合''A''和''B''，<math>\phi(A) \not= \{0\} \cup \phi(B)</math>。

以下是有序对 (''A'',''B'')的定义：

:<math>(A, B) = \{\varphi(a) : a \in A\} \cup \{\varphi(b) \cup \{0\} : b \in B \}.</math>

提取这个对中那些不包含0的所有元素，然後再還原<math>\varphi</math>的作用，就得出了''A''。类似的，''B''可以通过提取这个对的包含0的所有元素来復原。

有序对的这个定义有个显著的优点。在[[类型论]]和从类型论派生出的集合论如[[新基础]]中，这个对与它的投影有相同的类型（所以术语叫做“类型齐平”有序对<!--"type-level" ordered pair-->）。因此一個函数（定义为有序对的集合），有只比序對的投影的类型高1的类型。对蒯因集合论中有序对的广泛的讨论请参见Holmes (1998)。<ref>Holmes, Randall (1998) ''[http://math.boisestate.edu/~holmes/holmes/head.pdf  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.</ref>

=== Morse定义 ===
Morse（1965年）<ref>Morse, Anthony P., 1965. ''A Theory of Sets''. Academic Press</ref>提出的[[Morse-Kelley集合论]]可以自由的使用[[真类]]。Morse定义有序对的方法，使得它的投影可以是真类或者集合。（Kuratowski定义不允许这样）。它首先像Kuratowski的方式那樣，定义投影为集合的有序对。接着，他''重定义''对 (''x'',''y'')为 
:<math> (x, y) = (\{0\} \times s(x)) \cup (\{1\} \times s(y))</math>
这里的笛卡尔积是指由Kuratowski对組成的集合並且
:<math> s(x) = \{\emptyset \} \cup \{\{t\} | t \in x\} </math>
這便允許了定義以真類為投影的有序對。

== 参见 ==
* [[笛卡儿积]]
* [[二元关系]]

== 引用 ==
{{reflist}}

[[Category:集合論基本概念|Y]]
[[Category:序理论|Y]]

{{集合论}}