Processing math: 76%

Iniekcja i suriekcja

Iniekcja i suriekcja


Istotną własnością funkcji jest to, czy różnym elementom może ona przypisać tę samą wartość. Na przykład, w przypadku szyfrowania używamy takich funkcji, które dają się odszyfrować, a więc generują różne kody dla różnych wiadomości. Takie funkcje, których wartości są różne na różnych argumentach nazywamy iniekcjami. Ponieważ ta własność nie zależy od zbioru, na którym funkcja jest zdefiniowana, zdefiniujemy ją dla wszystkich funkcji częściowych.

Definicja 4.1.

Funkcję częściową f nazywamy iniekcją, jeśli różnym elementom przyporządkowuje różne wartości. Formalnie, jeśli spełnia następujący warunek:

yfPx1,x2fL(f(x1)=yf(x2)=y)x1=x2

Powyższy warunek mówi dokładnie tyle, że jeśli elementom x1,x2 funkcja przypisuje tę samą wartość y, to te elementy muszą być równe.

Przykład 4.2.

Następujące funkcje częściowe są iniekcjami:

1. ,
2. {(,)},
3. {(0,1),(1,0)},
4. funkcja, która każdej liczbie naturalnej przypisuje liczbę dwukrotnie większą.

Przykłady funkcji częściowych, które nie są iniekcjami:

1. {(,),({},)},
2. {(0,0),(1,0)},
3. funkcja, która każdej liczbie naturalnej przypisuje największą

liczbę parzystą nie większą od niej.

W poniższym ćwiczeniu pokazujemy, że jeśli funkcja częściowa nie "zlepia" ze sobą dwóch różnych argumentów, to jest "odwracalna".

Ćwiczenie 4.1.

Udowodnij, że funkcja częściowa f jest iniekcją wtedy i tylko wtedy, gdy f1 jest funkcją częściową.

Ćwiczenie 4.2.

Udowodnij, że funkcja f:XY jest iniekcją wtedy i tylko wtedy, gdy istnieje funkcja częściowa g taka, że gf=IX.

Ćwiczenie 4.3

Czy funkcja częściowa stała może być iniekcją? (funkcja częściowa jest stała, jeśli ma jednoelementowy zbiór wartości).

Przypuśćmy, że f nie jest suriekcją na Y, istnieje wtedy yY, dla którego f1({y})=. Wobec tego dla dowolnego BY{y} mamy

f1(B)=f1(B)f1({y})=f1(B{y}),

a więc funkcja f1 nie jest iniekcją.

Przypuśćmy teraz, że f jest suriekcją na Y. Weźmy dwa różne zbiory A,BY. Skoro są różne, to istnieje element y1AB lub y2BA. Zajmiemy się pierwszym przypadkiem, drugi jest symetryczny. Skoro y1B, to f1({y1})f1(B)=. Ponieważ, f jest suriekcją, to f1({y1}), więc istnieje element xf1({y1}). Mamy więc element x taki, że xf1({y1})f1(A) oraz xf1(B), więc zbiory f1(A) i f1(B) są różne. Wobec tego funkcja f1 jest iniekcją.

Ćwiczenie 4.5

Udowodnij, że dla dowolnej funkcji f:XY, f jest iniekcją wtedy i tylko wtedy, gdy funkcja f1 jest suriekcją na P(X).

Funkcję nazywamy bijekcją pomiędzy zbiorami X i Y, jeśli każdemu elementowi zbioru X przypisuje dokładnie jeden element zbioru Y, i w dodatku każdy element zbioru Y występuje w jakimś przypisaniu. Oznacza to dokładnie, że funkcja ta jest zarówno iniekcją jak i suriekcją na zbiór Y.

Definicja 4.5.

Funkcję częściową f nazywamy bijekcją ze zbioru X w zbiór Y, jeśli są spełnione poniższe warunki:

1. f:XY,
2. f jest iniekcją,
3. f jest suriekcją na Y.

Każda funkcja bijektywna pomiędzy zbiorem X a Y dobiera elementy tych zbiorów w pary.

Twierdzenie 4.6.

Funkcja f jest bijekcją ze zbioru X w zbiór Y wtedy i tylko wtedy, gdy f1 jest bijekcją (a więc także funkcją) ze zbioru Y w zbiór X.

Dowód

Z ćwiczenia 4 wynika, że relacja f1 jest iniekcją (bo f jest iniekcją). Z własności przeciwobrazów wynika, że f1(Y)=X. Pozostaje pokazać, że funkcja częściowa f1 jest określona na całym Y. Weźmy dowolny element yY. Ponieważ f jest suriekcją, to istnieje xX, dla którego (x,y)f. Wtedy (y,x)fy, a więc y należy do dziedziny f1. Wobec dowolności wyboru y dziedziną f1 jest cały zbiór Y. Podsumowując, f1:YY jest iniekcją oraz f1(Y)=X, a więc f1 jest bijekcją ze zbioru Y w zbiór X. Implikacja w drugą stronę wynika z faktu, że f=(f1)1.

Twierdzenie 4.7.

Jeśli funkcje częściowe f,g są iniekcjami, to ich złożenie jest iniekcją.

Dowód

Jeśli funkcja częściowa gf jest pusta to jest iniekcją. W przeciwnym razie weźmy dwie dowolne (niekoniecznie różne) pary należące do niej, które mają taką samą drugą współrzędną (x1,y),(x2,y)gf. Skoro należą one do złożenia f z g, to istnieją elementy z1,z2 w dziedzinie relacji f takie, że (x1,z1),(x2,z2)f oraz (z1,y),(z2,y)g. Z iniektywności funkcji częściowej g otrzymujemy, że z1=z2, oznaczmy ten element przez z. Mamy więc (x1,z),(x2,z)f. Z iniektywności funkcji częściowej f dostajemy x1=x2, co dowodzi, że funkcja częściowa gf jest iniekcją.

Ćwiczenie 4.6

Udowodnij że w twierdzeniu 4.7. (patrz twierdzenie 4.7.) implikacja w przeciwną stronę nie jest prawdziwa.

Twierdzenie 4.8.

Dla dowolnych funkcji f:XY,g:YZ, jeśli f jest suriekcją na Y i g jest suriekcją na Z, to gf jest suriekcją na Z.

Dowód

Weźmy dowolny zZ. Ponieważ funkcja g jest suriekcją na Z, to istnieje element yY taki, że (y,z)g. Skoro funkcja f jest suriekcją na Y, to istnieje xX taki, że (x,y)f. Z faktów (x,y)f oraz (y,z)g otrzymujemy (x,z)gf. Dobraliśmy więc do z element xX, z którym jest on w relacji gf. Wobec dowolności wyboru z funkcja gf jest suriekcją.

Ćwiczenie 4.7

Udowodnij, że w twierdzeniu 4.8. implikacja w przeciwną stronę nie jest prawdziwa.

Ćwiczenie 4.8

W ćwiczeniu 3 pokazaliśmy, że poniższe równości nie są prawdziwe dla wszystkich funkcji. Udowodnij, że:

1.dla funkcji f:XY równość f(A1A2)=f(A1)f(A2) jest prawdą dla dowolnych zbiorów A1,A2 wtedy i tylko wtedy, gdy f jest iniekcją,
2. dla funkcji f:XY równość f(XA1)=f(X)f(A1) jest prawdą dla dowolnego zbioru A1 wtedy i tylko wtedy, gdy f jest iniekcją,
3. dla funkcji f:XY równość f(XA1)=Yf(A1) jest prawdą dla dowolnego zbioru A1 wtedy i tylko wtedy, gdy f jest bijekcją.



Ćwiczenie 4.9

Udowodnij, że funkcja f:N^2 \rightarrow N określona w następujący sposób

f(x,y)= \frac{(x+y+1)\cdot(x+y)}{2}+x

jest iniekcją.