O pewnych szczególnych kongruencjach określonych w zbiorze liczb całkowitych była już mowa w tym wykładzie (punkt 5.5). Teraz przedstawimy pojęcie kongruencji w dowolnym systemie algebraicznym, abstrahując od typu elementów systemu i niezależnie od rodzaju jego operacji i relacji. Niech A = <A, o₁, o₂, ...,o_n, r₁, r₂,... r_m > będzie dowolnym danym system algebraicznym.

Warunki podane w definicji można przeczytać niezbyt dokładnie następująco: jeżeli argumenty operacji są równoważne, to wyniki operacji są też równoważne, oraz, jeśli jakaś relacja zachodzi dla danych argumentów, to również zachodzi dla argumentów równoważnych.

Przykład 15.5.1

(1) Relacja przystawania modulo p, por. punkt 4.5, określona w systemie algebraicznym <N, +> jako n ≡ n' wttw n mod p = n' mod p jest kongruencją, bo gdy a ≡ a' oraz b ≡ b', to mamy

a mod p = a' mod p, czyli dla pewnych liczb k i k', a = k*p+c i a' = k' * p+c oraz

b mod p = b' mod p, czyli dla pewnych m i m', b = m * p+d i b'= m' * p+d.

Stąd a+b = (k+m)p + (c+d) oraz a'+b' = (k'+m')p + (c+d). Czyli (a+b)mod p = (a'+b') mod p.

(2) Rozważmy zbiór wszystkich formuł rachunku zdań F. Możemy go traktować jako algebrę z operacjami ⊕ , ⊗ , © , określonymi dla dowolnych formuł α i β, następująco

tzn. np. wynik działania operacji ⊕ na dwóch formułach α i βjest formułą postaci (α∨β). Relacja &sim, określona w zbiorze formuł warunkiem:

&alpha ∼β wtedy i tylko wtedy |= α ≡ β,

mówi, że dwie formuły są w relacji wtedy i tylko wtedy, gdy wartości tych formuł są takie same dla wszystkich wartościowań zmiennych zdaniowych w nich występujących.

Taka relacja jest równoważnością i jest kongruencją ze względu na operacje ⊕ , ⊗ , © .

Dla dowodu weźmy formuły αβα', β' i niech α∼α', β∼β'. Jeśli α ⊕ β ma, przy pewnych wartościach zmiennych, wartość 1, tzn. w( α ∨ β) =1, wtedy albo w(α) =1 albo w(β) =1. Na mocy założenia |=(α ≡ α'), |=(β ≡ β'), zatem albo w(α') =1 albo w( β') =1, czyli musi być w( α' ∨ β') =1. Analogicznie, jeśli α ⊕ β ma przy pewnych wartościach zmiennych wartość 0, tzn. w( α ∨ β) = 0, zatem w( α) = 0 i w( β) = 0. Na mocy założenia mamy |= ( α≡ α'), |= ( β ≡ β'), a zatem, dla tych samych wartości zmiennych, mamy w( α') = 0 i w( β') =0, czyli w( α' ∨ β) =0. Ostatecznie α⊕ β∼α' ⊕ β'.

W podobny sposób można pokazać, że jeśli α∼α', β∼β', to

Nie każda relacja równoważności jest kongruencją ze względu na dany zestaw operacji i relacji. Przykład takiej relacji podajemy poniżej.

Przykład 15.5.2

Rozważmy zbiór skończonych ciągów zerojedynkowych o ustalonej długości k, B_k = {(b₀, b₁,..., b_k) : b_i = 0 lub b_i = 1} oraz dwie operacje dwuargumentowe ⊕ , ⊗ i jedną operacją jednoargumentową © :

dla dowolnych elementów b₀, b₁,..., b_k, a₀, a₁,..., a_k ∈ {0,1}. Operacje po prawej stronie równości w powyższych definicjach są operacjami alternatywy, koniunkcji i negacji w dwuelementowej algebrze Boole'a. Zbiór B_k z operacjami ⊕ , ⊗ , © tworzy system algebraiczny.

Niech f będzie funkcją, której wartością dla danego ciągu b ∈ B_k jest liczba jedynek występujących w ciągu b. Relacja taka, że dla dowolnych b, b' ∈ B_k,

jest relacją równoważności (por. lemat 4.1). Klasami abstrakcji tej relacji są zbiory: X0 - zbiór którego jedynym elementem jest ciąg złożony z samych zer, X1 - zbiór k-elementowy złożony z wszystkich ciągów, w których tylko raz występuje jedynka, X2 - zbiór, złożony z wszystkich ciągów, w których jedynka występuje dwukrotnie, itd. Jest dokładnie k+1 klas abstrakcji. Relacja ta nie jest jednak kongruencją w rozważanej algebrze. Kontrprzykładem mogą być ciągi a=(1,1,1,0,...0), a' = (0,1,1,1,0...0), b = (0,1,0,...,0), b' = (1,0,...,0). Chociaż a ∼ a' i b ∼ b', to a ⊕ b = (1,1,1,0...,0), a' ⊕ b' = (1,1,1,1,0,...,0) , a więc f(1,1,1,1,0...,0) ≠ f(1,1,1,0...,0). Podobne kontrprzykłady można znaleźć dla pozostałych działań.

W wykładzie 4 mówiliśmy o tym, że mając funkcję określoną na jakimś zbiorze A możemy zdefiniować relację równoważności grupując po prostu te elementy zbioru A, dla których funkcja przyjmuje te same wartości (por. wykład 5). Klasami abstrakcji takiej relacji są przeciwobrazy wszystkich wartości funkcji, tzn. zbiory f ^-1({b}) dla wszystkich b ∈ f(A). Okazuje się, że mamy podobny sposób na tworzenie relacji kongruencji. Trzeba jednak zwiększyć wymagania dotyczące funkcji.

Dowód.

Relacja ~ jest relacją równoważności na mocy lematu 5.1.1. Weźmy dowolną operację n-argumentową o w A oraz elementy a₁ ~ a'_{1 ,} a₂ ~ a'_{2 , ...,} a_n ~ a'_n. Ponieważ h jest homomorfizmem, to dla odpowiadającej operacji o' w B mamy

Ale na mocy założenia h(a_i) = h(a'_i) dla i=1, ...,n. Stąd

Zatem o(a₁, a₂, ...,a_n) ~ o(a'₁, a'₂, ...,a'_n). ♦

Pytanie 15.5.1: Czy relacja określona w przykładzie 15.5.1(1) jest kongruencją w algebrze <N, *>?