Niech ⊕ i będą dwoma działaniami w zbiorze A. Wtedy mówimy, że
działanie jest rozdzielne względem ⊕ jeśli:
∀a, b, c ∈ A a (b ⊕ c) = (a b) ⊕ (a c), (a ⊕ b) c = (a c) ⊕ (b c) Jeśli X jest dowolnym zbiorem to przez 2X oznaczamy rodzinę wszystkich podzbiorów zbioru X. Mamy więc A ∈ 2X ⇐⇒ A ⊆ X.
Przykład Niech X = {1, 2, 3}. Wtedy mamy
2X = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Twierdzenie 1 Jeśli X jest zbiorem skończonym i |X| = n to |2X| = 2n.
Dowód Zbiór X jest skończony i ma n elementów, więc X = {x1, x2, . . . , xn}.
Każdy podzbiór wiąże się z wyborem pewnych jego elementów, a więc pewnych numerów. Możemy więc określić odwzorowanie:
ξ : 2X → {0, 1}n
podzbiorów zbioru X w zbiór wszystkich n-elementowych ciągów zero-jedyn-kowych. Jeśli A jest podzbiorem zbioru X to przyporządkowujemy mu ciąg (a1, a2, . . . , an) taki, że
(
1
jeśli
x
a
i ∈ A
i =
0
jeśli
xi 6∈ A.
Na przykład:
∅
→ (0, 0, . . . , 0)
X
→ (1, 1, . . . , 1)
{x1} → (1, 0, . . . , 0)
Nietrudno zauważyć, że każdemu podzbiorowi odpowiada dokładnie jeden ciąg, różnym podzbiorom odpowiadają różne ciągi i każdy ciąg odpowiada pewnemu podzbiorowi. Zatem elementów zbioru 2X jest dokładnie tyle samo co elementów zbioru {0, 1}n, a tych ostatnich jest 2n.
Przykład Zilustrujmy działanie funkcji ξ, zdefiniowanej w dowodzie twier-dzenia na przykładzie zbioru X = {1, 2, 3}:
∅
→ (0, 0, 0)
{1}
→ (1, 0, 0)
{2}
→ (0, 1, 0)
{3}
→ (0, 0, 1)
ξ : {1, 2}
→ (1, 1, 0)
{1, 3}
→ (1, 0, 1)
{2, 3}
→ (0, 1, 1)
{1, 2, 3} → (1, 1, 1)
1
Zadanie Jakie własności mają działania ∩, ∪ w zbiorze 2X?
III. Struktury algebraiczne
Strukturą algebraiczną nazywamy zbiór wraz z pewnymi działaniami w
tym zbiorze. Strukturę algebraiczną zapisujemy wymieniając zbiór oraz dzia-
łania np. (N, +, ·) jest strukturą algebraiczną złożoną z N i dwóch działań dodawania i mnożenia. Działań w strukturze algebraicznej może być skoń-
czenie lub nieskończenie wiele.
W dalszym ciągu działanie ◦ będzie działaniem binarnym.
Dowolną strukturę (G, ◦) nazywamy grupoidem.
Grupoid (G, ◦) nazywamy półgrupą jeśli działanie ◦ jest łączne.
Półgrupę (G, ◦) nazywamy grupą jeśli ◦ ma element neutralny i każdy
element jest odwracalny.
Inaczej mówiąc (G, ◦) jest grupą jeśli:
(1) ∀a, b, c ∈ G a ◦ (b ◦ c) = (a ◦ b) ◦ c,
(2) Istnieje e ∈ G, że ∀a ∈ A e ◦ a = a ◦ e = a,
(3) ∀a ∈ G∃a0 aa0 = a0a = e.
jeśli dodatkowo
(4) ∀a, b ∈ G a ◦ b = b ◦ a
to grupę nazywamy przemienną lub abelową.
Przykład
(N, +) jest półgrupą i nie jest grupą,
(Z, +) jest grupą abelową,
(R \ {0}, ·) jest grupą abelową,
(Sn, ◦) jest grupą i jeśli n > 2 to jest to grupa nieabelowa.
Zbiór A = {e, a, b, c} z działaniem ◦ określonym w tabelce:
◦ e a b c
e
e
a
b
c
a
a
e
c
b
b
b
c
e
a
c
c
b
a
e
jest grupą abelową. Każdy element jest odwrotny sam do siebie.
Twierdzenie 2 Każdy element grupy posiada dokładnie jeden element odwrotny.
Dowód Z definicji grupy wynika, że każdy element posiada element odwrotny. Przypuśćmy, że pewien element a posiada dwa elementy odwrotne a0 i a00.
Wtedy, jeśli e oznacza element neutralny, mamy:
a ◦ a0 = a0 ◦ a = e
a ◦ a00 = a00 ◦ a = e
2
Korzystając z powyższych równości i z łączności działania, otrzymujemy: (1)
a0 = a0 ◦ e = a0 ◦ (a ◦ a00) =(a0 ◦ a) ◦ a00 = e ◦ a00 = a00.
Co oznacza, że element odwrotny jest dokładnie jeden.
Element odwrotny do a oznaczamy przez a−1.
Twierdzenie 3 Jeśli (G, ◦) jest grupą to:
(i) ∀a ∈ G (a−1)−1 = a,
(ii) ∀a, b ∈ G (a ◦ b)−1 = b−1 ◦ a−1.
Dowód
(i) Ponieważ a ◦ a−1 = a−1 ◦ a = e to element a jest odwrotny do a−1 i ponieważ element odwrotny jest wyznaczony jednoznacznie to (a−1)−1 = a.
(ii) Wystarczy sprawdzić, że element b−1 ◦ a−1 jest odwrotny do a ◦ b.
Zadanie Wyznaczyć elementy odwrotne do elementów grupy (S3, ◦).
Twierdzenie 4 Jeśli (G, ◦) jest grupą to:
(i) a ◦ x = b ◦ x ⇒ a = b,
(ii) x ◦ a = x ◦ b ⇒ a = b.
Dowód
(i) Jeśli a ◦ x = b ◦ x to mnożąc to równanie obustronnie z prawej strony przez x−1 otrzymujemy:
(a ◦ x) ◦ x−1 = (b ◦ x) ◦ x−1
a ◦ (x ◦ x−1) = b ◦ (x ◦ x−1)
a ◦ e = b ◦ e
a = b
(ii) Analogicznie jak poprzedni punkt.
Twierdzenie 5 Jeśli (G, ◦) jest grupą i a, b ∈ G to równanie a ◦ x = b ma dokładnie jedno rozwiązanie w zbiorze G.
Dowód Nietrudno zauważyć, że element a−1 ◦ b jest rozwiązaniem równania.
Nietrudno zauważyć, że jest to jedyne rozwiązanie tego równania.
Jeśli grupa jest abelowa to działanie binarne często zapisujemy przy pomocy znaku +, element odwrotny do a nazywamy przeciwnym i zapisujemy go w postaci −a, a element neutralny oznaczamy przez 0.
System algebraiczny (R, ⊕, ) nazywamy pierścieniem jeśli , ⊕ są
działaniami binarnymi oraz:
(1) (R, ⊕) jest grupą abelową,
(2) (R, ) jest półgrupą,
(3) działanie jest rozdzielne względem ⊕.
3