Kann man die Quantorenäquivalenz beweisen oder ist sie einfach definiert?

Neue Frage »

Pippen Auf diesen Beitrag antworten »
Kann man die Quantorenäquivalenz beweisen oder ist sie einfach definiert?
Es geht hier natürlich um die Äquivalenz For-all-x Px <=> ~Exist-x ~Px bzw. ~For-all-x Px <=> Exist-x ~Px.
Dopap Auf diesen Beitrag antworten »

wer soll das lesen können?

Ein klein wenig LATEX sollte ein so guter Hobbymathematiker schon kennen.

 
 
zweiundvierzig Auf diesen Beitrag antworten »

Das nennt man Quantorendualität, nicht -äquivalenz. Die beiden Quantoren sind nicht äquivalent, sondern dual zueinander.

Und ja, das kann man beweisen.
Dopap Auf diesen Beitrag antworten »
RE: Kann man die Quantorenäquivalenz beweisen oder ist sie einfach definiert?
Zitat:
Original von Pippen
~For-all-x Px <=> Exist-x ~Px.


oder in Schmalspur:



es fehlt der Doppelpunkt und die Menge.

Sauberes Schriftbild hilft beim Denken.
Elvis Auf diesen Beitrag antworten »

Gilt das auch für unsere speziellen Freunde, die Intuitionisten?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
Sauberes Schriftbild hilft beim Denken.

Aber unsauberes Schriftbild hilft auszusieben, d.h., dass nur wirklich engagierte Helfer am Ball bleiben, während das übrige anscheinend ja auch nur mäßig interessierte Volk (wozu ich mich zähle) draußen bleibt und somit die sehr fruchtbaren Pippen-Diskussionen nicht stört. smile
Finn_ Auf diesen Beitrag antworten »

Für endliche Universen sind die Regeln einfach nur die De Morgan'schen Gesetze. Diese lassen sich mittels Wahrheitstafel zeigen, bzw. allgemein mittels boolescher Algebra und vollständiger Induktion.

Uns interessieren nun also unendliche Universen. Bei einigen formalen Systemen ist die Äquivalenz axiomatisch angenommen um einen der beiden Quantoren auf den anderen zurückzuführen.

Betrachten wir daher nun die Semantik. Da ist die Allquantifizierung so definiert, dass genau dann erfüllt ist, wenn jede beliebige Substitution von durch einen Wert des Universums das Prädikat erfüllen wird. Entsprechend ist genau dann erfüllt, wenn sich eine erfüllende Substitution von finden lässt.

Nun lässt sich die Äquivalenz nicht für jede Substitution testen, weil es ja unendlich viele davon gibt. Allerdings wissen wir, dass entweder wahr oder falsch ist. Angenommen , dann ist für eine beliebige Substitution , also weiß man . Daher ist . Außerdem gilt ja . Mittels Ersetzungsregel (die man ohnehin ständig benutzt) ergibt sich dann , und damit .

Angenommen . Dann muss es eine Substitution mit geben, bzw. . Dann ist definitionsgemäß , und somit .

Die Schlussfolgerung sollte dergestalt sein, dass sie sich auch von rechts nach links führen lässt. Damit ist die Äquivalenz dann bewiesen.

Es stellt sich nun noch die Frage, warum die Definitionen der Quantoren nicht irgendwie zirkulär sind, denn es wird ja eine Quantifizierung im formalen System auf eine Quantifizierung in der Metasprache zurückgeführt.
Pippen Auf diesen Beitrag antworten »
RE: Kann man die Quantorenäquivalenz beweisen oder ist sie einfach definiert?
Zitat:
Original von Dopap




Danke, ich tue mich da immer schwer und gerade bei solchen "Quickiefragen" bohre ich gern am dünnen Brett. Nun ja, ist zB diese o.g. Äquivalenz folgerbar, d.h. beweisbar, d.h. ein Theorem oder einfach gesetzt/definiert? Ich würde sagen, in PL1 ist es einfach eine Definition, in PL2 und höher könnte man es als Theorem beweisen?!?
zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Gilt das auch für unsere speziellen Freunde, die Intuitionisten?

Nein. Es gilt , aber z.B. nicht
Elvis Auf diesen Beitrag antworten »

Danke, das dachte ich mir, nachdem ich diesem freundlichen Herrn ein paar Stunden gelauscht habe: https://www.youtube.com/watch?v=Sij1jIL2gEg (nach wenigen Stunden habe ich allerdings die Geduld verloren).
Also kann man auf Pippens Eingangsfrage antworten, dass man die Quantorendualität nicht in jeder Logik beweisen kann.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »