Eksistensiell kvantifisering - Existential quantification

I predikatlogikk er en eksistensiell kvantifisering en type kvantifiserende , en logisk konstant som tolkes som "det eksisterer", "det er minst en" eller "for noen". Det er vanligvis betegnet med logisk operator symbol ∃, som, når det brukes sammen med et predikat variabel, kalles et eksistens kvantifikator ( " $\exists x$ 'eller' $\exists (x)$ "). Eksistensiell kvantifisering er forskjellig fra universell kvantifisering ("for alle"), som hevder at eiendommen eller relasjonen gjelder for alle medlemmer av domenet. Noen kilder bruker begrepet eksistensialisering for å referere til eksistensiell kvantifisering.

Grunnleggende

Tenk på en formel som sier at et naturlig tall multiplisert med seg selv er 25.

0 · 0 = 25, eller 1 · 1 = 25, eller 2 · 2 = 25, eller 3 · 3 = 25, og så videre.

Dette ser ut til å være en logisk sondring på grunn av gjentatt bruk av "eller". Imidlertid gjør "og så videre" dette umulig å integrere og tolke det som en disjunksjon i formell logikk . I stedet kan uttalelsen omformuleres mer formelt som

For et naturlig tall n , n · n = 25.

Dette er en enkelt setning som bruker eksistensiell kvantifisering.

Denne uttalelsen er mer presis enn den opprinnelige, siden uttrykket "og så videre" ikke nødvendigvis inkluderer alle naturlige tall og utelukker alt annet. Og siden domenet ikke ble angitt eksplisitt, kunne uttrykket ikke tolkes formelt. I den kvantifiserte uttalelsen nevnes imidlertid de naturlige tallene eksplisitt.

Dette eksemplet er sant, fordi 5 er et naturlig tall, og når vi erstatter 5 med n , produserer vi "5 · 5 = 25", noe som er sant. Det spiller ingen rolle at " n · n = 25" bare er sant for et enkelt naturlig tall, 5; selv eksistensen av en enkelt løsning er nok til å bevise at denne eksistensielle kvantifiseringen er sann. I kontrast er "For noen partall n , n · n = 25" usant, fordi det ikke er noen jevne løsninger.

Den domene av tale , som angir verdiene den variable n tillates å finne, er derfor avgjørende for en setningens riktighet eller falseness. Logiske konjunksjoner brukes til å begrense diskursområdet til å oppfylle et gitt predikat. For eksempel:

For noen positive oddetall n , n · n = 25

er logisk ekvivalent til

For et naturlig tall n er n oddetall og n · n = 25.

Her er "og" den logiske sammenhengen.

I symbolisk logikk brukes "∃" (en rotert bokstav " E ", i en sans-serif- skrift) for å indikere eksistensiell kvantifisering. Så hvis P ( a , b , c ) er predikatet " a · b = c", og er settet med naturlige tall, så ${\ displaystyle \ mathbb {N}}$

{\ displaystyle \ finnes {n} {\ in} \ mathbb {N} \, P (n, n, 25)}

er det (sanne) utsagnet

For et naturlig tall n , n · n = 25.

Tilsvarende, hvis Q ( n ) er predikatet " n er jevnt", da

{\ displaystyle \ finnes {n} {\ in} \ mathbb {N} \, {\ big (} Q (n) \; \! \; \! {\ wedge} \; \! \; \! P ( n, n, 25) {\ big)}}

er (falsk) påstand

For et naturlig tall n er n jevn og n · n = 25.

I matematikk kan beviset på et "noen" utsagn oppnås enten ved et konstruktivt bevis , som viser et objekt som tilfredsstiller "noe" utsagnet, eller ved et ikke -konstruktivt bevis , som viser at det må være et slikt objekt, men uten å vise et .

Eiendommer

Negasjon

En kvantifisert proposisjonsfunksjon er et utsagn; dermed, i likhet med utsagn, kan kvantifiserte funksjoner negeres. Den symbolet brukes til å betegne negasjon. ${\ displaystyle \ lnot \}$

For eksempel, hvis P ( x ) er predikatet " x er større enn 0 og mindre enn 1", så eksisterer den eksistensielle kvantifiseringen "Det finnes et naturlig tall x som er større enn for et diskursområde X for alle naturlige tall. 0 og mindre enn 1 "kan symbolsk angis som:

{\ displaystyle \ finnes {x} {\ in} \ mathbf {X} \, P (x)}

Dette kan påvises å være feil. Sannferdig må det sies: "Det er ikke slik at det er et naturlig tall x som er større enn 0 og mindre enn 1", eller symbolsk:

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

.

Hvis det ikke er noe element i diskursområdet som utsagnet er sant for, må det være feil for alle disse elementene. Det vil si negasjonen av

{\ displaystyle \ finnes {x} {\ in} \ mathbf {X} \, P (x)}

er logisk ekvivalent med "For et naturlig tall x er x ikke større enn 0 og mindre enn 1", eller:

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

Generelt er negasjonen av en eksistensiell kvantifisering av en proposisjonsfunksjon en universell kvantifisering av den proposisjonelle funksjonens negasjon; symbolsk,

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

(Dette er en generalisering av De Morgans lover for å predikere logikk.)

En vanlig feil er å si at "alle personer er ikke gift" (dvs. "det eksisterer ingen som er gift"), når "ikke alle personer er gift" (dvs. "det eksisterer en person som ikke er gift") er ment :

{\ displaystyle \ lnot \ \ finnes {x} {\ in} \ mathbf {X} \, P (x) \ equiv \ \ forall {x} {\ in} \ mathbf {X} \, \ lnot P (x ) \ not \ equiv \ \ lnot \ \ forall {x} {\ in} \ mathbf {X} \, P (x) \ equiv \ \ finnes {x} {\ in} \ mathbf {X} \, \ lnot P (x)}

Negasjon kan også uttrykkes gjennom en uttalelse om "for nei", i motsetning til "for noen":

{\ displaystyle \ nexists {x} {\ in} \ mathbf {X} \, P (x) \ equiv \ lnot \ \ exist {x} {\ in} \ mathbf {X} \, P (x)}

I motsetning til den universelle kvantifisereren fordeler den eksistensielle kvantifisereren seg over logiske disjunksjoner:

${\ displaystyle \ exist {x} {\ in} \ mathbf {X} \, P (x) \ lor Q (x) \ to \ (\ exist {x} {\ in} \ mathbf {X} \, P (x) \ lor \ eksisterer {x} {\ in} \ mathbf {X} \, Q (x))}$

Inferensregler

En slutningsregel er en regel som begrunner et logisk skritt fra hypotese til konklusjon. Det er flere slutningsregler som bruker den eksistensielle kvantifisereren.

Eksistensiell introduksjon (∃I) konkluderer med at hvis proposisjonsfunksjonen er kjent for å være sann for et bestemt element i diskursområdet, må det være sant at det eksisterer et element som proposisjonsfunksjonen er sant for. Symbolsk,

{\ displaystyle P (a) \ to \ \ exist {x} {\ in} \ mathbf {X} \, P (x)}

Eksistensiell instantiering , når den utføres i et Fitch-fradrag, fortsetter ved å angi en ny underavledning mens den erstatter en eksistensielt kvantifisert variabel for et emne-som ikke vises i noen aktiv underavledning. Hvis en konklusjon kan nås innenfor denne underavledningen der det substituerte subjektet ikke vises, kan man gå ut av den deriveringen med den konklusjonen. Begrunnelsen bak eksistensiell eliminering (∃E) er som følger: Hvis det er gitt at det eksisterer et element som proposisjonsfunksjonen er sann for, og hvis en konklusjon kan nås ved å gi det elementet et vilkårlig navn, er den konklusjonen nødvendigvis sann , så lenge det ikke inneholder navnet. Symbolsk, for en vilkårlig c og for et forslag Q der c ikke vises:

{\ displaystyle \ finnes {x} {\ in} \ mathbf {X} \, P (x) \ to \ ((P (c) \ to \ Q) \ to \ Q)}

${\ displaystyle P (c) \ to \ Q}$ må være sant for alle verdier av c over samme domene X ; ellers følger ikke logikken: Hvis c ikke er vilkårlig, og i stedet er et spesifikt element i diskursdomenet, kan det å si P ( c ) uberettiget gi mer informasjon om det objektet.

Det tomme settet

Formelen er alltid usann, uavhengig av P ( x ). Dette er fordi det angir det tomme settet , og ingen x av noen beskrivelse - enn si et x som oppfyller et gitt predikat P ( x ) - eksisterer i det tomme settet. Se også Vacuous truth for mer informasjon. ${\ displaystyle \ exist {x} {\ in} \ emptyset \, P (x)}$ ${\ displaystyle \ emptyset}$

Som tilstøtende

I kategorien teori og teorien av elementære topoi kan eksistens kvantifikator forstås som den venstre adjungerte av en funktor mellom rotorsett , det inverse bildet funktor av en funksjon mellom settene; På samme måte er den universelle kvantifisereren den riktige adjointen .

Koding

I Unicode og HTML er symboler kodet U+ 2203 ∃ DET FINNES (HTML ∃ · ∃, &Exists; · som et matematisk symbol) og U+ 2204 ∄ DET FINNES IKKE (HTML ∄ · &nexist;, &nexists;, &NotExists; ).

I TeX er symbolet produsert med "\ exist".

Se også

Eksistensiell klausul
Eksistenssetning
Første ordens logikk
Lindström kvantifiser
Liste over logiske symboler - for unicode -symbolet ∃
Kvantifiseringsvarians
Kvantifiseringer
Unikhetskvantifisering
Universell kvantifisering

Merknader

^ ^a ^b "Omfattende liste over logiske symboler" . Math Vault . 06.04.2020 . Hentet 2020-09-04 .
^ "Predikater og kvantifisere" . www.csm.ornl.gov . Hentet 2020-09-04 .
^ "1.2 Kvantifiseringer" . www.whitman.edu . Hentet 2020-09-04 .
^ Allen, Colin; Hand, Michael (2001). Logic Primer . MIT Press. ISBN 0262303965.
^ Dette symbolet er også kjent som den eksistensielle operatøren . Det er noen ganger representert med V .
^ "Den definitive ordlisten for høyere matematisk sjargong: konstruktiv bevis" . Math Vault . 2019-08-01 . Hentet 2020-09-04 .
^ Saunders Mac Lane , Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 Se side 58

Referanser

Hinman, P. (2005). Grunnleggende om matematisk logikk . AK Peters. ISBN 1-56881-262-0.

[:0-1] "Omfattende liste over logiske symboler" . Math Vault . 06.04.2020 . Hentet 2020-09-04 .

[2] "Predikater og kvantifisere" . www.csm.ornl.gov . Hentet 2020-09-04 .

[3] "1.2 Kvantifiseringer" . www.whitman.edu . Hentet 2020-09-04 .

[4] Allen, Colin; Hand, Michael (2001). Logic Primer . MIT Press. ISBN 0262303965.

[5] Dette symbolet er også kjent som den eksistensielle operatøren . Det er noen ganger representert med V .

[6] "Den definitive ordlisten for høyere matematisk sjargong: konstruktiv bevis" . Math Vault . 2019-08-01 . Hentet 2020-09-04 .

[7] Saunders Mac Lane , Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 Se side 58

Languages

In other projects