有序对

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

符号${\displaystyle (a,b)}$也表示在实数轴上的开区间；在有歧义的场合可使用符号${\displaystyle \langle a,b\rangle }$。

一般性

设${\displaystyle (a_{1},b_{1})}$和${\displaystyle (a_{2},b_{2})}$是两个有序对。则有序对的特征或定义性质为：

${\displaystyle (a_{1},b_{1})=(a_{2},b_{2})\leftrightarrow (a_{1}=a_{2}\land b_{1}=b_{2})}$

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

有序对的概念对于定义笛卡尔积和关系是至关重要的。

有序对的集合论定义

诺伯特·维纳在1914年提议了有序对的第一个集合论定义：

${\displaystyle (x,y)\equiv _{def}\{\{\{x\},\emptyset \},\{\{y\}\}\}}$

他注意到这个定义将允许《数学原理》中所有类型只透過集合便能表达。（在《数学原理》中，所有元数的关系都是原始概念。）

标准Kuratowski定义

在公理化集合论中，有序对(a,b)通常定义为库拉托夫斯基对：

${\displaystyle (a,b)_{K}\equiv _{def}\{\{a\},\{a,b\}\}}$

陈述“${\displaystyle x}$是有序对${\displaystyle p}$的第一个元素”可以公式化为

${\displaystyle \forall \ Y\in p:x\in Y}$

而陳述“${\displaystyle x}$是${\displaystyle p}$的第二个元素”为

${\displaystyle (\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}))}$

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

变体定义

上述有序对的定义是“充足”的，在它满足有序对必须有的特征性质（也就是：如果${\displaystyle (a,b)=(x,y)}$则${\displaystyle a=x}$且${\displaystyle b=y}$）的意义上，但也是任意性的，因为有很多其他定义也是不更加复杂并且也是充足的。例如下列可能的定义

1. ${\displaystyle (a,b)_{\text{reverse}}:=\{\{b\},\{a,b\}\}}$
2. ${\displaystyle (a,b)_{\text{short}}:=\{a,\{a,b\}\}}$
3. ${\displaystyle (a,b)_{01}:=\{\{0,a\},\{1,b\}\}}$

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

证明有序对的特征性质

Kuratowski对： 证明：${\displaystyle (a,b)_{K}=(c,d)_{K}}$当且仅当${\displaystyle a=c}$且${\displaystyle b=d}$。

僅當：

如果${\displaystyle a=b}$，则${\displaystyle (a,b)_{K}=\{\{a\},\{a,a\}\}=\{\{a\}\}}$，且${\displaystyle (c,d)_{K}=\{\{c\},\{c,d\}\}=\{\{a\}\}}$。所以${\displaystyle \{c\}=\{a\}=\{c,d\}}$，或${\displaystyle c=d=a=b}$。

如果${\displaystyle a\neq b}$，则${\displaystyle \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}}$。

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

如果${\displaystyle \{c\}=\{a,b\}}$，则${\displaystyle a=b=c}$，这矛盾于${\displaystyle a\neq b}$。所以${\displaystyle \{c\}=\{a\}}$，即${\displaystyle c=a}$，且${\displaystyle \{c,d\}=\{a,b\}}$。

并且如果${\displaystyle d=a}$，则${\displaystyle \{c,d\}=\{a,a\}=\{a\}\neq \{a,b\}}$。所以。

所以同樣有${\displaystyle a=c}$且${\displaystyle b=d}$。

當：

反过来，如果${\displaystyle a=c}$并且${\displaystyle b=d}$，则顯然${\displaystyle \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}}$。所以${\displaystyle (a,b)_{K}=(c,d)_{K}}$。

逆对： ${\displaystyle (a,b)_{\text{reverse}}=\{\{b\},\{a,b\}\}=\{\{b\},\{b,a\}\}=(b,a)_{K}}$。

如果${\displaystyle (a,b)_{\text{reverse}}=(c,d)_{\text{reverse}}}$，则${\displaystyle (b,a)_{K}=(d,c)_{K}}$。所以${\displaystyle b=d}$且${\displaystyle a=c}$。

反过来，如果${\displaystyle a=c}$和${\displaystyle b=d}$，则顯然${\displaystyle \{\{b\},\{a,b\}\}=\{\{d\},\{c,d\}\}}$。所以${\displaystyle (a,b)_{\text{reverse}}=(c,d)_{\text{reverse}}}$。

Quine-Rosser定义

Rosser（1953年）^[1]扩展了蒯因的有序对定义。Quine-Rosser的定义要求自然数的先决定义。设${\displaystyle \mathbb {N} }$是自然数的集合，${\displaystyle x\setminus \mathbb {N} }$是${\displaystyle \mathbb {N} }$在${\displaystyle x}$內的相對差集，並定義：

${\displaystyle \varphi (x)=(x\setminus \mathbb {N} )\cup \{n+1:n\in (x\cap \mathbb {N} )\}}$

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

以下是有序对${\displaystyle (A,B)}$的定义：

${\displaystyle (A,B)=\{\varphi (a):a\in A\}\cup \{\varphi (b)\cup \{0\}:b\in B\}.}$

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

有序对的这个定义有个显著的优点。在类型论和从类型论派生出的集合论如新基础中，这个对与它的投影有相同的类型（所以术语叫做“类型齐平”有序对）。因此一個函数（定义为有序对的集合），有只比序對的投影的类型高1的类型。对蒯因集合论中有序对的广泛的讨论请参见Holmes (1998)。^[2]

Morse定义

Morse（1965年）^[3]提出的Morse-Kelley集合论可以自由的使用真类。Morse定义有序对的方法，使得它的投影可以是真类或者集合。（Kuratowski定义不允许这样）。它首先像Kuratowski的方式那樣，定义投影为集合的有序对。接着，他重定义对 (x,y)为

${\displaystyle (x,y)=(\{0\}\times s(x))\cup (\{1\}\times s(y))}$

这里的笛卡尔积是指由Kuratowski对組成的集合並且

${\displaystyle s(x)=\{\emptyset \}\cup \{\{t\}|t\in x\}}$

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