| « poprzedni punkt | następny punkt » |
Definicja 15.6.1
Niech będzie system algebraiczny A = <A, o1, o2, ...,on, r1, r2,... rm > i niech relacja ~ będzie kongruencją w A. Wtedy system
A/~ = <A/~, o*1, o*2, ...,o*n, r*1, r*2,..., r *m >,
którego uniwersum stanowi zbiór wszystkich klas abstrakcji relacji ~, a operacje i relacje są zdefiniowane przez następujące równości
o*([ a1], ...,[an]) =df [o(a1,..,an)]
dla dowolnej n-argumentowej operacji o* i dowolnych a1,..,an
r*([ a1], ...,[am]) wttw r(a1,...,am)
dla dowolnej m-argumentowej relacji r* i dowolnych a1,..,am
Warto zauważyć, że o* jest dobrze określoną operacją w zbiorze A/~. Rzeczywiście, wynik operacji o*([ a1], ...,[an]) nie zależy od wyboru reprezentantów klas, będących argumentami operacji. Gdybyśmy wzięli elementy a1~ b1,..., an~ bn, to na mocy definicji klas abstrakcji [ai]=[bi]. Mamy więc o*([ a1], ...,[an]) = o*([ b1], ...,[bn]). Z drugiej strony, ponieważ relacja ~ jest kongruencją, więc o(a1,..,an) ~ o(b1,..,bn), a zatem [o(a1,..,an)] = [o(b1,..,bn)].
Przykład 15.6.1
Rozważmy relację ≡ przystawania modulo p (p>0) w zbiorze liczb całkowitych Z, por. 5.5. Zgodnie z tym co udowodniliśmy w wykładzie 5, relacja ta jest kongruencją w algebrze <Z, +, × >. Zbiór klas abstrakcji relacji przystawania modulo p, stanowią klasy reszt modulo p, tzn. [0], [1],...,[p-1]. Określmy dwie operacje ⊕, ⊗ na klasach abstrakcji tak, jak to zrobiliśmy w wykładzie piątym, dla dowolnych x, y ∈ Z,
[x] ⊕ [y] =df [x+y]
[x] ⊗ [y] = df [x × y]
System < Z/ ≡ , ⊕ , ⊗ > jest systemem ilorazowym otrzymanym z algebry liczb całkowitych przez podzielenie jej przez relację kongruencji modulo p.
Lemat 15.6.1
System ilorazowy A/~ jest podobny do A, a odwzorowanie h(a) =df [a] ustala homomorfizm systemów A i A/~ .
Przykład 15.6.2
Rozważmy algebrę podzbiorów zbioru N, < 2N, ∪, ∩ , - > i relację X ∼ Y wttw 1 ∈ X ∩ Y lub 1 ∈ N\( X ∪ Y)
Zbiór klas abstrakcji relacji ~ ma dwie klasy [N] i [ ∅]. Do pierwszej z tych klas należą wszystkie zbiory, do których należy 1, a do drugiej wszystkie zbiory, do których nie należy jedynka. Ponieważ rozważana relacja jest kongruencją, więc można określić operacje na klasach abstrakcji zgodnie z definicją systemu ilorazowego:
[N] ∪* [ ∅ ] = [N] ∪* [N ] = [ ∅ ] ∪* [N ] = [N]
[ ∅ ] ∪* [ ∅ ] = [ ∅ ]
[N] ∩* [ ∅ ] = [ ∅ ] ∩* [N ] =[ ∅ ] ∩* [ ∅ ] = [ ∅ ]
[N] ∩* [N ] =[N]
-* [N] = [ ∅ ] -* [ ∅ ] =[N]
Łatwo zauważyć, że jest to algebra izomorficzna z algebrą Boole'a < {0,1}, ∨, ∧ , ¬ >. Funkcja h : {[N], [ ∅ ]} → {0,1} taka, że h([N]) = 1 i h([ ∅ ])=0 ustala izomorfizm między dwuelementową algebrą Boole'a, a algebrą ilorazową wyznaczoną przez kongruencję ~.
Zadanie 15.6.1 Udowodnić, że system ilorazowy < Z/ ≡ , ⊕ , ⊗ >, określony w przykładzie 15.6.1 jest izomorficzny z systemem Zp = < {0,1,2...,(p-1)}, +p, × p >, gdzie operacje +p, ×p są zdefiniowane następująco x +p y = (x+y) mod p, x ×p y = (x × y) mod p, dla dowolnych x, y.
Rozwiązanie: Definiujemy h(i) = [i] dla i =0, 1, ..., (p-1). Funkcja h jest różnowartościowa, bo dla różnych i, j ∈ Zp reszty z dzielenia przez p są różne, zatem [i] ≠ [j]. Jeśli [x] ∈ Z/ ≡ oraz x przy dzieleniu przez p daje resztę i, to h(i) = [i] =[x], czyli h jest odwzorowaniem "na". Ponadto, h jest homomorfizmem, bo
h(x +p y) = h((x+y) mod p) =[(x+y) mod p] = [x+y] = [x] ⊕ [y] = h(x) ⊕ h(y),
h(x ×p y) = h((x × y) mod p) =[(x × y) mod p] = [x × y] = [x] ⊗ [y] = h(x) ⊗ h(y).
| « poprzedni punkt | następny punkt » |