Universelle Quantifizierung - Universal quantification

In der mathematischen Logik ist eine universelle Quantifizierung eine Art Quantifizierer , eine logische Konstante, die als "gegebenenfalls" oder "für alle" interpretiert wird . Es drückt aus, dass ein Prädikat von jedem Mitglied eines Diskursbereichs erfüllt werden kann . Mit anderen Worten, es ist die Prädikation einer Eigenschaft oder Beziehung zu jedem Mitglied der Domäne. Es behauptet, dass ein Prädikat im Geltungsbereich eines universellen Quantors für jeden Wert einer Prädikatsvariablen gilt .

Es wird in der Regel durch den bezeichnet gedreht A (∀) logisches Operator - Symbol , das, wenn es zusammen mit einem Prädikatenvariable verwendet wird , ist ein sogenannter Allquantor ( " ∀ x ", " ∀ ( x ) ", oder manchmal von " ( x ) „allein). Die universelle Quantifizierung unterscheidet sich von der existenziellen Quantifizierung ("es existiert"), die nur behauptet, dass die Eigenschaft oder Relation für mindestens ein Mitglied der Domäne gilt.

Die Quantifizierung im Allgemeinen wird im Artikel zur Quantifizierung (Logik) behandelt . Der universelle Quantor ist in Unicode als U+2200 ∀ FOR ALL codiert , und wie in LaTeX und verwandten Formeleditoren , \forall

Grundlagen

Angenommen, es ist gegeben, dass

2,0 = 0 + 0, und 2,1 = 1 + 1, und 2,2 = 2 + 2 usw.

Dies scheint aufgrund der wiederholten Verwendung von "und" eine logische Verbindung zu sein . Das "usw." kann in der formalen Logik nicht als Konjunktion interpretiert werden . Stattdessen muss die Aussage umformuliert werden:

Für alle natürlichen Zahlen n gilt 2· n = n + n .

Dies ist eine einzige Aussage mit universeller Quantifizierung.

Man kann sagen, dass diese Aussage genauer ist als die ursprüngliche. Während das "usw." informell natürliche Zahlen einschließt , und nicht mehr, dies wurde nicht rigoros gegeben. In der universellen Quantifizierung hingegen werden die natürlichen Zahlen explizit erwähnt.

Dieses spezielle Beispiel ist wahr , da n durch jede natürliche Zahl ersetzt werden könnte und die Aussage "2· n = n + n " wahr wäre. Im Gegensatz,

Für alle natürlichen Zahlen n gilt 2· n > 2 + n

ist falsch , weil , wenn n mit substituiert ist, zum Beispiel 1, die Aussage "2 · 1> 2 + 1" falsch ist. Es ist unerheblich, dass "2· n > 2 + n " für die meisten natürlichen Zahlen n gilt : Schon die Existenz eines einzigen Gegenbeispiels reicht aus, um die universelle Quantifizierung als falsch zu beweisen.

Andererseits gilt für alle zusammengesetzten Zahlen n 2· n > 2 + n , denn keines der Gegenbeispiele sind zusammengesetzte Zahlen. Dies weist auf die Bedeutung des Diskursbereichs hin , der angibt, welche Werte n annehmen kann. Beachten Sie insbesondere, dass, wenn der Diskursbereich darauf beschränkt ist, nur aus den Objekten zu bestehen, die ein bestimmtes Prädikat erfüllen, für die universelle Quantifizierung eine logische Bedingung erforderlich ist . Beispielsweise,

Für alle zusammengesetzten Zahlen n gilt 2· n > 2 + n

ist logisch äquivalent zu

Für alle natürlichen Zahlen n gilt , wenn n zusammengesetzt ist, 2· n > 2 + n .

Hier gibt die "wenn ... dann"-Konstruktion die logische Bedingung an.

Notation

In der symbolischen Logik wird das universelle Quantifizierersymbol (ein umgedrehtes " A " in einer serifenlosen Schriftart, Unicode U+2200) verwendet, um die universelle Quantifizierung anzuzeigen. Es wurde zum ersten Mal auf diese Weise durch verwendet Gerhard Gentzen 1935, analog zu Giuseppe Peano ‚s (einge E) Notation für existentielle Quantifizierung und die späteren Verwendung Peanos Notation von Bertrand Russell . ${\displaystyle \forall}$${\displaystyle \exists}$

Wenn beispielsweise P ( n ) das Prädikat "2· n > 2 + n " und N die Menge der natürlichen Zahlen ist, dann

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

ist die (falsche) Aussage

"für alle natürlichen Zahlen n gilt 2· n > 2 + n ".

In ähnlicher Weise, wenn Q ( n ) das Prädikat " n ist zusammengesetzt" ist, dann

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

ist die (wahre) Aussage

"für alle natürlichen Zahlen n , wenn n zusammengesetzt ist, dann 2· n > 2 + n ".

Mehrere Variationen der Notation für die Quantifizierung (die für alle Formen gelten) finden Sie im Artikel Quantifier .

Eigenschaften

Negation

Die Negation einer universell quantifizierten Funktion erhält man, indem man den universellen Quantor in einen existenziellen Quantor umwandelt und die quantifizierte Formel negiert. Das ist,

${\displaystyle \lnot \forall x\;P(x)\quad {\text{entspricht}}\quad \exists x\;\lnot P(x)}$

wobei bezeichnet Negation . ${\displaystyle \lnot}$

Ist beispielsweise P ( x ) die Aussagenfunktion " x ist verheiratet", dann gilt für die Menge X aller lebenden Menschen die universelle Quantifizierung

Bei einer lebenden Person x ist diese Person verheiratet

ist geschrieben

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

Diese Aussage ist falsch. Ehrlich gesagt wird gesagt, dass

Es ist nicht der Fall, dass eine lebende Person x verheiratet ist

oder symbolisch:

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

Wenn die Funktion P ( x ) nicht für jedes Element von X wahr ist , dann muss es mindestens ein Element geben, für das die Aussage falsch ist. Das heißt, die Verneinung von ist logisch äquivalent zu „Es existiert eine lebende Person x, die nicht verheiratet ist“ oder: ${\displaystyle \forall x\in X\,P(x)}$

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

Es ist falsch, "alle Personen sind nicht verheiratet" (dh "es gibt keine Person, die verheiratet ist") mit "nicht alle Personen sind verheiratet" (dh "es gibt eine Person, die nicht verheiratet ist") zu verwechseln:

${\displaystyle \lnot \exists x\in X\,P(x)\equiv \ \forall x\in X\,\lnot P(x)\not \equiv\ \lnot \ \forall x\in X\ ,P(x)\equiv\\exists x\in X\,\nicht P(x)}$

Andere Verbindungen

Der universelle (und existenzielle) Quantor bewegt sich unverändert über die logischen Verknüpfungen ∧ , ∨ , → und ↚ , solange der andere Operand nicht betroffen ist; das ist:

${\displaystyle {\begin{ausgerichtet}P(x)\land (\exists {y}{\in}\mathbf{Y}\,Q(y))&\equiv\\exists {y}{\in} \mathbf {Y} \,(P(x)\land Q(y))\\P(x)\lor (\exists {y}{\in}\mathbf {Y} \,Q(y))& \equiv \ \exists {y}{\in}\mathbf {Y} \,(P(x)\lor Q(y)),&{\text{vorausgesetzt }}\mathbf{Y} \neq \emptyset \\P(x)\to (\exists {y}{\in}\mathbf{Y}\,Q(y))&\equiv\\exists {y}{\in}\mathbf{Y}\, (P(x)\to Q(y)),&{\text{vorausgesetzt }}\mathbf {Y} \neq \emptyset \\P(x)\nleftarrow (\exists {y}{\in}\ mathbf {Y} \,Q(y))&\equiv \ \exists {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)),&{\text{vorausgesetzt }}\mathbf {Y} \neq \emptyset \\P(x)\lor (\forall {y}{\in}\mathbf {Y} \,Q (y))&\equiv\\forall{y}{\in}\mathbf{Y}\,(P(x)\or Q(y))\\P(x)\to (\forall{y} {\in}\mathbf{Y}\,Q(y))&\equiv\\forall {y}{\in}\mathbf{Y}\,(P(x)\to Q(y))\\ P(x)\nPfeil nach links (\forall{y}{\in}\mathbf{Y}\,Q(y))&\equiv\\forall {y}{\in}\mathbf{Y}\,(P(x)\nleftarrow Q(y)),&{\text{vorausgesetzt }}\mathbf{Y} \neq \emptyset \end{aligned} }}$

Umgekehrt drehen sich die Quantoren für die logischen Verknüpfungen ↑ , ↓ , ↛ und ← um:

${\displaystyle {\begin{aligned}P(x)\uparrow (\exists {y}{\in}\mathbf{Y}\,Q(y))&\equiv\\forall {y}{\in} \mathbf {Y} \,(P(x)\uparrow Q(y))\\P(x)\downarrow (\exists {y}{\in}\mathbf {Y} \,Q(y))& \equiv \ \forall {y}{\in}\mathbf {Y} \,(P(x)\downarrow Q(y)),&{\text{vorausgesetzt }}\mathbf{Y} \neq \emptyset \\P(x)\nrightarrow (\exists {y}{\in}\mathbf{Y}\,Q(y))&\equiv\\forall {y}{\in}\mathbf {Y}\, (P(x)\nrightarrow Q(y)),&{\text{vorausgesetzt }}\mathbf {Y} \neq \emptyset \\P(x)\gets (\exists {y}{\in}\ mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in}\mathbf {Y} \,(P(x)\gets Q(y))\\P(x)\ uparrow (\forall{y}{\in}\mathbf{Y}\,Q(y))&\equiv\\exists {y}{\in}\mathbf{Y}\,(P(x)\uparrow Q(y)),&{\text{vorausgesetzt }}\mathbf {Y} \neq \emptyset \\P(x)\downarrow (\forall {y}{\in}\mathbf {Y} \,Q (y))&\equiv \ \exists {y}{\in}\mathbf {Y} \,(P(x)\downarrow Q(y))\\P(x)\nrightarrow (\forall {y} {\in}\mathbf{Y}\,Q(y))&\equiv\\exists {y}{\in}\mathbf{Y}\,(P(x)\nrightarrow Q(y))\\ P(x)\bekommt ( \forall {y}{\in}\mathbf{Y}\,Q(y))&\equiv\\exists {y}{\in}\mathbf{Y}\,(P(x)\gets Q( y)),&{\text{vorausgesetzt }}\mathbf {Y} \neq \emptyset \\\end{ausgerichtet}}}$

Schlussfolgerungsregeln

Eine Inferenzregel ist eine Regel, die einen logischen Schritt von der Hypothese bis zur Schlussfolgerung rechtfertigt. Es gibt mehrere Inferenzregeln, die den universellen Quantor verwenden.

Universelle Instantiierung schließt daraus, dass, wenn bekannt ist, dass die Aussagenfunktion universell wahr ist, sie für jedes beliebige Element des Diskursuniversums wahr sein muss. Symbolisch wird dies dargestellt als

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

wobei c ein völlig willkürliches Element des Diskursuniversums ist.

Die universelle Verallgemeinerung kommt zu dem Schluss, dass die Aussagefunktion universell wahr sein muss, wenn sie für ein beliebiges Element des Diskursuniversums gilt. Symbolisch für ein beliebiges c ,

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

Das Element  c muss völlig willkürlich sein; andernfalls folgt die Logik nicht: Wenn c nicht willkürlich, sondern ein spezifisches Element des Diskursuniversums ist, dann impliziert P( c ) nur eine existenzielle Quantifizierung der Aussagenfunktion.

Die leere Menge

Laut Konvention ist die Formel immer wahr, unabhängig von der Formel P ( x ); siehe leere Wahrheit . ${\displaystyle \forall {x}{\in}\emptyset \,P(x)}$

Universalverschluss

Der universelle Abschluss einer Formel φ ist die Formel ohne freie Variablen, die durch Hinzufügen eines universellen Quantors für jede freie Variable in φ erhalten wird. Zum Beispiel der universelle Verschluss von

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

ist

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

Als adjoint

In der Kategorientheorie und der Theorie der elementaren Topoi kann der universelle Quantor als Rechtsadjung eines Funktors zwischen Potenzmengen , der inverse Bildfunktor einer Funktion zwischen Mengen verstanden werden; ebenso ist der existentielle Quantor der linksadjungierte .

Für eine Menge sei ihre Potenzmenge bezeichnet . Für jede Funktion zwischen Mengen und gibt es einen inversen Bildfunktor zwischen Potenzmengen, der Teilmengen des Kobereichs von f auf Teilmengen seines Bereichs zurückführt. Der linke Adjungierte dieses Funktors ist der existentielle Quantor und der rechte Adjungierte ist der universelle Quantor . ${\displaystyle X}$${\displaystyle {\mathcal{P}}X}$${\displaystyle f:X\to Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle f^{*}:{\mathcal{P}}Y\to {\mathcal{P}}X}$${\displaystyle \exists _{f}}$${\displaystyle \forall_{f}}$

Das heißt, ist ein Funktor, der für jede Teilmenge die durch given gegebene Teilmenge liefert${\displaystyle \exists_{f}\colon {\mathcal{P}}X\to {\mathcal{P}}Y}$${\displaystyle S\Teilmenge X}$${\displaystyle \exists _{f}S\subset Y}$

${\displaystyle \exists_{f}S=\{y\in Y\;|\;\exists x\in X.\f(x)=y\quad\land \quad x\in S\},}$

die im Bild von unter . In ähnlicher Weise ist der universelle Quantor ein Funktor, der für jede Teilmenge die durch sub gegebene Teilmenge liefert${\displaystyle y}$${\displaystyle S}$${\displaystyle f}$${\displaystyle \forall_{f}\colon {\mathcal{P}}X\to {\mathcal{P}}Y}$${\displaystyle S\Teilmenge X}$${\displaystyle \forall _{f}S\subset Y}$

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

diejenigen, deren Urbild unter in enthalten ist . ${\displaystyle y}$${\displaystyle f}$${\displaystyle S}$

Die bekanntere Form der Quantoren, wie sie in der Logik erster Ordnung verwendet wird, erhält man, indem man die Funktion f als die eindeutige Funktion nimmt, so dass die Zwei-Elemente-Menge mit den Werten wahr und falsch ist, eine Teilmenge S die Teilmenge, für die die Prädikat gilt, und ${\displaystyle !:X\to 1}$${\displaystyle {\mathcal{P}}(1)=\{T,F\}}$ ${\displaystyle S(x)}$

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

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

was wahr ist, wenn nicht leer ist, und ${\displaystyle S}$

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

was falsch ist, wenn S nicht X ist.

Die oben angegebenen universellen und existentiellen Quantoren verallgemeinern auf die Kategorie der Pregarben .

Siehe auch

• Existenzielle Quantifizierung
• Logik erster Ordnung
• Liste der Logiksymbole —für das Unicode-Symbol ∀

Anmerkungen

Verweise

• Hinman, P. (2005). Grundlagen der mathematischen Logik . AK Peters . ISBN 1-56881-262-0.
• Franklin, J. und Daoud, A. (2011). Beweis in Mathematik: Eine Einführung . Kew-Bücher. ISBN 978-0-646-54509-7.CS1-Wartung: mehrere Namen: Autorenliste ( Link ) (Kap. 2)

Externe Links

• Die Wörterbuchdefinition von jedem bei Wiktionary