有序对

维基百科，自由的百科全书

在数学中，有序对是两个对象的搜集，使得可以区分出其中一个是“第一个元素”而另一个是“第二个元素” (第一个元素和第二个元素也叫做左投影和右投影)。带有第一个元素 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\}\}\}$

他观察到这个定义将允许《数学原理》中所有类型只使用集合来表达。(在 PM 中，所有元数的关系都是基本的。)

[编辑] 标准 Kuratowski 定义

在公理化集合论中，有序对 (a,b) 通常定义为 Kuratowski 对:

$(a,b)_K \equiv_{def} \{\{a\},\{a,b\}\}$

陈述 x 是有序对 p 的第一个元素可以公式化为

$\forall \ Y \in p : x \in Y$

而 x 是 p 的第二个元素为

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

注意这个定义对于有序对 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} }。

如果 {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年)扩展了蒯因的有序对定义。Quine-Rosser 定义要求自然数的先决定义。设 Nn 是自然数的集合，并定义

$\phi(x) = \{ z : \exists y\in x : (y\in Nn \wedge z = y + 1) \vee (y \not\in Nn \wedge z = y) \}$ 。

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

定义有序对 (A,B) 为毗连 0 到 φ(B) 的每个元素，并形成这个结果同 φ(A) 的并集:

$(A,B) = \phi(A) \cup \{x : \exists y \in\phi(B) : x = y\cup\{0\} \}$

提取这个对的不包含 0 的所有元素生成 A。类似的，B 可以通过提取这个对的包含 0 的所有元素来复原。

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

[编辑] Morse 定义

Morse (1965 年)提出的 Morse-Kelley 集合论自由的使用真类。Morse 定义有序对可以允许它的投影为真类同样于集合。(Kuratowski 定义不允许这样)。它首先定义其投影为 Kuratowski 方式下的集合的有序对。它接着重定义对 (x,y) 为 $(x \times \{0\}) \cup (y \times \{1\})$ ，这里的构成笛卡尔积是在集合上的 Kuratowski 对。这个第二步骤呈现了其投影是真类的可能的对。在前面章节中的 Rosser 定义也允许真类作为投影。

[编辑] 引用

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
J. Barkley Rosser, 1953. Logic for mathematicians. McGraw-Hill.

[编辑] 参见

来自“http://zh.wikipedia.org../../../%E6%9C%89/%E5%BA%8F/%E5%AF%B9/%E6%9C%89%E5%BA%8F%E5%AF%B9.html”

页面分类: 集合論基本概念

有序对