Universel kvantificering - Universal quantification

I matematisk logik er en universel kvantificering en type kvantificering , en logisk konstant, der fortolkes som "givet enhver" eller "for alle". Det udtrykker, at et prædikat kan opfyldes af ethvert medlem af et diskursdomæne . Med andre ord er det forudsigelsen af en ejendom eller relation til hvert medlem af domænet. Det hævder, at et prædikat inden for rammerne af en universel kvantificering er sandt for enhver værdi af en prædikatvariabel .

Det betegnes normalt med det drejede A (∀) logiske operator- symbol , som, når det bruges sammen med en predikatvariabel, kaldes en universel kvantificeringsmåler (" ∀ x ", " ∀ ( x ) " eller undertiden med " ( x ) "alene). Universel kvantificering adskiller sig fra eksistentiel kvantificering ("der eksisterer"), som kun hævder, at ejendommen eller forholdet gælder for mindst et medlem af domænet.

Kvantificering generelt er omfattet af artiklen om kvantificering (logik) . Den universelle kvantificering er kodet som U + 2200 ∀ FOR ALLE i Unicode , og som \foralli LaTeX og relaterede formelredigerere,

Grundlæggende

Antag det er givet det

2 · 0 = 0 + 0 og 2 · 1 = 1 + 1 og 2 · 2 = 2 + 2 osv.

Dette ser ud til at være en logisk sammenhæng på grund af gentagen brug af "og". Dog "osv." kan ikke fortolkes som en sammenhæng i formel logik . I stedet skal erklæringen omformuleres:

For alle naturlige tal n har man 2 · n = n + n .

Dette er en enkelt udsagn ved hjælp af universel kvantificering.

Denne erklæring kan siges at være mere præcis end den oprindelige. Mens "osv." uformelt inkluderer naturlige tal , og intet mere, dette blev ikke strengt givet. I den universelle kvantificering nævnes derimod de naturlige tal eksplicit.

Dette særlige eksempel er sandt , fordi ethvert naturligt tal kunne erstattes af n, og udsagnet "2 · n = n + n " ville være sandt. I modsætning,

For alle naturlige tal n har man 2 · n > 2 + n

er falsk , for hvis n er substitueret med for eksempel 1, er udsagnet "2 · 1> 2 + 1" forkert. Det er uvæsentligt, at "2 · n > 2 + n " er sandt for de fleste naturlige tal n : selv eksistensen af ​​et enkelt modeksempel er nok til at bevise, at den universelle kvantificering er falsk.

På den anden side har man for alle sammensatte tal n 2 · n > 2 + n er sandt, fordi ingen af ​​modeksemplerne er sammensatte tal. Dette indikerer vigtigheden af diskursens domæne , som specificerer hvilke værdier n kan tage. Bemærk især, at hvis diskursdomænet kun er begrænset til at bestå af de objekter, der tilfredsstiller et bestemt predikat, så for universel kvantificering kræver dette en logisk betingelse . For eksempel,

For alle sammensatte tal n har man 2 · n > 2 + n

er logisk svarende til

For alle naturlige tal n , hvis n er sammensat, så er 2 · n > 2 + n .

Her angiver "hvis ... så" -konstruktionen den logiske betingelse.

Notation

I symbolisk logik bruges det universelle kvantificeringssymbol (en vendt " A " i en sans-serif- skrifttype, Unicode U + 2200) til at indikere universel kvantificering. Det blev første gang brugt på denne måde ved Gerhard Gentzen i 1935, i lighed med Giuseppe Peano 's (vendt E) notation for eksistenskvantor og den senere anvendelse af Peano s notation af Bertrand Russell . ${\ displaystyle \ forall}$${\ displaystyle \ findes}$

For eksempel, hvis P ( n ) er prædikatet "2 · n > 2 + n " og N er sættet med naturlige tal, så

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

er (falsk) udsagn

"for alle naturlige tal n har man 2 · n > 2 + n ".

Tilsvarende, hvis Q ( n ) er prædikatet " n er sammensat", så

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

er (sand) udsagn

"for alle naturlige tal n , hvis n er sammensat, så er 2 · n > 2 + n ".

Flere variationer i notationen til kvantificering (som gælder for alle former) kan findes i Quantifier- artiklen.

Ejendomme

Negation

Negationen af ​​en universelt kvantificeret funktion opnås ved at ændre den universelle kvantificering til en eksistentiel kvantificeringsenhed og negere den kvantificerede formel. Det er,

${\ displaystyle \ lnot \ forall x \; P (x) \ quad {\ text {svarer til}} \ quad \ eksisterer x \; \ lnot P (x)}$

hvor betegner negation . ${\ displaystyle \ lnot}$

For eksempel, hvis P ( x ) er den foreslåede funktion " x er gift", så for sæt X af alle levende mennesker, er den universelle kvantificering

Givet enhver levende person x , er personen gift

er skrevet

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

Denne erklæring er falsk. Sandfærdigt er det anført, at

Det er ikke tilfældet, givet den levende person x , at personen er gift

eller symbolsk:

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

Hvis funktionen P ( x ) ikke er sand for hvert element i X , skal der være mindst et element, som udsagnet er falsk for. Det vil sige, at negationen af svarer logisk til "Der findes en levende person x, som ikke er gift", eller: ${\ displaystyle \ forall x \ i X \, P (x)}$

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

Det er fejlagtigt at forveksle "alle personer er ikke gift" (dvs. "der findes ingen person, der er gift") med "ikke alle personer er gift" (dvs. "der findes en person, der ikke er gift"):

${\ displaystyle \ lnot \ \ findes x \ i X \, P (x) \ equiv \ \ forall x \ i X \, \ lnot P (x) \ ikke \ equiv \ \ lnot \ \ forall x \ i X \ , P (x) \ equiv \ \ eksisterer x \ i X \, \ likke P (x)}$

Andre forbindelser

Den universelle (og eksistentielle) kvantifier bevæger sig uændret på tværs af de logiske forbindelser ∧ , ∨ , → og ↚ , så længe den anden operand ikke påvirkes; det er:

${\ displaystyle {\ begin {justeret} P (x) \ land (\ eksisterer {y} {\ i} \ mathbf {Y} \, Q (y)) & \ equiv \ \ findes {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)) \\ P (x) \ lor (\ eksisterer {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ eksisterer {y} {\ in} \ mathbf {Y} \, (P (x) \ lor Q (y)), & {\ text {forudsat at}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ til (\ eksisterer {y} {\ i} \ mathbf {Y} \, Q (y)) & \ equiv \ \ findes {y} {\ i} \ mathbf {Y} \, (P (x) \ til Q (y)), og {\ text {forudsat at}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ nleftarrow (\ eksisterer {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ eksisterer {y} {\ in} \ mathbf {Y} \, (P (x) \ n venstrebånd Q (y)) \\ P (x) \ land (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)), og {\ text {forudsat at}} \ 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) \ til Q (y)) \\ P (x) \ nleftarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ nleftarrow Q (y)), & {\ text {forudsat at}} \ mathbf {Y} \ neq \ tomme sæt \ ende {justeret} }}$

Omvendt, for de logiske forbindelser ↑ , ↓ , ↛ og ← vender kvantifikatorerne:

${\ displaystyle {\ begin {align} P (x) \ uparrow (\ eksisterer {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)) \\ P (x) \ downarrow (\ eksisterer {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ downarrow Q (y)), & {\ text {forudsat at}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ nrightarrow (\ eksisterer {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ nrightarrow Q (y)), og {\ tekst {forudsat at}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ gets (\ exist {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 \ \ eksisterer {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)), og {\ text {forudsat at}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ downarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ eksisterer {y} {\ in} \ mathbf {Y} \, (P (x) \ nedadgående Q (y)) \\ P (x) \ nrightarrow (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ findes {y} {\ in} \ mathbf {Y} \, (P (x) \ nrightarrow Q (y)) \\ P (x) \ får ( \ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ equiv \ \ findes {y} {\ in} \ mathbf {Y} \, (P (x) \ får Q ( y)), & {\ text {forudsat at}} \ mathbf {Y} \ neq \ emptyset \\\ end {aligned}}}$

Inferensregler

En slutningsregel er en regel, der retfærdiggør et logisk trin fra hypotese til konklusion. Der er flere regler for slutning, som anvender den universelle kvantificeringsenhed.

Universel instantiering konkluderer, at hvis den foreslåede funktion vides at være universelt sand, så skal den være sand for ethvert vilkårligt element i diskursens univers. Symbolisk er dette repræsenteret som

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

hvor c er et helt vilkårligt element i diskursens univers.

Universal generalisering konkluderer, at den propositionelle funktion skal være universel sand, hvis den er sand for ethvert vilkårligt element i diskursens univers. Symbolsk for et vilkårligt c ,

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

Elementet  c skal være helt vilkårligt; ellers følger logikken ikke: hvis c ikke er vilkårlig og i stedet er et specifikt element i diskursuniverset, betyder P ( c ) kun en eksistentiel kvantificering af den propositionelle funktion.

Det tomme sæt

Efter konvention er formlen altid sand uanset formlen P ( x ); se ledig sandhed . ${\ displaystyle \ forall {x} {\ in} \ emptyset \, P (x)}$

Universal lukning

Den universelle lukning af en formel φ er formlen uden gratis variabler opnået ved at tilføje en universel kvantificering for hver gratis variabel i φ. For eksempel den universelle lukning af

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

er

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

Som sammenhængende

I kategoriteori og teorien om elementær topoi kan den universelle kvantificering forstås som den rigtige sammenhæng mellem en funktor mellem magt-sæt , den inverse billed- funktion af en funktion mellem sæt; Ligeledes er den eksistentielle kvantor er den venstre adjungerede .

Lad os betegne dets powerset for et sæt . For enhver funktion mellem sæt og der er et omvendt billede functor mellem powersets, der tager undergrupper af den codomain af f tilbage til delmængder af sit domæne. Den venstre adjoint af denne funktor er den eksistentielle kvantificering, og den højre adjoint er den universelle kvantificering . ${\ displaystyle X}$${\ displaystyle {\ mathcal {P}} X}$${\ displaystyle f: X \ til Y}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle f ^ {*}: {\ mathcal {P}} Y \ til {\ mathcal {P}} X}$${\ displaystyle \ eksisterer _ {f}}$${\ displaystyle \ forall _ {f}}$

Det vil sige, er en funktion, der for hvert delmængde giver den delmængde, der er givet af ${\ displaystyle \ eksisterer _ {f} \ kolon {\ mathcal {P}} X \ til {\ mathcal {P}} Y}$${\ displaystyle S \ delmængde X}$${\ displaystyle \ findes _ {f} S \ delmængde Y}$

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

dem i billedet af under . Tilsvarende er den universelle kvantificering en funktor, der for hver delmængde giver den delmængde, der er givet af ${\ displaystyle y}$${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle \ forall _ {f} \ colon {\ mathcal {P}} X \ til {\ mathcal {P}} Y}$${\ displaystyle S \ delmængde X}$${\ displaystyle \ forall _ {f} S \ subset Y}$

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

dem, hvis præbillede under er indeholdt i . ${\ displaystyle y}$${\ displaystyle f}$${\ displaystyle S}$

Den mere velkendte form af kvantificeringsanordningerne som brugt i førsteordenslogik opnås ved at tage funktionen f til at være den unikke funktion, så det er to-elementssættet, der holder værdierne sandt og falsk, en delmængde S er den delmængde, for hvilken prædikat holder, og ${\ displaystyle!: X \ til 1}$${\ displaystyle {\ mathcal {P}} (1) = \ {T, F \}}$ ${\ displaystyle S (x)}$

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

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

hvilket er sandt, hvis det ikke er tomt, og ${\ displaystyle S}$

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

hvilket er falsk, hvis S ikke er X.

Ovenstående universelle og eksistentielle kvantificeringsmidler generaliserer til kategorien presheaf .

Se også

• Eksistentiel kvantificering
• Førsteordens logik
• Liste over logiske symboler - til Unicode-symbolet ∀

Bemærkninger

Referencer

• Hinman, P. (2005). Grundlæggende om matematisk logik . AK Peters . ISBN 1-56881-262-0.
• Franklin, J. og Daoud, A. (2011). Bevis i matematik: en introduktion . Kew Books. ISBN 978-0-646-54509-7.CS1 maint: flere navne: forfatterliste ( link ) (kap.2)

eksterne links

• Ordbogens definition af hver på Wiktionary