intro7.pdf

(89 KB) Pobierz
381442680 UNPDF
WSTE¸PDOMATEMATYKI Lista7
1. Zbada¢,którezponi»szychrelacjis¡relacjamiporz¡dku(cz¦±ciowego,liniowego,dobrego).
Wyznaczy¢-oileistniej¡-elementymaksymalne,minimalne,najwi¦kszeinajmniejsze.
( a ) P ( X ) zrelacj¡inkluzji ;
( b ) X 6 = ; ,x,y 2 X,x y $ x = y ;
( c ) x i ,y i 2 R , ( x 1 ,y 1 ) ( x 2 ,y 2 ) $ ( x 1 <x 2 ) _ ( x 1 = x 2 ^ y 1 ¬ y 2 );
( d )( X, ¬ X ) , ( Y, ¬ Y ) dowolnezbiorydobrzeuporz¡dkowane,,x 1 ,x 2 2 X,y 1 ,y 2 2 Y,
( x 1 ,y 1 ) ( x 2 ,y 2 ) $ ( x 1 ¬ X x 2 ^ x 1 6 = x 2 ) _ ( x 1 = x 2 ^ y 1 ¬ Y y 2 );
( e ) k,l 2 N \{ 0 , 1 , } ,x y $ x | y ;
2. Rozwa»myrelacj¦ zdefiniowan¡wpodpunkcie( c )zadania1.Wskaza¢(oileistniej¡)elementy
maksymalne,minimalne,najwi¦kszyinajmniejszywnast¦puj¡cychzbiorach: { ( x,y ): x 2 + y 2 ¬ 1 } ,
{ ( x,y ): x 2 + y 2 < 4 } , { ( x,y ): x 2 [ 1 , 1] ,y 2 [0 , 1 ) } .
3. Wzbiorze P (N)wprowadzili±myrelacj¦równowa»no±ci= ? (lista6,zad.5(a)).Niech[ A ] , [ B ] 2
P (N) / = ? b¦d¡klasamiabstrakcjiwyznaczonymiprzezzbiory A,B N . Definiujemyrelacj¦:
[ A ] ? [ B ] $ A \ Bjestzbioremsko ´ nczonym.
Pokaza¢,»ejesttopoprawniezdefiniowanarelacjacz¦±ciowegoporz¡dkuna P (N) / = ? . Wyznaczy¢jej
elementynajmniejszyinajwi¦kszy.
4. Zakładamy,»e F jestultrafiltremna P ( X ) ,Y =R . Wzbiorze X Rwprowadzili±myrelacj¦= F
(lista7,zad.5(d)).Pokaza¢,»erelacjazdefiniowanawzorem:
[ f ] F [ g ] ${ x 2 X : f ( x ) ¬ g ( x ) }2 F
jestcz¦±ciowymporz¡dkiemw X
R . Czyjesttoporz¡dekliniowy?
5. Drzewobinarne: Niech B oznaczazbiórwszystkichsko«czonychci¡gówzero-jedynkowych(tj.
funkcjipostaci { 0 , 1 ,...,n }!{ 0 , 1 } ).Zakładamy,»e p,q 2B . Pokaza¢,»e B jestcz¦±ciowouporz¡dkowany
relacj¡inkluzji( ). Gał¦zi¡ drzewa B nazywamymaksymalnyliniowouporz¡dkowanypodzbiór B .
Pokaza¢,»eka»dagał¡¹jestdobrzeuporz¡dkowana,oraz»ewyznaczawsposóbjednoznacznypodzbiór
zbioruN . Inaodwrót,ka»dypodzbiór A Nwyznaczadokładniejedn¡gał¡¹drzewabinarnego.
ZADANIEDOMOWE Lista7
1. Zbada¢,którezponi»szychrelacjis¡relacjamiporz¡dku(cz¦±ciowego,liniowego,dobrego).
Wyznaczy¢-oileistniej¡-elementymaksymalne,minimalne,najwi¦kszeinajmniejsze.
( a ) k,l 2 N ,k l $ l ¬ k ;
( b ) x i ,y i 2 [0 , 1)( x 1 ,y 1 ) ( x 2 ,y 2 ) $ ( x 1 <x 2 ) _ ( x 1 = x 2 ^ y 1 ¬ y 2 );
( c ) [0 , 1] , [0 , 1) , (0 , 1] , (0 , 1 ) zporz¡dkiemdziedziczonymz R;
( d ) ( X, ¬ X ) ,dowolnyzbiórdobrzeuporz¡dkowany,,x 1 ,x 2 ,y 1 ,y 2 2 X,
( x 1 ,y 1 ) ( x 2 ,y 2 ) $ max { x 1 ,y 1 } < max { x 2 ,y 2 }_ (max { x 1 ,y 1 } =max { x 2 ,y 2 }^ x 1 <x 2 ) _
_ (max { x 1 ,y 1 } =max { x 2 ,y 2 } x 1 = x 2 ^ y 1 ¬ y 2 );
2. Rozwa»myrelacj¦ zdefiniowan¡wpodpunkcie( b )zadania1.Wskaza¢(oileistniej¡)elementy
maksymalne,minimalne,najwi¦kszyinajmniejszywnast¦puj¡cychzbiorach: { ( x,y ): x 2 + y 2 < 1 } ,
{ ( x,y ): x 2 + y 2 < 1 4 } , { ( x,y ): x 2 [0 , 1 2 ] ,y 2 [ 1 2 , 3 4 ) } .
3. Wzbiorze N Nwprowadzili±myrelacj¦równowa»no±ci= ? (lista7,zad.5(b)).Niech f,g b¦d¡
dowolnymici¡gamiliczbnaturalnych,azbiory[ f ] , [ g ]wyznaczonymiprzeznieklasamiabstrakcji.
Definiujemyrelacj¦:
[ f ] ? [ g ] ${ n : f ( n ) >g ( n ) } jestzbioremsko ´ nczonym.
381442680.001.png 381442680.002.png 381442680.003.png
Pokaza¢,»ejesttopoprawniezdefiniowanarelacjacz¦±ciowegoporz¡dkuna N N / = ? . Wyznaczy¢jej
elementnajmniejszy.Pokaza¢,»eka»dyprzeliczalnypodzbiórjestograniczony.
4. Mówimy,»erelacja jestostrymporz¡dkiemna X, je»elijestprzechodniaiantyzwrotna(tzn.
8 x 2 X ¬ ( x x )).Udowodni¢,»e:
(a)Je»eli jestostrymporz¡dkiemna X, torelacja zadanawzorem: x y $ x y _ x = y
jestporz¡dkiemcz¦±ciowymna X .
(b)Je»eli jestporz¡dkiemcz¦±ciowymna X, torelacja zadanawzorem x y $ x y ^ x 6 = y
jestostrymporz¡dkiem.
5. WzbiorzeZokre±lamyrelacj¦:
k l $ (( k · l< 0 ^ k>l ) _ ( k · l ­ 0 ^| k |¬| l | ) .
(a)Sprawdzi¢,czytarelacjajestdobrymporz¡dkiemwzbiorzeZ .
(b)Sprawdzi¢,czyzbiory(N , ¬ )oraz(Z , )s¡porz¡dkowoizomorficzne(tzn.czyistniejemi¦dzynimi
zachowuj¡caporz¡dekbijekcja).
Zgłoś jeśli naruszono regulamin