集合論(六):關係
-
定義: 設X、Y為任意的集合,一個由X到Y的二元關係(binary
relation)是指X、Y的卡氏積X×Y的一個子集。如果(x, y)R,記作xRy,稱x與y有關係R。
-
如果X=Y,簡稱R在集合X上的一個二元關係。
-
設S、R是從X到Y的二元關係。稱S、R不相等如果作為集合S≠R。
-
例一:在大學中,把所有男生、女生的總體分別看成X、Y。引入以下的關係R:一個男生xX和另一個女生yY互相認識,則把(x,
y)放入R中,或(x, y)R。這個關係R可以看作男生和女生的認識關係。
-
例二:以上的兩個關係比較熟習,回到數學常用的例子。
設X={1, 2, 3, 4, 5}、Y={0, 1, 2, 3}。定義一個由X到Y的關係RX×Y如下:
-
在X×Y中,(a, b)R當且僅當a+b=5。
如此R={(2, 3)、(3, 2)、(4, 1)、(5, 0) }。在這個例子中,1X不能和Y中任一個數目有關係。
類似地,定義一個由Y到X的關係SY×X如下:
-
在Y×X中,(c, d)S當且僅當c+d=4。
如此S={(0, 4), (1, 3), (2, 2)、(3, 1) }。
-
例三:將所有整數分組,最簡單的,分為兩組(或一般地n組)。把同一組的任意兩個數x、y,視為有關係R,稱為同組關係,即(x,
y)R。
從這個例子,可以更加特殊化,用數學方法作分類:
(I) 分為兩組,按照奇偶性;所得到的關係記為RI。
(II) 分為兩組:非負數,及負數;所得到的關係記為RII。
(III) 分為n組:按照被n除後的(非負)餘數分組;所得到的關係記為RIII。
(IV) (x, y)Rn整數|
x-y | 能被n整除;所得到的關係記為RIV。
作為例子,可以檢查:
(I) (1, 3)、(2, 4)RI;(2,
3)RI。
(II) (1, 2)、(-2, -4)、(1, 0)RII;(2,
-1)RI。
(III) 當n=5時 (1, 6)、(2, 7)、(-1, 4)RIII;(7,
-1)RI。其實-1
=5(-1) +4。
(IV) 當n=5時 (1, 6)、(2, 7)、(-1, 4)RIV;(7,
-1)RI。其實可以證明RIII=RIV。
-
定義:設R是一個從X到Y的二元關係。
-
R中所有有序對的第一元素組成的集合稱為R的前域(或定義域),記作dom(R)。即dom(R)={
x |存在yY,使得(x,
y)R}。
-
類似地,R中所有有序對的第二元素組成的集合稱為R的後域(或值域),記作ran(R)。即ran(R)={
y |存在xX,使得(x,
y)R}。
-
定義:設RX×Y、SY×Z的兩個二元關係。
-
記R-1={ (y, x) Y×X
| (x, y) R}
為Y×X的一個子集,即R-1也是一個從Y到X的關係,稱為R的逆關係。因此有xRy當且僅當yR-1x。
-
記S。R={(x, z)X×Z
| yY(
xRyySz
) }為X×Z的一個子集,即S。R是一個從X到Z的一個關係,稱為R與S的複合。
-
例子:考慮例子二,X={1, 2, 3, 4, 5}、Y={0, 1, 2, 3}。及兩個關係RX×Y,SY×X如下:
-
在X×Y中,(a, b)R當且僅當a+b=5。
R={(2, 3)、(3, 2)、(4, 1)、(5, 0) };
-
在Y×X中,(c, d)S當且僅當c+d=4。
S={(0, 4), (1, 3), (2, 2)、(3, 1) }。
問題:試寫出R的逆關係R-1,及R與S的可能複合關係。
R-1={(3, 2)、(2, 3)、(1, 4)、(0, 5) };基本上是把R中的有序對的兩個坐標互相交換。
由於RX×Y、SY×X及關係複合的定義,可能得兩個複合R。S、S。R,如下:(i)S。R={(2,
1)、(3, 2)、(4, 3)、(5, 4) }及(ii)R。S={(0, 1)、(1, 2)、(2, 3) }。
-
方法一:舉個例:由於(2, 3)R、(3,
1)S所以(2,
1)S。R,以上的方法是針對元素的檢驗。
-
方法二:利用關係式:
(a, d) S。RbY(
aRbbSd
)
bY[(
a+b=5)(b+d=4
)]
bY[(
a+b=5)(b+d=4
)]
→bY[
a - d=1] (這步是要消去b,即a - d =(a+b)-(b+d)=5-4=1)。
→ a - d=1。
最後的兩步只是單向的蘊含。即d=a-1只是(a, d)S的必要條件,但條件的充份性仍未獲證。此時,對於X的任意元素a{2,
3, 4, 5},設b=5-a,則b{0,
1, 2, 3}=Y,如此設c=4-b=a-1{1,
2, 3, 4}X。所以(a,
b)=(a, 5-a)R及(b,
c)=(5-a, a-1)S。因此(a,
d)=(a, a-1)S。R。
-
R。S={(0, 1)、(1, 2)、(2, 3) }。略去解釋,請自行用以上的兩種方法證明。
-
家課七習題:設QX×Y、RY×Z、SZ×W,求證
-
(R-1)-1=R;
-
(S。R)。Q=S。(R。Q),其中Q是從W到X的一個兩元關係;
-
(S。R)-1=R-1。S-1。
家課五、六的澄清:
-
學生問:為何有時在證明中,要加入量詞,但有時又不用加入量詞?
解答:在證明兩個(簡單的)集合相等時,如A=B,通常我們只會用
x A
x ......
x ......
x B。
即使在外延公理中,A=Bx[
xAxB]。
此時,無需加上量詞。因為我們只在證明比較簡單的等價命題:
(xA)(xB)。
如果這等價命題真的成立,則含有量詞(且較深的)命題x[
xAxB]亦自動成立。
註:在以上的情形,減少了量詞(x)在書寫上省了很多麻煩。
此外有時涉及量詞x、x的命題演算不一定是雙向的。(參考
常用邏輯等式
。)
-
學生問:但是為何有時我們在證明過程中,量詞的出現在證明中作著決定性的作用?
解:
-
舉個例:考慮兩個集合A、不相同時。以上的證明方法行不通。所以要從邏輯的角度,改寫集合相等的否定式。
A≠(A=)(x[
xAx]).....x
( xA)。
這時,存在量詞x的出現對A為非空集便是不可缺少的。