Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2
DziedzinąrelacjiR⊂A×BnazywamyzbiórD
R⊂A,którydefiniujemy
następująco:
D
R:
{aEA:∃bEB:aRb}.
Jednymznajczęściejstosowanychtypówrelacjiwmatematycejestrelacja
równoważności,zapomocąktórejwprowadzasięwielepojęćwmatematyce.
RelacjęRokreślonąwzbiorzeAnazywamy:
zwrotną,jeżelivaEA:aRa,
symetryczną,jeżeliva,bEA:aRbżbRa,
przechodnią,jeżeliva,b,cEA:(aRb∧bRc)żaRc.
RelacjęRokreślonąwzbiorzeAnazywamyrelacjąrównoważności,jeżeli
jestonarelacjązwrotną,symetrycznąiprzechodnią.Relacjętęoznaczamy
symbolem~.
Przykład5.Sprawdzić,jakiewłasnościmarelacjaR,jeżeliR⊂Z2
ivk,mEZ:kRm⇔k
m≠3.
Sprawdzimy,czyprawdziwejestzdanie:vkEZ:kRk⇔k
k≠3.
Jestoczywiste,że2kniemożebyćliczbąnieparzystą,zatemdanezdanie
jestprawdziwe,czylirelacjajestzwrotna.
Sprawdzamy,czyprawdziwejestzdanie:vk,mEZ:(k
m≠3)ż
ż(m
k≠3).Zdanietojestprawdziwe,bododawanieliczbcałkowi-
tychjestprzemienne,zatemrelacjajestsymetryczna.
Sprawdzamy,czyprawdziwejestzdanie:vk,m,nEZ:(k
n≠3).
Zdanie
to
Mamy
nie
jest
wtedy
prawdziwe,
m≠3∧
zdanie:
∧m
bowystarczy
przyjąć
k
3,
m
1
i
n
0.
n≠3)ż(k
(4≠3∧1≠3)ż(3≠3),którejestoczywiściefałszywe,zatemrelacjata
niejestprzechodnia.
NiechabędzieustalonymelementemzbioruA.Zbiórtychwszystkichele-
mentówzbioruA,któresąrównoważneelementowia(czylipozostająznim
wrelacji)oznaczamy[a]inazywamyklasąrównoważności(alboklasąab-
strakcji)elementuawzględemdanejrelacji(generowanąprzezelementa),
takwięc[a]
{bEA:b~a}.
Twierdzenie1(zasadaabstrakcji)
RelacjarównoważnościwzbiorzeAdzielitenzbiórnaniepusteirozłącz-
neklasyabstrakcji.
Dowód.To,żeklasysąniepustewynikazezwrotnościrelacji,bojeślia~a,
tzn.aE[a].Dowódrozłącznościprzeprowadzimyniewprost.Przypuśćmy,że
dlaa′≠afltakich,żea′,aflEAia′niejestwrelacjizaflistniejetakiea,że
16
