Udowodnić prawo rachunku kwantyfikatorów używając zbiorów

[nne]

Wróciłem do dowodów praw rachunków kwantyfikatorów z książki pana Kraszewskiego i pojawiają się u mnie pewne niejasności.

Niech \(\displaystyle{ X}\) będzie niepustym zbiorem.

Mam definicje
\(\displaystyle{ (\forall x \in X) \varphi(x)}\) jest prawdą \(\displaystyle{ \Leftrightarrow \{x \in X: \varphi(x)\} = X}\)
\(\displaystyle{ (\exists x \in X) \varphi(x)}\) jest prawdą \(\displaystyle{ \Leftrightarrow \{x \in X: \varphi(x)\} \not = \emptyset}\)
oraz niech
\(\displaystyle{ D_{\varphi} = \{x \in X : \varphi(x)\}}\).

Poza tym mam udowodnione proste twierdzenia
\(\displaystyle{ D_{\varphi \vee \psi} = D_{\varphi} \cup D_{\psi}}\)
\(\displaystyle{ D_{\varphi \wedge \psi} = D_{\varphi} \cap D_{\psi}}\)
\(\displaystyle{ D_{\neg \varphi} = D^c_{\varphi}}\).

Mam przedstawiony dowód twierdzenia \(\displaystyle{ \neg (\forall x) \varphi(x) \Leftrightarrow (\exists x) \neg \varphi(x)}\), który wygląda następująco \(\displaystyle{ \neg (\forall x) \varphi(x) \Leftrightarrow \neg (D_{\varphi} = X) \Leftrightarrow D_{\varphi} \not = X \Leftrightarrow^* D_{\varphi}^C \not = \emptyset \Leftrightarrow D_{\neg \varphi} \not = \emptyset \Leftrightarrow (\exists x) \neg \varphi(x)}\).

Wszystko wydaje mi się jasne z wyjątkiem przejścia, które zaznaczyłem *. Intuicyjnie jest ono dla mnie oczywiste, ale czy właśnie nasza intuicja nie bazuje na prawach rachunku kwantyfikatorów? Jeżeli tak to mamy zwykłe masło maślane, zupełnie zbędne.

Spróbujmy to rozpisać. Mam udowodnić \(\displaystyle{ D_{\varphi} \not = X \Leftrightarrow X \setminus D_{\varphi} \not = \emptyset}\). \(\displaystyle{ D_{\varphi}}\) składa się z definicji z elementów \(\displaystyle{ X}\) czyli \(\displaystyle{ D_{\varphi} \subseteq X}\), zamieniając \(\displaystyle{ D_{\varphi}}\) na \(\displaystyle{ A}\) mam udowodnić:
\(\displaystyle{ A \subseteq X \wedge A \not = X \Leftrightarrow X \setminus A \not = \emptyset}\). \(\displaystyle{ X \setminus A \not = \emptyset}\) oznacza, zgodnie z definicją u góry \(\displaystyle{ (\exists x \in X) (x \in X \wedge x \not \in A)}\).

Dowód:
\(\displaystyle{ A \subseteq X \wedge A \not = X \Leftrightarrow \\
A \subseteq X \wedge \neg (A \subseteq X \wedge X \subseteq A) \Leftrightarrow \\
A \subseteq X \wedge (A \not \subseteq X \vee X \not \subseteq A) \Leftrightarrow \\
A \subseteq X \wedge X \not \subseteq A \Leftrightarrow \\
A \subseteq X \wedge \neg (X \subseteq A) \Leftrightarrow \\
A \subseteq X \wedge \neg \forall x (x \in X \Rightarrow x \in A) \Leftrightarrow \\
A \subseteq X \wedge \neg \forall x (x \not \in X \vee x \in A) \Leftrightarrow \\
A \subseteq X \wedge (\exists x \in X)(x \in X \wedge x \not \in A)}\).

No i udowodniłem, ale co z tego skoro za pomocą prawa rachunku kwantyfikatorów. Jaki to ma sens albo jak to powinno poprawnie wyglądać?

[Sir George]

(...) ale co z tego skoro za pomocą prawa rachunku kwantyfikatorów. Jaki to ma sens albo jak to powinno poprawnie wyglądać?

nne, zależy od tego, co przyjmujesz za pierwotne definicje. Równoważność, którą chcesz pokazać, można udowodnić odwołując się jedynie do aksjomatów ZF. A dokładniej należy skorzystać z jednego z praw de Morgana: \(\displaystyle{ A\subseteq B\Leftrightarrow X\!\setminus\!A \supseteq X\!\setminus\!B}\). Czyli
\(\displaystyle{ D_{\varphi}\neq X \ \leftrightarrow \
\neg(D_{\varphi}= X) \ \leftrightarrow \
\neg\big((D_{\varphi}\subseteq X)\wedge(D_{\varphi}\supseteq X)\big)\ \leftrightarrow \\
\neg\big((X\!\setminus\!D_{\varphi}\supseteq X\!\setminus\!X)
\wedge(X\!\setminus\!D_{\varphi}\subseteq X\!\setminus\!X)\big)\ \leftrightarrow \
\neg(X\!\setminus\!D_{\varphi}= X\!\setminus\!X) \leftrightarrow \\
X\!\setminus\!D_{\varphi}\neq X\!\setminus\!X\,.}\)

... i wszystko jasne...?

[krl]

Równoważność, którą chcesz pokazać, można udowodnić odwołując się jedynie do aksjomatów ZF. A dokładniej należy skorzystać z jednego z praw de Morgana: \(\displaystyle{ A\subseteq B\Leftrightarrow X\!\setminus\!A \supseteq X\!\setminus\!B}\)

W podanym przez Ciebie dowodzie nie odwołujesz się wprost do aksjomatów ZF, lecz do praw rachunku zbiorów, które oczywiście wynikają z aksjomatów ZF, ale by udowodnić je formalnie musimy skorzystać z pewnych tautologii, np. praw de Morgana rachunku kwantyfikatorów. No i mamy błędne koło.

Po prostu w sensie formalnym tautologii rachunku kwantyfikatorów się nie dowodzi. Tak jak nie definiuje się pojęć pierwotnych i nie dowodzi się aksjomatów.

[Jan Kraszewski]

Po prostu w sensie formalnym tautologii rachunku kwantyfikatorów się nie dowodzi. Tak jak nie definiuje się pojęć pierwotnych i nie dowodzi się aksjomatów.

Dodam, że celem dowodu w książce jest przekonanie Czytelnika o poprawności tych praw, a do tego "przetłumaczenie" ich na zbiory nadaje się dość dobrze (bo wydaje się, że zbiory są bardziej intuicyjne od kwantyfikatorów, których studenci zazwyczaj się boją). Dlatego można ten dowód uznać za dowód "praktyczny" (bo od strony formalnej wygląda to tak, jak wyżej).

JK

[nne]

Trochę zapomniałem o tym temacie, wybaczcie. Poradziłem sobie z tym problemem udowadniając
\(\displaystyle{ A \subseteq X \Rightarrow (A \not = X \Leftrightarrow X \setminus A \not = \emptyset)}\) na bazie naiwnej teorii zbiorów. Nie widzę tutaj, żebym bazował na prawach rachunku kwantyfikatorów, może dla tego, że aksjomaty ZF nie wiele mi mówią. Dla mnie sposób udowadniania na zbiorach jak powyżej jest na tyle intuicyjny, że trudno mi dostrzec użycie w tym kwantyfikatorów, w takiej formie jaką udowadniam. Co innego w pierwszym poście, gdzie tak naprawdę z góry korzystałem z definicji bazującej na kwantyfikatorach. Możliwe, że tutaj też to robię tylko mniej świadomie, dlatego wkleję dowód i fajnie jakbyście mi powiedzieli gdzie korzystam z praw, które chcę udowodnić.

Mam udowodnić \(\displaystyle{ A \subseteq X \Rightarrow (A = X \Leftrightarrow X \setminus A = \emptyset)}\).

\(\displaystyle{ \Rightarrow}\): Otrzymujemy \(\displaystyle{ X \setminus X = \emptyset}\). Załóżmy, że jest to nieprawdą, a więc mamy \(\displaystyle{ x \in X \wedge x \notin X}\) co jest fałszem.

\(\displaystyle{ \Leftarrow}\):
\(\displaystyle{ A \subseteq X}\): Weźmy dowolny \(\displaystyle{ x \in A}\). Z założenia mamy \(\displaystyle{ x \in X}\).
\(\displaystyle{ X \subseteq A}\): Załóżmy, że jest to fałszem czyli \(\displaystyle{ x\in X}\) i \(\displaystyle{ x \notin A}\). Mamy wtedy \(\displaystyle{ x \in X\setminus A}\) co jest sprzeczne z założeniem.