Logika, zbiory, relacje i odwzorowania

Streszczenie

Fundament całej analizy: rachunek zdań i spójniki logiczne, kwantyfikatory i ich negacja, algebra zbiorów z prawami De Morgana, iloczyn kartezjański i zbiór potęgowy, relacje (równoważności i porządku) oraz odwzorowania — iniekcja, surjekcja, bijekcja, złożenie, funkcja odwrotna i moc zbioru aż po twierdzenie Cantora. Każde pojęcie z osobnym, profesjonalnym rysunkiem.

Zanim policzymy pierwszą granicę czy pochodną, musimy ustalić język, w którym mówimy o obiektach matematycznych. Tym językiem są logika i teoria mnogości: zdania i spójniki, kwantyfikatory, zbiory, relacje i odwzorowania. To nie jest tylko formalny rytuał — precyzyjne pojęcie funkcji, dziedziny, przeciwobrazu czy mocy zbioru wraca w analizie na każdym kroku, a w ekonometrii decyduje o tym, czy model jest dobrze postawiony. Ten rozdział buduje cały ten aparat od podstaw, z osobnym rysunkiem do każdej definicji, twierdzenia i przykładu.

Rachunek zdań

Istota logiki matematycznej.

Logika matematyczna nie zajmuje się tym, o czym mówimy, lecz jak łączymy w całość proste stwierdzenia i kiedy wniosek jest prawdziwy niezależnie od treści. Dzięki temu dowód da się sprawdzić mechanicznie: poprawność rozumowania wynika z jego kształtu, a nie z naszej intuicji co do faktów.

Definicja

Zdanie logiczne

Zdaniem logicznym nazywamy wypowiedź, której można jednoznacznie przypisać jedną z dwóch wartości logicznych: prawdę (oznaczaną $1$ lub P) albo fałsz ($0$ lub F). Wypowiedzi nierozstrzygalne, pytania i rozkazy zdaniami logicznymi nie są.

Odwzorowanie zdań w zbiór wartości logicznych zero-jeden — Zdanie logiczne to obiekt, który funkcja wartościowania odwzorowuje w dwuelementowy zbiór $\{0,1\}$. „$2+2=4$” trafia w $1$, „$2+2=5$” w $0$, a „która godzina?” nie jest zdaniem logicznym.

Spójniki logiczne

Ze zdań prostych $p, q$ budujemy zdania złożone za pomocą spójników. Każdy spójnik jest w pełni opisany przez tabelę prawdy — przepis, jaką wartość ma zdanie złożone przy każdej kombinacji wartości składników.

Definicja

Pięć podstawowych spójników

Negacja $\lnot p$ („nieprawda, że $p$”) — odwraca wartość logiczną.
Koniunkcja $p \land q$ („$p$ i $q$”) — prawdziwa tylko, gdy oba człony są prawdziwe.
Alternatywa $p \lor q$ („$p$ lub $q$”) — fałszywa tylko, gdy oba człony są fałszywe.
Implikacja $p \Rightarrow q$ („jeśli $p$, to $q$”) — fałszywa tylko w jednym przypadku: prawdziwy poprzednik, fałszywy następnik.
Równoważność $p \Leftrightarrow q$ („$p$ wtedy i tylko wtedy, gdy $q$”) — prawdziwa, gdy oba człony mają tę samą wartość.

Tabela prawdy negacji, koniunkcji, alternatywy, implikacji i równoważności — Tabela prawdy pięciu spójników. Czarne pole oznacza prawdę ($1$), białe — fałsz ($0$). Implikacja jest fałszywa **tylko** w wierszu $p=1,\ q=0$; to najczęstsze źródło nieporozumień.

Implikacja: warunek konieczny i wystarczający.

W zdaniu $p \Rightarrow q$ poprzednik $p$ jest warunkiem wystarczającym dla $q$ (wystarczy $p$, by zaszło $q$), a następnik $q$ — warunkiem koniecznym dla $p$ (bez $q$ nie ma $p$). Implikacja o prawdziwym poprzedniku i fałszywym następniku jest jedyną fałszywą; gdy poprzednik jest fałszywy, całość jest prawdziwa „pusto” (ex falso quodlibet).

Implikacja przedstawiona jako zawieranie zbioru sytuacji p w zbiorze sytuacji q — Implikacja $p \Rightarrow q$ jako zawieranie sytuacji: każdy przypadek, w którym zachodzi $p$, mieści się wśród przypadków, w których zachodzi $q$. Stąd $p$ „wystarcza” dla $q$, a $q$ jest „konieczne” dla $p$.

Tautologie i prawa De Morgana

Tautologia to zdanie złożone prawdziwe przy każdym wartościowaniu zmiennych. Tautologie to „prawa logiki” — schematy poprawnego rozumowania. Najważniejsze z nich to prawa De Morgana, które mówią, jak negacja przechodzi przez koniunkcję i alternatywę.

Twierdzenie

Prawa De Morgana dla zdań

Dla dowolnych zdań $p, q$ następujące równoważności są tautologiami:

$$ \lnot(p \land q) \;\Leftrightarrow\; (\lnot p \lor \lnot q), \qquad \lnot(p \lor q) \;\Leftrightarrow\; (\lnot p \land \lnot q). $$

Dowód

Prawa De Morgana dla zdań

Metoda. Zdanie o dwóch zmiennych $p,q$ ma cztery możliwe wartościowania. Wystarczy sprawdzić, że w każdym z nich obie strony równoważności mają tę samą wartość logiczną — wtedy równoważność jest prawdziwa zawsze, czyli jest tautologią.
Pierwsze prawo. $\lnot(p\land q)$ jest fałszywe dokładnie wtedy, gdy $p\land q$ jest prawdziwe, czyli gdy $p=1$ i $q=1$. Z drugiej strony $\lnot p \lor \lnot q$ jest fałszywe dokładnie wtedy, gdy oba człony są fałszywe, czyli $\lnot p = 0$ i $\lnot q = 0$, to znaczy $p=1$ i $q=1$. Obie strony są więc fałszywe w tym samym, jedynym przypadku, a w pozostałych trzech prawdziwe — mają identyczne kolumny w tabeli prawdy.
Drugie prawo. $\lnot(p\lor q)$ jest prawdziwe dokładnie wtedy, gdy $p\lor q$ jest fałszywe, czyli $p=0$ i $q=0$. Tymczasem $\lnot p \land \lnot q$ jest prawdziwe dokładnie wtedy, gdy $\lnot p = 1$ i $\lnot q = 1$, to jest $p=0$ i $q=0$. Znów zgodność we wszystkich czterech wierszach.
Wniosek. Obie równoważności są prawdziwe przy każdym wartościowaniu, są więc tautologiami. $\;$

∎

Graficzna ilustracja praw De Morgana na dwóch nakładających się obszarach — Prawo De Morgana w wersji zbiorowej: zaprzeczenie koniunkcji (część wspólna) to alternatywa zaprzeczeń (suma uzupełnień). Zacieniony obszar po lewej — dopełnienie części wspólnej — pokrywa się z sumą dopełnień po prawej.

Kwantyfikatory

Logika zdań nie wystarcza, gdy mówimy o wszystkich lub niektórych obiektach z pewnego zbioru. Wprowadzamy formy zdaniowe $\varphi(x)$ — wypowiedzi z parametrem $x$, które stają się zdaniami dopiero po podstawieniu konkretnej wartości — oraz dwa kwantyfikatory wiążące parametr.

Definicja

Kwantyfikator ogólny i szczegółowy

Niech $\varphi(x)$ będzie formą zdaniową określoną dla $x$ z pewnego zbioru $X$.

Kwantyfikator ogólny $\;\forall_{x\in X}\,\varphi(x)\;$ czytamy „dla każdego $x$ z $X$ zachodzi $\varphi(x)$”. Jest prawdziwy, gdy $\varphi(x)$ zachodzi bez wyjątku.
Kwantyfikator szczegółowy $\;\exists_{x\in X}\,\varphi(x)\;$ czytamy „istnieje $x$ z $X$, dla którego zachodzi $\varphi(x)$”. Jest prawdziwy, gdy znajdzie się choć jeden taki $x$.

Wykres funkcji nieujemnej ilustrujący kwantyfikator ogólny — Kwantyfikator ogólny: zdanie $\forall_{x}\;f(x)\ge 0$ jest prawdziwe, bo **cały** wykres leży nad osią — nie ma ani jednego punktu poniżej.

Wykres funkcji z miejscem zerowym ilustrujący kwantyfikator szczegółowy — Kwantyfikator szczegółowy: zdanie $\exists_{x}\;g(x)=0$ jest prawdziwe, bo **istnieje** punkt, w którym wykres przecina oś. Wystarczy jedno takie miejsce zaznaczone kropką.

Przykład

Prawda a fałsz pod kwantyfikatorem

W zbiorze liczb rzeczywistych:

$$ \forall_{x\in\mathbb{R}}\; x^2 \ge 0 \quad\text{(prawda)}, \qquad \exists_{x\in\mathbb{R}}\; x^2 = 2 \quad\text{(prawda, } x=\pm\sqrt 2\text{)}, $$

ale $\;\forall_{x\in\mathbb{R}}\; x^2 = 2\;$ jest fałszem, bo już dla $x=0$ równość nie zachodzi. Kolejność kwantyfikatorów też ma znaczenie: $\forall_{x}\exists_{y}\;y \gt x$ jest prawdą (do każdego $x$ dobierzemy większe $y$), lecz $\exists_{y}\forall_{x}\;y \gt x$ jest fałszem (nie ma liczby większej od wszystkich).

Ilustracja wpływu kolejności kwantyfikatorów na prawdziwość zdania — Zamiana kolejności kwantyfikatorów zmienia sens. Po lewej $\forall_{x}\,\exists_{y}\;y \gt x$: dla każdego $x$ dobieramy zależne od niego $y$. Po prawej żądamy jednego $y$ dobrego dla wszystkich $x$ — taki nie istnieje.

Twierdzenie

Prawa De Morgana dla kwantyfikatorów

Zaprzeczenie kwantyfikatora ogólnego jest kwantyfikatorem szczegółowym zaprzeczenia i odwrotnie:

$$ \lnot\,\forall_{x\in X}\,\varphi(x) \;\Leftrightarrow\; \exists_{x\in X}\,\lnot\varphi(x), \qquad \lnot\,\exists_{x\in X}\,\varphi(x) \;\Leftrightarrow\; \forall_{x\in X}\,\lnot\varphi(x). $$

Dowód

Prawa De Morgana dla kwantyfikatorów

Pierwsza równoważność, w prawo. Załóżmy, że $\lnot\,\forall_{x}\,\varphi(x)$. To znaczy: nieprawda, że $\varphi$ zachodzi dla wszystkich $x$. Gdyby dla każdego $x$ zachodziło $\varphi(x)$, kwantyfikator ogólny byłby prawdziwy — sprzeczność. Zatem dla pewnego $x_0$ zachodzi $\lnot\varphi(x_0)$, czyli $\exists_{x}\,\lnot\varphi(x)$.
Pierwsza równoważność, w lewo. Załóżmy $\exists_{x}\,\lnot\varphi(x)$, czyli istnieje $x_0$ z $\lnot\varphi(x_0)$. Wtedy nie może być prawdą, że $\varphi$ zachodzi dla wszystkich $x$ (bo zawodzi w $x_0$), więc $\lnot\,\forall_{x}\,\varphi(x)$. Obie implikacje dają równoważność.
Druga równoważność. Wynika z pierwszej przez podstawienie $\varphi := \lnot\psi$ i skorzystanie z prawa podwójnej negacji $\lnot\lnot\psi \Leftrightarrow \psi$. Wówczas $\lnot\,\exists_{x}\,\psi(x)$ to to samo co $\lnot\,\exists_{x}\,\lnot\varphi(x)$, a stąd $\forall_{x}\,\varphi(x) = \forall_{x}\,\lnot\psi(x)$.
Reguła praktyczna. Przy zaprzeczaniu zdania z kwantyfikatorami zamieniamy każdy $\forall$ na $\exists$, każdy $\exists$ na $\forall$ i negujemy formę pod spodem. $\;$

∎

Schemat przejścia negacji przez kwantyfikatory — Schemat zaprzeczania: negacja „przechodzi przez” łańcuch kwantyfikatorów, zamieniając $\forall \leftrightarrow \exists$, aż dotrze do formy zdaniowej, którą neguje. Tu na przykładzie zdania o ciągłości.

Zbiory i działania na nich

Definicja

Zbiór, element, należenie

Zbiór to kolekcja rozróżnialnych obiektów, zwanych jego elementami. Fakt, że $a$ jest elementem zbioru $A$, zapisujemy $a \in A$; w przeciwnym razie $a \notin A$. Zbiór jest wyznaczony przez swoje elementy (zasada ekstensjonalności): dwa zbiory są równe wtedy i tylko wtedy, gdy mają te same elementy. Zbiór bez elementów to zbiór pusty $\varnothing$.

Zbiór jako obszar z elementami należącymi i nienależącymi — Zbiór $A=\{2,4,6,8\}$ jako worek elementów. $4\in A$ (kropka wewnątrz), ale $5\notin A$ (kropka na zewnątrz). O zbiorze decyduje wyłącznie to, co do niego należy.

Definicja

Zawieranie (podzbiór)

Mówimy, że $A$ jest podzbiorem $B$ (zawiera się w $B$), i piszemy $A \subseteq B$, gdy każdy element $A$ jest też elementem $B$:

$$ A \subseteq B \;\;\stackrel{\text{def}}{\Longleftrightarrow}\;\; \forall_{x}\,(x \in A \Rightarrow x \in B). $$

Jeżeli dodatkowo $A \ne B$, mówimy o podzbiorze właściwym $A \subsetneq B$. Zbiór pusty jest podzbiorem każdego zbioru.

Diagram Venna podzbioru A zawartego w B — Zawieranie $A\subseteq B$: cały obszar $A$ leży wewnątrz $B$. Każdy element $A$ jest automatycznie elementem $B$, lecz nie odwrotnie.

Z dwóch zbiorów tworzymy nowe za pomocą czterech podstawowych działań. Wszystkie odczytujemy z diagramów Venna.

Definicja

Suma, przekrój, różnica, dopełnienie

Dla zbiorów $A, B$ zawartych w pewnej przestrzeni $U$:

Suma $A \cup B = \{x : x \in A \lor x \in B\}$ — elementy należące do co najmniej jednego.
Przekrój (iloczyn) $A \cap B = \{x : x \in A \land x \in B\}$ — elementy wspólne.
Różnica $A \setminus B = \{x : x \in A \land x \notin B\}$ — w $A$, ale nie w $B$.
Dopełnienie $A' = U \setminus A = \{x \in U : x \notin A\}$ — wszystko poza $A$.

Diagram Venna sumy zbiorów A i B — Suma $A\cup B$: zacieniony jest **cały** obszar objęty którymkolwiek z kół. Element wpada do sumy, gdy należy do $A$ lub do $B$ (lub do obu).

Diagram Venna przekroju zbiorów A i B — Przekrój $A\cap B$: zacieniona tylko **część wspólna** obu kół — elementy należące jednocześnie do $A$ i do $B$.

Diagram Venna różnicy zbiorów A bez B — Różnica $A\setminus B$: zacieniona część $A$ leżąca **poza** $B$. Usuwamy z $A$ wszystko, co wpada również do $B$.

Diagram Venna dopełnienia zbioru A w przestrzeni U — Dopełnienie $A'$: zacieniona cała przestrzeń $U$ **poza** $A$. To, czego brakuje $A$ do pełnego prostokąta.

Twierdzenie

Prawa De Morgana dla zbiorów

Dla dowolnych $A, B \subseteq U$:

$$ (A \cup B)' = A' \cap B', \qquad (A \cap B)' = A' \cup B'. $$

Dopełnienie sumy jest przekrojem dopełnień, a dopełnienie przekroju — sumą dopełnień.

Dowód

Pierwsze prawo De Morgana dla zbiorów: $(A\cup B)' = A'\cap B'$

Strategia. Równość zbiorów dowodzimy przez **podwójne zawieranie**: pokazujemy $(A\cup B)' \subseteq A'\cap B'$ oraz $A'\cap B' \subseteq (A\cup B)'$. Tu zrobimy to jednym ciągiem równoważności, co od razu daje obie inkluzje.
Przepisanie warunku. Weźmy dowolny $x \in U$. Wtedy $$ x \in (A\cup B)' \;\Leftrightarrow\; x \notin A\cup B \;\Leftrightarrow\; \lnot(x\in A \lor x\in B). $$
De Morgan dla zdań. Stosujemy udowodnione wcześniej prawo $\lnot(p\lor q)\Leftrightarrow(\lnot p\land\lnot q)$ do $p:\,x\in A$, $q:\,x\in B$: $$ \lnot(x\in A \lor x\in B) \;\Leftrightarrow\; (x\notin A \land x\notin B). $$
Powrót do zbiorów. Ostatni warunek to dokładnie $x\in A' \land x\in B'$, czyli $x\in A'\cap B'$. Łącząc kroki: dla każdego $x$ zachodzi $x\in(A\cup B)' \Leftrightarrow x\in A'\cap B'$, więc oba zbiory mają te same elementy i są równe.
Drugie prawo. Dowodzi się analogicznie, wychodząc od $\lnot(x\in A \land x\in B)$ i stosując pierwsze prawo De Morgana dla zdań. $\;$

∎

Diagram Venna prawa De Morgana dla zbiorów — Prawo $(A\cup B)' = A'\cap B'$ na diagramie: dopełnienie sumy (pole poza oboma kołami) to dokładnie część wspólna dopełnień. Zacieniony narożny obszar należy zarazem do $A'$ i do $B'$.

Iloczyn kartezjański i zbiór potęgowy

Definicja

Iloczyn kartezjański

Iloczynem kartezjańskim zbiorów $X$ i $Y$ nazywamy zbiór wszystkich par uporządkowanych:

$$ X \times Y = \{(x,y) : x \in X \;\land\; y \in Y\}. $$

Para uporządkowana spełnia $(x,y)=(x',y') \Leftrightarrow x=x' \land y=y'$ — kolejność jest istotna. Iloczyn $\mathbb{R}\times\mathbb{R}=\mathbb{R}^2$ to płaszczyzna, na której rysujemy wykresy.

Siatka punktów iloczynu kartezjańskiego trzech i dwóch elementów — Iloczyn kartezjański $X\times Y$ dla $X=\{1,2,3\}$, $Y=\{a,b\}$: każda para $(x,y)$ to jeden węzeł siatki. Łącznie $3\cdot 2 = 6$ par — moc iloczynu jest iloczynem mocy.

Definicja

Zbiór potęgowy

Zbiorem potęgowym zbioru $A$ nazywamy zbiór wszystkich jego podzbiorów:

$$ \mathcal{P}(A) = \{B : B \subseteq A\}. $$

Jeżeli $A$ ma $n$ elementów, to $\mathcal{P}(A)$ ma $2^n$ elementów: każdy element niezależnie albo bierzemy do podzbioru, albo nie.

Diagram Hassego zbioru potęgowego dwuelementowego zbioru — Zbiór potęgowy $\mathcal{P}(\{a,b\})$ jako diagram Hassego: cztery podzbiory ($\varnothing,\{a\},\{b\},\{a,b\}$) uporządkowane przez zawieranie. Krawędź w górę oznacza „jest podzbiorem” z dodaniem jednego elementu.

Relacje

Definicja

Relacja dwuargumentowa

Relacją (dwuargumentową) między zbiorami $X$ i $Y$ nazywamy dowolny podzbiór $R \subseteq X \times Y$. Zamiast $(x,y)\in R$ piszemy zwykle $x\,R\,y$ („$x$ jest w relacji $R$ z $y$”). Gdy $X=Y$, mówimy o relacji w zbiorze $X$.

Relacja jako podzbiór par iloczynu kartezjańskiego — Relacja $R$ jako wyróżniony podzbiór siatki $X\times Y$: zaznaczone węzły to pary należące do relacji. Tu $R=\{(1,a),(2,a),(3,b)\}$ — reszta par leży poza relacją.

Definicja

Własności relacji w zbiorze

Relacja $R$ w zbiorze $X$ jest:

zwrotna, gdy $\forall_{x}\; x\,R\,x$ (każdy element w relacji ze sobą),
symetryczna, gdy $\forall_{x,y}\;(x\,R\,y \Rightarrow y\,R\,x)$,
przechodnia, gdy $\forall_{x,y,z}\;(x\,R\,y \land y\,R\,z \Rightarrow x\,R\,z)$,
antysymetryczna, gdy $\forall_{x,y}\;(x\,R\,y \land y\,R\,x \Rightarrow x=y)$.

Grafy ilustrujące zwrotność, symetrię i przechodniość relacji — Trzy własności na grafie relacji (strzałka $x\to y$ znaczy $x\,R\,y$). **Zwrotność** — pętla przy każdym węźle; **symetria** — strzałki parami w obie strony; **przechodniość** — skrót domykający każdą dwukrokową ścieżkę.

Relacja równoważności

Definicja

Relacja równoważności i klasy abstrakcji

Relację zwrotną, symetryczną i przechodnią nazywamy relacją równoważności (oznaczaną często $\sim$). Dla elementu $a$ jego klasą abstrakcji jest zbiór wszystkich elementów z nim równoważnych:

$$ [a] = \{x \in X : x \sim a\}. $$

Twierdzenie

Zasada abstrakcji

Klasy abstrakcji relacji równoważności $\sim$ w zbiorze $X$ tworzą podział $X$: są niepuste, parami rozłączne, a ich suma daje całe $X$. Na odwrót, każdy podział $X$ wyznacza relację równoważności, której klasami są części podziału.

Dowód

Klasy abstrakcji tworzą podział

Niepustość. Ze zwrotności $a\sim a$, więc $a\in[a]$ — żadna klasa nie jest pusta.
Pokrycie. Każdy $a\in X$ należy do swojej klasy $[a]$, zatem suma wszystkich klas to całe $X$.
Rozłączność — klucz. Pokażemy, że jeśli dwie klasy mają wspólny element, to są identyczne. Niech $c\in[a]\cap[b]$, czyli $c\sim a$ i $c\sim b$. Z symetrii $a\sim c$, a z przechodniości i $c\sim b$ dostajemy $a\sim b$.
Wzajemne zawieranie. Weźmy $x\in[a]$, czyli $x\sim a$. Skoro $a\sim b$, to z przechodniości $x\sim b$, więc $x\in[b]$. Zatem $[a]\subseteq[b]$; przez symetrię argumentu $[b]\subseteq[a]$. Stąd $[a]=[b]$.
Wniosek. Dwie klasy są więc albo rozłączne, albo równe — nigdy „częściowo nachodzące”. To dokładnie definicja podziału. $\;$

∎

Podział liczb całkowitych na klasy reszt modulo trzy — Relacja przystawania modulo $3$ dzieli liczby całkowite na **trzy** klasy abstrakcji — reszty $0,1,2$ z dzielenia przez $3$. Klasy są rozłączne i wypełniają cały zbiór: to podział.

Relacja porządku

Definicja

Relacja porządku

Relację zwrotną, antysymetryczną i przechodnią nazywamy (częściowym) porządkiem (oznaczanym $\preceq$). Jeśli dodatkowo każde dwa elementy są porównywalne ($x\preceq y$ lub $y\preceq x$), porządek jest liniowy (totalny). Inaczej — częściowy: istnieją elementy nieporównywalne.

Przykład

Podzielność jako porządek częściowy

W zbiorze $\{1,2,3,4,6,12\}$ relacja „$a$ dzieli $b$” jest porządkiem częściowym. Jest zwrotna ($a\mid a$), antysymetryczna (jeśli $a\mid b$ i $b\mid a$ przy dodatnich, to $a=b$) i przechodnia. Nie jest liniowa: $2$ i $3$ są nieporównywalne — żadne nie dzieli drugiego.

Diagram Hassego relacji podzielności dzielników liczby dwanaście — Diagram Hassego podzielności w zbiorze dzielników $12$. Krawędź w górę = „dzieli i jest tuż poniżej”. $2$ i $3$ leżą obok siebie bez połączenia — są nieporównywalne, więc porządek jest tylko częściowy.

Odwzorowania (funkcje)

Definicja

Odwzorowanie

Odwzorowaniem (funkcją) ze zbioru $X$ w zbiór $Y$ nazywamy relację $f \subseteq X\times Y$, która każdemu $x\in X$ przypisuje dokładnie jeden $y\in Y$, oznaczany $f(x)$. Piszemy $f\colon X\to Y$. Zbiór $X$ to dziedzina, $Y$ — przeciwdziedzina, a $f(X)=\{f(x):x\in X\}$ — zbiór wartości (obraz).

Sednem są trzy „jakości” odwzorowań, opisujące, jak gęsto i jak jednoznacznie $f$ pokrywa przeciwdziedzinę.

Definicja

Iniekcja, surjekcja, bijekcja

Odwzorowanie $f\colon X\to Y$ jest:

iniekcją (różnowartościowe), gdy różne argumenty mają różne wartości: $x_1\ne x_2 \Rightarrow f(x_1)\ne f(x_2)$,
surjekcją („na”), gdy każdy element $Y$ jest wartością: $\forall_{y\in Y}\,\exists_{x\in X}\; f(x)=y$,
bijekcją, gdy jest jednocześnie iniekcją i surjekcją — wtedy ustanawia idealne „sparowanie” elementów $X$ i $Y$.

Diagram strzałkowy iniekcji — Iniekcja: różne argumenty trafiają w różne wartości (żadne dwie strzałki nie zbiegają się w jednym punkcie $Y$). Element $4$ w $Y$ pozostaje niewykorzystany — to dozwolone, iniekcja nie musi być „na”.

Diagram strzałkowy surjekcji — Surjekcja: każdy element $Y$ jest trafiony co najmniej raz (do $b$ prowadzą dwie strzałki). Pokrywamy całe $Y$, lecz kosztem różnowartościowości.

Diagram strzałkowy bijekcji — Bijekcja: dokładne sparowanie — każdy element $X$ ma jedną wartość, każdy element $Y$ jest trafiony dokładnie raz. Strzałki tworzą doskonałe „kojarzenie w pary”.

Złożenie i odwzorowanie odwrotne

Definicja

Złożenie odwzorowań

Dla $f\colon X\to Y$ i $g\colon Y\to Z$ złożeniem nazywamy odwzorowanie $g\circ f\colon X\to Z$ dane wzorem $(g\circ f)(x)=g\big(f(x)\big)$ — najpierw działa $f$, potem $g$.

Diagram złożenia dwóch odwzorowań — Złożenie $g\circ f$: argument przechodzi przez $f$ do $Y$, a stamtąd przez $g$ do $Z$. Cały proces to jedno odwzorowanie z $X$ wprost do $Z$ (strzałka łukowa).

Twierdzenie

Złożenie iniekcji jest iniekcją

Jeżeli $f\colon X\to Y$ i $g\colon Y\to Z$ są iniekcjami, to $g\circ f$ jest iniekcją. (Analogicznie złożenie surjekcji jest surjekcją, a złożenie bijekcji — bijekcją.)

Dowód

Złożenie iniekcji jest iniekcją

Cel. Pokazać, że z $(g\circ f)(x_1)=(g\circ f)(x_2)$ wynika $x_1=x_2$ (równoważna postać różnowartościowości).
Rozpisanie. Założenie znaczy $g\big(f(x_1)\big)=g\big(f(x_2)\big)$.
Iniektywność $g$. Skoro $g$ jest różnowartościowe, równość wartości wymusza równość argumentów: $f(x_1)=f(x_2)$.
Iniektywność $f$. Z tej samej zasady dla $f$ otrzymujemy $x_1=x_2$. Zatem $g\circ f$ jest iniekcją. $\;$

∎

Definicja

Odwzorowanie odwrotne

Jeżeli $f\colon X\to Y$ jest bijekcją, to istnieje dokładnie jedno odwzorowanie odwrotne $f^{-1}\colon Y\to X$ spełniające $f^{-1}\big(f(x)\big)=x$ oraz $f\big(f^{-1}(y)\big)=y$. Przypisuje ono każdej wartości jej jedyny argument.

Wykres funkcji i jej odwrotności jako odbicia względem prostej y równa się x — Funkcja $f(x)=2^x$ i jej odwrotność $f^{-1}(y)=\log_2 y$ są swoimi lustrzanymi odbiciami względem prostej $y=x$. Odwracalność jest możliwa dokładnie dlatego, że $f$ jest bijekcją.

Moc zbioru i twierdzenie Cantora

Bijekcja pozwala porównywać „liczebność” zbiorów także nieskończonych.

Definicja

Równoliczność i przeliczalność

Zbiory $A$ i $B$ są równoliczne ($|A|=|B|$), gdy istnieje bijekcja $A\to B$. Zbiór jest przeliczalny, gdy jest skończony albo równoliczny ze zbiorem liczb naturalnych $\mathbb{N}$ — czyli jego elementy da się ustawić w ciąg $a_1,a_2,a_3,\dots$.

Przykład

Liczby wymierne są przeliczalne

Choć między dowolnymi dwiema liczbami wymiernymi leży nieskończenie wiele innych, wszystkie liczby wymierne dodatnie da się ponumerować. Ustawiamy ułamki $\tfrac{p}{q}$ w nieskończoną tablicę ($p$ — wiersz, $q$ — kolumna) i obchodzimy ją po przekątnych, pomijając ułamki skracalne. Każdy ułamek prędzej czy później dostaje swój numer — więc $\mathbb{Q}$ jest przeliczalny.

Przekątniowe przeliczanie liczb wymiernych w tablicy ułamków — Przeliczanie ułamków metodą przekątniową Cantora: wężykiem po skośnych przechodzimy przez całą tablicę $\tfrac{p}{q}$, nadając kolejne numery. Skoro każdy ułamek zostaje osiągnięty, zbiór dodatnich liczb wymiernych jest przeliczalny.

Twierdzenie

Twierdzenie Cantora o nieprzeliczalności

Zbiór liczb rzeczywistych z przedziału $(0,1)$ nie jest przeliczalny. Nie istnieje bijekcja $\mathbb{N}\to(0,1)$ — nieskończoność continuum jest istotnie większa niż nieskończoność $\mathbb{N}$.

Dowód

Metoda przekątniowa Cantora

Dowód nie wprost. Przypuśćmy przeciwnie, że $(0,1)$ jest przeliczalny. Wtedy wszystkie jego liczby da się ustawić w ciąg $x_1,x_2,x_3,\dots$ obejmujący każdą z nich.
Zapis dziesiętny. Rozwińmy każdą liczbę dziesiętnie: $x_n = 0{,}d_{n1}d_{n2}d_{n3}\dots$, gdzie $d_{nk}$ to $k$-ta cyfra liczby $x_n$. (Ułamki o dwóch rozwinięciach, jak $0{,}4999\ldots = 0{,}5000\ldots$, ustalamy raz na zawsze, np. bez ogona dziewiątek.)
Budujemy „odstępcę”. Definiujemy liczbę $y=0{,}e_1e_2e_3\dots$, zmieniając przekątną: niech $e_k=5$, gdy $d_{kk}\ne 5$, oraz $e_k=4$, gdy $d_{kk}=5$. Każda cyfra $e_k$ różni się od $d_{kk}$ i jest spośród $\{4,5\}$, więc $y$ należy do $(0,1)$ i nie ma kłopotliwego ogona zer ani dziewiątek.
Sprzeczność. Dla każdego $n$ liczba $y$ różni się od $x_n$ na $n$-tej pozycji po przecinku ($e_n\ne d_{nn}$), więc $y\ne x_n$. Zatem $y\in(0,1)$ nie występuje w ciągu — wbrew założeniu, że ciąg obejmował wszystkie liczby z $(0,1)$.
Wniosek. Założenie o przeliczalności prowadzi do sprzeczności, więc $(0,1)$ jest nieprzeliczalny. Tym samym istnieją „różne nieskończoności”. $\;$

∎

Tablica rozwinięć dziesiętnych z zaznaczoną przekątną w dowodzie Cantora — Argument przekątniowy: z listy rzekomo **wszystkich** liczb z $(0,1)$ czytamy przekątną cyfr $d_{11},d_{22},d_{33},\dots$ i każdą zmieniamy. Powstała liczba $y$ różni się od $x_n$ na $n$-tym miejscu, więc nie ma jej na liście — sprzeczność.

Podsumowanie

Zbudowaliśmy język całej dalszej analizy. Logika dała nam spójniki, tautologie i dyscyplinę dowodu; kwantyfikatory — sposób mówienia o „wszystkich” i „pewnych” obiektach oraz mechaniczną regułę zaprzeczania (zamień $\forall\leftrightarrow\exists$ i zaneguj wnętrze), z której skorzystamy przy definicjach granic. Teoria mnogości dostarczyła zbiorów, działań i praw De Morgana, a iloczyn kartezjański jest sceną, na której żyją pary, wykresy i przestrzeń $\mathbb{R}^n$. Relacje dały nam równoważność (podział na klasy) i porządek (porównywanie), a odwzorowania — pojęcia iniekcji, surjekcji, bijekcji, złożenia i funkcji odwrotnej, którymi posługujemy się odtąd bez ustanku. Wreszcie bijekcja pozwoliła porównać nieskończoności: liczby wymierne są przeliczalne, lecz rzeczywiste — już nie. W następnym rozdziale na tym fundamencie zbudujemy przestrzenie metryczne, w których pojęcie odległości otworzy drogę do granic i ciągłości.