查看“︁有序对”︁的源代码

{{各種函數}}

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

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

== 一般性 ==

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

有序对可以有其他有序对作为投影。所以有序对使得能够递归定义有序[[多元组|''n''-元组]]（''n''项的列表）。例如，有序三元组<math>(a,b,c)</math>可以定义为<math>(a,(b,c))</math>，一个对嵌入了另一个对。这种方法也反映在计算机编程语言中，就是从嵌套的有序对构造元素的列表。例如，列表 (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>
陈述“<math>x</math>是有序对<math>p</math>的第一个元素”可以公式化为
: <math>\forall \ Y \in p : x \in Y</math>
而陳述“''<math>x</math>''是''<math>p</math>''的第二个元素”为
: <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>

注意这个定义对于有序对<math>p=(x,x)=\{\{x\},\{x,x\}\}=\{\{x\},\{x\}\}=\{\{x\}\}</math>仍是有效的；在这种情况下陈述（<math>\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)</math>）顯然是真的，因为不会有<math>Y_1 \neq Y_2</math>的情况。

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

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

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

''僅當：''
:如果<math>a=b</math>，则<math>(a,b)_K= \{ \{a\}, \{a,a\} \} = \{\{a\}\}</math>，且<math>(c,d)_K = \{ \{c\}, \{c,d\} \} = \{\{a\}\} </math>。所以<math>\{c\} = \{a\} = \{c,d\}</math>，或<math>c=d=a=b</math>。

:如果<math>a\neq b</math>，则<math>\{\{a\}, \{a,b\}\} = \{\{c\},\{c,d\}\}</math>。

::如果<math>\{c,d\} = \{a\}</math>，则<math>c=d=a</math>或<math>\{\{c\},\{c,d\}\} = \{\{a\}, \{a,a\}\} = \{\{a\}, \{a\}\} = \{ \{a\} \}</math>。但這樣<math>\{\{a\}, \{a, b\}\}</math>就會等於<math>\{\{a\}\}</math>，繼而<math>b = a</math>，跟先前的假設矛盾。

::如果<math>\{c\} = \{a,b\}</math>，则<math>a=b=c</math>，这矛盾于<math>a\neq b</math>。所以<math>\{c\} = \{a\}</math>，即<math>c=a</math>，且<math>\{c,d\} = \{a,b\}</math>。

::并且如果<math>d=a</math>，则<math>\{c,d\} = \{a,a\} = \{a\}\neq\{a,b\}</math>。所以。

:所以同樣有<math>a=c</math>且<math>b=d</math>。

''當：''
:反过来，如果''<math>a=c</math>''并且''<math>b=d</math>''，则顯然<math>\{\{a\},\{a,b\}\} = \{\{c\},\{c,d\}\} </math>。所以<math>(a,b)_K = (c,d)_K</math>。


'''逆'''对：
<math>(a,b)_{\text{reverse}} = \{\{b\},\{a,b\}\} = \{\{b\},\{b,a\}\} = (b,a)_K</math>。

:如果<math>(a,b)_{\text{reverse}} = (c,d)_{\text{reverse}}</math>，则<math>(b,a)_K = (d,c)_K</math>。所以<math>b=d</math>且<math>a=c</math>。

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

=== 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>

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

以下是有序对<math>(A,B)</math>的定义：

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

提取这个对中那些不包含0的所有元素，然後再還原<math>\varphi</math>的作用，就得出了''<math>A</math>''。类似的，''<math>B</math>''可以通过提取这个对的包含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] {{Wayback|url=http://math.boisestate.edu/~holmes/holmes/head.pdf |date=20110411041046 }}''. 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]]