w3relacjezbiorynieskonczone_E.pdf

Wyk“ad3.Relacjeizbioryniesko«czone

3.1.Relacje

Przyjmijmy,»e Z jestzbioremjaki–obiekt ó wobdarzonychpewnymicechami.Jestrzecz¡

naturaln¡“¡czenieobiekt ó wmaj¡cychpewnewsp ó lnecechywparywceluichsklasy kowa-

nialubuporz¡dkowania.Zmatematycznegopunktuwidzeniaka»detakiepo“¡czenieobiekt ó w

wparyjestokre–leniempewnejrelacjiwzborze Z. Zmatematycznegopunktuwidzeniaciekawe

jesttak»ebadaniew“asno–cisamychrelacji.Otoog ó lnade nicjarelacji.

De nicja1.Niech A oraz B oznaczaj¡pewnezbiory.Dowolnypodzbi ó r R zbioru A × B na-

zywamyrelacj¡.Je»eli A = B tom ó wimy,»e R jestrelacj¡w A .

Abyzapisa¢,»e a jestwrelacjioznaczonejprzez R z b czyli( a,b ) 2 R A × B, u»ywasiƒ

skr ó conegozapisu aRb .

Przyk“ad3.1.Oznaczmyprzez A zbi ó ros ó bwaudytorium.Okre–limydwier ó »nerelacje

wtymzbiorze.

1.Osoba a jestwrelacji R 1 zosob¡ b w.t.w.gdyurodzi“ysiƒwtymsamymmiesi¡cu.

2.Osoba a jestwrelacji R 2 z b w.t.w.gdyurodzi“asiƒconajmniejojedendzie«wcze–niejni»

b lubtegosamegodnia.

Jakiecechymaj¡obieterelacjeajakiecechyjeodr ó »niaj¡?Dwiecechys¡wsp ó lne.Osoba

a woczywistyspos ó bjestwrelacji R 1 atak»e R 2 zsam¡sob¡.Taw“asno–¢tozwrotno–¢

relacji.Je–liosoba a urodzi“asiƒwtymsamymmiesi¡cucoosoba b aosoba b wtymsamym

miesi¡cucoosoba c torzeczjasnaosoba a urodzi“asiƒwtymsamymmiesi¡cucoosoba c .Tƒ

w“asno–¢nazywasiƒprzechodnio–ci¡relacji.Przechodniajestzatemrelacja R 1 aletak»e

relacja R 2 ,co“atwosprawdzi¢.Zauwa»my,»eje–lijaka–osoba a urodzi“asiƒwtymsamym

miesi¡cucoosoba b totak»ezamiennieosoba b urodzi“asiƒwtymsamymmiesi¡cuco a .Ta

w“asno–¢tosymetria.Zwr ó ¢myuwagƒ,»erelacja R 2 symetrycznaniejestgdy»naprzyk“ad,

je–liosoba a urodzi“asiƒodwadniwcze–niejodosoby b ,tozamieni¢miejscami a i b wtym

zdaniuniemo»na.Zobaczymydalej,»erelacja R 1 dzielizbi ó r A naroz“¡czneklasysk“adaj¡ce

siƒzos ó burodzonychwposzczeg ó lnychmiesi¡cachadrugaporz¡dkujetenzbi ó r.

De nicja2.Relacj¡odwrotn¡dorelacji R nazywamyrelacjƒoznaczon¡jako R − 1 B × A

R − 1 = { ( b,a ) 2 B × A :( a,b ) 2 R }

Dlaprzyk“aduniech A =[0 , 2]a B =[0 , 4].Okre–lamyrelacjƒ,kt ó r¡oznaczymyprzez W

A × B ;dla x 2 A i y 2 B , xWy w.t.w.gdy y 2 x .Przyjmiemy,»eprzez x oznaczamydowolny

punktzezbiorubƒd¡cegonapierwszymmiejscuwiloczyniekartezja«skimaprzez y punkt

zdrugiegozbioru.Dziƒkitemuobierelacje W i W − 1 mo»naprzedstawi¢najednymuk“adzie

wsp ó “rzƒdnych.Relacjaodwrotna W − 1 B × A okre–lonajest,zgodniezde nicj¡,przez

warunek;dla x 2 B i y 2 A, ( x,y ) 2 W − 1 w.t.w.gdy( y,x ) 2 W czyli x 2 y awiƒcpo

przekszta“ceniu, y ¬ x 2 .

y 2 x

W − 1

1 2 3 4 5

Rys.2.7.Relacjaodwrotna.

Otoniekt ó retypyrelacjiokre–lonychwzbiorze A .

1. R jestzwrotnaw.t.wgdy

8 x 2 AxRx.

2. R jestsymetrycznaw.t.w.gdy

8 x,y 2 A ( xRy ) ) ( yRx ) .

3. R jestantysymetrycznaw.t.wgdy

8 x,y 2 A ( xRy ) ^ ( yRx ) ) x = y

W“asno–¢tƒmanaprzyk“adrelacjainkluzjiwdowolnejrodziniepodzbior ó wjakiego–zbioru.

4. R jestprzechodniaw.t.w.gdy

8 x,y 2 A ( xRy ) ^ ( yRz ) ) ( xRz ) .

5. R jestrelacj¡r ó wnowa»no–ciw.t.w.gdyjestzwrotna,przechodniaisymetryczna

6. R jestczƒ–ciowoporz¡dkuj¡caw.t.wgdyjestzwrotna,przechodniaiantysymetryczna.

7. R jestliniowoporz¡dkuj¡cazbi ó r A w.t.wgdyjestczƒ–ciowoporz¡dkuj¡caitaka,»e

8 x,y 2 AxRy _ yRx.

Przyk“ademrelacjiczƒ–ciowoporz¡dkuj¡cejjestzbi ó rwszystkichpodzbior ó w P ( Z )zbioru Z

wrazzrelacj¡inkluzjizbior ó w .Bysiƒotymprzekona¢zauwa»my,»eka»dyzbi ó rzawiera

siƒsamwsobie.Niech A,B,C bƒd¡dowolnymipodzbioramizbioru Z .Je–li A B i B C

to A C .Dodatkowoje–li A B i B A to A = B . Š atwoznale„¢przyk“adtakichdw ó ch

podzbior ó w A i B zbioru Z ,»eniejestprawd¡zar ó wno,»e A B jaki»e B A .Wystarczy

wzi¡¢zbi ó r Z = { a,b } i A = { a } a B = { b } .Jesttozateminnyporz¡dekodtego,kt ó ryzadaje

relacja ¬ wzbiorzeliczbrzeczywistychgdy»tudlaka»dychdw ó chliczb x i y albo x ¬ y albo

y ¬ x .Porz¡dekwzbiorzeliczbrzeczywistychjestporz¡dkiemliniowym.Zbi ó rosko«czenie

wieluelementachmo»nazawszeponumerowa¢liczbaminaturalnymiiuporz¡dkowa¢liniowo

wykorzystuj¡crelacjƒporz¡dkuwzbiorzeliczbnaturalnych.Takiporz¡dekmo»ejednakby¢

zjakich–powod ó wnieciekawy.Wyobra„mysobiezwierzƒtawogrodziezoologicznymkt ó rym

przypisanoliczbynaturalnezgodnieztymwjakispos ó brozmieszczones¡wklatkachodlewej

doprawej.Zbi ó rzwierz¡twtenspos ó bjestuporz¡dkowanyliniowo,tyletylko,»ejesttopo-

rz¡dekarbitralnyitrywialny.Ciekawyjestporz¡dekokre–laj¡cypokrewie«stwo logenetyczne,

kt ó ryporz¡dkiemliniowymniejest.Takierelacjemo»naprzedstawi¢zapomoc¡drzew loge-

netycznychokt ó rychwiƒcejpowiemynawyk“adzie6.Drzewa logenetycznewsystematyce

przedstawiaj¡gra cznierelacjƒ ApochodziodB .Jesttoprzyk“adrelacjiczƒ–ciowegopo-

rz¡dkuzzastrze»eniem,»etakarelacjaniejestzwrotnaapozatymmawszystkiecechyrelacji

czƒ–ciowegoporz¡dku.Oczywi–cieniejesttorelacjaporz¡dkuj¡caliniowo.Homoerectusnie

pochodziodgorylacho¢obagatunkimaj¡odleg“egowsp ó lnegoprzodka.

Zajmijmysiƒterazrelacj¡r ó wnowa»no–ci,kt ó ramapodstawoweznaczenieprzybudowaniu

wszelkiegorodzajuklasy kacji.

De nicja3.Niech R bƒdzierelacj¡r ó wnowa»no–ciwpewnymzbiorze A 6 = ; .Dla x 2 A

oznaczamyprzez] x [zbi ó rtychelement ó w y 2 A t.»e xRy

y 2 ] x [ , xRy.

Zbi ó r] x [nazywasiƒklas¡abstrakcjirelacji R (ew.klas¡r ó wnowa»no–ci)

Wa»new“asno–citegopojƒciaujmujenastƒpuj¡cetwierdzenie.

Twierdzenie4.Je–li A 6 = ; i R jestrelacj¡r ó wnowa»no–ciw A todladowolnych x 0 ,x 1 ,x 2 2

a) x 0 2 ] x 0 [ ,

b)] x 1 [=] x 2 [ , x 1 Rx 2 ,

c)je–li] x 1 [ 6 =] x 2 [to] x 1 [ \ ] x 2 [= ; .

WPrzyk“adzie3.1,podpunkt1wszystkieosoby,kt ó reurodzi“ysiƒwtymsamymmiesi¡cu

nale»¡dotejsamejklasyabstrakcji.Wszystkichklasabstrakcjijestzatem12.

Dowolnarelacjar ó wnowa»no–ciwdanymzbiorze X 6 = ; ustalapodzia“tegozbioruna

roz“¡czneiniepustepodzbiory,mianowicienaklasyabstrakcjiwtakispos ó b,»edwaelementy

x,y zbioru X nale»¡dotejsamejklasyabstrakcjiw.t.w.gdy xRy .Ka»dypodzia“jakiego–

zbiorunaroz“¡cznepodzbioryodpowiadapewnejrelacjir ó wnowa»no–ciiodwrotnie.Jestto

podstawadoprzeprowadzaniawszelkiegotypuklasy kacjiipodzia“ ó w.

Zadanie.Zbada¢w“asno–cinastƒpuj¡cychrelacjiwprowadzonychwzbiorzeos ó bznajdu-

j¡cychsiƒwaudytorium.

1.Osoba A jestwrelacji R 1 zosob¡ B w.t.wgdyurodzi“ysiƒwtymsamympa«stwie.

2.Osoba A jestwrelacji R 2 zosob¡ B w.t.wgdyposiadaj¡wsp ó lnegoprzodkadotrzech

pokole«wstecz.

3.2.Funkcje

Funkcja,pojƒciebezkt ó regotrudnosiƒoby¢wmatematyce,toszczeg ó lnegotypurelacja.

De nicja5.Funkcj¡okre–lon¡nazbiorze X owarto–ciachwzbiorze Y nazywamytak¡relacjƒ

R okre–lon¡wprodukciezbior ó w X × Y o,»edladowolnego x 2 X istniejedok“adniejeden

y 2 Y taki,»e xRy .

Wida¢zatem,»efunkcjawtymujƒciujestpewnympodzbioremproduktudw ó chzbior ó w.To

jeszczerazpokazuje,»epojƒciezbiorujestpojƒciempierwotnym.Innymis“owypojƒciefunkcji

uto»samiasiƒtuzeznanymzeszko“ypojƒciemwykresufunkcji.Wed“uginnejdo–¢wygod-

nejterminologiifunkcjƒokre–lasiƒjakoprzyporz¡dkowaniedowolnemuelementowizbioru X

zwanegodziedzin¡dok“adniejednegoelementuzbioru Y .Zbi ó rwszystkichwtenspos ó bprzy-

porz¡dkowanych y − k ó wnazywamyprzeciwdziedzin¡danejfunkcji.Mo»natak»epowiedzie¢,»e

jestonobrazemzbioru X .Przytakimujƒciupojƒciafunkcjipojƒciewykresufunkcjitrzeba

wprowadzi¢osobno.Zauwa»my,»etermin przyporz¡dkowanie wistocieoznaczaokre–lenie

relacji.Dlarelacji,kt ó res¡funkcjamistosujesiƒznan¡zeszko“ykonwencjƒnotacyjn¡.Je–li

relacja f jestfunkcj¡tozamiast xfy piszemy y = f ( x )wtedytrzebadoda¢okre–leniedziedziny

pisz¡c x 2 X .Mo»nar ó wnie»napisa¢

7! Y lub f : X 7! Y

lubnawet

X 3 x 7−! f ( x ) 2 Y

Jesttusporodowolno–ciprzywyborzesymboli,najwa»niejszebypamiƒta¢osprecyzowaniu

dziedzinyfunkcji.Pozostawieniedziedzinydomy–lnejmo»eprowadzi¢donieporozumie«.

Otoprzyk“adrelacjiokre–lonejw X × Y gdzie X = { a,b,c,d } a Y = { e,f,g } ,kt ó ranie

jestfunkcj¡.

a b c d

Rys.3.1Relacja,kt ó raniejestfunkcj¡.

De nicja6.Niech f : X ! Y , g : Y ! Z .Dlaka»degoelementu x 2 X istniejedok“adnie

jedenelement z 2 Z taki,»ez=g(f(x)).Wyznaczonajestzatemnowafunkcja h

h ( x )= g ( f ( x )) 8 x 2 X,

kt ó r¡nazywamysuperpozycj¡(z“o»eniem)funkcji f i g ioznaczamyj¡ h = g f czyli h ( x )=

g f ( x )= g ( f ( x )).

De nicja7.Funkcjƒ f : A ! B nazywamyiniekcj¡(funkcj¡r ó »nowarto–ciow¡)je»eli

8 x 1 ,x 2 2 A ( f ( x 1 )= f ( x 2 )) ) ( x 1 = x 2 )

przeciwdziedzina

Rys.3.2.Funkcjar ó »nowarto–ciowa(iniekcja).

De nicja8.Funkcjƒ f : A ! B nazywamysurjekcj¡(funkcj¡ na )je»eli

8 b 2 B 9 a 2 A : f ( a )= b.

X f

Rys.3.3.Funkcja na (surjekcja).

Naprzyk“adprzyporz¡dkowanieka»dejosobiewPolscenumerumiesi¡cawkt ó rymsiƒ

urodzi“aniejestiniekcj¡,alejestsurjekcj¡.

De nicja9.Funkcja,kt ó rajestiniekcj¡isurjekcj¡,awiƒcprzekszta“caswoj¡dziedzinƒwza-

jemniejednoznacznienaprzeciwdziedzinƒ,nazywasiƒbijekcj¡.

Rys.3.4.Bijekcja.

3.3.R ó wnoliczno–¢zbior ó w

Jednymzpodstawowychpyta«,kt ó remo»nazada¢maj¡cdoczynieniazdwomazbiorami

jest-czyjedenznichmawiƒcejelement ó wni»drugiczymo»es¡oner ó wnoliczne.Zliczaj¡c

elementyjakiego–zbiorukonstruujemynie–wiadomiebijekcjƒpomiƒdzytymzbioremapewnym

podzbioremzbioruIN.Taobserwacjadajepodstawƒdobardzowa»nejizgodnejzintuicj¡

de nicji

De nicja10.M ó wimy,»edwazbiorymaj¡tƒsam¡moc(lubs¡r ó wnoliczne)je–liistnieje

bijekcjazjednegozbiorunadrugi.

Je–lijaki–zbi ó rma n element ó wtoznaczy,»ejegoelementymo»emyponumerowa¢kolej-

nymiliczbaminaturalnymiod1do n .Innymis“owyistniejebijekcjaztegozbiorunazbi ó r

{ 1 , 2 ,...,n } .

Przyk“ad3.2.Wpewnympa«stwiedoparlamentudostalisiƒprzedstawiciele10partiipo-

litycznych.Ilemaksymalniekoalicjiparlamentarnychmo»eby¢utworzonychje–liprzyjmie-

my,»ekoalicjƒmog¡tworzy¢conajmniejdwiepartie.Ka»dejpartiiprzypisujemykolejno

liczbyod1do10.Ka»dypodzbi ó rzbioru10-elementowegooliczbieelement ó wwiƒkszejod

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: