Univerzális kvantifikáció

Az univerzális kvantifikáció az a logikai operátor (speciális kvantor), mely a „minden”, „bármely”, „összes” természetes nyelvi szavaknak feleltethető meg valamely formális nyelven belül. Univerzális kvantor szerepét töltik be például az alábbi mondatokban a dőlt betűs szavak:

„Minden ember halandó.”

„Ezügyben érdeklődhet bármelyik munkatársunknál.”

„A gyerek az összes tojást összetörte.”

Az említett szavak akkor válnak univerzális kvantorrá, ha a mondatokat egy formális nyelv kifejezéseiből állítjuk össze, például ekképpen:

ha φ(x) jelentése az, hogy „x halandó”, akkor (∀x)φ(x) jelentése „Minden ember halandó.”

Itt (∀x)φ(x)-t úgy mondjuk ki, hogy „minden x-re fí-x” és a

$\forall \,$

szimbólum az univerzális kvantifikáció jele.

Szintaktika és szándékolt jelentés

A (∀x)φ formulát akkor veszünk egy elsőrendű formális nyelvben, ha a „Minden dolog 'φ' tulajdonságú.” metanyelvi mondatot kívánjuk a tárgynyelvben megfogalmazni (fordítani). Ez az univerzális kvantor szándékolt jelentése. Vegyük észre, hogy míg a formalizálatlan metanyelv fenti mondatában nincsenek változók, addig a tárnynyelvben már vannak. Mi több, például a (∀x)(x=y) tárgynyelvi formula szándékolt jelentése:

„minden egyenlő a ...-tal”

ami egy hiányos mondat, egy predikátum. A (∀x)(x=y)-ben két külön típusú változó szerepel. A metanyelvi fordításban az x, mely a kvantifikáció megfogalmazásának segédváltozója, nem szerepel. Az y a metaelmélet természetes nyelvében egy kitöltetlen hely marad. A szintaktikai vonatokozásoknál a változók ezen megkülönböztetése nagy odafigyelést követel a formalizálótól. A szándékolt jelentés a formális nyelvvel szemben természetes követelményeket támaszt, melyek némelyikének az elsőrendű nyelvek tökéletesen megfelelnek, másokat csak részben teljesít. A formális tudományokban, például a matematikában a szándékolt jelentésre úgy kell tekintenünk, mint egy kezdeti feltevésre, melynek fennállását mindig ellenőriznünk kell. Könnyen előfordulhat, hogy a formalizálás elején még összhangban van a metanyelv és a tárgynyelv, de formális manipulációk sorozata után a kezdetben betáplált szándékolt jelentés már nem öröklődik a végállapotra. Erre a legjobb példa a második Gödel-tétel, melyben bizonyos metaelméleti mondatok fordítása során olyan tárgynyelvi mondatok jönnek létre, melyek pont fordításuk ellenkezőjét állítják.

Változók lekötése

Formális nyelvekben a kvantorok változót lekötő operátorok. Ez azt jelenti, hogy míg a φ(x,y) formula kétbemenetűnek tekinthető (x és y is szabad változója a φ-nek), addig a (∀x)φ(x,y) már csak egy bemenettel rendelkezik (x szabad változója φ-nek, y pedig kötött változója φ-nek). Ekkor még azt is mondjuk, hogy a (∀x)φ(x,y) formulában szereplő (∀x) kvantor hatóköre a φ(x,y) formula, amelyen belül tehát az x kötött módon szerepel.

Például, míg a

φ ≡ 'x=x'

formulában az x változót a c konstansra cserélve az új

φ[x/c] ≡'c=c'

zárt formulát (mondatot) kapjuk, addig a

(∀x)φ

már maga is zárt formula, x nem szabad változója, így helyettesítése a c konstanssal definíció szerint nem eredményez új mondatot:

((∀x)φ)[x/c] ≡ (∀x)φ

Ezt úgy is mondjuk, hogy kötött változóba nem lehet semmit behelyettesíteni.

Tiltott helyettesítések

Egy

ψ ≡ (∀x)φ(x,y)

alakú formulában formálisan (grafikusan) végrehajtható az [y/x] helyettesítés:

((∀x)φ(x,y))[y/x] ≡ (∀x)φ(x,x)

de egy ilyen helyettesítés az y helyére kerülő x-et bevonja a kvantor hatókörébe, miközben az y eredetileg ψ-nek szabad változója volt. Világos, hogy egy ilyen helyettesítés lényegesen megváltoztatja a ψ jelentését. Például a

ψ(y) ≡ (∀x)(x = y)

szándékolt jelentése:

ψ(y) ≡ „y mindennel egyenlő”,

míg

ψ[y/x] ≡ (∀x)(x = x) ≡ „minden egyenlő saját magával”.

Mindeközben például a

ψ[y/z] ≡ (∀x)(x = z) ≡ „z mindennel egyenlő”

egy jelentésmegőrző helyettesítés.

Azt mondjuk, hogy a (∀x)φ(x,y) formulában az t kifejezés szabad az y-ba történő helyettesítésre nézve, ha t-nek nem szabad változója az x. Ekkor a ((∀x)φ(x,y))[y/t] helyettesítés nem köt le t-beli szabad x-et, mivel nincs is olyan.

Bizonyításelméleti szemantika

Egy formális elméletbeli univerzális kvantifikációnak nem csak szándékolt jelentése (vagyis hogy a „minden” szót rövidíti) létezik. Értelmet adhatunk a (∀x)φ univerzális kijelentéseknek, ha megmondjuk, hogy milyen szabály örökíti az igazságot rájuk és mire örökítik az igazságot. Az elsőrendű nyelvekben a következő alapvető jelentőségű levezetési szabályok érvényesek az univerzális kijelentésekre.

Univerzális generalizáció

Az univerzális generalizáció az a következtetési szabály, mely valamely premisszából egy (∀x)φ formulára enged következtetni. A következő természetes nyelvi aktusról van szó:

Tegyük fel, hogy egy φ tulajdonság tetszőleges t dologra igaz. Ekkor helyesen következtetünk, ha azt mondjuk: „Minden dolog φ tulajdonságú”.

Példa. Igazoljuk, hogy minden kettőnél nagyobb prímszám páratlan!

1. (tetszőleges választás) Legyen p tetszőleges kettőnél nagyobb prímszám.
2. (indirekt feltevés) Ha p páros lenne, akkor lenne k pozitív egész, hogy 2k = p
3. (ellentmondás) De mivel p > 2, ezért k > 1, azaz p fölbontható két olyan pozitív egész szám szorzatára, mely közül egyik sem az 1, azaz p nem prím.
4. (konklúzió) Tehát p páratlan.
5. (univerzális generalizáció) Mivel p tetszőleges volt, ezért kijelenthetjük: minden kettőnél nagyobb prímszám páratlan.

Az érvelésben, amikor 1. és 4. fennállása miatt 5.-re következetettünk, univerzális generalizációt végeztünk.

Az univerzális kvantor bevezetési szabálya lényegesen függ attól, hogy Γ |- φ levezethetőség esetén levezetési szabályok közé veszik-e föl a korlátozatlan generalizációt (GEN) is vagy egyedüli levezetési szabálynak a modus ponenst (MP) tekintik. Az egyik lehetséges definíciója Γ |- φ-nek az, hogy létezik olyan (ψ₁,...,ψ_n) formulasorozat, hogy ψ_n≡φ és minden k<n-re

1. ψ_k logikai axióma vagy eleme Γ-nak vagy
2. (MP) létezik i,j < k ψ_j≡ψ_i$\to$ψ_k vagy
3. (GEN) létezik i < k (∀x)ψ_i≡ψ_k

Ha ezzel szemben (GEN)-t elhagyjuk és a logikai axiómákat bővítjük a φ$\to$(∀x)φ sémával (melyben x nem szerepel szabadon φ-ben), akkor megváltoznak az univerzális kvantorra vonatkozó alapvető szabályok.

Korlátozatlan univerzális generalizáció

(GEN)-nel.

Tetszőleges φ formulára, Γ formulahalmazra és x változóra:

${\frac {\Gamma \vdash \varphi }{\Gamma \vdash (\forall \,x)\varphi \;}}\quad \quad (\mathrm {UG} )$

Ebben az esetben viszont a dedukciótételt nem lehet korlátozatlan formában alkalmazni, legegyszerűbb esetben csak zárt premisszákra. Például az alábbi gondolatmenetben azt látjuk be, hogy ha minden dolog olyan, hogy ha az a, akkor b is, akkor minden dolog b. Ilyen következtetés például a {c≠b,a=b} elméletben nyilvánvalóan érvénytelen.

$c\neq b,a=b\vdash (\forall x)(x=a\;\rightarrow \;x=b)$

$c\neq b,a=b\vdash x=a\;\rightarrow \;x=b$

$c\neq b,a=b,x=a\vdash x=b$

$c\neq b,a=b,x=a\vdash (\forall x)(x=b)$ [korlátozatlan univerzális generalizálás: x szerepel az |- jel előtt]

$c\neq b,a=b\vdash x=a\;\rightarrow \;(\forall x)(x=b)$ [korlátozatlan dedukciótétel: x-től függő premissza felvétele]

$c\neq b,a=b\vdash (\forall x)(x=a\;\rightarrow \;(\forall x)(x=b))$

$c\neq b,a=b\vdash a=a\;\rightarrow \;(\forall x)(x=b)$ [univerzális specifikáció a külső x-re]

$c\neq b,a=b\vdash (\forall x)(x=b)$ [a=a axióma]

Ezekben az elméletekben a változók azon a kitüntetett szerepen kívül, hogy szabad és kötött szereplésük is létezik oly módon is kitüntetettek a konstansokkal szemben, hogy minden körülmények között (amikor egy levezethető formulában szerepelnek) univerzálisan generalizálhatók.

Korlátozott univerzális generalizáció

Ha a GEN-t nem tekintjük levezetési szabálynak, akkor az azzal az előnnyel jár, hogy a dedukciótétel feltételek nélkül érvényes: ha Γ U {ψ} |- φ, akkor Γ |- ψ $\rightarrow$ φ (DT). Cserébe azonban az UG szabály csak az alábbi formában érvényes:

Tetszőleges φ formulára, Γ formulahalmazra és x változóra:

${\frac {\Gamma \vdash \varphi }{\Gamma \vdash (\forall \,x)\varphi \;}}\quad \quad (\mathrm {UG} )$
ahol x nem szabad változója Γ egyetlen elemének sem.

Az előző szakaszban említett példa ez esetben is mutatja, hogy korlátozatlan módon egyszerre DT-t és UG-t nem lehet alkalmazni.

Mindkét esetben igaz az, hogy konstanssal is működik a generalizálás a következő formában:

${\frac {\Gamma \vdash \varphi (c)}{\Gamma \vdash (\forall \,x)\varphi [x/c]\;}}\quad \quad (\mathrm {UG-konst} )$
ahol c nem szerepel  Γ egyetlen elemében sem és
x szabad a c-be történő behelyettesítésre nézve a φ-ben.

Ez mutatja, hogy ha GEN-t nem szerepeltetjük, mint levezetési szabályt (a bizonyíthatóság definíciójában), akkor a változóknak (azon felül, hogy létezik kötött és szabad előfordulásuk) lényegében nincs kitüntetett szerepük a konstansokat történő összevetésben.

Univerzális specifikáció

Az univerzális specifikálás vagy univerzális instanciáció az a következtetési szabály, mely a (∀x)φ premisszából valamely más formulára enged következtetni. A következő természetes nyelvi aktusról van szó:

Tegyük fel, hogy „Minden dolog φ tulajdonságú”. Ekkor helyesen következtetünk, ha tetszőleges t dologról azt állítjuk: „A t dolog φ tulajdonságú”.

Például:

Szókratész ember $\vdash$ Minden ember halandó
-----------------------------------------
Szókratész ember $\vdash$  Szókratész halandó

∀ kiküszöbölési szabálya (az univerzális specifikáció)

Tetszőleges φ formulára, Γ formulahalmazra, x változóra és t kifejezésre:

${\frac {\Gamma \vdash (\forall \,x)\varphi \;}{\Gamma \vdash \varphi [t/x]}}\quad \quad (\mathrm {UE} )$
ahol t szabad φ-ben az x-be történő behelyettesítésre nézve
(másként: a [t/x] helyettesítés megengedett φ-ben).

A megfogalmazott kitétel arra vonatkozik, hogy az érv nem érvényes például a következő esetben:

${\frac {a\neq b\vdash (\forall \,x)(\exists y)(x\neq y)\;}{a\neq b\vdash (\exists y)(y\neq y)}}\quad \quad \scriptstyle {/((\exists y)(x\neq y))[y/x]}$

Ugyanis a két különböző a és b konstansot tartalmazó elméletben érvényes a φ ≡ (∀x)(∃y)(x ≠ y) formula, hiszen van két különböző individuum, de a

((∃y)(x ≠ y))[y/x]

nem megengedett helyettesítéssel nyert

(∃y)(y ≠ y)

formula már semelyik ellentmondásmentes elméletben sem lehet érvényes. Itt persze a jelentés is csorbul: φ(x) jelentése: „x olyan, amitől létezik különböző”, míg (∃y)(y ≠ y) nem azt jelenti, hogy „y-tól nincs különböző”, ahogy az x-be történő helyettesítés után értenének, hanem hogy „létezilk olyan dolog, ami saját magától különbözik”. Egy ilyen jelentésváltozás nem szándékolt, ezért tiltjuk el az példában végrehajtott következtetést.

Modellelméleti szemantika

Alfred Tarski az 1930-as években adott először osztályelméleti jelentést a kvantoroknak. Ennek szellemében, legyen $\scriptstyle {{\mathfrak {M}}=(M,(f_{i})_{i\in I},(r_{j})_{j\in J},(c_{k})_{k\in K})}$ modellje egy $\scriptstyle {\mathcal {L}}$ elsőrendű nyelvnek. Adott φ formulára, az i-edik v_i változójelre és adott a=(a₁, a₂,...) ∈ M^ω végtelen értékeléssorozatra fennáll, hogy

${\mathfrak {M}}\models (\forall v_{i})\varphi [a]$

azaz „(∀v_i)φ igaz az a értékelés szerint”, pontosan akkor, ha

minden u ∈ M-re ${\mathfrak {M}}\models \varphi [a_{i}^{u}]$

azaz akármilyen értéket adva az a i-edik elemének az így létrejövő értékelés szerint is igaz a φ formula az $\scriptstyle {\mathfrak {M}}$ modellben.

Kapcsolata az ∧ konnektívummal

Az univerzális kvantor működésében rokonítható az „és” szót megjelenítő ∧ logikai konjunkcióval: ∀ bizonyos értelemben egy végtelen konjunkciónak felel meg. Véges modell esetén előállítható a modellnek olyan bővítése, mely konjunkcióvá alakítja az univerzális formulákat. Ha $\scriptstyle {\mathfrak {M}}$ véges modell, $\scriptstyle {{\mathcal {L}}_{M}={\mathcal {L}}\cup \{c_{m}\}_{m\in M}}$ bővített nyelvben az új konstansok {c_m}_m∈M halmaza |M| elemszámú és $\scriptstyle {({\mathfrak {M}},m)_{m\in M}}$ az $\scriptstyle {{\mathcal {L}}_{M}}$ nyelv azon modellje, mely $\scriptstyle {\mathfrak {M}}$-nek bővítése és melyben az új konstansok különböző M-beli értékeket vesznek fel, akkor

$({\mathfrak {M}},m)_{m\in M}\models (\forall x)\varphi (x)\quad \quad \Longleftrightarrow \quad \quad ({\mathfrak {M}},m)_{m\in M}\models \bigwedge \limits _{m\in M}\varphi (c_{m})$

Ha a konstansokat beszámozzuk: {u_k}_k=1...n={c_m}_m∈M, akkor tehát

$(\forall x)\varphi (x)\quad \quad \Longleftrightarrow \quad \quad \varphi (u_{1})\wedge \varphi (u_{2})\wedge ...\wedge \varphi (u_{n})$

a mondott modellben. Tehát a „12. a. osztály minden tanulója ötöst kapott” mondat ekvivalens azzal, hogy „Almási Anna ötöst kapott és Bán Balázs ötöst kapott és ... és Zoltán Zsófi ötöst kapott.”.

A jobb oldali formula általában nem írható fel a nyelvben. Egyrészt nem biztos, hogy egy modellben minden elem meg van nevezve, másrészt ha ez igaz is lenne, végtelen modellben végtelen hosszú formulát kellene felírni, ami nincs.

Algebrai modellelméleti szemantika

Ha $\scriptstyle {\mathbf {A} =(A,\cup ,\cap ,\setminus ,0,U^{\omega },\mathrm {C} _{i},\mathrm {d} _{ij})_{i,j\in \omega }}\in {\mathsf {Cs}}_{\omega }$ olyan cilindrikus halmazalgebra, mely reguláris és lokálisan véges dimenziós, akkor izomorfizmus erejéig egyértelműen megfeleltethető egy elsőrendű nyelv $\scriptstyle {\mathfrak {M}}$ modelljének. Ebben az algebrában a C cilindrifikáció lényegében az egzisztenciális kvantifikáció:

$X\in A:\quad \quad \mathrm {C} _{i}X=\{a:\omega \to U\mid (\exists u\in U)(b\in X:\quad b_{j}=a_{j}\quad (j\neq i),\;b_{i}=u)\}$

tehát, mely egy A-beli X sorozathalmazhoz azon sorozatok halmazát rendeli, melyek megváltoztathatók úgy, hogy még mindig X-ben legyenek.

Ez esetben az univerzális kvantor algebrai művelettel megfogalmazva:

$\mathrm {C} _{i}^{\partial }X=U^{\omega }\setminus \mathrm {C} _{i}(U^{\omega }\setminus X)$

(itt ∂ a C_i operátor duálisára utal.) Ezzel például a következő logikai azonosságok az alábbi algebrai alakot öltik:

$\mathrm {C} _{i}^{\partial }(X\cap Y)=(\mathrm {C} _{i}^{\partial }X)\cap (\mathrm {C} _{i}^{\partial }Y)\quad \quad \mathrm {minden} \;X,Y\in A$

$\mathrm {C} _{i}^{\partial }(X\cup Y)\supseteq (\mathrm {C} _{i}^{\partial }X)\cup (\mathrm {C} _{i}^{\partial }Y)\quad \quad \mathrm {minden} \;X,Y\in A$

Megjegyezzük, hogy a cilindrikus halmazalgebrák egyben Boole-halmazalgebrák is, annyiban többek, hogy a kvantifikációnak és az egyenlőségnek művelet is be van vezetve.

Logikai azonosságok

Tetszőleges modellben igazak ill. minden elméletben érvényesek a következő formulák:

$(\forall x)\varphi \leftrightarrow \neg (\exists x)\neg \varphi$

$(\forall x)(\forall y)\varphi \leftrightarrow (\forall y)(\forall x)\varphi$

$(\exists x)(\forall y)\varphi \rightarrow (\forall y)(\exists x)\varphi$

$(\forall x)(\varphi \wedge \psi )\leftrightarrow (\forall x)\varphi \wedge (\forall x)\psi$

$(\forall x)\varphi \vee (\forall x)\psi \rightarrow (\forall x)(\varphi \vee \psi )$

Továbbá, ha ψ-ben nem szerepel szabadon az x változó, akkor

$(\forall x)(\psi \vee \varphi )\leftrightarrow \psi \vee (\forall x)\varphi$

$(\forall x)(\psi \wedge \varphi )\leftrightarrow \psi \wedge (\forall x)\varphi$

Feltételes és halmazbeli univerzális kvantor

Ha ψ tetszőleges formula, akkor a ψ feltétel melletti univerzális kvantifikáció:

$(\forall _{\psi }x)\equiv (\forall x)(\psi \rightarrow \varphi )$

Speciálisan, ha a halmazelméletben ψ egy ' x ∈ H ' alakú formula, akkor az ezen feltétel melletti kvantort halmazbeli kvantornak nevezzük:

$(\forall x\in H)\varphi \equiv (\forall _{x\in H}x)\varphi$

Intuicionista univerzális kvantor

Az intuicionista logika univerzális kvantora (mint az összes többi logikai operátora) különbözik a klasszikus logika szerintitől. A klasszikus (∀x)φ jelentése, hogy az, hogy φ a tárgyalási univerzum minden elemére igaz. Ezzel szemben az intuicionista (∀x)φ egy jellegzetes interpretációja a Kolmogorov-féle feladatinterpretáció. Ebben a φ formulák paraméteres feladatok és a

(∀x)φ feladatot megoldani nem más, mint általános eljárást adni a φ(x) x-szel paraméterezett feladat megoldására (tehát az x paraméter minden értékére).

Ezt az interpretációt tekintve egyáltalán nem meglepő, hogy az intuicionista kvantifikációelméletben csak a következő formulák levezethetők:

$(\forall x)\varphi (x)\rightarrow \neg (\exists x)\neg \varphi (x)\,$

a ∀ megfogalmazhatósága egzisztenciális kvantorral csak negatív φ-re teljesül:

$(\forall x)\neg \varphi (x)\leftrightarrow \neg (\exists x)\varphi (x)\,$

$(\forall x)\neg \neg \varphi (x)\leftrightarrow \neg (\exists x)\neg \varphi (x)\,$

Hivatkozások

• Mendelson, Elliott, Introduction to Mathematical Logic, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, Calif. (1964) OCLC 13580200
• Ruzsa Imre–Máté András, Bevezetés a modern logikába, Budapest, Osiris Kiadó, 1997.
• Monk, J. Donald, An introduction to cylindric set algebras (with an appendix by H. Andreka) Logic Journal of the IGPL 8 (2000), pp. 451–506. online