Univerzální kvantifikace - Universal quantification

V matematické logice je univerzální kvantifikace typem kvantifikátoru , logické konstanty, která je interpretována jako „daný libovolný“ nebo „pro všechny“. Vyjadřuje, že predikát může být spokojen každý člen jednoho domény diskursu . Jinými slovy, je to tvrzení o vlastnictví nebo vztahu ke každému členu domény. To tvrdí, že predikát v rámci všeobecného kvantifikátoru platí o každé hodnotě jednoho predikátu proměnné .

Obvykle se označuje symbolem logického operátoru A (∀) , který se při použití společně s predikátovou proměnnou nazývá univerzální kvantifikátor („ ∀ x “, „ ∀ ( x ) “ nebo někdy „ ( x ) " sám). Univerzální kvantifikace se liší od existenční kvantifikace („existuje“), která pouze tvrdí, že vlastnost nebo vztah platí alespoň pro jednoho člena domény.

Kvantifikaci obecně pojednává článek o kvantifikaci (logice) . Univerzální kvantifikátor je kódován jako U + 2200 ∀ FOR ALL v Unicode a jako \forallv LaTeXu a souvisejících editorech vzorců,

Základy

Předpokládejme, že je to dané

2 · 0 = 0 + 0 a 2 · 1 = 1 + 1 a 2 · 2 = 2 + 2 atd.

To se zdá být logickou spojkou kvůli opakovanému použití „a“. „Atd.“ nelze ve formální logice interpretovat jako spojení . Místo toho musí být prohlášení přeformulováno:

Pro všechna přirozená čísla n má jeden 2 · n = n + n .

Toto je jediné prohlášení využívající univerzální kvantifikaci.

Lze říci, že toto tvrzení je přesnější než původní. Zatímco „atd.“ neformálně zahrnuje přirozená čísla a nic víc, toto nebylo důsledně dáno. V univerzální kvantifikaci jsou naopak přirozená čísla výslovně uvedena.

Tento konkrétní příklad je pravdivý , protože jakékoli přirozené číslo by mohlo být nahrazeno n a tvrzení „2 · n = n + n “ by bylo pravdivé. V porovnání,

Pro všechna přirozená čísla n má jeden 2 · n > 2 + n

je nepravdivé , protože pokud je n nahrazeno například 1, výraz „2 · 1> 2 + 1“ je nepravdivý. Je nepodstatné, že „2 · n > 2 + n “ platí pro většinu přirozených čísel n : k prokázání nepravdivosti univerzální kvantifikace stačí i existence jediného protipříkladu .

Na druhou stranu, pro všechna složená čísla n má jeden 2 · n > 2 + n je true, protože žádný z protipříkladů nejsou složená čísla. To naznačuje důležitost oblasti diskurzu , která určuje, jaké hodnoty může n mít. Zejména si všimněte, že pokud je doména diskurzu omezena pouze na ty objekty, které splňují určitý predikát, pak pro univerzální kvantifikaci to vyžaduje logickou podmínku . Například,

Pro všechna složená čísla n má jeden 2 · n > 2 + n

je logicky ekvivalentní s

Pro všechna přirozená čísla n , je-li n složené, pak 2 · n > 2 + n .

Zde konstrukce „pokud ... pak“ označuje logickou podmínku.

Zápis

V symbolické logice se pro označení univerzální kvantifikace používá symbol univerzálního kvantifikátoru (otočené „ A “ v bezpatkovém písmu, Unicode U + 2200). Poprvé byl použit v této cestě od Gerhard Gentzen v roce 1935, obdobně s Giuseppe Peano ‚s (obrátil E) notací pro existenční kvantifikace a pozdější použití Peanovy v zápisu u Bertrand Russell . ${\ displaystyle \ forall}$${\ displaystyle \ existuje}$

Například pokud P ( n ) je predikát „2 · n > 2 + n “ a N je množina přirozených čísel, pak

${\ displaystyle \ forall n \! \ in \! \ mathbb {N} \; P (n)}$

je (nepravdivé) prohlášení

"pro všechna přirozená čísla n má jeden 2 · n > 2 + n ".

Podobně, pokud Q ( n ) je predikát „ n je složený“, pak

${\ displaystyle \ forall n \! \ in \! \ mathbb {N} \; {\ bigl (} Q (n) \ rightarrow P (n) {\ bigr)}}$

je (pravdivé) tvrzení

"pro všechna přirozená čísla n , pokud n je složené, pak 2 · n > 2 + n ".

Několik variací v notaci pro kvantifikaci (které platí pro všechny formy) lze nalézt v článku Kvantifikátor .

Vlastnosti

Negace

Negace univerzálně kvantifikované funkce se získá změnou univerzálního kvantifikátoru na existenční kvantifikátor a negací kvantifikovaného vzorce. To znamená,

${\ displaystyle \ lnot \ forall x \; P (x) \ quad {\ text {je ekvivalentní k}} \ quad \ existuje x \; \ lnot P (x)}$

kde označuje negaci . ${\ displaystyle \ lnot}$

Například pokud P ( x ) je výroková funkce „ x je ženatý“, pak pro množinu X všech živých lidí univerzální kvantifikace

Vzhledem k jakékoli žijící osobě x je tato osoba vdaná

je psáno

${\ displaystyle \ forall x \ in X \, P (x)}$

Toto tvrzení je nepravdivé. Je pravdou, že se uvádí, že

Není pravda, že vzhledem k jakékoli žijící osobě x je tato osoba vdaná

nebo symbolicky:

${\ displaystyle \ lnot \ \ celkově x \ v X \, P (x)}$.

Pokud funkce P ( x ) není pravdivá pro každý prvek X , pak musí existovat alespoň jeden prvek, pro který je příkaz nepravdivý. To znamená, že negace je logicky ekvivalentní „Existuje živá osoba x, která není vdaná“, nebo: ${\ displaystyle \ forall x \ in X \, P (x)}$

${\ displaystyle \ existuje x \ v X \, \ ne P (x)}$

Je chybné zaměňovat „všechny osoby nejsou vdané“ (tj. „Neexistuje žádná osoba, která je vdaná“) s „ne všechny osoby jsou vdané“ (tj. „Existuje osoba, která není vdaná“):

${\ Displaystyle \ lnot \ \ existuje x \ v X \, P (x) \ equiv \ \ pro všechny x \ v X \, \ lnote P (x) \ ne \ equiv \ \ not \ \ pro všechny x \ v X \ , P (x) \ equiv \ \ existuje x \ v X \, \ ne P (x)}$

Další spojovací prostředky

Univerzální (a existenční) kvantifikátor se pohybuje beze změny napříč logickými spojkami ∧ , ∨ , → a ↚ , pokud není ovlivněn druhý operand; to je:

${\ displaystyle {\ begin {zarovnáno} P (x) \ land (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)) \\ P (x) \ lor (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ lor Q (y)), a {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ to (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ to Q (y)), & {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ nleftarrow (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ nleftarrow Q (y)) \\ P (x) \ land (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)), & {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ lor (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ lor Q (y)) \\ P (x) \ to (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ až Q (y)) \\ P (x) \ nleftarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ nleftarrow Q (y)), a {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \ end {zarovnáno} }}$

Naopak pro logické spojky ↑ , ↓ , ↛ a ← se kvantifikátory otočí:

${\ displaystyle {\ begin {zarovnáno} P (x) \ uparrow (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)) \\ P (x) \ downarrow (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ downarrow Q (y)), a {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ nrightarrow (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ nrightarrow Q (y)), & {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ gets (\ existuje {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ získá Q (y)) \\ P (x) \ uparrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)), & {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ downarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ downarrow Q (y)) \\ P (x) \ nrightarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ nrightarrow Q (y)) \\ P (x) \ dostane ( \ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existuje {y} {\ in} \ mathbf {Y} \, (P (x) \ získá Q ( y)), & {\ text {za předpokladu, že}} \ mathbf {Y} \ neq \ emptyset \\\ end {zarovnáno}}}$

Pravidla odvození

Pravidlo závěru je pravidlo odůvodnit logický krok z hypotézy s uzavřením. Existuje několik pravidel odvození, která využívají univerzální kvantifikátor.

Univerzální instance dospěla k závěru, že pokud je známo, že výroková funkce je všeobecně pravdivá, pak musí platit pro libovolný prvek diskurzního vesmíru. Symbolicky je to znázorněno jako

${\ displaystyle \ forall {x} {\ in} \ mathbf {X} \, P (x) \ až P (c)}$

kde c je zcela libovolný prvek vesmíru diskurzu.

Univerzální generalizace dospěla k závěru, že výroková funkce musí být všeobecně pravdivá, pokud platí pro libovolný prvek diskurzního vesmíru. Symbolicky, pro libovolné c ,

${\ displaystyle P (c) \ to \ \ vše {x} {\ in} \ mathbf {X} \, P (x).}$

Prvek  c musí být zcela libovolný; jinak logika nenásleduje: pokud c není libovolné a je místo toho specifickým prvkem vesmíru diskurzu, pak P ( c ) implikuje pouze existenciální kvantifikaci výrokové funkce.

Prázdná sada

Podle konvence je vzorec vždy pravdivý, bez ohledu na vzorec P ( x ); vidět prázdnou pravdu . ${\ displaystyle \ forall {x} {\ in} \ emptyset \, P (x)}$

Univerzální uzavření

Univerzální uzávěr ze vzorce cp je rovnice s žádnými volnými proměnnými získaných přidáním univerzální kvantifikátor pro každou volnou proměnnou v cp. Například univerzální uzavření

${\ Displaystyle P (y) \ země \ existuje xQ (x, z)}$

je

${\ displaystyle \ forall y \ forall z (P (y) \ land \ existuje xQ (x, z))}$.

Jako adjoint

V kategorii teorie a teorie elementární topoi , univerzální quantifier lze chápat jako pravé adjoint jednoho funktoru mezi soustrojí , v inverzní obrazu funktoru z funkce mezi sadami; Stejně tak je existenční kvantifikátor je levá adjoint .

Pro sadu , ať značí jeho POWERSET . Pro jakoukoli funkci mezi množinami a existuje inverzní obrazový funktor mezi výkonovými sadami , který bere podmnožiny domény f zpět na podmnožiny její domény. Levý adjoint tohoto funktoru je existenciální kvantifikátor a pravý adjoint je univerzální kvantifikátor . ${\ displaystyle X}$${\ displaystyle {\ mathcal {P}} X}$${\ displaystyle f: X \ až Y}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle f ^ {*}: {\ mathcal {P}} Y \ až {\ mathcal {P}} X}$${\ displaystyle \ existuje _ {f}}$${\ displaystyle \ forall _ {f}}$

To znamená, že je funktor, který pro každou podmnožinu udává podmnožinu danou ${\ displaystyle \ existuje _ {f} \ dvojtečka {\ mathcal {P}} X \ až {\ mathcal {P}} Y}$${\ displaystyle S \ podmnožina X}$${\ displaystyle \ existuje _ {f} S \ podmnožina Y}$

${\ displaystyle \ existuje _ {f} S = \ {y \ v Y \; | \; \ existuje x \ v X. \ f (x) = y \ quad \ land \ quad x \ v S \},}$

ti na obrázku pod . Podobně je univerzální kvantifikátor funktor, který pro každou podmnožinu dává podmnožinu danou ${\ displaystyle}$${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle \ forall _ {f} \ colon {\ mathcal {P}} X \ až {\ mathcal {P}} Y}$${\ displaystyle S \ podmnožina X}$${\ displaystyle \ forall _ {f} S \ podmnožina Y}$

${\ displaystyle \ forall _ {f} S = \ {y \ v Y \; | \; \ forall x \ v X. \ f (x) = y \ quad \ implikuje \ quad x \ v S \},}$

ti, jejichž preimage under je obsažen v . ${\ displaystyle}$${\ displaystyle f}$${\ displaystyle S}$

Známější forma kvantifikátorů, jak se používá v logice prvního řádu, se získá tak, že se funkce f považuje za jedinečnou funkci, takže jde o dvouprvkovou množinu obsahující hodnoty true a false, podmnožina S je podmnožina, pro kterou predikátové blokování a ${\ displaystyle!: X \ až 1}$${\ displaystyle {\ mathcal {P}} (1) = \ {T, F \}}$ ${\ displaystyle S (x)}$

${\ displaystyle {\ begin {array} {rl} {\ mathcal {P}} (!) \ colon {\ mathcal {P}} (1) & \ to {\ mathcal {P}} (X) \\ T & \ mapsto X \\ F & \ mapsto \ {\} \ end {pole}}}$

${\ displaystyle \ existuje _ {!} S = \ existuje xS (x),}$

což je pravda, pokud není prázdné, a ${\ displaystyle S}$

${\ displaystyle \ forall _ {!} S = \ forall xS (x),}$

což je nepravdivé, pokud S není X.

Univerzální a existenční kvantifikátory uvedené výše zobecňují kategorii presheaf .

Viz také

• Existenční kvantifikace
• Logika prvního řádu
• Seznam logických symbolů - pro symbol Unicode ∀

Poznámky

Reference

• Hinman, P. (2005). Základy matematické logiky . AK Peters . ISBN 1-56881-262-0.
• Franklin, J. a Daoud, A. (2011). Důkaz z matematiky: Úvod . Kew Books. ISBN 978-0-646-54509-7.CS1 maint: více jmen: seznam autorů ( odkaz ) (kap. 2)

externí odkazy

• Slovníková definice každého na Wikislovníku