18361

Algebra - wykład 2- konspekt - studia dzienne SAP 2011/2012

U. Relacje równoważnościowe i porządkujące

X * 0: S c. X x X (X = Y) relacja binarna w zbiorze X

Definicja 2.5 (własności relacji)    _ę

1.    S -zwrotna <=» Vx £ X: xSx <=> Vx G X    .............................................]

2. S -symetryczna <=> Vx.y G    [.. YA5.?.........7. .!$*>.................]

<=>Vx,yG.Y: [(x,y) G S =» (y,x)GS],

3.    5 -przechodnia <=> Vx,y, z £ X:    [..K»    „A..    ...................]

«s> Vx,y,z G Z:    [(x,y) G S A (y,z) GS =s (x,z) G 5],

4.    S -antysymetryczna «=> Vx,y 6 X: [.X^ ..A.    ....................]

<=> Vx,y G X: [(x,y) G S A (y,x) £S=> x = y],

5. S -spójna <=> Vx,y G J(: [..36.^. ..Tu!,Y...    .................]

« Vx, y G X: fe * y ...7>..* % A..0.................]

<=> Vx,y G X,x * y: [(x,y) G S v (y,x) G 5]

Definicja 2.6

1)    5 nazywamy relacją równoważnościową <=> S jest    I!?.A. I.

2)    S nazywamy relacją częściowo porządkującą zbiór o 5 jest ł?hł&ę?TN^j

3)    ■ S nazywamy relacją porządkującą zbiór o Sjest ^^"9    A. 1. f

__spóinA_

Przykład 4    ,

1)    S c R x R, xSy <=>x = y relacja ..ł^NP.^AŁrOSCIO^/T........

2)    S c R x R, xSy <=> x < y relacja .    .®~......

X * 0, S c X x X S -relacja równoważnościowa

Definicja 2.7.

Niech ScXxX(X*0) jest relacją równoważnościową.

Klasą ..W!<J^<S?“?^V.’tP5ęA (klasą    ........) elementu x G X ze względu na relację

nazywamy zbiór:    [x]_s = {...    ....................................}•

Przykład 5

a)    S c R x R, xSy <=> x = y [x]_s = {.X...........}

b)    S c R x R, xSy <=> |x| = |y| [x]_s =    .................