Wstęp do algebry i teorii liczb
Jacek Jaśniewski
13 listopada 2013
1
Relacje
Mając dwa elementy a, b ∈ A możemy utworzyć parę uporządkowaną o poprzedniku a i następniku b (zapisujemy (a, b)) taką,że
(a, b) = (c, d) ⇔ a = c ∧ b = d
(a, b) = (b, a) ⇔ a = b
Definicja 1. Produktem Kartezjańskim (iloczynem Kartezjańskim)
zbiorów niepustych A i B nazywamy zbiór wszystkich par uporządkowanych
(a, b) takich, że poprzednik należy do A, następnik należy do B i oznaczmy
A×B
A × B = {(a, b) : a ∈ A ∧ b ∈ B}
Przykład 1.
A = {−1, 5}, B = {k, l, m}
A × B = {(−1, k), (−1, l), (−1, m), (5, k), (5, l), (5, m)}
B × A = {(k, −1), (k, 5), (l, −1), (l, 5), (m, −1), (m, 5)}
A×B =B×A
¯
¯
¯
A = x, B = y ⇒ A × B = xy
Definicja 2. Jeśli dane są dwa zbiory A, B, to każdy podzbiór ρ ⊂ A × B
nazywamy relacją między elementami zbioru A i B. Jeśli A = B, relacja ρ
określona jest w zbiorze A
Przykład 2.
ρ = {(x, y) ∈ A × B : x = −1, y ∈ {k, l, m}}
Zamiast (−1, k) ∈ ρ będziemy pisać −1ρk
Zamiast (a, b) ∈ ρ będziemy pisać aρb
Definicja 3. Niech ρ będzie określone w zbiorze A. Mówimy, że relacja jest:
zwrotna, jeśli
aρa
a∈A
aρb ⇒ bρa
symetryczna, jeśli
a,b∈A
[(aρb ∧ bρa) ⇒ aρc)]
przechodnia, jeśli
a,b,c∈A
1
Definicja 4. Relację ρ ⊂ A × A, która spełnia warunki a),b) i c) nazywamy
relacją równoważności określoną w zbiorze A
Przykład 3. .
A - obecni studenci
ρ relacja w A taka, że
aρb ⇔ aib urodziły się w tym samym miesiącu
Ta relacja spełnia warunki a),b),c) ⇒ jest relacją równoważności.
Relacja ρ dzieli A na 12 podzbiorów. Są one rozłączne a ich suma daje A.
A-mieszkańcy Polski
aρb ⇔ a jest bratem b
ρ nie jest zwrotna ani symetryczna ani przechodnia
Definicja 5. Dla dowolnego a ∈ A podzbiór
[a] = {b ∈ A : aρb}
nazywamy klasą abstrakcji (klasą równoważności) elementów a względem ρ
Definicja 6. Zbiór wszystkich klas abstrakcji nazywamy zbiorem ilorazowym
i oznaczamy A\ρ
Dziedziną relacji ρ ⊂ A × B nazywamy zbiór takich elementów a ∈ A, dla
których istnieje element b ∈ B taki, że a jest w relacji ρZb:
D(ρ) = {a ∈ A :
aρb}
b∈B
Przeciwdziedziną relacji ρ nazywamy zbiór takich elementów b ∈ B, dla których
istnieje element a ∈ A taki, że a jest w relacji ρZb:
D∗ = {b ∈ B :
aρb}
a∈A
Twierdzenie 7. Niech ρ będzie relacją równoważności określoną w zbiorze A.
• każdy element zbioru A należy do pewnej klasy abstrakcji i klasy abstrakcji
są zbiorami niepustymi
• klasy abstrakcji relacji ρ są albo identyczne albo rozłączne, tzn
[a] = [b] ∨ [a] ∩ [b] = ∅
a∈A
oraz suma wszystkich klas abstrakcji tworzy cały zbiór.
2
Dowód 1. .
• Zdefinicji relacji równoważności - jej warunku zwrotności - wynika, że
∀a ∈ A
a ∈ [a],
aρa
[a] = {b ∈ A
aρb}
Zatem każdy element zbioru A należy do pewnej klasy abstrakcji i klasy
abstrakcji są zbiorami niepustymi.
• Załóżmy, że dla pewnych elementów a, b ∈ A klasy abstrakcji [a] i [b] nie
są rozłączne. Wtedy
[a] ∩ [b] = ∅
Istnieje więc element c ∈ [a] ∩ [b], czyli c ∈ [a] ∧ c ∈ [b].Zdefinicji klasy
abstrakcji otrzymujemy:
aρc ∧ bρc ⇒ aρc ∧ cρb
.
Z
(…)
…
(e ◦ f )(x) = e(f (x)) = f (x)
x∈A
Zatem f ◦ e = f ∧ e ◦ f = f , tzn. e jest elementem neutralnym dla
składania przekształceń.
Funkcję e nazywamy identycznością lub tożsamością (odwzorowaniem identycznościowym/tożsamościowym) zbioru A i nazywamy
idA : A ⇒ A,
ida (a) = a
a∈A
4.
f ◦ g = id ∧ g ◦ f = id
f ∈Bij(A) g∈Bij(A)
UWAGA: Funkcja odwrotna istnieje tylko dla bijekcji.
Niech f : A ⇒ B…
…
14
(f −1 ◦ f )(a) = f −1 (f (a)) = f −1 (b) = a ⇒ f −1 ◦ f = idA
Podobnie:
a∈A
Definicja 19. Jeśli zbiór A jest zbiorem skończonym n-elementowym, to sumę
bijekcji A nazywamy grupą permutacji zbioru A stopnia n − tego i oznaczamy
Sn a każdą bijekcję tej grupy nazywamy permutacją zbioru A.
|Sn | = n!
Definicja 20. Niech A = ∅ i niech +, · będą działaniami wewnętrznymi w A.
Strukturę (P, +, ·) nazywamy…
…. Mnożenie liczb zespolonych jest działaniem łącznym i przemiennym (bo C
jest ciałem) a G jako podciało posiada te same własność.
3. Elementem neutralnym dla mnożenia liczb zespolonych w ciele jest
1 = 1 + 0 · i = E0 ⊂ G
4.
Ek · El = 1 = E0
Ek ∈G El ∈G
Mamy
Ek · El =
Ek+l
Er
dla 0 k + l < n
dla k + l n
Stąd
Ek · El = 1 ⇔
Zatem
−1
E0
−1
Ek
E0
Er
dla 0 k + l = 0
dla k + l = n
= E0
= En−k dla k = 0
33
Grupę (G…
… + . . . + an · z¯ = 0 = a0 + a1 zo + . . . + an z¯ = 0
¯
¯ ¯
¯ 0
¯
0
34
Grupa permutacji (Bij(A), ◦) = SA - grupa bijekcji/grupa przekształceń
(grupa symetryczna zbioru) A. Jeśli zbiór
A = {a1 , a2 . . . an }
jest zbiorem skończonym, to każdą bijekcję zbioru A nazywamy permutacją
zbioru A a grupę SA nazywamy grupą permutacji zbioru A. i oznaczamy Sn .
Rząd grupy Sn jest równy n!, tzn. |Sn | = n!.
Każdą…
….
a, b ∈ H ⇒ a · b ∈ H
3.
a ∈ H ⇒ a−1 ∈ H
Każda grupa niezerowa ma co najmniej dwie podgrupy:
1.
H1 = {e} (podgrupa zerowa),
2.
H2 = G (podgrupa niewłaściwa)
Przykład 8. Podgrupy grupy Z6 (Z6 , +)
n
H1 = {0}
H2 = {0, 2, 4}
H3 = {0, 3}
H4 = Z 6
Definicja 17. Rzędem grupy (G, ·) nazywamy moc zbioru G, a w przypadku,
gdy jest zbiorem skończonym, jest to liczba elementów zbioru G.
Oznaczenie: |G| = n…
... zobacz całą notatkę
Komentarze użytkowników (0)