Existenční kvantifikátor

Existenční kvantifikátor (∃) (také malý kvantifikátor) je matematický symbol používaný nejčastěji v predikátové logice. Do běžného jazyka lze jeho význam přeložit jako „existuje“. Duálním kvantifikátorem k němu je obecný kvantifikátor s významem „pro každé“.

Etymologie

Znak ∃ pro existenční kvantifikátor vznikl převrácením písmena E z latinského existo a anglického - existuje.

Ukázka použití

Řekněme, že chceme napsat matematickou formuli, která bude pravdivá právě tehdy, pokud nějaké přirozené číslo na druhou je rovno 25. Nejjednodušším přístupem by bylo napsat následující formuli:

:0·0 = 25 nebo 1·1 = 25 nebo 2·2 = 25 nebo 3·3 = 25 atd.

Mohlo by se zdát, že toto je korektní formule výrokové logiky, protože jediná použitá spojka je "nebo". Ve výrokové logice bohužel není možno použít nekonečně mnoho spojek v jedné formuli a proto je potřeba zvolit jiný přístup, například rozšířit logiku tak, aby byla schopna vyjádřit následující formuli:

:Pro nějaké přirozené číslo n platí n·n = 25.

Tato formule používá existenční kvantifikátor a přesněji vyjadřuje původní tvrzení, jelikož v původní formuli nebyl význam termínu atd. přesně zadefinován. +more Nebylo například zřejmé, že se má pokračovat pro všechna přirozená čísla. Oproti tomu druhá formule přímo specifikuje, že se jedná o přirozená čísla.

Formule "pro nějaké přirozené číslo n platí n·n = 25" je pravdivá, protože pokud nahradíme n číslem 5, dostaneme 5. 5=25, což platí. +more Nezáleží na tom, zda pro ostatní n tvrzení platí (v tomto případě dokonce neplatí pro žádné číslo různé od 5). Stačí najít jedno jediné číslo.

Pokud změníme formuli na "Pro nějaké sudé číslo n platí n·n = 25", dostaneme nepravdivé tvrzení (nelze nalézt sudé číslo, kterým bychom n nahradili, a podmínka byla splněna). Na těchto dvou příkladech je vidět, že volba čísel, která můžeme použít, je důležitá a může změnit pravdivost tvrzení).

Formální zápis výše uvedených formulí je následující. Mějme predikát P(a,b,c) vyjadřující a. +moreb=c a predikát Q(a) vyjadřující "a je sudé". Potom se formule "pro nějaké přirozené číslo n platí n·n = 25" dá vyjádřit jako.

:\exists{n}\in\mathbb{N}.\, P(n,n,25)

a formule „pro nějaké sudé číslo n platí n·n = 25“ jako

:\exists{n}\in\mathbb{N}.\, Q(n) \wedge P(n,n,25)

Vztah k obecnému kvantifikátoru

Fakt, že existuje a splňující tvrzení \phi lze alternativně vyjádřit tak, že není pravda, že každé a nesplňuje \phi. Platí tedy * \exists\equiv\neg\forall\neg * \forall\equiv\neg\exists\neg

Kvantifikátor jednoznačné existence

V matematických zápisech je někdy potřeba vyjádřit, že počet prvků, které danou formuli splňují, je přesně jedna, například "Existuje právě jedno přirozené číslo n, které splňuje n. n=25" je pravdivá formule, ale formule "Existuje právě jedno sudé číslo n, které splňuje n. +moren=25" a "Existuje právě jedno sudé číslo" pravdivé nejsou. Ve formálních zápisech se potom místo \exists{n} používá \exists. {n}.

Ve skutečnosti se ale \exists. dá vyjádřit pomocí samotného \exists. +more Formule \exists. n\phi totiž platí právě když platí \exist n (\phi \wedge \neg\exist k\,(k\not=n \wedge \phi')) kde formule \phi' vznikne z \phi záměnou volných výskytů proměnné n za k.

Pro všechny formule \phi platí, že jestliže \exists! n\,\phi, pak i \exists n\,\phi , naopak to ale platit nemusí.

Kvantifikátor "existuje nekonečně mnoho"

Někdy je třeba vyjádřit, že existuje nekonečně mnoho prvků splňujících danou formuli. Například tvrzení "Existuje přirozené číslo n, které splňuje n \stackrel{\infty}{\exists}, tedy pokud P(a) je predikát „a>8“, vyjadřuje \stackrel{\infty}{\exists} n\in\mathbb{N}\, P(n) tvrzení „Existuje nekonečně mnoho přirozených čísel n takových, že n > 8“.

Pro všechny formule \phi platí, že jestliže \stackrel{\infty}{\exists} n\,\phi , pak i \exists n\,\phi, naopak to ale platit nemusí. Na druhou stranu pro žádnou formuli \phi nemůže zároveň platit \stackrel{\infty}{\exists} n\,\phi a \exists. +more n\,\phi.

Kvantifikátor \stackrel{\infty}{\exists} nelze obecně v predikátové logice vyjádřit, pokud ale jsou ale prvky, přes které kvantifikujeme, lineárně uspořádány, lze formuli \stackrel{\infty}{\exists} n\, \phi zapsat jako \forall k\, \exists n\, (n > k \wedge \phi).

Související články

Kvantifikátor * Kvantifikátor jednoznačné existence * Obecný kvantifikátor

Kategorie:Matematická logika