Logika i teoria mnogości/Wykład 6: Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wprowadzenie

W poniższym wykładzie wprowadzamy formalnie pojęcie funkcji. Bardzo duży fragment współczesnej matematyki dotyczy właśnie badania własności funkcji. W teorii zbiorów funkcje są relacjami, które spełniają dodatkowy warunek jednoznaczności. Każda funkcja jest więc zbiorem par. W teorii zbiorów, której pojęciem pierwotnym jest należenie do zbioru, reprezentowanie funkcji za pomocą zbiorów jest pewną koniecznością. W praktyce jednak patrzymy na funkcje raczej jako na operacje, działające na elementach pewnych zbiorów. Często do opisu funkcji używamy wzorów, np. . Warto jednak podkreślić różnicę pomiędzy wzorem a funkcją. Przykładowy wzór może opisywać wiele funkcji, w zależności od tego, z jakiego zbioru elementy będziemy podstawiać w miejsce , a nawet od tego, jak będziemy rozumieć podnoszenie do kwadratu (np. przez oznaczaliśmy iloczyn kartezjański , ale równocześnie dla liczby naturalnej przez będziemy oznaczać jej kwadrat). W kolejnych wykładach przekonamy się również, że istnieją funkcje, których nie da się opisać żadnym wzorem.

Warto wspomnieć, że rozważa się również teorie, w których pierwotnymi pojęciami są właśnie funkcje i składanie funkcji. Okazuje się, że bardzo wiele twierdzeń klasycznej matematyki (opartej na teorii zbiorów) da się udowodnić na ich gruncie. Takiemu właśnie podejściu poświęcony jest wykład Teoria kategorii dla informatyków.

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ę nazywamy funkcją ze zbioru w zbiór , jeśli ma następujące własności:

1.


2.

Zbiór wszystkich funkcji ze zbioru w zbiór będziemy oznaczać przez .

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

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 . Na przykład relacja jest funkcją ze zbioru w zbiór , ale nie jest funkcją ze zbioru w zbiór . Czasem wygodniej jest rozważać funkcje po prostu jako relacje, dlatego wprowadzamy pojęcie funkcji częściowej.

Definicja 2.2.

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

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

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

Fakt 2.1.

Każda funkcja częściowa jest funkcją ze zbioru w zbiór . Dla dowolnych zbiorów każda relacja, która jest funkcją ze zbioru w zbiór , 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 wprowadzamy poniższe oznaczenia, których będziemy również używać dla funkcji. Dla dowolnego , jeśli istnieje taki element , dla którego , to oznaczamy go przez , podobnie fakt notujemy jako . Mówimy wtedy, że funkcja częściowa przyporządkowuje elementowi element . Elementy nazywamy argumentami funkcji częściowej , a elementy wartościami funkcji częściowej .

Przykład 2.3.

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

1. (poprzednik implikacji (patrz definicja 2.2.), jest zawsze fałszywy więc implikacja (patrz definicja 2.2.), jest zawsze prawdziwa),
2. ,
3. ,
4. dla dowolnego zbioru ,
5.

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

1. ,
2. , dla dowolnego niepustego zbioru .

Ćwiczenie 2.1

1. Udowodnij, że złożenie funkcji częściowych jest funkcją częściową.
2. Udowodnij, że jeśli i , to relacja jest

funkcją ze zbioru w zbiór .

Rozwiązanie 1
Rozwiązanie 2

Ćwiczenie 2.2

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

Rozwiązanie

Obrazy i przeciwobrazy

Czasem warto spojrzeć na funkcję z szerszej perspektywy. Rozważmy pewną funkcję . Funkcja ta w naturalny sposób wyznacza pewną funkcję przekształcającą podzbiory zbioru w podzbiory zbioru , przyporządkowując zbiorowi , zbiór elementów zbioru , które są wartościami funkcji dla pewnych argumentów ze zbioru . Funkcję tą formalnie definujemy w poniższy sposób.

Definicja 3.1.

Każda funkcja wyznacza pewną funkcję tak, że dla dowolnego zbioru

Dla dowolnego zbioru zbiór nazywamy obrazem zbioru przez funkcję .

Przykład 3.2.

Niech będzie określona wzorem . Wtedy

1. jest zbiorem liczb parzystych,
2. ,
3. ,
4. ,
5. obrazem zbioru liczb parzystych przez funkcję jest zbiór liczb podzielnych przez 4.

W podobny sposób definiujemy przeciwobrazy zbiorów przez funkcję. Przeciwobrazem zbioru przez funkcję nazwiemy zbiór tych elementów zbioru , którym funkcja przypisuje wartości ze zbioru .

Definicja 3.3.

Każda funkcja wyznacza pewną funkcję w następujący sposób. Dla dowolnego zbioru

Dla dowolnego zbioru zbiór nazywamy przeciwobrazem zbioru przez funkcję .

Przykład 3.4.

Niech będzie określona wzorem . Wtedy

1. ,
2. ,
3. ,
4. ,
5. przeciwobrazem zbioru liczb nieparzystych przez funkcję jest zbiór pusty,
6. przeciwobrazem zbioru liczb podzielnych przez 4, przez funkcję jest zbiór liczb parzystych,
7. przeciwobrazem zbioru liczb parzystych przez funkcję jest .

Fakt 3.1.

Nietrudno zauważyć, że dla dowolnej funkcji częściowej

W poniższych ćwiczeniach badamy podstawowe własności obrazów i przeciwobrazów dowolnych funkcji.

Ćwiczenie 3.1

Dla dowolnej funkcji i dla dowolnych zbiorów udowodnij następujące fakty:

1. ,
2. ,
3. .
Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3

Ćwiczenie 3.2

Dla dowolnej funkcji i dowolnej rodziny podzbiorów (czyli ) udowodnij następujące fakty:

1. ,
2. .
Rozwiązanie 1
Rozwiązanie 2

Ćwiczenie 3.3

Skonstruuj kontrprzykłady dla poniższych inkluzji:

1. ,
2. ,
3. .
Rozwiązanie


Znacznie bardziej regularnie zachowują się przeciwobrazy funkcji. Podstawowe własności są tematem następnych ćwiczeń.

Ćwiczenie 3.4

Dla dowolnej funkcji i dla dowolnych zbiorów udowodnij następujące fakty:

1. ,
2. ,
3. .
Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3

Ćwiczenie 3.5

Dla dowolnej funkcji i dowolnej rodziny podzbiorów (czyli ) udowodnij następujące fakty:

1. ,
2. .
Rozwiązanie 1
Rozwiązanie 2

Istnieje ścisły związek pomiędzy funkcjami a relacjami równoważności. Każda funkcja wyznacza pewną relację binarną w poniższy sposób.

Definicja 3.5.

Dla dowolnej funkcji definujemy relację binarną następująco:

W myśl powyższej definicji elementy są w relacji , jeśli funkcja na tych elementach przyjmuje te same wartości. W poniższym ćwiczeniu dowodzimy, że relacja ta jest relacją równoważności na zbiorze . Relacja ta pełni ważną rolę w podstawowych konstrukcjach liczb, które będą tematem Wykładu 8.

Ćwiczenie 3.6

Udowodnij, że dla dowolnej funkcji relacja jest relacją równoważności na zbiorze .

Rozwiązanie

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ą nazywamy iniekcją, jeśli różnym elementom przyporządkowuje różne wartości. Formalnie, jeśli spełnia następujący warunek:

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

Przykład 4.2.

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

1. ,
2. ,
3. ,
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. ,
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 jest iniekcją wtedy i tylko wtedy, gdy jest funkcją częściową.

Rozwiązanie

Ćwiczenie 4.2.

Udowodnij, że funkcja jest iniekcją wtedy i tylko wtedy, gdy istnieje funkcja częściowa taka, że .

Rozwiązanie

Ć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).

Rozwiązanie

W praktyce często posługujemy się elementami pewnego ustalonego zbioru (np. liczb naturalnych, rzeczywistych itp.) i funkcjami operującymi na tych elementach. W takich przypadkach przydatna okazuje się poniższa definicja funkcji suriektywnej.

Definicja 4.3.

Funkcję częściową nazywamy suriekcją na zbiór , jeśli . Możemy to zapisać jako

Zauważmy, że nie ma sensu nazywanie funkcji częściowej suriekcją bez odniesienia się do zbioru . Dla każdej funkcji możemy dobrać zbiór tak, aby była, i tak, aby nie była suriekcją. W przypadku funkcji określenie, że jest suriekcją, będzie oznaczało, że jest suriekcją na zbiór .

Przykład 4.4.

1. jest suriekcją na , ale nie jest suriekcją na żaden inny zbiór,
2. jest suriekcją na zbiór i nie jest suriekcją na ,
3. jest suriekcją na zbiór i nie jest suriekcją na ,
4. funkcja taka, że jest suriekcją na zbiór liczb naturalnych silnie większych od 0 (czasem oznaczany przez ), ale nie jest suriekcją na .

Fakt 4.1.

Funkcja jest suriekcją wtedy i tylko wtedy, gdy istnieje funkcja taka, że .

Do udowodnienia powyższego faktu konieczne jest użycie aksjomatu wyboru. Jego dowód (nietrudny) odłożymy więc do wykładu, który jest poświęcony temu aksjomatowi oraz jego równoważnikom.

Ćwiczenie 4.4

Udowodnij, że dla dowolnej funkcji , jest suriekcją na wtedy i tylko wtedy, gdy funkcja jest iniekcją na .

Rozwiązanie

Ćwiczenie 4.5

Udowodnij, że dla dowolnej funkcji , jest iniekcją wtedy i tylko wtedy, gdy funkcja jest suriekcją na .

Rozwiązanie


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

Definicja 4.5.

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

1. ,
2. jest iniekcją,
3. jest suriekcją na .

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

Twierdzenie 4.6.

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

Dowód

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

End of proof.gif

Twierdzenie 4.7.

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

Dowód

Jeśli funkcja częściowa 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ą . Skoro należą one do złożenia z , to istnieją elementy w dziedzinie relacji takie, że oraz . Z iniektywności funkcji częściowej otrzymujemy, że , oznaczmy ten element przez . Mamy więc . Z iniektywności funkcji częściowej dostajemy , co dowodzi, że funkcja częściowa jest iniekcją.

End of proof.gif

Ćwiczenie 4.6

{{{3}}}

Twierdzenie 4.8.

Dla dowolnych funkcji , jeśli jest suriekcją na i jest suriekcją na , to jest suriekcją na .

Dowód

Weźmy dowolny . Ponieważ funkcja jest suriekcją na , to istnieje element taki, że . Skoro funkcja jest suriekcją na , to istnieje taki, że . Z faktów oraz otrzymujemy . Dobraliśmy więc do element , z którym jest on w relacji . Wobec dowolności wyboru funkcja jest suriekcją.

End of proof.gif

Ćwiczenie 4.7

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

Rozwiązanie

Ć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 równość jest prawdą dla dowolnych zbiorów wtedy i tylko wtedy, gdy jest iniekcją,
2. dla funkcji równość jest prawdą dla dowolnego zbioru wtedy i tylko wtedy, gdy jest iniekcją,
3. dla funkcji równość jest prawdą dla dowolnego zbioru wtedy i tylko wtedy, gdy jest bijekcją.
Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3

Ćwiczenie 4.9

Udowodnij, że funkcja określona w następujący sposób

jest iniekcją.

Rozwiązanie

Twierdzenie o faktoryzacji

W tym rozdziale udowodnimy ważne twierdzenie dobrze ilustrujące rolę, którą spełniają iniekcje i suriekcje wśród wszystkich funkcji.

Rysunek 6.1.

Twierdzenie 5.1.

Dla każdej funkcji istnieje zbiór oraz funkcje takie, że , jest suriekcją i jest iniekcją.

Dowód

Niech będzie zbiorem klas abstrakcji relacji . Wtedy definujemy jako funkcję, która każdemu elementowi zbioru przypisuje jego klasę abstrakcji względem relacji , czyli

Zauważmy, że tak zdefiniowana funkcja jest suriekcją na zbiór , gdyż klasy abstrakcji nie mogą być puste. Funkcję defniujemy jako funkcję przypisującą klasom abstrakcji relacji wartość funkcji na dowolnym elemencie tej klasy, czyli

Zauważmy, że rzeczywiście jest funkcją, gdyż, zgodnie z definicją relacji , funkcja przypisuje wszystkim elementom danej klasy te same wartości.

Pokażemy teraz, że jest iniekcją. Weźmy dowolne dwie klasy i przypuśćmy, że . Niech będą takimi elementami, że oraz . Zgodnie z definicją mamy oraz . Założyliśmy, że , więc również . Wynika stąd, że , a więc , co oznacza dokładnie, że . Pokazaliśmy więc, że jest iniekcją.

Pozostaje pokazać, że . Dla dowolnego elementu mamy

oraz

Wobec czego otrzymujemy

Skoro własność ta zachodzi dla każdego , otrzymujemy .

End of proof.gif

Ćwiczenie 5.1

Dla poniższych funkcji podaj przykład funkcji oraz zbioru z twierdzenia 5.1 o faktoryzacji (patrz twierdzenie 5.1.)

1. Niech będzie zbiorem okręgów na płaszczyźnie, funkcja niech przypisuje okręgom długości ich średnic,

2. w taki sposób, że .

Rozwiązanie

Produkt uogólniony

W wykładzie dotyczącym relacji zdefiniowaliśmy iloczyn kartezjański skończonej liczby zbiorów. Poniższa definicja uogólnia tamte rozważania, definiując produkt dowolnej (nawet nieskończonej) rodziny zbiorów.

Definicja 6.1.

Produktem uogólnionym zbioru nazwiemy zbiór zdefiniowany następująco:

Czyli zbiór to zbiór wszystkich tych funkcji, które zbiorom z rodziny przypisują ich elementy.

Zauważmy, że istnienie produktu uogólnionego dla każdego zbioru wynika z aksjomatu wyróżniania. Znacznie ważniejszą własnością jednak jest niepustość produktu uogólnionego. Z aksjomatu wyboru w Wykładzie 4 wynika, że produkt uogólniony dowolnej niepustej rodziny niepustych zbiorów jest zawsze niepusty. W konkretnych przypadkach można wykazać niepustość, nie odwołując się do aksjomatu wyboru (np. ).

W poniższym twierdzeniu pokazujemy, że produkt uogólniony jest w dużej mierze zgodny ze zdefiniowanym wcześniej iloczynem kartezjańskim. Jest to przy okazji pierwszy przykład konstrukcji funkcji bijektywnej, która pozwala "tłumaczyć" elementy jednego zbioru na drugi, co z kolei usprawiedliwia wymienne posługiwanie się nimi.

Twierdzenie 6.2.

Dla dowolnych różnych zbiorów istnieje bijekcja pomiędzy zbiorami a zbiorem .

Dowód

Jeśli któryś ze zbiorów jest pusty, to , a więc istnieje pomiędzy nimi bijekcja (ćwiczenie: jaka?). Poniżej rozważamy przypadek, gdy oba zbiory są niepuste.

Zdefiniujemy funkcję . Dla dowolnej funkcji niech . Zauważmy najpierw, że para jest rzeczywiście elementem zbioru , ponieważ z definicji zbioru mamy oraz .

Pokażemy, że funkcja jest iniekcją. Weźmy dowolne funkcje , dla których . Z definicji funkcji otrzymujemy , a to jest spełnione tylko wtedy, gdy i . Przypomnijmy, że dziedziną funkcji i jest zbiór . Skoro przyjmują te same wartości na elementach dziedziny, to są sobie równe, a to wobec dowolności wyboru i oznacza, że jest iniekcją.

Pozostało pokazać, że jest suriekcją. Weźmy dowolną parę i rozważmy funkcję . Ponieważ zbiory i są różne, to jest funkcją określoną na zbiorze . Dodatkowo spełnia warunek i , a więc . Zauważmy, że . Wskazaliśmy więc element dziedziny funkcji , dla którego wartością jest właśnie . Wobec dowolności wyboru dowiedliśmy, że jest suriekcją.

End of proof.gif

Ćwiczenie 6.1

Udowodnij, że założenie o różności zbiorów i w powyższym twierdzeniu jest konieczne.

Rozwiązanie

Twierdzenie Knastra-Tarskiego

Bronisław Knaster (1893-1980)
Zobacz biografię

W tym rozdziale przedstawimy podstawową wersję twierdzenia

Knastra-Tarskiego o punktach stałych funkcji monotonicznych oraz kilka przykładów zastosowań.

Definicja 7.1.

Funkcję nazwiemy monotoniczną ze względu na inkluzję, jeśli

Funkcje monotoniczne ze względu na inkluzję zachowują relację inkluzji pomiędzy przekształcanymi zbiorami. Nie oznacza to jednak wcale, że argument funkcji musi byc podzbiorem wartości funkcji na tym argumencie.

Ćwiczenie 7.1

Podaj przykład funkcji monotonicznej , dla której nieprawdą jest, że dla każdego zbioru , zachodzi .

Rozwiązanie

Definicja 7.2.

Element jest punktem stałym funkcji , jeśli

Ćwiczenie 7.2

Podaj przykłady punktów stałych następujących funkcji:

1. jest określona wzorem ,
2. jest określona wzorem ,
3. jest określona wzorem .
Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3

Zwróćmy uwagę, że istnieją funkcje, które nie mają punktów stałych. Prostym przykładem może być funkcja .

Ćwiczenie 7.3

Niech będzie niepustym zbiorem. Udowodnij, że dla funkcji zdefiniowanej wzorem nie istnieje punkt stały.

Rozwiązanie

Definicja 7.3.

Punkt jest najmniejszym punktem stałym funkcji , jeśli oraz

Czyli wtedy, kiedy każdy inny punkt stały jest jego nadzbiorem.

Definicja 7.4.

Punkt jest największym punktem stałym funkcji , jeśli oraz

Czyli wtedy, kiedy każdy inny punkt stały jest jego podzbiorem.

Poniższy przykład ilustruje, że istnienie najmniejszego i największego punktu stałego wcale nie jest oczywiste.

Przykład 7.5.

Dla funkcji określonej wzorem punktami stałymi są oraz singletony zawierające podzbiory zbioru (czyli zbiory postaci dla ). Jeśli jest niepusty, to istnieją przynajmniej dwa różne punkty stałe będące singletonami. Nie istnieje wtedy punkt stały będący ich nadzbiorem, gdyż musiałby zawierać przynajmniej dwa elementy. Wobec tego nie istnieje największy punkt stały funkcji .

Alfred Tarski (1901-1983)
Zobacz biografię

Twierdzenie 7.6. [Knaster-Tarski]


Każda monotoniczna funkcja posiada najmniejszy i największy punkt stały.

Dowód

Niech . Pokażemy, że jest największym punktem stałym funkcji . Zauważmy, że dla każdego z monotoniczności otrzymujemy

Wobec tego również

skąd otrzymujemy, że . Przekształcając obie strony poprzedniego równania przez dzięki monotoniczności tej funkcji, otrzymamy

Wobec czego również . Ponieważ każdy element jest podzbiorem , to również . Stąd i z równania 7.1 otrzymujemy

a więc jest punktem stałym funkcji . Co więcej, wszystkie punkty stałe należą do zbioru , wobec czego każdy z nich jest podzbiorem , co oznacza dokładnie, że jest największym punktem stałym.

Analogicznie wykażemy istnienie najmniejszego punktu stałego. Niech . Pokażemy, że jest najmniejszym punktem stałym. Z monotoniczności mamy dla każdego

skąd otrzymujemy

wobec czego . Przekształcając obie strony ostatniego równania przez , dzięki monotoniczności tej fukcji, otrzymamy

skąd wynika, że . Ponieważ jest podzbiorem każdego elementu , więc również . Stąd i z równania 7.2 otrzymujemy . Oznacza to, że jest punktem stałym funkcji . Ponieważ wszystkie punkty stałe należą do zbioru , to jest najmniejszym punktem stałym.

End of proof.gif

Przykład 7.7.

Niech będzie zbiorem induktywnym (czyli takim, którego istnienie jest gwarantowane przez aksjomat nieskończoności). Zdefiniujmy funkcję w następujący sposób. Dla dowolnego niech

Zwróćmy uwagę, że dzięki temu, że zbiór jest induktywny. Z definicji łatwo wynika, że funkcja jest monotoniczna. Wobec tego z twierdzenia 7.6 (patrz twiedzenie 7.6.) wynika, że ma najmniejszy i największy punkt stały. Zauważmy, że z definicji funkcji wynika, że każdy punkt stały tej funkcji jest zbiorem induktywnym. Największy punkt stały łatwo wskazać, gdyż jest to cały zbiór . Znacznie ciekawszy jest najmniejszy punkt stały, nazwijmy go . Jest to najmniejszy zbiór induktywny będący podzbiorem . W wykładzie 7 dotyczącym liczb naturalnych pokażemy, że zbiór jest również podzbiorem każdego innego zbioru induktywnego (dociekliwi mogą spróbować udowodnić to już teraz).

Ćwiczenie 7.4

{{{3}}}

Ćwiczenie 7.5

Niech będzie zdefiniowana tak, że dla każdego

Czyli funkcja przekształca rodziny zbiorów liczb w rodziny zbiorów liczb. Udowodnij, że funkcja jest monotoniczna. Co jest najmniejszym punktem stałym funkcji ? Czy jest elementem tego punktu stałego?

Rozwiązanie

Lemat Banacha

Stefan Banach (1892-1945)
Zobacz biografię

Twierdzenie Knastra-Tarskiego posłuży nam do udowodnienia lematu

Banacha, który z kolei wykorzystamy w wykładzie 9 dotyczącym teorii mocy.

Twierdzenie 7.8.

Dla dowolnych zbiorów oraz funkcji i istnieją zbiory oraz takie, że:

1. jest podziałem zbioru ,
2. jest podziałem zbioru ,
3. ,
4. .
Rysunek 6.2.

Dowód

Rozważmy funkcję zdefiniowaną następująco. Dla dowolnego niech

Pokażemy najpierw, że jest monotoniczna. Weźmy dowolne zbiory takie, że . Wtedy

więc

a więc .

Skoro jest monotoniczna, to na mocy twierdzenia 7.6 (patrz twierdzenie 7.6.) Knastra-Tarskiego posiada najmniejszy punkt stały. Oznaczmy go przez . Zdefiniujemy teraz pozostałe zbiory z tezy twierdzenia. Niech:

Z definicji zbiorów natychmiast wynika, że zbiory oraz tworzą odpowiednio podziały zbiorów i . Również z definicji spełniony jest punkt trzeci tezy (czyli ). Pozostaje pokazać, że zachodzi punkt czwarty. Skoro jest punktem stałym funkcji , to

Podstawiając kolejno w powyższym wzorze zdefiniowane zbiory, otrzymujemy:

Odejmując obie strony od , otrzymamy:

Ponieważ jednak lewa strona w powyższej równości jest z definicji równa , to otrzymujemy:

Wobec tego zdefiniowane zbiory spełniają wszystkie własności postulowane w tezie twierdzenia.

End of proof.gif