第5講二元關系基本概念

北京大學內容提要1.有序對與卡氏積2.二元關系3.二元關系基本運算/10/101《集合論與圖論》第5講有序對與卡氏積有序對(有序二元組)有序三元組,有序n元組卡氏積卡氏積性質/10/102《集合論與圖論》第5講有序對(orderedpair)有序對:<a,b>={{a},{a,b}}

其中,a是第一元素,b是第二元素.<a,b>也記作(a,b)定理1:<a,b>=<c,d>a=cb=d推論:ab<a,b><b,a>/10/103《集合論與圖論》第5講有序對(引理1)引理1:{x,a}={x,b}a=b證實:()顯然.()分兩種情況.(1)x=a.{x,a}={x,b}{a,a}={a,b}{a}={a,b}a=b.(2)xa.a{x,a}={x,b}a=b.#/10/104《集合論與圖論》第5講有序對(引理2)引理2:若A=B,則(1)∪A=∪B(2)

∩A=∩B證實:(1)x,x∪A

z(zA

xz)z(zB

xz)

x∪B.(2)x,x∩A

z(zA

xz)z(zB

xz)

x∩B.#/10/105《集合論與圖論》第5講有序對(定理1)定理1:<a,b>=<c,d>a=cb=d證實:()顯然.()由引理2,<a,b>=<c,d>{{a},{a,b}}={{c},{c,d}}∪{{a},{a,b}}=∪{{c},{c,d}}{a,b}={c,d}.又{{a},{a,b}}={{c},{c,d}}∩{{a},{a,b}}=∩{{c},{c,d}}{a}={c}a=c.再由引理1,得b=d.#/10/106《集合論與圖論》第5講有序對(推論)推論:ab<a,b><b,a>證實:(反證)<a,b>=<b,a>a=b,與ab矛盾.#/10/107《集合論與圖論》第5講有序三元組(orderedtriple)有序三元組:<a,b,c>=<<a,b>,c>有序n(2)元組:<a1,a2,…,an>=<<a1,a2,…,an-1>,an>定理2:<a1,a2,…,an>=<b1,b2,…,bn>ai

=bi,i=1,2,…,n.#/10/108《集合論與圖論》第5講卡氏積(Cartesianproduct)卡氏積:AB={<x,y>|xAyB}.例:A={,a},B={1,2,3}.AB={<,1>,<,2>,<,3>,<a,1>,<a,2>,<a,3>}.BA={<1,>,<1,a>,<2,>,<2,a>,<3,>,<3,a>}.AA={<,>,<,a>,<a,>,<a,a>}.BB={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}.#/10/109《集合論與圖論》第5講卡氏積性質非交換:AB

BA(除非A=BA=B=)非結合:(AB)CA(BC)(除非A=B=C=)分配律:A(BC)=(AB)(AC)等其它:AB=A=B=等/10/1010《集合論與圖論》第5講卡氏積非交換性非交換:AB

BA(除非A=BA=B=)反例:A={1},B={2}.AB={<1,2>},BA={<2,1>}./10/1011《集合論與圖論》第5講卡氏積非結合性非結合:(AB)CA(BC)(除非A=B=C=)反例:A=B=C={1}.(AB)C={<<1,1>,1>},A(BC)={<1,<1,1>>}./10/1012《集合論與圖論》第5講卡氏積分配律1.A(BC)=(AB)(AC)2.A(BC)=(AB)(AC)3.(BC)A=(BA)(CA)4.(BC)A=(BA)(CA)

/10/1013《集合論與圖論》第5講卡氏積分配律(證實1)A(BC)=(AB)(AC).證實:<x,y>,<x,y>A(BC)xAy(BC)xA(yByC)(xAyB)(xAyC)(<x,y>AB)(<x,y>AC)<x,y>(AB)(AC)

A(BC)=(AB)(AC).#/10/1014《集合論與圖論》第5講例題1例題1:設A,B,C,D是任意集合,(1)AB=A=B=(2)若A,則ABACBC.(3)ACBDABCD,而且當(A=B=)(AB)時,ABCD

ACBD./10/1015《集合論與圖論》第5講卡氏積圖示ABCA(BC)=(AB)(AC)ACBDABCDBACD/10/1016《集合論與圖論》第5講例題1(證實(2))(2)若A,則ABACBC.證實:()若B=,則BC.設B,由A,設xA.y,yB<x,y>AB<x,y>ACxAyCyC.BC/10/1017《集合論與圖論》第5講例題1(證實(2),續)(2)若A,則ABACBC.證實(續):()若B=,則AB=AC.設B.<x,y>,<x,y>AB

xAyBxAyC<x,y>ACABAC.#討論:在()中不需要條件A./10/1018《集合論與圖論》第5講

n維卡氏積n維卡氏積:A1A2…An

={<x1,x2,…,xn>|x1A1x2A2…xnAn}An=AA…A|Ai|=ni,i=1,2,…,n|A1A2…An|=n1n2…nn.n維卡氏積性質與2維卡氏積類似./10/1019《集合論與圖論》第5講n維卡氏積(性質)非交換:ABCBCA(要求A,B,C均非空,且互不相等)非結合:(非2元運算)分配律:比如AB(CD)=(ABC)(ABD)其它:如ABC=A=B=C=./10/1020《集合論與圖論》第5講二元關系n元關系二元關系A到B二元關系A上二元關系一些特殊關系/10/1021《集合論與圖論》第5講n元關系(n-aryrelation)n元關系:是集合,其元素全是有序n元組.例1:F1={<a,b,c,d>,<1,2,3,4>,<物理,化學,生物,數學>},

F1是4元關系.例2:F2={<a,b,c>,<,,>,<大李,小李,老李>}

F2是3元關系.#/10/1022《集合論與圖論》第5講二元關系(binaryrelation)2元關系(簡稱關系):是集合,其元素全是有序對.例3:R1={<1,2>,<,>,<a,b>}R1是2元關系.例4:R2={<1,2>,<3,4>,<白菜,小貓>}R2是2元關系.例5:A={<a,b>,<1,2,3>,a,,1}

A不是關系.#/10/1023《集合論與圖論》第5講二元關系記號設F是二元關系,則<x,y>Fx與y含有F關系xFy對比:xFy

(中綴(infix)記號)

F(x,y)(前綴(prefix)記號)

<x,y>F(后綴(suffix)記號)比如:2<15<(2,15)<2,15><./10/1024《集合論與圖論》第5講A到B二元關系A到B二元關系:是AB任意子集.R是A到B二元關系RABRP(AB)若|A|=m,|B|=n,則|AB|=mn,故|P(AB)|=2mn即A到B不一樣二元關系共有2mn個/10/1025《集合論與圖論》第5講A到B二元關系(舉例)例:設A={a1,a2},B={b},則A到B二元關系共有4個:R1=,R2={<a1,b>},R3={<a2,b>},

R4={<a1,b>,<a2,b>}.

B到A二元關系也有4個:R5=,R6={<b,a1>},R7={<b,a2>},

R8={<b,a1>,<b,a2>}.#/10/1026《集合論與圖論》第5講A上二元關系A上二元關系:是AA任意子集R是A上二元關系RAARP(AA)若|A|=m,則|AA|=m2,故|P(AA)|=即A上不一樣二元關系共有個/10/1027《集合論與圖論》第5講A上二元關系(例1)例1:設A={a1,a2},則A上二元關系共有16個:R1=,R2={<a1,a1>},R3={<a1,a2>},R4={<a2,a1>},R5={<a2,a2>},/10/1028《集合論與圖論》第5講A上二元關系(例1,續1)R6={<a1,a1>,<a1,a2>},R7={<a1,a1>,<a2,a1>},

R8={<a1,a1>,<a2,a2>},R9={<a1,a2>,<a2,a1>},R10={<a1,a2>,<a2,a2>},R11={<a2,a1>,<a2,a2>},/10/1029《集合論與圖論》第5講A上二元關系(例1,續2)R12={<a1,a1>,<a1,a2>,<a2,a1>}R13={<a1,a1>,<a1,a2>,<a2,a2>}R14={<a1,a1>,<a2,a1>,<a2,a2>}R15={<a1,a2>,<a2,a1>,<a2,a2>}

R16={<a1,a1>,<a1,a2>,<a2,a1>,<a2,a2>}.#/10/1030《集合論與圖論》第5講A上二元關系(例2)例2:設B={b},則B上二元關系共有2個:R1=,R2={<b,b>}.#例3:設C={a,b,c},則C上2元關系共有29=512個!#/10/1031《集合論與圖論》第5講一些特殊關系空關系恒等關系全域關系整除關系小于等于關系,…包含關系,真包含關系/10/1032《集合論與圖論》第5講特殊關系設A是任意集合,則能夠定義A上:空關系:恒等關系:IA

={<x,x>|xA}全域關系:EA

=AA={<x,y>|xAyA}/10/1033《集合論與圖論》第5講特殊關系(續)設AZ,則能夠定義A上:整除關系:DA={<x,y>|xAyAx|y}例:A={1,2,3,4,5,6},則DA={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<4,4>,<5,5>,<6,6>}.#/10/1034《集合論與圖論》第5講特殊關系(續)設AR,則能夠定義A上:小于等于(lessthanorequalto)關系:LEA={<x,y>|xAyAxy}小于(lessthan)關系,LA={<x,y>|xAyAx<y}大于等于(greaterthanorequalto)關系大于(greatthan)關系,…/10/1035《集合論與圖論》第5講特殊關系(續)設A為任意集合,則能夠定義P(A)上:包含關系:A

={<x,y>|xAyAxy}真包含關系:A

={<x,y>|xAyAxy}/10/1036《集合論與圖論》第5講與二元關系相關概念定義域,值域,域逆,合成(復合)限制,象單根,單值/10/1037《集合論與圖論》第5講定義域,值域,域對任意集合R,能夠定義:定義域(domain)

:domR={x|y(xRy)}值域(range):ranR={y|x(xRy)}域(field):fldR=domRranR/10/1038《集合論與圖論》第5講定義域,值域,域圖示ABdom

R

ran

R

/10/1039《集合論與圖論》第5講定義域,值域,域(舉例)例:R1={a,b},R2={a,b,<c,d>,<e,f>},R3={<1,2>,<3,4>,<5,6>}.

當a,b不是有序對時,R1和R2不是關系.domR1=,ranR1=,fldR1=domR2={c,e},ranR2={d,f},fldR2={c,d,e,f}domR3={1,3,5},ranR3={2,4,6},fldR3={1,2,3,4,5,6}.#/10/1040《集合論與圖論》第5講逆,合成(復合)對任意集合F,G,能夠定義:逆(inverse)

:F-1={<x,y>|yFx}合成(復合)(composite):F○G={<x,y>|z(xGz

zFy)}xzyGF/10/1041《集合論與圖論》第5講關于合成次序合成(右合成):F○G={<x,y>|z(xFzzGy)}逆序合成(左合成):F○G={<x,y>|z(xGzzFy)}/10/1042《集合論與圖論》第5講限制,象對任意集合F,A,能夠定義:限制(restriction):FA={<x,y>|xFyxA}象(image):F[A]=ran(FA)F[A]

=

{y|x(xAxRy)}/10/1043《集合論與圖論》第5講單根,單值對任意集合F,能夠定義:單根(singlerooted):F是單根y(yranF!x(xdomFxFy))(yranF)(!xdomF)(xFy)單值(singlevalued):F是單值x(xdomF!y(yranFxFy))(xdomF)(!yranF)(xFy)/10/1044《集合論與圖論》第5講例題2例2:設A={a,b,c,d},B={a,b,<c,d>},R={<a,b>,<c,d>},F={<a,b>,<a,{a}>,<{a},{a,{a}}>},G={<b,e>,<d,c>}.求:(1)A-1,B-1,R-1.(2)B○R-1,G○B,G○R,R○G.(3)F{a},F{{a}},F{a,{a}},F-1{{a}}.(4)F[{a}],F[{a,{a}}],F-1[{a}],F-1[{{a}}]./10/1045《集合論與圖論》第5講例題2(解(1))已知:A={a,b,c,d},B={a,b,<c,d>},R={<a,b>,<c,d>},求:(1)A-1,B-1,R-1.解:(1)A-1=,B-1={<d,c>},R-1={<b,a>,<d,c>}./10/1046《集合論與圖論》第5講例題2(解(2))已知:B={a,b,<c,d>},R={<a,b>,<c,d>},G={<b,e>,<d,c>}.求:(2)B○R-1,G○B,G○R,R○G.解:(2)B○R-1={<d,d>},G○B={<c,c>},G○R={<a,e>,<c,c>},R○G={<d,d>}./10/1047《集合論與圖論》第5講例題2(解(3))已知:F={<a,b>,<a,{a}>,<{a},{a,{a}}>},求:(3)F{a},F{{a}},F{a,{a}},F-1{{a}}.解:(3)F{a}={<a,b>,<a,{a}>},F{{a}}={<{a},{a,{a}}>},F{a,{a}}=F,F-1{{a}}={<{a},a>}./10/1048《集合論與圖論》第5講例題2(解(4))已知:F={<a,b>,<a,{a}>,<{a},{a,{a}}>},求:(4)F[{a}],F[{a,{a}}],F-1[{a}],F-1[{{a}}].解:(4)F[{a}]={b,{a}},F[{a,{a}}]={b,{a},{a,{a}}

},F-1[{a}]=,F-1[{{a}}]={a}.#/10/1049《集合論與圖論》第5講例題3設R={<x,y>|x,yZy=|x|

},A={0,1,2},B={0,-1,-2}求:(1)R[AB]和R[A]R[B];(2)R[A]-R[B]和R[A-B].解:(1)R[AB]=R[{0}]={0},R[A]R[B]={0,1,2}{0,1,2}={0,1,2};(2)R[A]-R[B]={0,1,2}-{0,1,2}=,

R[A-B]=R[{1,2}]={1,2}.#/10/1050《集合論與圖論》第5講定理3定理3:設F,G是任意集合,則(1)dom(FG)=domFdomG(2)ran(FG)=ranFranG(3)dom(FG)domFdomG(4)ran(FG)ranFranG(5)domF-domGdom(F-G)(6)ranF-ranGran(F-G)/10/1051《集合論與圖論》第5講定理3(證實(1))(1)dom(FG)=domFdomG證實:(1)x,xdom(FG)y(x(FG)y)y(xFyxGy)y(xFy)y(xGy)xdomFxdomGxdomFdomGdom(FG)=domFdomG./10/1052《集合論與圖論》第5講定理3(證實(4))(4)ran(FG)ranFranG證實:(4)x,xran(FG)y(y(FG)x)y(yFxyGx)y(yFx)

y(yGx)xranFxranGxranFranGran(FG)ranFranG./10/1053《集合論與圖論》第5講定理3(證實(5))(5)domF-domGdom(F-G)證實:(5)x,xdomF-domGxdomFxdomG

y(xFy)y(xGy)y(xFy)y(xGy)y(x(F-G)y)xdom(F-G)domF-domGdom(F-G).#/10/1054《集合論與圖論》第5講定理4定理4:設F是任意集合,則(1)domF-1=ranF;(2)ranF-1=domF;(3)(F-1)-1

F,當F是關系時,等號成立./10/1055《集合論與圖論》第5講定理4(證實(1))(1)domF-1=ranF;證實:(1)x,xdo