$(\exists x)(\forall y)P(x,y)$ a $(\forall y)(\exists x)P(x$

[Martin Sleziak]

Na minulom cvičení sme nestihli poriadne dokončiť úlohu o vzťahu medzi $P_3\equiv (\exists x)(\forall y)P(x,y)$ a $P_6\equiv(\forall y)(\exists x)P(x,y)$. Vrátim sa k nej teda tu.

$P_3\Rightarrow P_6$ Vieme, že existuje také $x$, že platí $P(x,y)$ pre ľubovoľné $y$. Označme si nejaké také $x$ ako $x_0$. Potom platí, že pre každé $y$ existuje $x$ spĺňajúce $P(x,y)$. (Konkrétne môžeme zobrať $x_0$. Samozrejme je možné, že existujú aj nejaké ďalšie prvky s touto vlastnosťou, nám však stačí zdôvodniť, že existuje aspoň jedno také $x$.)

$P_6\not\Rightarrow P_3$ Kontrapríklad: Pracujme s celými číslami a zoberme za podmienku $P(x,y)$ podmienku $x<y$.
Pri tejto voľbe $P_6$ platí lebo $(\forall y\in\mathbb Z)(\exists x\in\mathbb Z) x<y$. (Pre každé celé číslo existuje číslo od neho menšie, napríklad pre $y$ môžeme zobrať $x=y-1$.)
Ale $P_3$ neplatí. Ak máme výrok $(\exists x\in\mathbb Z)(\forall x\in\mathbb Z) x<y$ tak sa pýtame, či existuje celé číslo $x$, ktoré je menšie od všetkých celých čísel. Napríklad by potom platilo aj $x<x$, čo určite nie je pravda.