6. Kwantyfikatory

Kwantyfikatory to określenia ilościowe dotyczące liczby obiektów jakiegoś typu. Na przykład niech $X$ oznacza zbiór Polaków, zaś $\varphi(x),x\in X$ funkcję zdaniową ``$x$ jest praworęczny''. Rozważmy zdanie:

$(*)$

Każdy Polak jest praworęczny.

Możemy to zdanie przepisać w sposób częściowo symboliczny:

Dla każdego $x\in X$, $x$ jest praworęczny.

W rachunku zdań zastępowaliśmy spójniki języka potocznego przez pewne symbole. W rachunku kwantyfikatorów zwrot ``dla każdego '' zapisujemy symbolicznie w postaci $\forall$. Zdanie $(*)$ możemy więc zapisać w postaci

$$(**) (\forall x\in X)\varphi(x).$$

Zdanie to jest równoważne temu, że wykres funkcji zdaniowej $\varphi(x)$ to cały zbiór $X$, tzn.

$$\{x\in X:\varphi(x)\}=X.$$

Zdanie $(**)$ możemy odczytywać na wiele równoważnych sposobów:

1. Dla każdego $x\in X$, $\varphi(x)$ .
2. Dla dowolnego $x\in X$, $\varphi(x)$.
3. Dla wszystkich $x\in X$, $\varphi(x)$.
4. Wszystkie $x\in X$ mają własność $\varphi(x)$.
5. Każdy $x\in X$ spełnia $\varphi(x)$.
6. $\varphi(x)$ dla wszystkich $x\in X$.

Symbol $\forall$ nazywamy dużym kwantyfikatorem (lub kwantyfikatorem ogólnym, uniwersalnym)^6.1. Ogólnie, dla dowolnej funkcji zdaniowej $\varphi(x),x\in X$ zapis $(**)$ odczytujemy na dowolny z powyższych sposobów. Oznacza on zawsze, że $\{x\in X:\varphi(x)\}=X$.

Rozważmy teraz zdanie

$(\dagger)$

Pewien Polak jest praworęczny.

Oznaczając znów przez $X$ zbiór Polaków i używając $\varphi(x)$ na oznaczenie funkcji zdaniowej ``$x$ jest praworęczny'' możemy zdanie to zapisać w postaci

Istnieje $x\in X$ taki, że $\varphi(x)$.

Zwrot ``istnieje'' zapisujemy symbolicznie w postaci $\exists$. Zatem zdanie $(\dagger)$ możemy zapisać symbolicznie jako

$$(\ddagger) (\exists x\in X)\varphi(x).$$

Zdanie to jest równoważne temu, że wykres funkcji zdaniowej $\varphi(x)$ jest niepusty, tzn.

$$\{x\in X:\varphi(x)\}\neq\emptyset.$$

Zdanie $(\ddagger)$ możemy odczytywać na wiele równoważnych sposobów:

1. Istnieje $x\in X$ takie, że $\varphi(x)$.
2. Dla pewnego $x\in X$ mamy $\varphi(x)$.
3. Jakieś $x\in X$ spełnia $\varphi(x)$.
4. $\varphi(x)$ dla pewnego $x\in X$.

Symbol $\exists$ nazywamy małym kwantyfikatorem (lub kwantyfikatorem egzystencjalnym)^6.2. Ogólnie, dla dowolnej funkcji zdaniowej $\varphi(x),x\in X$ zapis $(\ddagger)$ odczytujemy na dowolny z powyższych sposobów. Oznacza on zawsze, że $\{x\in X:\varphi(x)\}\neq\emptyset$.

Zbiór $X$ w wyrażeniach $(**)$ i $(\ddagger)$ nazywamy zakresem kwantyfikatora. Gdy jest on znany z kontekstu, można pomijać fragment ``$\in X$'' w $(**)$ i $(\ddagger)$, pisząc odpowiednio

$$\forall x \varphi(x)\mbox{ i }\exists x \varphi(x).$$

Używając kwantyfikatorów wiele matematycznych zdań możemy zapisać w przejrzystej formie. Na przykład zdanie

$$\exists x(x^2+x-1=0)$$

mówi, że ``równanie $x^2+x-1=0$ ma rozwiązanie''. Fakt, że $A$ zawiera się w $B$, możemy zapisać w postaci

$$\forall x(x\in A\Rightarrow x\in B),$$

zaś to, że zbiory $A$ i $B$ nie są rozłączne, znaczy, że

$$\exists x(x\in A\land x\in B).$$

W przypadku kwantyfikowania po zbiorze skończonym mały kwantyfikator możemy zastąpić przez kilkukrotną alternatywę, zaś duży kwantyfikator przez kilkukrotną koniunkcję. Załóżmy mianowicie, że rozważamy funkcję zdaniową $\varphi(x),x\in X$, gdzie $X=\{a_1,\dots,a_n\}$ jest zbiorem skończonym. Wówczas zdanie $\exists x\varphi(x)$ jest równoważne

$$\varphi(a_1)\lor\varphi(a_2)\lor\dots\lor\varphi(a_n),$$

zaś zdanie $\forall x\varphi(x)$ jest równoważne

$$\varphi(a_1)\land\varphi(a_2)\land\dots\land\varphi(a_n).$$

W matematyce używa się też często tak zwanych kwantyfikatorów ograniczonych (inaczej: zrelatywizowanych).

Przykład 1. Zdanie ``Jeśli liczba rzeczywista $x$ jest $\geq 5$, to $x^2\geq 5x$'' w formie symbolicznej ma postać

$$\forall x(x\geq 5\Rightarrow x^2\geq 5x),$$

gdzie zakres kwantyfikatora to zbiór liczb rzeczywistych. Możemy je jednak również wyrazić mówiąc: ``Dla każdej liczby rzeczywistej $x$ większej lub równej $5$ mamy $x^2\geq 5x$'', co w formie symbolicznej ma postać:

$$(\forall x\geq 5)(x^2\geq 5x).$$

W wyrażeniu tym zakres kwantyfikatora jest ograniczony do liczb rzeczywistych $\geq 5$, dlatego nazywamy go tu kwantyfikatorem ograniczonym (zrelatywizowanym).

Podobnie dla funkcji zdaniowej $\varphi(x),x\in X$ i zbioru $A\subseteq X$ zdanie

$$\forall x(x\in A\Rightarrow\varphi(x))$$

czytamy ``Dla każdego $x$, jeśli $x\in A$, to $\varphi(x)$''. Jest ono równoważne temu, że $\{x\in A:\varphi(x)\}=A$. Zatem równoważnie możemy wyrazić to zdanie mówiąc: ``Dla każdego $x\in A$ mamy $\varphi(x)$''. W formie symbolicznej zdanie to ma postać

$$(\forall x\in A)\varphi(x),$$

zakres kwantyfikatora został tu ograniczony do zbioru $A$.

Przykład 2. Rozważmy zdanie ``Istnieje liczba rzeczywista $x$ taka, że $x<5$ i $x^2>3x$''. Symbolicznie zdanie to ma postać

$$\exists x(x<5\land x^2>3x).$$

Możemy jednak wysłowić je mówiąc: ``Istnieje liczba $x$ mniejsza od $5$, taka że $x^2>3x$''. Symbolicznie zapisujemy to w postaci:

$$(\exists x<5)(x^2>3x).$$

Znów zakres kwantyfikatora, ktory początkowo był równy $\mathbb{R}$, został tu ograniczony do liczb rzeczywistych $<5$.

Podobnie, gdy mamy funkcję zdaniową $\varphi(x),x\in X$ i $A\subseteq X$, zdanie

$$\exists x(x\in A\land \varphi(x))$$

jest równoważne temu, że $\{x\in A:\varphi(x)\}\neq\emptyset$. Możemy więc zapisać je w formie

$$(\exists x\in A)\varphi(x).$$

Zakres kwantyfikatora, który początkowo był równy $X$, jest tu ograniczony do zbioru $A$.

Warto podkreślić, że relatywizacja dużego kwantyfikatora odpowiada ``schowaniu'' poprzednika implikacji, zaś relatywizacja małego kwantyfikatora odpowiada ``schowaniu'' pierwszego członu koniunkcji, i tylko w takich przypadkach mogą być one dokonane. Formalnie rzecz biorąc, każda z form zapisu (zrelatywizowana lub nie) jest równie dobra, wybór formy jest więc kwestią smaku. W miarę potrzeby można przechodzić od jednej formy zapisu do drugiej. Kwantyfikatory ograniczone zazwyczaj ujmujemy w nawiasy.

Jako kolejny przykład zauważmy, że w zrelatywizowanej formie zdanie $\forall x(x\in A\Rightarrow x\in B)$ ma postać $(\forall x\in A)(x\in B)$. Podobnie zdanie $\exists x(x\in A\land x\in B)$ w postaci zrelatywizowanej można zapisać na dwa sposoby: $(\exists x\in A)(x\in B)$ i $(\exists x\in B)(x\in A)$. (W obu tych przykładach zakładamy, że zbiory $A$ i $B$ są podzbiorami jednej przestrzeni $X$, która jest zakresem kwantyfikatorów w postaci niezrelatywizowanej.)

Możemy również kwantyfikować funkcje zdaniowe większej liczby zmiennych. Rozważmy funkcję zdaniową $\varphi(x,y),x\in X,y\in Y$. Wówczas możemy utworzyć nowe funkcje zdaniowe:

``dla każdego $x\in X, \varphi(x,y)$'' oraz ``istnieje $x\in X$ takie, że $\varphi(x,y)$''.

W formie symbolicznej zapisujemy je następująco:

$$(\dagger\dagger) (\forall x\in X)\varphi(x,y)\mbox{ oraz\ }(\exists x\in X)\varphi(x,y).$$

Są to funkcje zdaniowe zmiennej $y$ o zakresie $Y$. Zmienna $x$ została tu ``związana'' przez kwantyfikatory $\forall x$ i $\exists x$. Gdy zakres kwantyfikatorów jest znany z kontekstu, możemy pomijać fragment ``$\in X$'' w $(\dagger\dagger)$, pisząc $\forall x\varphi(x,y)$ i $\exists x\varphi(x,y)$.

Niech $A\subseteq X\times Y$ będzie wykresem funkcji zdaniowej $\varphi(x,y),x\in X,y\in Y$. Widzimy, że

$$\pi_X[A]=\{x\in X:(\exists y\in Y)\langle x,y\rangle\in A\}=\{x\in X:(\exists y\in Y)\varphi(x,y)\},$$

$$\pi_Y[A]=\{y\in Y:(\exists x\in X)\langle x,y\rangle\in A\}=\{y\in Y:(\exists x\in X)\varphi(x,y)\}.$$

Dla dowolnych $a\in X,b\in Y$ mamy też

$$(\forall y\in Y)\varphi(a,y)\Leftrightarrow A_a=Y, (\exists y\in Y)\varphi(a,y)\Leftrightarrow A_a\neq\emptyset,$$

$$(\forall x\in X)\varphi(x,b)\Leftrightarrow A^b=X, (\exists x\in X)\varphi(x,b)\Leftrightarrow A^b\neq\emptyset.$$

Przy pomocy cięć pionowych zbioru $A$ możemy więc zinterpretować zdania typu $(\forall x\in X)(\exists y\in Y)\varphi(x,y)$.

$$(\forall x\in X)(\forall y\in Y)\varphi(x,y)\Leftrightarrow\mbox{ każde cięcie pionowe zbioru $A$ jest całym $Y$.}$$

$$(\forall x\in X)(\exists y\in Y)\varphi(x,y)\Leftrightarrow\mbox{ każde cięcie pionowe zbioru $A$ jest niepuste.}$$

$$(\exists x\in X)(\forall y\in Y)\varphi(x,y)\Leftrightarrow\mbox{ pewne cięcie pionowe zbioru $A$ jest całym $Y$.}$$

$$(\exists x\in X)(\exists y\in Y)\varphi(x,y)\Leftrightarrow\mbox{ pewne cięcie pionowe zbioru $A$ jest niepuste.}$$

Podobnie przy pomocy cięć poziomych zbioru $A$ interpretujemy zdania

$$(\forall y\in Y)(\forall x\in X)\varphi(x,y), (\forall y\in Y)(\exists x\in X)\varphi(x,y),$$

$$(\exists y\in Y)(\forall x\in X)\varphi(x,y), (\exists y\in Y)(\exists x\in X)\varphi(x,y).$$

Rozważymy teraz kilka przykładów z języka potocznego. Niestety, zarówno w języku potocznym, jak i w matematyce, by sformalizować zdanie przy pomocy kwantyfikatorów, trzeba je często najpierw przeformułować.

Przykład 1. Sformalizujemy zdanie: ``Każdy kij ma przynajmniej dwa końce''. Niech mianowicie $X$ oznacza zbiór kijów, $Y$ zbiór końców, zaś $\varphi(x,y),x\in X,y\in Y,$ funkcję zdaniową: ``$y$ jest końcem $x$''. Nasze zdanie możemy wysłowić mówiąc:

Dla każdego kija $x$ istnieją końce $y,z$ takie, że $y$ jest końcem $x$ i $z$ jest końcem $x$ i $y\neq z$.

Symbolicznie nasze zdanie ma postać:

$$(\forall x\in X)(\exists y\in Y)(\exists z\in Y)(\varphi(x,y)\land\varphi(x,z)\land y\neq z).$$

Zapis $y\neq z$ jest skrótem dla $\neg(y=z)$.

Przykład 2. Sformalizujemy zdanie: ``Każdy dudek ma swój czubek''. Niech $X$ oznacza zbiór dudków, $Y$ zbiór czubków, zaś $\varphi(x,y),x\in X,y\in Y,$ funkcję zdaniową: ``$x$ ma $y$''. Nasze zdanie możemy przeformułować następująco:

Dla każdego dudka $x$ istnieje czubek $y$ taki, że $x$ ma $y$.

W formie symbolicznej nasze zdanie ma postać

$$(\forall x\in X)(\exists y\in Y)\varphi(x,y).$$

W tym miejscu zwróćmy uwagę, że zdanie z kwantyfikatorami w zmienionej kolejności:

$$(\exists y\in Y)(\forall x\in X)\varphi(x,y)$$

odczytujemy jako:

Istnieje taki czubek, że każdy dudek go ma.

co jest jawnym fałszem. Widzimy więc, że ogólnie zdania

$$\forall x\exists y\varphi(x,y)\mbox{ i }\exists y\forall x\varphi(x,y)$$

nie są równoważne, to znaczy kwantyfikatory $\forall$ i $\exists$ nie są przemienne.

Przykład 3. Sformalizujemy zdanie: ``Nie wszystko złoto, co się świeci''. Niech $X$ oznacza zbiór rzeczy, $\varphi(x),x\in X$, funkcję zdaniową ``$x$ jest złote'', zaś $\psi(x),x\in X$ funkcję zdaniową ``$x$ się świeci''. Nasze zdanie możemy przeformułować w postaci: ``Nieprawda, że każda rzecz $x$, która się świeci, jest złota.'', czy też inaczej: ``Nieprawda, że dla każdej rzeczy $x$, jeśli $x$ się świeci, to $x$ jest złota.'' Zatem nasze zdanie ma postać symboliczną:

$$\neg\forall x(\psi(x)\Rightarrow\varphi(x)).$$

Formalizacja zdań matematycznych przy pomocy spójników logicznych i kwantyfikatorów nie jest celem samym w sobie. Warto ją stosować, gdy rozjaśnia znaczenie matematycznego zdania lub upraszcza jego zapis. Gdy jednak zdanie jest wystarczająco jasne w potocznym języku matematycznym, nie należy ulegać manierze zastępowania w nim zwyczajnych słów (takich jak ``i'', ''lub'', ``dla każdego'') przez sztuczne znaczki ( $\land,\lor,\forall$).