有序对

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

一般性[编辑]

设 (a1, b1) 和 (a2, b2) 是两个有序对。则有序对的特征或定义性质为:

(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

而陳述“ xp 的第二个元素”为

(\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} } 仍是有效的;在这种情况下陈述(∀ Y1p, ∀ Y2p : Y1Y2 → (x Y1x Y2))顯然是真的,因为不会有 Y1Y2 的情况。

变体定义[编辑]

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

  1. (a,b)reverse:= { {b}, {a,b} }
  2. (a,b)short:= { a, {a,b} }
  3. (a, b)01:= { {0,a}, {1,b} }

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

证明有序对的特征性质[编辑]

Kuratowski 对: 证明:(a,b)K = (c,d)K 当且仅当 a=cb=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
如果 ab,则 {{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,这矛盾于 ab。所以 {c} = {a},即 c=a,且 {c,d} = {a,b}。
并且如果 d=a,则 {c,d} = {a,a} = {a}≠{a,b}。所以 d=b
所以同樣有 a=cb=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=da=c
反过来,如果 a=cb=d,则顯然 {{b},{a,b}} = {{d},{c,d}}。所以 (a,b)reverse = (c,d)reverse

Quine-Rosser 定义[编辑]

Rosser(1953年)[1]扩展了蒯因的有序对定义。Quine-Rosser 的定义要求自然数的先决定义。设 \N 是自然数的集合,x \setminus \N\Nx內的相對差集,並定義:

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

φ(x) 包含在 x 中所有自然数的后继,和 x 中的所有非数成员。特别是,φ(x) 不包含数 0,所以对于任何集合 AB\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\}

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

参见[编辑]

引用[编辑]

  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