2. Quan hÖ trªn mét tËp.
Mét quan hÖ( hoÆc quan hÖ hai ng«i) S trªn tËp E lµ mét phÐp t¬ng øng d¹ng S=(E,E,G). NÕu S,S’ lµ c¸c quan hÖ trªn E th× SoS’ vµ S-1 còng lµ c¸c quan hÖ trªn E. Quan hÖ S-1 gäi lµ quan hÖ ngîc cña quan hÖ S.
Gi¶ sö x,y E, nÕu x S y th× ta nãi r»ng phÇn tö x n»m trong quan hÖ S víi phÇn tö y.
Quan hÖ cã ®å thÞ lµ ®êng chÐo
E = (x, x) : x E
Gäi lµ quan hÖ ®ång nhÊt trªn E.
Gi¶ sö S = (E, E, G), khi ®ã:
S gäi lµ quan hÖ ®èi xøng nÕu E G, tøc lµ x S x,x E.
S gäi lµ quan hÖ b¸c cÇu nÕu S oS S tøc lµ nÕu x S y vµ y S z th× xSz.
S gäi lµ quan hÖ ®èi xøng nÕu S = S-1, tøc lµ nÕu xS y th× y S x.
S gäi lµ quan hÖ ph¶n ®èi xøng nÕu G G-1 = E, tøc lµ nÕu x S y vµ y S x th× x= y.
Ta còng sö dônh thuËt ng÷ t¬ng tù ®èi víi ®å thÞ G cña quan hÖ S. ViÖc nghiªn cøu c¸c quan hÖ trªn mét tËp (thêng dÉn tíi ngiªn cøu c¸c ®å thÞ cña chóng) tá ra rÊt h÷u Ých vµ lÝ thó trong nhiÌu lÜnh vùc lý thuyÕt còng nh ¸p dông (c¸c vÊn ®Ò vÒ ph©n lo¹i, t« mµu, lu th«ng , c¸c d©y chuyÒn MarKov,.v.v…). Do ®ã ë ®©y chóng ta còng nªn lµm quen víi mét sè kh¸I niÖm quan träng cña lý thuyÕt ®å thÞ.
Gi¶ sö G lµ mét ®å thÞ trªn tËp E, tøc lµ G E E. Khi ®ã c¸c phÇn tö cña E gäi lµ c¸c ®Ønh cña ®å thÞ G. Mçi cÆp (x,y) G gäi lµ mét cung cña ®å thÞ G, phÇn tö x gäi lµ gèc cña cung, phÇn tö y gäi lµ ngän cña cung. Mçi cung d¹ng (x,x) gäi lµ mét khuyªn cña ®å thÞ G.
Mét dêng ®i trªn ®å thÞ G lµ mét d·y kh¸c rçng (x1,x2,…xk) c¸c ®Ønh cña G sao cho (xi, xi+1) lµ mét cung cña G, i=1,2,…, k-1. §Ønh x1 gäi lµ gèc, ®Ønh xk gäi lµ ngän cña ®êng ®i. §é dµi cña ®êng ®I lµ k-1.
Víi mçi x E, theo ®Þnh nghÜa th× d·y (x) lµ mét ®êng ®I trªn G, cã ®é dµi 0. Gèc vµ ngän cña ®êng ®I (x) trïng nhau. Chó ý r»ng nÕu khuyªn (x,x) G th× (x) vµ (x,x) lµ hai ®êng ®I kh¸c nhau, v× ®êng ®I (x,x) cã ®é dµi b»ng 1.
3. Quan hÖ t¬ng ®¬ng.
§Þnh nghÜa:
Mét quan hÖ trªn tËp gäi lµ quan hÖ t¬ng ®¬ng nÕu ®ã lµ quan hÖ ph¶n x¹, ®èi xøng vµ b¸c cÇu.
Gi¶ sö S lµ mét quan hÖ t¬ng ®¬ng trªn E. Khi ®ã quan hÖ ph¶n x¹, ®èi xøng b¸c cÇu.
Gi¶ sö S lµ mét quan hÖ t¬ng ®¬ng trªn E, víi mçi phÇn tö x E, tËp con
S(x) = x’ E : x S x’
gäi lµ líp t¬ng ®¬ng theo S cña phÇn tö x, thêng ®îc ký hiÖu = S(x).
MÖnh ®Ò 1.5:
Gi¶ sö S lµ mét quan hÖ t¬ng ®¬ng trªn E. Khi ®ã tËp c¸c líp t¬ng ®¬ng theo S lµ mét sù chia líp cña tËp E.
Ngîc l¹i nÕu AiiI mét sù chia líp cö tËp E. Khi ®ã tån t¹i duy nhÊt mét quan hÖ t¬ng ®¬ng trªn E, cã c¸c líp t¬ng ®¬ng lµ c¸c tËp con Ai, iI
Chøng minh:
Gi¶ sö S lµ mét quan hÖ t¬ng ®¬ng trªn E. V× S ph¶n x¹ nªn x S(x), x E. E. VËy hä c¸c líp t¬ng ®¬ng theo S lµ mét c¸I phñ cña E, E=R(x) vµ R(x) x E. Ta sÏ chøng tá r»ng nÕu x’S(x) th× S(x’)= S(x). ThËt vËy nÕu x’S(x) th× x S x’. Gi¶ sö yS(x’) th× x’ S y, theo tÝnh b¾c cÇu cña S ta cã x S y. Do ®ã yS(x). VËy ta cã S(x) S(x). Theo tÝnh ®èi xøng cña S nÕu x S x’ th× x’ S x. Theo ®Þnh nghÜa x S(x’). Mét c¸ch t¬ng tù ta cã S(x) S(x’). VËy S(x) = S(x’). Do ®ã nÕu hai líp S(x) vµ S(y) cã mét ®iÓm chung z th× S(x)= S(z) = S(y). Tõ ®ã suy ra r»ng c¸c líp t¬ng ®¬ng theo S hoÆc trïng nhau hoÆc rêi nhu. VËy hä c¸c líp t¬ng ®¬ng theo S lµ mét sù chia líp cña tËp E.
Ngîc l¹i gi¶ sö AiiI lµ sù chia líp cña tËp E. Khi ®ã dÔ dµng thÊy r»ng S = lµ mét quan hÖ t¬ng ®¬ng duy nhÊt trªn E cã c¸c líp t¬ng ®¬ng lµ c¸c tËp Ai, iI.
Tõ mÖnh ®Ò 1.5 suy ra r»ng gi÷a tËp c¸c quan hÖ t¬ng ®¬ng trªn tËp E vµ tËp c¸c chia líp cña tËp E cã sù t¬ng øng 1-1.
§4 tËp ®îc s¾p
1. Quan hÖ thø tù
a. Quan hÖ thø tù.
Quan hÖ thø tù trªn mét tËp lµ mét quan hÖ cã tÝnh ph¶n x¹, b¾c cÇu vµ ph¶n ®èi xøng.
C¸c quan hÖ thø tù thêng ký hiÖu bëi . TËp E ®îc trang bÞ mét quan hÖ thø tù gäi lµ tËp ®îc s¾p, ký hiÖu lµ(E, ).
§Þnh nghÜa cã thÓ ph¸t biÓu nh sau:
Quan hÖ thø tù trªn E lµ mét quan hÖ tho¶ m·n c¸c tÝnh chÊt:
x x (tÝnh ph¶n x¹)
x y vµ y z th× x z ( tÝnh b¾c cÇu)
x y vµ y x th× x= y( tÝnh chÊt ph¶n ®èi xøng)
NÕu x y ta nãi x ®i tríc y hoÆc y ®i sau x. NÕu x y vµ x y ta viÕt x< y (gäi lµ bÊt ®¼ng thøc chÆt).
TËp ®îc s¾p (E, ) gäi lµ ®îc s¾p hoµn toµn (hoÆc s¾p tuyÕn tÝnh) nÕu víi hai phÇn tö x, y bÊt k× cñatËp E lu«n lu«n so s¸nh ®îc, tøc lµ hoÆc x y hoÆc y x.
D©y chuyÒn:TËp con A E ®îc gäi lµ mét d©y truyÒn trong (E, ) nÕu A lµ tËp ®îc s¾p hoµn toµn bëi thø tù trong E (tøc lµ víi x, y A, y x trong A khi vµ chØ khi y x trong (E , ).
VÝ dô: cã nhiÒu vÝ dô vÒ tËp ®îc s¾p, ch¼ng h¹n:
P(X): A B khi vµ chØ khi A B. NÕu X lµ tËp cã h¬n 1 phÇn tö th× thø tù bao hµm kh«ng ph¶I lµ thø tù hoµn toµn.
Theo thø tù th«ng thêng N, Z, Q, R lµ c¸c t¹p ®îc s¾p tuyÕn tÝnh.
Gi¶ sö f lµ mét ¸nh x¹ tõ tËp ®îc s¾p (E, ) vµo tËp ®îc s¾p (E’, ). f gäi lµ ¸nh x¹ t¨ng (hoÆc ®ång cÊu ) nÕu x y th× f(x) f(y). f gäi lµ ¸nh x¹ gi¶m nÕu x y th× f(y) f(x). NÕu f lµ mét song ¸nh sao cho f vµ f-1 lµ c¸c ®ång cÊu th× f lµ mét ®¼ng cÊu tõ (E, ) lªn (E’, ).
Gi¶ sö (E, S) lµ tËp ®îc s¾p. Khi ®ã S-1 còng lµ mét quan hÖ thø trªn E vµ gäi lµ thø tù ngîc cña thø tù S. NÕu thø tù S kÝ hiÖu bëi th× thø tù ngîc S-1 ®îc kÝ hiÖu .
VÝ dô:
Trªn tËp N xÐt quan hÖ “íc sè” S: x, y N, x S y khi vµ chØ khi x lµ íc sè cña y. Khi ®ã quan hÖ ngîc S-1 lµ quan hÖ “béi sè” x, y N, x S-1y khi vµ chØ khi x lµ béi sè cña y.
Gi¶ sö (E, R) vµ (E’, S) lµ c¸c tËp ®îc s¾p. Mét ®¼ng cÊu tõ (E, R) lªn (E’,S). Ch¼ng h¹n ¸nh x¹ ®ång nhÊt idE lµ mét ph¶n ®¼ng cÊu tõ (E, R) lªn (E, R-1).
b. Quan hÖ tiÒn thø tù.
Quan hÖ tiÒn thø tù trªn mét tËplµ c¸c quan hÖ ph¶n x¹, b¾c cÇu.
VÝ dô:
Quan hÖ “ íc sè” S lµ mét quan hÖ tiÒn thø tù trªn tËp c¸c sè nguyªn Z. Quan hÖ nµy kh«ng ph¶i lµ quan hÖ thø tù trªn Z v× 1 chia hÕt cho -1 vµ -1 chia hÕt cho 1 vµ -1 1.
Mét quan hÖ tiÒn thø tù trªn mét tËp sÏ c¶m sinh mét quan hÖ thø tù trªn tËp th¬ng cña tËp ®· cho theo quan hÖ t¬ng ®¬ng:
X y x y vµ y x.
c. Thø tù tù ®iÓn.
Gi¶ sö (E1, ), … , (En, ) lµ c¸c tËp ®îc s¾p hoµn toµn. Thø tù tù ®iÓn trªn tËp tÝnh E1 ... En, ) lµ c¸c thø tù x¸c ®Þnh bëi ®¼ng thøc chÆt sau ®©y:
(x1, x2, … , xn) < ( y1, y2, …,yn) khi vµ chØ khi tån t¹i i n sao cho xk=yk víi k = 1, 2, …. ,i-1 vµ xi < y1.
DÔ dµng thÊy r»ng thø tù tù ®iÓn còng lµ mét thø tù hoµn toµn.
VÝ dô:
Gi¶ sö E = x, y, z ®îc s¾p theo quan hÖ x < y < z. TËp E3 = E EE cã 27 phÇn tö ph©n biÖt. Ta cã thÓ xem 27 phÇn tö ®ã nh 27 tõ kh¸c nhau, mçi tõ ®îc viÕt bëi 3 ch÷ c¸i tõ c¸c ch÷ x, y ,z. Thø tù tù ®iÓn trªn tËp E EE lµ
xxx < xxy < xxz < xyy < … < zzy < zzz.
§ã còng lµ c¸ch s¾p xÕp thø tù c¸c tõ cña tù ®iÓn. §iÒu ®ã gi¶i thÝch nguån gèc cña thuËt ng÷ “Thø tù tù ®iÓn”.
2. CËn trªn, cËn díi.
a. CËn trªn vµ cËn díi.
Gi¶ sö x, y lµ c¸c phÇn tö cña tËp ®îc s¾p (E, ). NÕu x y th× ta nãi r»ng phÇn tö y lµ cËn trªn cña phÇn tö x vµ phÇn tö x lµ cËn díi cña phÇn tö lµ cËn díi cña phÇn tö y.
PhÇn tö a gäi lµ cËn trªn cña tËp con A E nÕu a lµ cËn trªn cña tÊt c¶ c¸c phÇn tö thuéc tËp A. CËn díi cña tËp con A ®îc ®Þnh nghÜa mét c¸ch t¬ng tù. TËp c¸c cËn trªn, cËn díi cña tËp con A ®îc kÝ hiÖu t¬ng øng bëi M(A), m(A).
PhÇn tö x E gäi lµ phÇn tö tèi ®¹i (hoÆc max) nÕu M(x) = x vµ gäi lµ phÇn tö tèi tiÓu(hoÆc min) nÕu m(x) = x.
Chó ý r»ng trong mét tËp ®îc s¾p cã thÓ nhiÒu phÇn tö tèi ®¹i hoÆc tèi tiÓu. Ch¼ng h¹n trong tËp E = N -1 ®îc s¾p theo quan hÖ thø tù x y khi vµ chØ khi x lµ béi cña lµ béi cña y. Khi ®ã c¸c sè nguyªn tè lµ c¸c phÇn tö tèi ®¹i.
DÔ thÊy r»ng c¸c tËp A M(A) vµ A m(A) mçi tËp kh«ng cã qu¸ mét phÇn tö. NÕu A M(A) , phÇn tö duy nhÊt a* gäi lµ phÇn tö lín nhÊt cña tËp A vµ nÕu A m(A) , phÇn tö, phÇn tö a* cña A m(A) gäi lµ phÇn tö bÐ nhÊt cña tËp A.
PhÇn tö nhá nhÊt cña tËp M(A) (nÕu cã) gäi lµ cËn trªn ®óng cña tËp A, ký hiÖu bëi Sup A, vËy
Sup A = m( M(A)) M (A).
PhÇn tö lín cña tËp m(A) (nÕu cã) gäi lµ cËn díi ®óng cña tËp A, kÝ hiÖu bëi Inf A, vËy
Inf A = M(m(A)) m(A).
b. Kh¸i niÖm dµn.
Mét tËp ®îc s¾p mµ mäi cÆp phÇn tö x, y ®Òu cã cËn trªn ®óng Supx, y vµ cËn díi ®óng infx, y dîc gäi lµ mét dµn.
VÝ dô:
TËp ®îc s¾p P(X) theo thø tù bao hµm lµ mét dµn:
A, B P(X), supA, B = A B,
Inf A, B = A B
TËp ®îc s¾p hoµn toµn lµ mét dµn.
c. TËp s¾p tèt.
TËp ®îc s¾p (E, ) gäi lµ tËp s¾p tèt nÕu mäi tËp con kh¸c rçng cña E ®Òu cã phÇn tö bÐ nhÊt.
PhÇn tö bÐ nhÊt cuae E cßn gäi lµ phÇn tö ®Çu tiªn.
VÝ dô: N lµ tËp ®îc s¾p tèt theo quan hÖ so s¸nh th«ng thêng. Nhng Z, Q, R víi quan hÖ thø tù th«ng thêng kh«ng ph¶I lµ mét tËp ®îc s¾p tèt.
MÖnh ®Ò 1.6 ( Nguyªn lý quy n¹p siªu h¹n):
Gi¶ sö (E, ) lµ tËp s¾p tèt. NÕu phÇn tö ®Çu tiªn cña E cã tÝnh chÊt P vµ nÕu tõ gi¶ thiÕt mäi phÇn tö x E mµ x < a ®Ìu cã tÝnh chÊt P suy ra phÇn tö a còng cã tÝnh chÊt P th× mäi phÇn tö cña tËp E cã tÝnh chÊt P.
Chøng minh:
Gäi lµ tËp tÊt c¶ c¸c phÇn tö cña tËp E kh«ng cã tÝnh chÊt P. NÕu A th× A cã phÇn tö bÐ nhÊt lµ ao. Khi ®ã mäi phÇn tö x E mµ x < ao ®Òu cã tÝnh chÊt P; theo gi¶ thiÕt phÇn tö ao còng cã tÝnh chÊt P. §iÒu nµy m©u thuÉn víi gi¶ thiÕt ao A. VËy A = .
3. C¸c mÖnh ®Ò t¬ng ®¬ng víi tiªn ®Ò chän.
§Þnh lý 1.7:
C¸c ®iÒu kh¼ng ®Þnh sau lµ t¬ng ®¬ng:
Tiªn ®Ò chän: NÕu ®· cho mét tËp E th× víi mçi tËp con A cña E cã thÓ chän ®îc mét phÇn tö (A) A.
§Þnh lý Zermelo: Mäi tËp ®Òu cã thÓ s¾p tèt.
Bæ ®Ò Zoãc: NÕu mäi d©y chuyÒn cña tËp ®îc s¾p (E, ) cã cËn trªn trong E th× mçi phÇn tö cña E ®îc chøa trong mét phÇn tö tèi ®¹i, tøc lµ x E, a tèi ®¹i: x a.i
Chøng minh:
a) Tiªn ®Ò chän suy ra ®Þnh lý Zermelo.
Gi¶ sö (A, ) lµ tËp ®îc s¾p. Víi mçi a A, tËp Pa =x A:x gäi lµ mét ®äan cña (A, ) x¸c ®Þnh bëi phÇn tö a. NÕu a lµ mét phÇn tö tèi thiÓu th× Pa . DÔ thÊy r»ng nÕu (A, ) lµ tËp ®îc s¾p hoµn toµn th× hîp, giao cña c¸c ®o¹n cña (A, ) lµ mét ®o¹n cña(A, ).
Gi¶ sö E lµ tËp kh¸c rçng cho tríc. Theo tiªn ®Ò chän víi mçi tËp A cña E ta cã thÓ chän ®îc mét phÇn tö (A) A x¸c ®Þnh.
TËp con A cña E gäi lµ tËp con tèt nÕu A ®îc s¾p tèt vµ víi mçi aA ta cã a = (E- Pa). C¸c tËp con tèt cña E tån t¹i, ch¼ng h¹n tËp chØ gåm mét phÇn tö (E). DÔ thÊy r»ng (E) lµ phÇn tö ®Çu tiªn cña c¸c tËp con tèt cña E.
Gi¶ sö A, B lµ hai tËp con tèt cña E. V× A, B lµ c¸c tËp ®îc s¾p tèt cã chung phÇn tö ®Çu tiªn (E) nªn chóng cã nh÷ng ®o¹n chung kh¸c rçng . Gäi C lµ hîp c¸c ®o¹n chung cña A vµ B. C lµ mét ®o¹n cña A vµ cña B vµ lµ ®o¹n chung lín nhÊt. NÕu A C vµ B C, theo ®Þnh nghÜa tËp con tèt, tån t¹i phÇn tö c A B sao cho C = Pc vµ c = (E – Pc). VËy A vµ B cã ®o¹n chung C’ = A c lín h¬n ®o¹n chung C, ®iÒu nµy v« lý v× C lµ ®o¹n chung lín nhÊt. VËy trong hai tËp con tèt A vµ B cã mét tËp sÏ lµ mét ®o¹n cña tËp kia.
Gäi M lµ hîp tÊt c¶ c¸c tËp con tèt cña tËp E. Ta sÏ chøng tá r»ng M còng lµ mét tËp con tèt cña E. Trong M chóng ta x©y dùng mét quan hÖ thø tù nh sau: Víi hai phÇn tö a, b M, theo chøng minh trªn tån t¹i mét tËp con tèt A cña E chóa c¸c phÇn tö a vµ b. NÕu a b trong M. Gi¶ sö N lµ mét tËp con kh¸c rçng cña M. Khi ®ã tån t¹i tËp con tèt B cña E sao cho N B . DÔ thÊy r»ng phÇn tö bÐ nhÊt cña tËp N B trong B còng lµ phÇn tö bÐ nhÊt cña N trong M. VËy tËp M ®îc s¾p tèt. Víi aM th× a sÏ thuéc tËp con tèt A nµo ®ã cña E. Khi ®ã phÇn tö a sÏ x¸c ®Þnh trong M vµ trong A cïng méy ®o¹n Pa vµ a = (E – Pa). VËy M lµ tËp con tèt lín nhÊt cña tËp E.
NÕu M E, khi ®ã b»ng c¸ch coi phÇn tö (E – M) ®I sau mäi phÇn tö thuéc M th× tËp M’ = M (E – M) sÏ lµ mét tËp con tèt cña E chøa tËp M. VËy M = E vµ E ®îc s¾p tèt.
b) §Þnh lý Zermelo suy ra bæ ®Ò Zoãc.
Gi¶ sö r»ng mäi d©y chuyÒn cña tËp ®îc s¾p (E, ) ®Òu cã cËn trªn trong E. Ta sÏ chøng tá r»ng víi mçi phÇn tö a E trong (E, ) tån t¹i phÇn tö m tèi ®¹i sao cho a m.
Theo ®Þnh lý Zermelo, sÏ tån t¹i mét quan hÖ thø tù sao cho (E,) lµ tËp s¾p tèt. Nãi chung (E, ) (E, ).
Ta sÏ ph©n lo¹i c¸c phÇn tö cña E ra hai lo¹i: lo¹i 1 vµ lo¹i 2.
Gi¶ sö xo lµ phÇn tö ®µu tiªn cña (E, ).
PhÇn tö xo thuéc lo¹i 1 nÕu a xo; xo thuéc lo¹i 2 trong c¸c trêng hîp kh¸c. Gi¶ sö ta ®· ph©n lo¹i ®îc mäi phÇn tö x’x sao cho x’ thuéc lo¹i 1 nÕu trong (E, ), x’ ®i sau a vµ ®i sau mäi phÇn tö thuéc lo¹i 1 ®· cã vµ x’ thuéc lo¹i 2 trong c¸c trêng hîp kh¸c. ThÕ th× x sÏ thuéc lo¹i 1 nÕu trong ( E, ) x ®I sau a vµ ®i sau mäi phÇn tö thuéc lo¹i 1 ®· cã vµ x thuéc lo¹i 2 trong c¸c trêng hîp kh¸c.
Theo nguyªn lý quy n¹p siªu h¹n ta ph©n lo¹i ®îc mäi phÇn tö thuéc E. Gäi A lµ tËp tÊt c¶ c¸c phÇn tö thuéc lo¹i 1. DÔ th¸y r»ng, A lµ mét d©y truyÒn trong (E, ). Theo gi¶ thiÕt A cã Ýt nhÊt mét cËn trªn m nµo ®ã trong (E, ). Ta cã a m. Gi¶ sö n lµ mét cËn trªn cña m trong (E,), tøc lµ m n. Khi ®ã trong (E, ), phÇn tö n ®i sau phÇn tö a vµ ®I sau mäi phÇn tö lo¹i 1 nªn n còng lµ mét phÇn tö lo¹i 1. VËy n a vµ nm. Do ®ã m = n hay sup m =m, m lµ phÇn tö tèi ®¹i cña (E, 0.
Chia sẻ với bạn bè của bạn: |