3. Funkcje zdaniowe i zbiory

Zbiór (inaczej zwany mnogością) to podstawowe pojęcie w matematyce. Przy jego pomocy można zdefiniować na gruncie teorii mnogości (zwanej też teorią zbiorów) wszystkie inne pojęcia matematyczne. Przyjmuje się, że jest to pojęcie pierwotne, tzn. nie wymagające definicji. Z drugiej strony matematycy w praktyce nadają temu pojęciu pewien określony intuicyjny sens. Intuicyjnie można powiedzieć, że zbiór jest to objęcie przez umysł pewnej liczby przedmiotów (materialnych lub duchowych), zwanych elementami tego zbioru. Tę nieformalną definicję podajemy dla wygody czytelnika, zastrzegając się jednak, że nie oddaje ona w pełni treści pojęcia zbioru. Jest tylko pewnym przybliżeniem.

Zazwyczaj zbiory oznaczamy dużymi literami, zaś ich elementy małymi literami. Gdy $x$ jest elementem zbioru $Z$, mówimy też, że $x$ należy do $Z$ i zapisujemy to zdanie symbolicznie w postaci:

$$x\in Z.$$

$\in$ nazywamy symbolem należenia do zbioru.

$$x\not\in Z$$

oznacza zdanie $\neg (x\in Z)$. Koniunkcję zdań postaci

$$x_1\in Z\land x_2\in Z\land\dots\land x_k\in Z$$

zapisujemy krócej w formie

$$x_1,\dots,x_k\in Z.$$

Przykłady zbiorów to zbiór uczniów w klasie, zbiór jabłek na drzewie, zbiór liczb rzeczywistych dodatnich. Przyjmujemy, że dwa zbiory, które mają te same elementy, są równe. Innymi słowy, dla dowolnych zbiorów $X,Y$ mamy

$$X=Y\Leftrightarrow (\mbox{dla wszystkich }x, x\in X\Leftrightarrow x\in Y).$$

Zasadniczo zbiory możemy określać na dwa sposoby.

Sposób 1. Określenie zbioru przez wypisanie jego elementów. Na przykład, zapis

$$Z=\{\mbox{Piotr, Jan, Ewa, Ala,}\dots\}$$

oznacza, że wszystkimi elementami zbioru $Z$ są Piotr, Jan, Ewa, Ala, $\dots$. W szczególności prawdą jest, że Piotr $\in Z$. Podobnie zapis

$$\{0,1,2,3\}$$

oznacza zbiór, którego wszystkie elementy to liczby $0,1,2,3$. $\{1\}$ oznacza zbiór, którego jedynym elementem jest liczba $1$. Należy tu podkreślić, że $1$ i $\{1\}$ to różne obiekty. Podobnie jabłko i zbiór jednoelementowy złożony z jabłka to dwa różne przedmioty. Najprościej wyjaśnić to mówiąc, że jabłko wisi na drzewie, a zbiór złożony z tego jabłka istnieje w umyśle.

W przypadku zbioru skończonego

$$Z=\{a_1,\dots,a_n\}$$

dla wszystkich $x$ prawdziwa jest równoważność

$$x\in Z\Leftrightarrow x=a_1\lor x=a_2\lor\dots\lor x=a_n.$$

Dlatego zapisy $\{1,1,1,1,1\}$ i $\{1\}$ oznaczają ten sam zbiór złożony z $1$.

Zanim przystąpimy do podania drugiego sposobu określania zbiorów, wprowadzimy pojęcie funkcji zdaniowej.

Wypełniając różne formularze często wpisujemy różne słowa w odpowiednie wolne miejsca. Rozważmy na przykład wyrażenie:

$$(*) \dots\mbox{ jest dobrym człowiekiem.}$$

Gdy w miejsce kropek wpiszemy określenie jakiejś osoby (np. słowo Janek), wyrażenie to stanie się zdaniem. Podobnie, jeśli w wyrażeniu algebraicznym

$$(**) x^2+1=x$$

w miejsce niewiadomej $x$ wpiszemy konkretną liczbę, stanie sie ono zdaniem. Obydwa rozważane powyżej wyrażenia są przykładami funkcji zdaniowych.

Definicja 3.1   Wyrażenie $W(x)$, które staje się zdaniem, gdy za $x$ podstawimy obiekt określonego typu (np. element jakiegoś zbioru) nazywamy funkcją zdaniową (predykatem). Jeśli określony jest zbiór $Z$, z którego bierzemy obiekty do podstawiania za zmienną $x$, to mówimy, że zmienna $x$ w funkcji zdaniowej $W(x)$ ma zakres zmienności (lub krótko: zakres) $Z$. Piszemy wówczas $W(x),x\in Z$. Można również rozważać funkcje zdaniowe bez określania zakresu zmiennej.

W funkcji zdaniowej $(*)$ zakresem zmiennej jest zbiór ludzi. W $(**)$ zakresem zmiennej $x$ jest zbiór liczb rzeczywistych. Podobnie definiuje się funkcje zdaniowe $W(x,y),W(x,y,z),\dots$ większej (skończonej) liczby zmiennych.

Przykładem funkcji zdaniowej dwóch zmiennych jest wyrażenie $x\in Z$. Równania i nierówności (na przykład takie, jak rozważane w rozdziale 2) to również funkcje zdaniowe.

Przy pomocy spójników logicznych $\land,\lor,\Rightarrow,\Leftrightarrow,\neg$ i nawiasów możemy z danych funkcji zdaniowych tworzyć nowe (złożone) funkcje zdaniowe. Na przykład, jeśli $V(x)$ i $W(x,y)$ to dane funkcje zdaniowe, to również

$$\neg V(x)\land (W(x,y)\Rightarrow V(x))\mbox{ i }V(x)\Rightarrow W(x,y)$$

są funkcjami zdaniowymi, przy czym wymagamy tu zgodności zakresów wspólnych zmiennych w tych funkcjach (o ile są określone); w naszym przypadku zmienna $x$ powinna mieć ten sam zakres w funkcjach $V(x)$ i $W(x,y)$. Bardziej konkretny przykład to funkcja zdaniowa

$$x^2+1=x\Rightarrow x\cdot y-y=12, x,y\in{\mathbb{R}}$$

(tu $\mathbb{R}$ oznacza zbiór liczb rzeczywistych). Ogólnie, gdy $\alpha(p,q,r)$ jest formułą zdaniową, zaś $V,W,U$ są funkcjami zdaniowymi o odpowiednio zgodnych zakresach zmiennych, to podstawiając w $\alpha(p,q,r)$ funkcje $V,W,U$ za zmienne zdaniowe $p,q,r$ odpowiednio, dostajemy złożoną funkcję zdaniową.

Teraz możemy przedstawić drugi sposób określania zbioru.

Sposób 2. Określenie zbioru przez podanie własności, którą mają wszystkie jego elementy. Załóżmy, że $W(x)$ jest funkcją zdaniową. Zapis

$$\{x:W(x)\}$$

oznacza zbiór tych wszystkich $x$, dla których zdanie $W(x)$ jest prawdziwe^3.1. Zauważmy, że wówczas dla wszystkich $x$ mamy

$$x\in \{x:W(x)\}\Leftrightarrow W(x).$$

Jeśli zakresem zmiennej $x$ w $W(x)$ jest dany zbiór $X$, to zbiór $\{x:W(x)\}$ istnieje, zapisujemy go wówczas również w formie $\{x\in X:W(x)\}$. Zapis ten odczytujemy następująco:

``zbiór takich $x$ należących do $X$, które spełniają warunek $W(x)$''.

W matematyce zbiory określone w ten sposób to m.in.
${\mathbb{N}}=\{0,1,2,3,\dots\}=\{x: x$ jest liczbą naturalną$\}$ (zbiór wszystkich liczb naturalnych),
${\mathbb{R}}=\{x:x$ jest liczbą rzeczywistą$\}$ (zbiór wszystkich liczb rzeczywistych),
zbiory liczb całkowitych ${\mathbb{Z}}$, liczb wymiernych ${\mathbb{Q}}$ czy liczb niewymiernych $\mathbb{IQ}$.

Szczególnym zbiorem jest tak zwany zbiór pusty, tzn. zbiór bez elementów. Przyjęliśmy, że zbiory o tych samych elementach są równe. Dlatego dowolne dwa zbiory puste są sobie równe. Istnieje więc tylko jeden zbiór pusty. Oznaczamy go symbolem $\emptyset$.

Rozważmy funkcję zdaniową $x^2+x=1,x\in{\mathbb{R}}$. Wówczas

$$\{x:x^2+x=1\}=\{x\in{\mathbb{R}}:x^2+x=1\}$$

oznacza zbiór takich liczb rzeczywistych $x$, które spełniają warunek $x^2+x=1$. Rozwiązując odpowiednie równanie znajdujemy, że dla wszystkich liczb rzeczywistych $x$ mamy

$$x^2+x=1$$

$$\Updownarrow$$

$$x={-1+\sqrt{5}\over 2} \lor x={-1-\sqrt{5}\over 2},$$

a zatem jedynymi elementami tego zbioru są liczby ${-1+\sqrt{5}\over 2},{-1-\sqrt{5}\over 2}$. Mamy więc

$$\{x\in{\mathbb{R}}:x^2+x=1\}=\left\{{-1+\sqrt{5}\over 2},{-1-\sqrt{5}\over 2}\right\}.$$

Lewa strona tej równości określa nasz zbiór przez podanie warunku spełnianego przez jego elementy, prawa strona określa ten sam zbiór przez wypisanie jego elementów.

Przykład. Antynomia (paradoks) Russella. Niech $W(x)$ oznacza funkcję zdaniową $x\not\in x$. Wówczas nie istnieje zbiór $Z=\{x:W(x)\}$.

Dowód. Przypuśćmy nie wprost, że zbiór $Z=\{x:x\not\in x\}$ istnieje. Wówczas dla wszystkich $x$ mamy

$$(\dagger) x\in Z\Leftrightarrow x\not\in x.$$

W szczególności zdanie $(\dagger)$ jest słuszne, gdy $x$ oznacza zbiór $Z$. Wówczas dostajemy, że $Z\in Z$ wtedy i tylko wtedy, gdy $Z\not\in Z$, sprzeczność. $\Box$