Na zbiorach określa się działania. Efektem tych działań są nowe zbiory. Jest jeszcze jeden sposób tworzenia nowych zbiorów - za pomocą danych zbiorów, tzw. operacja tworzenia iloczyn kartezjańskiego (produkt kartezjański).

Para uporządkowana - mając dowolne dwa elementy a i b możemy z nich tworzyć parę uporządkowana o poprzedniku a i następniku b. Parę uporządkowaną (a, b) uważamy różną od (b, a) jeżeli a nie równa się b. Pary uporządkowane (a, b) i (c, d) są takie same jeżeli a równa się c i b równa się d.

Definicja 1
Iloczynem kartezjańskim (produktem kartezjańskim) zbiorów X i Y nazywamy zbiór wszystkich par uporządkowanych (x, y) takich że x należy do X i y należy do Y.

X x Y:={(x, y): x € X, y € Y}

x1, x2, xn

x1 x x2 x xn = {(x1, x2, xn): xi € Xi, i=1, ..., n}

x^n = x1 x ... x xn

X = IR

X^n = IR^n

Elementy x1, x2, xn € X^n będziemy często zapisywać w postaci kolumny.

Definicja 2
Relacja pomiędzy elementami zbioru X i Y nazywamy dowolny zbiór R par uporządkowanych (x, y) gdzie x należy do X a y należy do Y. Jeżeli R jest relacją to zbiór poprzedników par uporządkowanych tworzących R nazywamy dziedziną relacji R a zbiór następników tych par nazywamy zbiorem wartości.

x R y lub x ~ y

Zatem relacje R można interpretować jako podzbiór produktu kartezjanskiego.

Definicja 3 !

Relację ~ określoną w zbiorze X (jeżeli relacją R € X x X to mówimy że relacja określona jest w zbiorze X) nazywa się relacją ważności jeżeli macierz posiada 3 następujące własności:
zwrotność x € X : x~x
symetria x, y € X : jeśli x ~ y to y ~ x
przechodność x, y, z € X : jeśli x ~ y oraz y ~ z to x ~ z

Definicja 4
Jeżeli ~ jest relacją równoważności w zbiorze X to zbiór [y]~ : = {x € X : x~y} nazywamy klasą abstrakcji elementu y ~

Twierdzenie 1 !!! (zasada abstrakcji)
Relacja rownowazności ~ określona w zbiorze X określa podział tego zbioru na rozłączne niepuste podzbiory, na klasy abstrakcji w tej relacji takie że dwa elementy x i y zbioru X należą do tej samej klasy abstrakcji wtedy i tylko wtedy gdy są w tej relacji x ~ y
x, y € X <=> x~y

Definicja 5
Niech f: X -> Y
Fukcja f jest:
(i) przekształceniem identycznościowym (tożsamościowym) idx jezeli X = Y oraz f(x) = x dla każdego x € X
(ii) suriekcją (funkcja na)
f(X) = Y
(iii) iniekcją (różnowartościowa)
x1 != x2 => f(x1) != f(x2)
(iv) bijekcją jeżeli jest jednocześnie surjekcją i iniekcją

Bogatym źródłem otrzymywania nowych funkcji jest operacja składania.
Jeżeli odwzorowania f : X -> Y : y : są takie że jedno z nich jest określone na zbiorze wartości drugiego to można zbudować nowe odwzorowanie g o f = g(f(x)) - złożenie lub superpozycja

Podstawowe struktury algebraiczne:
grupy (pierścienia)
pierścień (podpierścień)
ciało (podciało)

Definicja 6
Niech X będzie dowolnym niepustym zbiorem. Działaniem w zbiorze X nazywamy każdą funkcję f : X x X -> X
np. W zbiorze liczb naturalnych f(m, n) = m x n itp. ARGUMENTY SĄ ZE ZBIORU I WYNIKI SĄ NA ZBIORZE

Definicja 7 !
Grupą nazywamy dowolny zbiór G niepusty, na którym określono działanie zwanym działaniem grupowym lub mnożeniem G spełniającym następujące warunki
(G1) dla dowolnych a, b, c € G
a x (b x c) = (a x b) x c (łączność)
(G2) istnieje element e neutralny będący jedynką grupy taki że dla każdego a z G pozostaje nam a (jedynka)
e x a = a = a x e
(G3) dla każdego a z G istnieje b z G zwany elementem odwrotnym do a takim że a x b = b x a = e

Ponadto
(G4)
a x b = b x a (przemienność)
Jeżeli jest to także spełnione to jest to grupa abelowa

Jeżeli liczba elementów jest skończona to liczbę jej elementów nazywamy rzędem grupy G. Jeżeli liczna elementów jest nieskonczona to jej rząd jest nieskończony.

Uwaga
Nie należy mylić działania grupowego z mnożeniem liczb. Zgodnie z tradycją wynik działania • na parze (a, b) zapisujemy w postaci a • b lub ab, a elementy neutralne grupy oznaczamy symbolem 1.
W grupie abelowej przyjęło się stosować terminologię addytywną i nazywamy to działanie dodawaniem a + b, elementem neutralnym jest i 0

Lemat 1
G jest grupą
(i) element neutralny grupy jest tylko jeden
(ii) dla dowolnego a € G element odwrotny do G jest jednoznacznie określony, oznaczamy to symbolem a^-1
(iii) dla każdego a € G (a^-1)^-1 = A
(a b)^-1 = b^-1 • a^-1

Przykłady
Z, IR, Q, C:
Zbiór liczb naturalnych nie jest grupą

Każdy z następujących zbiorów
Q^x = Q \ {0}
IR^x = IR \ {0}
C^x = C \ {0}
Z mnożeniem jako działaniem grupowym jest grupą abelowa


Grupy odwzorowań, permutacje

Twierdzenie 2
Jeżeli X jest niepustym zbiorem to zbiór jego wszystkich bijekci jest grupą ze składaniem odwzorowań jako działaniem grupowym.
Grupę te nazywamy grupą symetryczną zbioru X. Elementem neutralnym grupy Sx jest odwzorowanie identycznościowe.

Definicja 8
Niech X będzie zbiorem skończonym. Każdą bijekcja zbioru X na siebie nazywamy permutację elementu a1, ..., an. Permutację sigma
X -> X
ak -> ajk = 2(ak)

Uwaga
Każda permutacja sigma dowolnego zbioru X o n elementach określona na zbiorze sprowadza się do permutacji k -> jk Jn = {1, 2, ... , n}
Tak więc mówiąc o permutacji zbioru n elementowego będziemy mieli na myśli permutację zbioru Jn.

Zgodnie z powyższym twierdzeniem zbiór wszystkich permutacji zbioru Jn jest grupą z operacją składania permutacji. Grupę te oznaczamy symbolem Sn i nazywamy grupą symetryczną stopnia n. Elementem neutralnym jest permutacja identycznościowa a składanie permutacji jest działaniem którego wykonanie sprowadza się do "mechanicznego" stosowania szeregu prostych operacji. Wykonywanie tego działania ilustruje następujący przykład

1 2 3 4 1 2 3 4
(3 1 4 2)(2 4 3 1) = (1 2 4 3)
1 2 3 4 1 2 3 4
(2 4 3 1)(3 1 4 2) = (3 2 1 4)

(3 1 4 2)^-1 = (3 1 4 2) = (2 4 1 3)
(1 2 3 4)

(3 1 4 2)(2 4 1 3) = (1 2 3 4)
(2 4 1 3)(3 1 4 2) = (1 2 3 4)