Funkcja jako relacja

W poprzednim wykładzie wyróżniliśmy pewną grupę relacji (relacje zwrotne, symetryczne i przechodnie), które to relacje nazwaliśmy relacjami równoważności. Podobnie teraz wyróżnimy pewne relacje, które nazwiemy funkcjami. Podkreślmy jeszcze raz, że funkcja jako relacja jest zbiorem, którego elementami są pary.

Definicja 2.1.

Relację \( f\subset X \times Y \) nazywamy funkcją ze zbioru \( X \) w zbiór \( Y \), jeśli ma następujące własności:

1. \( \forall_{x\in X} \forall_{y\in Y}\forall_{z\in Y}((x,y)\in f \wedge (x,z)\in f) \Rightarrow (y=z). \quad \mbox{(2.1)} \)

2. \( f_L = X. \)

Zbiór wszystkich funkcji ze zbioru \( X \) w zbiór \( Y \) będziemy oznaczać przez \( Y^X \).

Czyli funkcja to relacja taka, że do każdego elementu \( x \) ze zbioru \( X \) można dobrać dokładnie jeden element \( y\in Y \) taki, że \( (x,y)\in f \). Pierwsza własność mówi dokładnie tyle, że jeśli do jakiegoś elementu \( x \) możemy dobrać elementy \( y \) i \( z \) takie, aby obydwa były w relacji z \( x \), to muszą one być sobie równe, a więc do każdego elementu zbioru \( X \) można dobrać co najwyżej jeden element będący z nim w relacji \( f \). Druga własność mówi, że do każdego elementu ze zbioru \( X \) da się dobrać przynjamniej jeden element będący z nim w relacji \( f \). Często będziemy używać skrótowego zapisu \( f:X \rightarrow Y \), który będzie oznaczał, że \( f \) jest funkcją ze zbioru \( X \) w zbiór \( Y \) (a więc \( f_L=X \) i \( f_P\subset Y \)). Mówimy też, że funkcja \( f \) odwzorowuje zbiór \( X \) w zbiór \( Y \).

W definicji funkcji konieczne było odwołanie się do zbioru, na którym funkcja jest określona. Zwróćmy uwagę, że dla konkretnej relacji nie możemy powiedzieć, czy jest ona funkcją, czy nie, gdyż zależy to od tego, jaki zbiór przyjmiemy za \( X \). Na przykład relacja \( r=\{(0,0), (1,1)\} \) jest funkcją ze zbioru \( \{0,1\} \) w zbiór \( \{0,1\} \), ale nie jest funkcją ze zbioru \( N \) w zbiór \( \{0,1\} \). Czasem wygodniej jest rozważać funkcje po prostu jako relacje, dlatego wprowadzamy pojęcie funkcji częściowej.

Definicja 2.2.

Relację \( f \) nazywamy funkcją częściową, jeśli ma następującą własność:

\( \forall_{x} \forall_{y}\forall_{z}((x,y)\in f \wedge (x,z)\in f) \Rightarrow (y=z). \quad \mbox{(2.1)} \)

Zwróćmy uwagę, że równie dobrze powyższą własność moglibyśmy sformułować następująco:

\( \forall_{x\in f_L} \forall_{y\in f_P}\forall_{z \in f_P}((x,y)\in f \wedge (x,z)\in f) \Rightarrow (y=z). \)

Sformułowanie to jest równoważne z (patrz definicja 2.2.), gdyż we wszysktich przypadkach, w których poprzednik implikacji jest prawdziwy, mamy \( x\in f_L, y\in f_P, z \in f_P \).

Fakt 2.1.

Każda funkcja częściowa \( f \) jest funkcją ze zbioru \( f_L \) w zbiór \( f_P \). Dla dowolnych zbiorów \( X,Y \) każda relacja, która jest funkcją ze zbioru \( X \) w zbiór \( Y \), jest funkcją częściową.

Wobec powyższego faktu, w przypadkach, kiedy nie jest istotne, na jakim zbiorze funkcja jest zdefiniowana, będziemy rozważać odpowiadającą jej funkcję częściową. Dla dowolnej funkcji częściowej \( f \) wprowadzamy poniższe oznaczenia, których będziemy również używać dla funkcji. Dla dowolnego \( x \), jeśli istnieje taki element \( y \), dla którego \( (x,y)\in f \), to oznaczamy go przez \( f(x) \), podobnie fakt \( (x,y) \in f \) notujemy jako \( f(x)=y \). Mówimy wtedy, że funkcja częściowa \( f \) przyporządkowuje elementowi \( x \) element \( y \). Elementy \( f_L \) nazywamy argumentami funkcji częściowej \( f \), a elementy \( f_P \) wartościami funkcji częściowej \( f \).

Przykład 2.3.

Poniżej przedstawiamy przykłady relacji, które są funkcjami częściowymi:

1. \( \emptyset \) (poprzednik implikacji (patrz definicja 2.2.), jest zawsze fałszywy więc implikacja (patrz definicja 2.2.), jest zawsze prawdziwa),

2. \( \{ (\emptyset,\emptyset) \} \),

3. \( \{ (0,0), (1,0),(2,1)\} \),

4. \( X \times \{0\} \) dla dowolnego zbioru \( X \),

5. \( \mathbb{I}_{X} \)

oraz relacje, które funkcjami częściowymi nie są:

1. \( \{(0,0), (0,1)\} \),

2. \( X\times \{0,1\} \), dla dowolnego niepustego zbioru \( X \).

Ćwiczenie 2.1

1. Udowodnij, że złożenie funkcji częściowych jest funkcją częściową.

2. Udowodnij, że jeśli \( f:X \rightarrow Y \) i \( g:Y \rightarrow Z \), to relacja \( g\circ f \) jest

funkcją ze zbioru \( X \) w zbiór \( Z \).

Rozwiązanie 1

Niech \( f, g \) będą funkcjami częściowymi. Dla dowodu nie wprost przypuśćmy, że złożenie \( g\circ f \) nie jest funkcją częściową. Jest to równoważne faktowi, że istnieją elementy \( x,y_1,y_2 \) takie, że \( (x,y_1),(x,y_2) \in g\circ f \) i \( y_1\neq y_2 \). Skoro \( (x,y_1)\in g\circ f \), to z definicji złożenia relacji istnieją pary \( (x,z_1) \in f \) oraz \( (z_1,y_1)\in g \), dla pewnego elementu \( z_1 \). Podobnie dla \( (x,y_2)\in g\circ f \) istnieją pary \( (x,z_2) \in f \) oraz \( (z_2,y_2)\in g \), dla pewnego elementu \( z_2 \). Ponieważ \( (x,z_1), (x,z_2) \in f \) oraz \( f \) jest funkcją częściową, to \( z_1=z_2 \), będziemy więc ten element oznaczać przez \( z \). Wobec tego mamy \( (z,y_1),(z,y_2)\in g \). Skoro jednak \( g \) jest funkcją częściową, to \( y_1=y_2 \). Jest to sprzeczność z założeniem nie wprost.

Rozwiązanie 2

Z poprzedniego punktu otrzymujemy, że \( g\circ f \) jest funkcją częściową. Wystarczy pokazać, że jest określona na wszystkich elementach zbioru \( X \). Weźmy dowolny \( x\in X \), ponieważ \( f:X \rightarrow Y \) to \( f_L=X \), a więc istnieje \( y\in Y \), dla którego \( (x,y)\in f \). Podobnie skoro \( g:Y \rightarrow Z \), to istnieje \( z\in Z \) taki, że \( (y,z) \in g \). Z definicji złożenia relacji otrzymujemy \( (x,z)\in g\circ f \), a zatem \( g\circ f \) jest określona na \( x \). Wobec dowolności wyboru \( x \) jest określona na całym zbiorze \( X \).

Ćwiczenie 2.2

Czy na każdym zbiorze \( X \) istnieje relacja równoważności, która jest funkcją z \( X \) w \( X \)?

Rozwiązanie

Dla każdego zbioru \( X \) relacja równoważności \( \mathbb{I}_{X} \) (identyczność) jest funkcją.