Universell kvantifiering - Universal quantification

I matematisk logik är en universell kvantifiering en typ av kvantifierare , en logisk konstant som tolkas som "given any" eller "for all". Det uttrycker att ett predikat kan uppfyllas av varje medlem i en diskursdomän . Med andra ord är det predikationen av en egendom eller relation till varje medlem av domänen. Det hävdar att ett predikat inom ramen för en universell kvantifierare är sant för varje värde i en predikatvariabel .

Det är vanligtvis betecknas med vände A (∀) logisk operator symbol , som, när de används tillsammans med ett predikat variabel, kallas en universellt kvantifierare ( " ∀ x ", ' ∀ ( x ) ', eller ibland med " ( x ) "ensam). Universell kvantifiering skiljer sig från existentiell kvantifiering ("det existerar"), som endast hävdar att egenskapen eller förhållandet gäller för minst en medlem av domänen.

Kvantifiering i allmänhet behandlas i artikeln om kvantifiering (logik) . Den universella kvantifieraren är kodad som U + 2200 ∀ FÖR ALLA i Unicode , och som \foralli LaTeX och relaterade formelredigerare,

Grunderna

Antag att det ges det

2 · 0 = 0 + 0 och 2 · 1 = 1 + 1 och 2 · 2 = 2 + 2 , etc.

Detta verkar vara en logisk sammankoppling på grund av den upprepade användningen av "och". Men "etc." kan inte tolkas som en sammankoppling i formell logik . Istället måste uttalandet omformuleras:

För alla naturliga tal n har man 2 · n = n + n .

Detta är ett enda uttalande med universell kvantifiering.

Detta uttalande kan sägas vara mer exakt än det ursprungliga. Medan "etc." informellt inkluderar naturliga tal , och ingenting mer, detta gavs inte rigoröst. I den universella kvantifieringen nämns å andra sidan de naturliga siffrorna uttryckligen.

Detta speciella exempel är sant , eftersom valfritt naturligt tal kan ersättas med n och uttalandet "2 · n = n + n " skulle vara sant. I kontrast,

För alla naturliga tal n har man 2 · n > 2 + n

är falskt , för om n ersätts med till exempel 1, är påståendet "2 · 1> 2 + 1" falskt. Det är oväsentligt att "2 · n > 2 + n " är sant för de flesta naturliga tal n : även förekomsten av ett enda motexempel räcker för att bevisa att den universella kvantifieringen är falsk.

Å andra sidan, för alla sammansatta tal n har man 2 · n > 2 + n är sant, eftersom inget av motexemplen är sammansatta tal. Detta indikerar vikten av diskursens domän , som anger vilka värden n kan ta. Observera i synnerhet att om diskursens område är begränsat till att endast bestå av de objekt som uppfyller ett visst predikat, så för universell kvantifiering kräver detta en logisk villkor . Till exempel,

För alla sammansatta tal n har man 2 · n > 2 + n

är logiskt sett lika med

För alla naturliga tal n , om n är sammansatt, då 2 · n > 2 + n .

Här anger "om ... då" -konstruktionen det logiska villkoret.

Notation

I symbolisk logik används den universella kvantifieringssymbolen (ett vänt " A " i ett sans-serif- teckensnitt, Unicode U + 2200) för att indikera universell kvantifiering. Den användes först på detta sätt av Gerhard Gentzen 1935, i analogi med Giuseppe Peano : s (vände E) notation för existentiell kvantifiering och senare användning av Peano notation av Bertrand Russell . ${\ displaystyle \ forall}$${\ displaystyle \ existerar}$

Till exempel, om P ( n ) är predikatet "2 · n > 2 + n " och N är uppsättningen naturliga tal, då

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

är (falskt) uttalande

"för alla naturliga tal n har man 2 · n > 2 + n ".

På samma sätt, om Q ( n ) är predikatet " n är sammansatt", då

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

är (sant) uttalande

"för alla naturliga tal n , om n är sammansatt, då 2 · n > 2 + n ".

Flera variationer i kvantifieringsnotationen (som gäller alla former) finns i kvantifieringsartikeln .

Egenskaper

Negation

Negationen av en universellt kvantifierad funktion erhålls genom att ändra den universella kvantifieraren till en existentiell kvantifierare och negera den kvantifierade formeln. Det är,

${\ displaystyle \ lnot \ forall x \; P (x) \ quad {\ text {motsvarar}} \ quad \ existerar x \; \ lnot P (x)}$

där betecknar negation . ${\ displaystyle \ lnot}$

Till exempel, om P ( x ) är den föreslagna funktionen " x är gift", för uppsättningen X för alla levande människor, den universella kvantifieringen

Med tanke på vilken levande person som helst x är personen gift

är skrivet

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

Detta uttalande är falskt. Sanningsenligt sägs det

Det är inte så att, med tanke på någon levande person x , den personen är gift

eller symboliskt:

${\ displaystyle \ lnot \ \ forall x \ i X \, P (x)}$.

Om funktionen P ( x ) inte är sant för varje element i X måste det finnas minst ett element för vilket uttalandet är falskt. Det vill säga negationen av är logiskt sett ekvivalent med "Det finns en levande person x som inte är gift", eller: ${\ displaystyle \ forall x \ i X \, P (x)}$

${\ displaystyle \ existerar x \ i X \, \ lnot P (x)}$

Det är felaktigt att förväxla "alla personer är inte gifta" (dvs. "det finns ingen person som är gift") med "inte alla personer är gifta" (dvs. "det finns en person som inte är gift"):

${\ displaystyle \ lnot \ \ existerar x \ i X \, P (x) \ equiv \ \ forall x \ i X \, \ lnot P (x) \ inte \ equiv \ \ lnot \ \ forall x \ i X \ , P (x) \ equiv \ \ existerar x \ i X \, \ lnot P (x)}$

Andra anslutningar

Den universella (och existentiella) kvantifieraren rör sig oförändrad över de logiska anslutningarna ∧ , ∨ , → och ↚ , så länge den andra operanden inte påverkas; det är:

${\ displaystyle {\ begin {align} P (x) \ land (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)) \\ P (x) \ lor (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {y} {\ in} \ mathbf {Y} \, (P (x) \ lor Q (y)), & {\ text {förutsatt att}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ till (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {y} {\ in} \ mathbf {Y} \, (P (x) \ till Q (y)), & {\ text {förutsatt att}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ nleftarrow (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {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)), och {\ text {förutsatt att}} \ 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 \ \ all {y} {\ in} \ mathbf {Y} \, (P (x) \ till Q (y)) \\ P (x) \ nleftarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ nleftarrow Q (y)), & {\ text {förutsatt att}} \ mathbf {Y} \ neq \ emptyset \ end {aligned} }}$

Omvänt, för de logiska anslutningarna ↑ , ↓ , ↛ och ← vänder kvantifierarna:

${\ displaystyle {\ begin {align} P (x) \ uparrow (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)) \\ P (x) \ downarrow (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ downarrow Q (y)), & {\ text {förutsatt att}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ nrightarrow (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ nrightarrow Q (y)), & {\ text {förutsatt att}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ gets (\ existerar {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ får Q (y)) \\ P (x) \ uparrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)), och {\ text {förutsatt att}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ downarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {y} {\ in} \ mathbf {Y} \, (P (x) \ downarrow Q (y)) \\ P (x) \ nrightarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {y} {\ in} \ mathbf {Y} \, (P (x) \ nrightarrow Q (y)) \\ P (x) \ får ( \ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ existerar {y} {\ in} \ mathbf {Y} \, (P (x) \ får Q ( y)), och {\ text {förutsatt att}} \ mathbf {Y} \ neq \ emptyset \\\ slut {justerad}}}$

Slutsatsregler

En slutsats är en regel som motiverar ett logiskt steg från hypotes till slutsats. Det finns flera slutsatser som använder den universella kvantifieraren.

Universell instansiering drar slutsatsen att, om den propositionella funktionen är känd för att vara universellt sant, så måste den vara sant för alla godtyckliga delar av diskursens universum. Symboliskt representeras detta som

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

där c är ett helt godtyckligt element i diskursens universum.

Universell generalisering avslutar att den propositionella funktionen måste vara universell sant om den är sant för något godtyckligt element i diskursens universum. Symboliskt, för en godtycklig c ,

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

Elementet  c måste vara helt godtyckligt; annars följer inte logiken: om c inte är godtyckligt och istället är ett specifikt element i diskursens universum, så innebär P ( c ) bara en existentiell kvantifiering av den propositionella funktionen.

Den tomma uppsättningen

Enligt konvention är formeln alltid sant, oavsett formel P ( x ); se vakuum sanning . ${\ displaystyle \ forall {x} {\ in} \ emptyset \, P (x)}$

Universell stängning

Den universella stängningen av en formel φ är formeln utan fria variabler erhållna genom att lägga till en universell kvantifierare för varje ledig variabel i φ. Till exempel den universella stängningen av

${\ displaystyle P (y) \ land \ existerar xQ (x, z)}$

är

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

Som angränsande

I kategoriteori och teorin om elementär topoi kan den universella kvantifieraren förstås som rätt angränsning mellan en funktion mellan kraftuppsättningar , den inversa bildfunktionen för en funktion mellan uppsättningar; på samma sätt är den existentiella kvantifieraren den vänstra gränsen .

För en uppsättning , låt beteckna dess powerset . För varje funktion mellan seten och det finns en omvänd bild funktor mellan powersets, som tar delmängder av Målmängd av f tillbaka till delmängder av sin domän. Den vänstra gränsen till denna funktion är den existentiella kvantifieraren och den högra anslutningen är den universella kvantifieraren . ${\ displaystyle X}$${\ displaystyle {\ mathcal {P}} X}$${\ displaystyle f: X \ till Y}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle f ^ {*}: {\ mathcal {P}} Y \ till {\ mathcal {P}} X}$${\ displaystyle \ existerar _ {f}}$${\ displaystyle \ forall _ {f}}$

Det vill säga är en funktion som för varje delmängd ger den delmängd som ges av ${\ displaystyle \ existerar _ {f} \ kolon {\ mathcal {P}} X \ till {\ mathcal {P}} Y}$${\ displaystyle S \ delmängd X}$${\ displaystyle \ existerar _ {f} S \ delmängd Y}$

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

de i bilden av under . På samma sätt är den universella kvantifieraren en funktion som för varje delmängd ger den delmängd som ges av ${\ displaystyle y}$${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle \ forall _ {f} \ colon {\ mathcal {P}} X \ till {\ mathcal {P}} Y}$${\ displaystyle S \ delmängd X}$${\ displaystyle \ forall _ {f} S \ delmängd Y}$

${\ displaystyle \ forall _ {f} S = \ {y \ i Y \; | \; \ forall x \ i X. \ f (x) = y \ quad \ innebär \ quad x \ i S \},}$

de vars preimage under finns i . ${\ displaystyle y}$${\ displaystyle f}$${\ displaystyle S}$

Den mer välbekanta formen av kvantifierarna som används i första ordningens logik erhålls genom att ta funktionen f till den unika funktionen så att det är tvåelementuppsättningen som håller värdena sanna och falska, en delmängd S är den delmängd för vilken predikat innehar, och ${\ displaystyle!: X \ till 1}$${\ displaystyle {\ mathcal {P}} (1) = \ {T, F \}}$ ${\ displaystyle S (x)}$

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

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

vilket är sant om det inte är tomt, och ${\ displaystyle S}$

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

vilket är falskt om S inte är X.

De universella och existentiella kvantifierarna som anges ovan generaliserar till kategorin för föring .

Se även

• Existentiell kvantifiering
• Första ordningens logik
• Lista över logiska symboler — för Unicode-symbolen ∀

Anteckningar

Referenser

• Hinman, P. (2005). Grundläggande för matematisk logik . AK Peters . ISBN 1-56881-262-0.
• Franklin, J. och Daoud, A. (2011). Bevis i matematik: en introduktion . Kew Books. ISBN 978-0-646-54509-7.CS1 maint: flera namn: författarlista ( länk ) (kap. 2)

externa länkar

• Ordboksdefinitionen av varje på Wiktionary