Existenzielle Quantifizierung

In der Prädikatenlogik ist die Existenzquantifizierung ein Quantor , der die Existenz eines Objekts mit einer gegebenen Eigenschaft aussagt . Sie wird üblicherweise durch das logische Operatorsymbol ∃ bezeichnet , das, zusammen mit einer Prädikatvariablen verwendet, als Existenzquantor („ ∃x “ oder „ ∃ ( x ) “ oder „ (∃x ) “ ^{[ 1 ]} ) gelesen wird als „es existiert“, „es gibt mindestens eins“ oder „für einige“. Die Existenzquantifizierung unterscheidet sich von der Allquantifizierung („für alle“), die aussagt, dass die Eigenschaft oder Relation für alle Elemente des Definitionsbereichs gilt. ^{[ 2 ] [ 3 ]} Manche Quellen verwenden den Begriff Existenzialisierung synonym für Existenzquantifizierung. ^{[ 4 ]}

Die Quantifizierung im Allgemeinen wird im Artikel über Quantifizierung (Logik) behandelt . Der Existenzquantor wird in Unicode als U+2203 ∃ THERE EXISTS kodiert , ebenso wie in LaTeX und verwandten Formeleditoren. \exists

Betrachten wir den formalen Satz

Für eine natürliche Zahl , .${\displaystyle n}$${\displaystyle n\times n=25}$

Dies ist eine einzelne Aussage, die Existenzquantifizierung verwendet. Sie ist in etwa analog zu dem informellen Satz „Entweder , oder , oder , oder... und so weiter“, aber präziser, da wir die Bedeutung der Wendung „und so weiter“ nicht erschließen müssen. (Insbesondere legt der Satz explizit fest, dass sein Diskursbereich die natürlichen Zahlen sind, nicht etwa die reellen Zahlen .) ${\displaystyle 0\times 0=25}$${\displaystyle 1\times 1=25}$${\displaystyle 2\times 2=25}$

Dieses spezielle Beispiel ist wahr, da 5 eine natürliche Zahl ist, und wenn wir 5 für n einsetzen , erhalten wir die wahre Aussage . Es spielt keine Rolle, dass die Aussage nur für diese eine natürliche Zahl, nämlich 5, wahr ist; die Existenz einer einzigen Lösung genügt, um die Wahrheit dieser Existenzquantifizierung zu beweisen. ${\displaystyle 5\times 5=25}$${\displaystyle n\times n=25}$

Im Gegensatz dazu ist „Für eine gerade Zahl n “ falsch, da es keine geraden Lösungen gibt. Der Diskursbereich , der die Werte festlegt, die die Variable n annehmen darf, ist daher entscheidend für die Wahrheit oder Falschheit einer Aussage. Logische Konjunktionen werden verwendet, um den Diskursbereich so einzuschränken, dass er ein gegebenes Prädikat erfüllt. Zum Beispiel der Satz ${\displaystyle n}$${\displaystyle n\times n=25}$

Für eine positive ungerade Zahl ,${\displaystyle n}$${\displaystyle n\times n=25}$

ist logisch äquivalent zu dem Satz

Für eine bestimmte natürliche Zahl ist ungerade und .${\displaystyle n}$${\displaystyle n}$${\displaystyle n\times n=25}$

Der mathematische Beweis einer Existenzaussage über ein „irgendeinen“ Objekt kann entweder durch einen konstruktiven Beweis , der ein Objekt aufzeigt, das die Aussage „irgendein“ Objekt erfüllt, oder durch einen nicht-konstruktiven Beweis , der zeigt, dass es ein solches Objekt geben muss, ohne es konkret aufzuzeigen, erbracht werden.

In der symbolischen Logik wird das Symbol "∃" (ein umgedrehtes " E " in einer serifenlosen Schriftart, Unicode U+2203) verwendet, um Existenzquantifizierungen anzuzeigen. Beispielsweise repräsentiert diese Notation die (wahre) Aussage ${\displaystyle \exists {n}{\in }\mathbb {N} :n\times n=25}$

Es gibt ein Element in der Menge der natürlichen Zahlen, sodass .${\displaystyle n}$${\displaystyle n\times n=25}$

Die erste Verwendung des Symbols wird Giuseppe Peano in seinem Werk „Formulario mathematico“ (1896) zugeschrieben . Später popularisierte Bertrand Russell dessen Verwendung als Existenzquantor. Im Rahmen seiner Forschungen zur Mengenlehre führte Peano außerdem die Symbole ∅ und ∇ ein, um den Schnitt bzw. die Vereinigung von Mengen zu bezeichnen. ^{[ 5 ]}${\displaystyle \cap }$${\displaystyle \cup }$

Eine quantifizierte Aussagefunktion ist eine Aussage; daher können quantifizierte Funktionen, wie Aussagen, negiert werden. Das Symbol → wird verwendet, um die Negation zu kennzeichnen. ${\displaystyle \lnot \ }$

Wenn beispielsweise P ( x ) das Prädikat „ x ist größer als 0 und kleiner als 1“ ist, dann kann für einen Diskursbereich X aller natürlichen Zahlen die Existenzquantifizierung „Es existiert eine natürliche Zahl x , die größer als 0 und kleiner als 1 ist“ symbolisch wie folgt ausgedrückt werden:

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

Dies lässt sich als falsch beweisen. Korrekterweise muss gesagt werden: „Es gibt keine natürliche Zahl x, die größer als 0 und kleiner als 1 ist“, oder symbolisch ausgedrückt:

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

Wenn es kein Element des Diskursbereichs gibt, für das die Aussage wahr ist, dann muss sie für alle diese Elemente falsch sein. Das heißt, die Negation von

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

ist logisch äquivalent zu „Für jede natürliche Zahl x gilt: x ist nicht größer als 0 und nicht kleiner als 1“, oder:

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

Im Allgemeinen ist also die Negation der Existenzquantifizierung einer Aussagefunktion eine universelle Quantifizierung der Negation dieser Aussagefunktion; symbolisch gesprochen,

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

(Dies ist eine Verallgemeinerung der De Morganschen Gesetze auf die Prädikatenlogik.)

Ein häufiger Fehler ist die Aussage „nicht alle Personen sind verheiratet“ (d. h. „es gibt keine verheiratete Person“), wenn eigentlich „nicht alle Personen sind verheiratet“ (d. h. „es gibt eine unverheiratete Person“) gemeint ist.

${\displaystyle \lnot \ \exists {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 \ \exists {x}{\in }\mathbf {X} \,\lnot P(x)}$

Negation kann auch durch eine Aussage wie „für nein“ ausgedrückt werden, im Gegensatz zu „für einige“:

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

Im Gegensatz zum Allquantor distributivt der Existenzquantor über logische Disjunktionen:

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

Eine Schlussregel ist eine Regel, die einen logischen Schritt von der Hypothese zur Schlussfolgerung rechtfertigt. Es gibt mehrere Schlussregeln, die den Existenzquantor verwenden.

Die Existenzielle Einführung (∃I) besagt, dass, wenn bekannt ist, dass die Aussagefunktion für ein bestimmtes Element des Diskursbereichs wahr ist, dann auch die Existenz eines Elements wahr sein muss, für das die Aussagefunktion wahr ist. Symbolisch ausgedrückt:

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

Die existentielle Instanziierung , durchgeführt in einer Fitch-Deduktion, erfolgt durch den Eintritt in eine neue Teilableitung, wobei eine existentiell quantifizierte Variable anstelle eines Subjekts eingesetzt wird, das in keiner aktiven Teilableitung vorkommt. Lässt sich innerhalb dieser Teilableitung eine Schlussfolgerung ziehen, in der das ersetzte Subjekt nicht auftritt, so kann man die Teilableitung mit dieser Schlussfolgerung verlassen. Die Begründung für die existentielle Elimination (∃E) lautet wie folgt: Ist gegeben, dass ein Element existiert, für das die Aussagefunktion wahr ist, und lässt sich durch Benennung dieses Elements eine Schlussfolgerung ziehen, so ist diese Schlussfolgerung notwendigerweise wahr , solange sie den Namen nicht enthält. Symbolisch ausgedrückt: Für ein beliebiges c und eine Aussage Q, in der c nicht vorkommt:

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

${\displaystyle P(c)\to \ Q}$muss für alle Werte von c über demselben Definitionsbereich X wahr sein ; andernfalls folgt die Logik nicht: Wenn c nicht beliebig ist, sondern ein bestimmtes Element des Diskursbereichs darstellt, dann könnte die Aussage P ( c ) ungerechtfertigterweise mehr Informationen über dieses Objekt liefern.

Die Formel ist immer falsch, unabhängig von P ( x ). Das liegt daran, dass die leere Menge bezeichnet und kein x – egal welcher Art – existiert, geschweige denn ein x, das ein gegebenes Prädikat P ( x ) erfüllt. Siehe auch „Vakuumwahrheit“ für weitere Informationen. ${\displaystyle \exists {x}{\in }\varnothing \,P(x)}$${\displaystyle \varnothing }$

In der Kategorientheorie und der Theorie der elementaren Topoi kann der Existenzquantor als Linksadjungierter eines Funktors zwischen Potenzmengen , als Urbildfunktor einer Funktion zwischen Mengen, verstanden werden; analog dazu ist der Allquantor der Rechtsadjungierte . ^{[ 6 ]}

• Existenzklausel
• Existenzsatz
• Prädikatenlogik erster Stufe
• Lindström-Quantifizierer
• Liste der Logiksymbole – für das Unicode-Symbol ∃
• Quantorenvarianz
• Einzigartigkeitsquantifizierung