22953

Jeżeli: R<z X² i R - relacja równoważności wtedy, gdy

^vm*^: *«[*!,

dowód:

1) V„_X :xRx=>xe\x\_R

2) bierzemy : x,ye X :[x]_R^[.y|_R *0=>3,_fX : ze [ x]_R n[y]_R =>3_kX :zRxAzRy=> =>3_kX :xRzAzRy=>xRy=>xe[y]_RAye[x]_R

symelrytiiKac    pner/iodhtoM'

oe [x]_R => xRa AxRy => aRxAxRy => aRy => ae [y]_R \=> [ x]_R c[y]_R

ona log icznie: [ y\_R c [ x] _R

czy/i;|x],=ly|_s

3.    Klasa równoważności

Jeżeli R - relacja równoważności to zbiór (a]_R :={ b e X : aRb] nazywamy klasą równoważności/abstrakcji elementu a względem relacji R.

4.    Zbiór ilorazowy

Jeżeli R - relacja równoważności to zbiór X |_R:={{a]_R : ae X} nazywamy ilorazowym/ilorazem zbioru X przez relację R.

5.    Podział

Niech X *0

Podziałem zbioru X nazywamy rodzinę D( X | c P( X ) taką że:

1)

2)    V_tMI|:AnB*0=»/l=B

3)    UD(X)=X

(i Zasada abstrakcji

1)    Jeżeli Rc. X² i R - relacja równoważności to X \ _R jest podziałem zbioru X

2)    Jeżeli D(X) jest podziałem zbioru X to relacja R :={( x,y) e X ²: 3^_x :xe AAye aJ jest

relacją równoważności.

Dowód:

X|_r={[x]_r:x€ X}

X |_R - podział _ zbioru <=>[x]_R ^0 a[x]_r n[y]_R ^0 =^[x]_R =[y]_R a UX |_R = U[[x]_R :xe X) = X

D( X) - podział _ zbioru _ X

R:=[(x,y):3_AcaX[:xeA^yeA]

(x,x) € R <=> 3^^,: x€ A <=> xe UD( X) = X R-zwrotna 2) (x,y)e R <=>3_MD{Xj :xe AAye    : ye A ax€ A<=>(y,x)e R |=> R - symetryczna

(x,y|efiA(y,z|eR <=>3^^, :xeAAye A/\3_teI)(J :ye Bazę B=*

^^_ABeDm :xe Aa ze BA(ye AAye B) <=> 3_AfleD(Jn : xe Aa ze BAyeAnB^ =^3_ABfD|jr|^:xe/\Aze B aA= B=> 3^*,: xe A a ze B <=» (x, z) e R\=* R - przechodnia