LEKTION 03-31

Vi fortsätter med ekvivalensrelationer. Först noterar vi några egenskaper av ekvivalevsklasser: Låt R vara en ekvivalenrelation

på A.

• x ∈ [x]_{R} för varje x ∈ A.

• xRy om och endast om x ∈ [y]_{R}.

• om [x]_{R} ≠ [y]_{R} är [x]_{R} ∩ [y]_{R} = ∅.

Antag att [x]_{R} ≠ [y]_{R}. Om [x]_{R} ∩ [y]_{R} ≠ ∅ då kan man hitta v ∈ [x]_{R} ∩ [y]_{R}, dvs att vRx oxh vRy. Eftersom R är simmetrisk är xRv. Så xRv och vRy och då (R är transitiv) gäller xRy, dvs [x]_{R} = [y]_{R}.

Vi har visat att {[x]_{R}}_{x∈A} är en partition av A.

Exempel Betrakta ekvivalensrelationen:

xRy ⟺ x ≡_{n} y

Ekvivalensklassen [x]_{R} är kongruensklasser [x]_{n} och

ℤ = [0]_{n} ∪ [1]_{n} ∪ ... ∪ [n − 1]_{n}

Exempel LA vara en mängd med |A| = n. Vi kan definera en relation på P (A):

B, C ⊆ A, ARB ⟺ |C| = |B|

• Den är riflexiv: |B| = |B| för varje delmängd B ∈ P (A).

• Den är symmetrisk: on |B| = |C| då är |C| = |B|.

• den är transitiv. Det finns n + 1 ekvivalens klasser: A_{i} = {B ∈ P (A)||B| = i}, i = 0, ..., n där A_{0} = {∅}

och A_{n} = {A}.