有序對
各種函數 |
---|
x ↦ f (x) |
不同定義域和陪域 |
函數類/性質 |
構造 |
推廣 |
在數學中,有序對是兩個對象的搜集,使得可以區分出其中一個是「第一個元素」而另一個是「第二個元素」(第一個元素和第二個元素也叫做左投影和右投影)。帶有第一個元素a和第二個元素b的有序對通常寫為(a, b)。
符號(a, b)也表示在實數軸上的開區間;在有歧義的場合可使用符號。
一般性
設(a1, b1)和(a2, b2)是兩個有序對。則有序對的特徵或定義性質為:
有序對可以有其他有序對作為投影。所以有序對使得能夠遞歸定義有序n-元組(n項的列表)。例如,有序三元組 (a,b,c)可以定義為(a, (b,c)),一個對嵌入了另一個對。這種方法也反映在計算機編程語言中,就是從嵌套的有序對構造元素的列表。例如,列表 (1 2 3 4 5)變成了(1, (2, (3, (4, (5, {} )))))。Lisp編程語言使用這種列表作為基本數據結構。
有序對的集合論定義
諾伯特·維納在1914年提議了有序對的第一個集合論定義:
他注意到這個定義將允許《數學原理》中所有類型只透過集合便能表達。(在《數學原理》中,所有元數的關係都是原始概念。)
標準Kuratowski定義
在公理化集合論中,有序對(a,b)通常定義為庫拉托夫斯基對:
陳述「x是有序對p的第一個元素」可以公式化為
而陳述「x是p的第二個元素」為
注意這個定義對於有序對p = (x,x) = { {x}, {x,x} } = { {x}, {x} } = { {x} }仍是有效的;在這種情況下陳述(∀ Y1 ∈ p, ∀ Y2 ∈ p : Y1 ≠ Y2 → (x ∉ Y1 ∨ x ∉ Y2))顯然是真的,因為不會有Y1 ≠ Y2的情況。
變體定義
上述有序對的定義是「充足」的,在它滿足有序對必須有的特徵性質(也就是:如果(a,b)=(x,y)則a=x且b=y)的意義上,但也是任意性的,因為有很多其他定義也是不更加複雜並且也是充足的。例如下列可能的定義
- (a,b)reverse:= { {b}, {a,b} }
- (a,b)short:= { a, {a,b} }
- (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=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} }。但這樣{{a}, {a, b}}就會等於{{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)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年)[1]擴展了蒯因的有序對定義。Quine-Rosser的定義要求自然數的先決定義。設是自然數的集合,是在內的相對差集,並定義:
φ(x)包含在x中所有自然數的後繼,和x中的所有非數成員。特別是,φ(x)不包含數0,所以對於任何集合A和B,。
以下是有序對 (A,B)的定義:
提取這個對中那些不包含0的所有元素,然後再還原的作用,就得出了A。類似的,B可以通過提取這個對的包含0的所有元素來復原。
有序對的這個定義有個顯著的優點。在類型論和從類型論派生出的集合論如新基礎中,這個對與它的投影有相同的類型(所以術語叫做「類型齊平」有序對)。因此一個函數(定義為有序對的集合),有隻比序對的投影的類型高1的類型。對蒯因集合論中有序對的廣泛的討論請參見Holmes (1998)。[2]
Morse定義
Morse(1965年)[3]提出的Morse-Kelley集合論可以自由的使用真類。Morse定義有序對的方法,使得它的投影可以是真類或者集合。(Kuratowski定義不允許這樣)。它首先像Kuratowski的方式那樣,定義投影為集合的有序對。接着,他重定義對 (x,y)為
這裡的笛卡爾積是指由Kuratowski對組成的集合並且
這便允許了定義以真類為投影的有序對。
參考文獻
- ^ J. Barkley Rosser, 1953. Logic for Mathematicians. McGraw-Hill.
- ^ 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
參見
|