§¹i Sè §¹i C­¬ng

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× S_oS’ 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 ®ã:

1. 
   S gäi lµ quan hÖ ®èi xøng nÕu _E  G, tøc lµ x S x,x  E.
   
2. 
   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.
   
3. 
   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.
   
4. 
   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.
   

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 (x₁,x₂,…x_k) c¸c ®Ønh cña G sao cho (x_i, x_i+1) lµ mét cung cña G, i=1,2,…, k-1. §Ønh x₁ gäi lµ gèc, ®Ønh x_k 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.

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

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 A_i_iI 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 A_i, iI

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ö yS(x’) th× x’ S y, theo tÝnh b¾c cÇu cña S ta cã x S y. Do ®ã yS(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.

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:

1. 
   x  x (tÝnh ph¶n x¹)
   
2. 
   x  y vµ y  z th× x  z ( tÝnh b¾c cÇu)
   
3. 
   x  y vµ y  x th× x= y( tÝnh chÊt ph¶n ®èi xøng)
   

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.

1. 
   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.
   
2. 
   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ö (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.

Quan hÖ tiÒn thø tù trªn mét tËplµ c¸c quan hÖ ph¶n x¹, b¾c cÇu.

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ö (E₁, ), … , (E_n, ) lµ c¸c tËp ®­îc s¾p hoµn toµn. Thø tù tù ®iÓn trªn tËp tÝnh E₁  ...  E_n, ) lµ c¸c thø tù x¸c ®Þnh bëi ®¼ng thøc chÆt sau ®©y:

(x₁, x₂, … , x_n) < ( y­₁, y₂, …,y_n) khi vµ chØ khi tån t¹i i  n sao cho x_k=y_k víi k = 1, 2, …. ,i-1 vµ x_i < y₁.

DÔ dµng thÊy r»ng thø tù tù ®iÓn còng lµ mét thø tù hoµn toµn.

Gi¶ sö E = x, y, z ®­îc s¾p theo quan hÖ x < y < z. TËp E³ = E EE 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 EE lµ

§ã 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”.

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

Mét tËp ®­îc s¾p mµ mäi cÆp phÇn tö x, y ®Òu cã cËn trªn ®óng Supx, y vµ cËn d­íi ®óng infx, y d­îc gäi lµ mét dµn.

• 
  TËp ®­îc s¾p P(X) theo thø tù bao hµm lµ mét dµn:
  

• 
  TËp ®­îc s¾p hoµn toµn lµ mét dµn.
  

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. Nh­ng 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.

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µ a_o. Khi ®ã mäi phÇn tö x  E mµ x < a_o ®Òu cã tÝnh chÊt P; theo gi¶ thiÕt phÇn tö a_o còng cã tÝnh chÊt P. §iÒu nµy m©u thuÉn víi gi¶ thiÕt a_o  A. VËy A = .

C¸c ®iÒu kh¼ng ®Þnh sau lµ t­¬ng ®­¬ng:

1. 
   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.
   
2. 
   §Þnh lý Zermelo: Mäi tËp ®Òu cã thÓ s¾p tèt.
   
3. 
   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
   

Gi¶ sö (A, ) lµ tËp ®­îc s¾p. Víi mçi a  A, tËp P_a =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× P_a  . 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 aA ta cã a = (E- P_a). 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 = P_c vµ c = (E – P_c). 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 aM 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 P_a vµ a = (E – P_a). 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ö x_o lµ phÇn tö ®µu tiªn cña (E, ).

PhÇn tö x_o thuéc lo¹i 1 nÕu a  x_o; x_o 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µ nm. Do ®ã m = n hay sup m =m, m lµ phÇn tö tèi ®¹i cña (E, 0.

Каталог: 2009
2009 -> Công ty cổ phần Xây dựng Điện vneco3
2009 -> Ủy ban nhân dân cộng hòa xã HỘi chủ nghĩa việt nam thành phố HỒ chí minh độc lập Tự do Hạnh phúc
2009 -> BỘ NÔng nghiệp và phát triển nông thôN
2009 -> Nghị ĐỊnh số 163/2004/NĐ-cp ngàY 07/9/2004 quy đỊnh chi tiết thi hành một số ĐIỀu của pháp lệNH
2009 -> BỘ CÔng thưƠng cộng hoà XÃ HỘi chủ nghĩa việt nam
2009 -> Mẫu số: 01 (Ban hành kèm theo Thông tư liên tịch số 31 /2009/ttlt-btc –BLĐtbxh ngày 09 tháng 09 năm 2009) CỘng hòa xã HỘi chủ nghĩa việt nam
2009 -> BỘ y tế Số: 12/2006/QĐ-byt cộng hoà XÃ HỘi chủ nghĩa việt nam
2009 -> CỘng hòa xã HỘi chủ nghĩa việt nam sở TƯ pháP Độc lập Tự do Hạnh phúc
2009 -> CÔng ty cp đIỆn tử BÌnh hòa cộng hòa xã HỘi chủ nghĩa việt nam
2009 -> Ủy ban nhân dân thành phố HỒ chí minh

tải về 2.2 Mb.

Chia sẻ với bạn bè của bạn: