Univerzális számszerűsítés - Universal quantification

A matematikai logikában az univerzális kvantifikáció egyfajta kvantor , egy logikai állandó, amelyet úgy értelmeznek , hogy "adott minden" vagy "mindenki számára". Azt fejezi ki, hogy a predikátum lehet elégedett a minden tagja egy domain a diskurzus . Más szóval, ez egy tulajdonság vagy reláció predikciója a tartomány minden tagjával. Azt állítja, hogy az univerzális kvantor hatókörébe tartozó predikátum igaz egy predikátum változó minden értékére .

Általában a megfordult A (∀) logikai operátor szimbólummal jelölik , amelyet predikátum változóval együtt használva univerzális kvantornak (" $\forall x$ ", " $\forall (x)$ ", vagy néha " $(x)$ nevezzük $.$ " egyedül). Az univerzális kvantifikáció különbözik az egzisztenciális kvantifikálástól ("létezik"), amely csak azt állítja, hogy a tulajdonság vagy reláció a tartomány legalább egy tagjára vonatkozik.

A számszerűsítést általában a számszerűsítésről szóló cikk (logika) tárgyalja . Az univerzális kvantor U + 2200 ∀ FOR ALL kódolású az Unicode-ban , valamint \foralla LaTeX és a kapcsolódó képletszerkesztőkben,

Alapok

Tegyük fel, hogy ezt megadják

2 · 0 = 0 + 0 és 2 · 1 = 1 + 1, és 2 · 2 = 2 + 2 stb.

Ez logikus összefüggésnek tűnik a "és" ismételt használata miatt. Azonban az "stb." nem értelmezhető együttesként a formális logikában . Ehelyett az állítást át kell fogalmazni:

Valamennyi n természetes szám esetén az egyik értéke 2 · n = n + n .

Ez egyetlen állítás, amely egyetemes számszerűsítést használ.

Ez a megállapítás pontosabbnak mondható, mint az eredeti. Míg az "stb." informálisan tartalmazza a természetes számokat , és semmi mást, ezt nem adták meg szigorúan. Az egyetemes számszerűsítésben viszont kifejezetten megemlítik a természetes számokat.

Ez a példa igaz , mert bármely természetes szám helyettesíthető n-vel, és a "2 · n = n + n " állítás igaz lenne. Ellentétben,

Valamennyi n természetes szám esetén az egyik értéke 2 · n > 2 + n

jelentése hamis , mert ha n van helyettesítve, például, 1, a kimutatás "2 · 1> 2 + 1" hamis. Lényegtelen, hogy a "2 · n > 2 + n " a legtöbb n természetes számra igaz : még egyetlen ellenpélda megléte is elegendő az egyetemes kvantifikáció hamis bizonyításához.

Másrészt az összes n összetett számra az egyik 2 · n > 2 + n igaz, mert az ellenpéldák egyike sem összetett szám. Ez jelzi a diskurzus területének fontosságát , amely meghatározza, hogy mely értékeket vehetjük át n . Különösen vegye figyelembe, hogy ha a diskurzus tartománya csak azokból az objektumokból áll, amelyek kielégítenek egy bizonyos predikátumot, akkor az univerzális számszerűsítéshez logikai feltételre van szükség . Például,

Minden n összetett szám esetében az egyik értéke 2 · n > 2 + n

a logikailag ekvivalens a

Minden n természetes szám esetén , ha n összetett, akkor 2 · n > 2 + n .

Itt a "ha ... akkor" konstrukció jelzi a logikai feltételet.

Jelölés

A szimbolikus logikában az univerzális kvantor szimbólum (fordított " A " sans-serif betűtípussal, Unicode U + 2200) az univerzális kvantifikáció jelzésére szolgál. Ez volt az első ilyen módon felhasznált által Gerhard Gentzen 1935, hasonlóan Giuseppe Peano „s (fordult E) jelölését egzisztenciális mennyiségi és a későbbi felhasználásra Peano féle függvénnyel Bertrand Russell . ${\ displaystyle \ forall}$ ${\ displaystyle \ létezik}$

Például, ha a P ( n ) a predikátum „2 · n > 2 + n ”, és N jelentése a halmaza a természetes számok, akkor

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

a (hamis) állítás

"minden n természetes számra az egyik 2 · n > 2 + n ".

Hasonlóképpen, ha Q ( n ) az " n összetett" állítmány , akkor

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

az (igaz) állítás

"minden n természetes számra , ha n összetett, akkor 2 · n > 2 + n ".

A számszerűsítés jelölésében (amely minden formára vonatkozik) számos variáció található a Kvantáló cikkben.

Tulajdonságok

Tagadás

Az univerzálisan számszerűsített függvény tagadását úgy kapjuk meg, hogy az univerzális kvantumort egzisztenciális kvantorrá változtatjuk, és a kvantifikált képletet tagadjuk. Vagyis

{\ displaystyle \ lnot \ forall x \; P (x) \ quad {\ text {egyenértékű}} \ quad \ pastāv x \; \ lnot P (x)}

ahol negációt jelöl . ${\ displaystyle \ lnot}$

Például, ha $a P (x)$ a propozicionális funkció „ $x$ házas”, akkor a halmaz $X$ minden élő emberi lény, az univerzális mennyiségi

Bármely $x$ élő emberre tekintettel ez a személy házas

meg van írva

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

Ez az állítás hamis. Igazság szerint azt állítják

Nem arról van szó, hogy bármely élő $x$ emberre való tekintettel ez a személy házas

vagy szimbolikusan:

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

.

Ha a $P (x)$ függvény nem minden $X$ elemre igaz , akkor legalább egy olyan elemnek kell lennie, amelyre az állítás hamis. Vagyis a tagadás logikailag egyenértékű a következővel: "Van $x$ élő személy, aki nem házas", vagy: ${\ displaystyle \ forall x \ in X \, P (x)}$

{\ displaystyle \ létezik x \ X-ben \, \ lnot P (x)}

Hibás összetéveszteni "minden ember nem házas" (azaz "nincs olyan személy, aki házas lenne") és "nem minden ember házas" (azaz "van olyan személy, aki nem házas"):

{\ displaystyle \ lnot \ \ létezik x \ X-ben \, P (x) \ equiv \ \ forall x \ X-ben \, \ lnot P (x) \ not \ equiv \ \ lnot \ \ allall x \ X-ben \ , P (x) \ equiv \ \ létezik x \ X-ben, \ n P (x)}

Egyéb csatlakozók

Az univerzális (és egzisztenciális) kvantor változatlanul mozog a ∧ , ∨ , → és logical logikai kapcsolatok között , mindaddig , amíg a másik operandus nincs hatással; vagyis:

{\ displaystyle {\ begin {aligned} P (x) \ land (\ pastāv {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)) \\ P (x) \ lor (\ létezik {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ lor Q (y)) és {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ emptyyset \\ P (x) \ to (\ létezik {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ - Q (y)), és {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ tyhjyset \\ P (x) \ nlearrow (\ létezik {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ nbaloldali Q (y)) \\ P (x) \ land (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)), és a {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ emptyyset \\ P (x) \ lor (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ összes {y} {\ in} \ mathbf {Y} \, (P (x) \ lor Q (y)) \\ P (x) \ to (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ összes {y} {\ in} \ mathbf {Y} \, (P (x) \ - Q (y)) \\ P (x) \ nlearrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ összes {y} {\ in} \ mathbf {Y} \, (P (x) \ noldalsó Q (y)) és {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ emptyyset \ end {igazítva} }}

Ezzel szemben a ↑ , ↓ , ↛ és ← logikai kapcsolatoknál a kvantorok elfordulnak :

{\ displaystyle {\ begin {aligned} P (x) \ felfelé (\ létezik {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ összes {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)) \\ P (x) \ downarrow (\ pastāv {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ összes {y} {\ in} \ mathbf {Y} \, (P (x) \ lefelé mutató Q (y)) és {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ emptyyset \\ P (x) \ nrarkony (\ létezik {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ mind {y} {\ in} \ mathbf {Y} \, (P (x) \ nregyenes Q (y)), és a {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ emptyyset \\ P (x) \ get (\ létezik {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ mind {y} {\ in} \ mathbf {Y} \, (P (x) \ kap Q (y)) \\ P (x) \ felfelé (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ felfelé Q (y)), és a {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ emptyyset \\ P (x) \ lefelé (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ lefelé mutató Q (y)) \\ P (x) \ nrightarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ noightarrow Q (y)) \\ P (x) \ get ( \ forall {y} {\ in} \ mathbf {Y} \, Q (y)) és \ equiv \ \ létezik {y} {\ in} \ mathbf {Y} \, (P (x) \ Q-t kap ( y)), és a {\ text {feltéve, hogy}} \ mathbf {Y} \ neq \ emptyyset \\\ end {igazítva}}}

A következtetés szabályai

A következtetési szabály olyan szabály, amely igazolja a hipotézistől a következtetésig tartó logikus lépést. Számos következtetési szabály létezik, amelyek az univerzális kvantort használják.

Az univerzális példányosítás arra a következtetésre jut, hogy ha a propozíciós függvényről ismert, hogy univerzálisan igaz, akkor annak igaznak kell lennie a diskurzus univerzumának bármely önkényes elemére. Jelképesen ez a következőképpen van ábrázolva

{\ displaystyle \ forall {x} {\ in} \ mathbf {X} \, P (x) \ - P (c)}

ahol c a diskurzus univerzumának teljesen önkényes eleme.

Az egyetemes általánosítás arra a következtetésre jut, hogy a propozíciós funkciónak egyetemesen igaznak kell lennie, ha ez igaz a diskurzus univerzumának tetszőleges elemére. Jelképesen, egy tetszőleges c esetén

{\ displaystyle P (c) \ to \ \ allall {x} {\ in} \ mathbf {X} \, P (x).}

A c elemnek teljesen önkényesnek kell lennie; máskülönben a logika nem következik: ha c nem önkényes, és ehelyett a diskurzus univerzumának sajátos eleme, akkor P ( c ) csak a propozíciós függvény egzisztenciális számszerűsítését jelenti.

Az üres készlet

Megállapodás szerint a képlet mindig igaz, függetlenül a P ( x ) képlettől ; lássa az ürességes igazságot . ${\ displaystyle \ forall {x} {\ in} \ emptyyset \, P (x)}$

Univerzális zárás

A φ képlet univerzális lezárása az a képlet, amely nem tartalmaz szabad változót , ha egyetemes kvantort adunk hozzá minden universal szabad változóhoz. Például a

{\ displaystyle P (y) \ land \ létezik xQ (x, z)}

van

{\ displaystyle \ forall y \ forall z (P (y) \ land \ létezik xQ (x, z))}

.

Mint mellék

A kategóriában elmélet és az elmélet elemi toposzok , az univerzális kvantor lehet értelmezni, mint a jobb adjoint egy funktorhoz közötti teljesítmény-készletek , a fordított kép funktorhoz függvény sorozatok között; hasonlóképpen az egzisztenciális kvantor a bal oldali adjunktus .

Egy sor , hadd jelölik a PowerSet . Bármely funkcióhoz a halmazok között, és van egy inverz képfunkció a PowerSet között, amely visszaviszi az f kodomén részhalmazait a tartományának részhalmazaiba. Ennek a funkciónak a bal oldali melléke az egzisztenciális kvantor , a jobb oldali pedig az univerzális kvantor . ${\ displaystyle X}$ ${\ displaystyle {\ mathcal {P}} X}$ ${\ displaystyle f: X \ - Y}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle f ^ {*}: {\ mathcal {P}} Y \ - {\ mathcal {P}} X}$ ${\ displaystyle \ létezik _ {f}}$ ${\ displaystyle \ forall _ {f}}$

Vagyis egy olyan funkció, amely minden részhalmazra megadja az által megadott részhalmazt ${\ displaystyle \ pastāv _ {f} \ kettőspont {\ mathcal {P}} X \ to {\ mathcal {P}} Y}$ ${\ displaystyle S \ X részhalmaz}$ ${\ displaystyle \ létezik _ {f} S \ Y részhalmaz$

{\ displaystyle \ pastāv _ {f} S = \ {y \ Y-ben \; | \; \ x-ben létezik X-ben. \ f (x) = y \ quad \ land \ quad x \ S-ben \},}

azok a kép alatt . Hasonlóképpen, az univerzális kvantor olyan funkció, amely minden részhalmazra megadja az által megadott részhalmazt ${\ displaystyle y}$ ${\ displaystyle S}$ ${\ displaystyle f}$ ${\ displaystyle \ forall _ {f} \ kettőspont {\ mathcal {P}} X \ - {\ mathcal {P}} Y}$ ${\ displaystyle S \ X részhalmaz}$ ${\ displaystyle \ forall _ {f} S \ Y részhalmaz$

{\ displaystyle \ forall _ {f} S = \ {y \ Y-ben \; | \; \ forall x \ X-ben. \ f (x) = y \ quad \ implicit \ quad x \ S-ben \},}

azok, akiknek előzetes képét a . ${\ displaystyle y}$ ${\ displaystyle f}$ ${\ displaystyle S}$

A kvantoroknak az elsőrendű logikában használt ismertebb formáját úgy kapjuk meg, hogy az f függvényt vesszük egyedi függvénynek , vagyis az igaz és hamis értékeket tartó kételemes halmaz, az S részhalmaz pedig az a részhalmaz, amelyre a állítmány megtartja, és ${\ displaystyle!: X \ to 1}$ ${\ displaystyle {\ mathcal {P}} (1) = \ {T, F \}}$ ${\ displaystyle S (x)}$