Äquivalenz und Herleitbarkeit von Axiomen

Neue Frage »

Tr123 Auf diesen Beitrag antworten »
Äquivalenz und Herleitbarkeit von Axiomen
Meine Frage:


In Zoglauer: Einführung in die formale Logik für Philosophen wird ein aussagenlogisches System u.a. mit folgenden Axiomen genannt:

1. p-> (q->p)
2. p -> ((q ->p) -> p)

Das Axiomensystem wird unabhängig genannt, d.h. doch, soweit ich verstanden habe, dass kein Axiom aus dem anderen herleitbar ist.

Das System wird weiterhin vollständig und widerspruchsfrei genannt.

Nun lässt sich jedoch per Wahrheitstafelmethode folgende Aussage als logisch wahr erweisen:

(p-> (q->p)) <--> (p -> ((q ->p) -> p))

Das bedeutet doch, dass "p-> (q->p)" und "p -> ((q ->p) -> p)" äquivalent sind, oder?

Bedeutet das nicht gleichzeitig, dass p-> (q->p) aus p -> ((q ->p) -> p) herleitbar ist und umgekehrt? Dies dürfte aber doch bei einem unabhängigen Axiomensystem nicht der Fall sein.

Ich würde mich sehr freuen, wenn mir jemand einen Hinweis geben könnte, wo ich dabei einen Denkfehler mache.

Vielen Dank!

Meine Ideen:
Eine Idee zur Lösung habe ich bis jetzt leider keine...
pseudo-nym Auf diesen Beitrag antworten »

Das Problem ist, dass du nicht genau genug festgelegt hast was eine Herleitung ist.

Schau doch in deinen Unterlagen nach Herleitungen oder dem Kalkül des natürlichen Schließens.
Tr123 Auf diesen Beitrag antworten »

Erst einmal danke für die schnelle Reaktion.

Ich würde sagen, herleiten bedeutet, eine zu beweisende Behauptung mit Hilfe von Schlussregeln und ggf. aus Axiomen gewinnen. Vgl. http://de.wikipedia.org/wiki/Beweis_(Logik)

Das System, um dem es bei Zoglauer geht, ist angeblich vollständig und korrekt. D.h. alle logisch wahren Sätze sind herleitbar und umgekehrt.

Wenn also
(p-> (q->p)) <--> (p -> ((q ->p) -> p))

logisch wahr ist, muss diese Aussage doch auch herleitbar sein.

und hierher (http://de.wikipedia.org/wiki/Axiomensyst...h.C3.A4ngigkeit) habe ich folgende Info:

"Ein Ausdruck A wird unabhängig von einer Menge M von Axiomen genannt, wenn A nicht aus den Axiomen in M hergeleitet werden kann. Entsprechend ist eine Menge M von Axiomen unabhängig, wenn jedes einzelne der Axiome in M von den restlichen Axiomen unabhängig ist:"
Prägnant zusammengefasst: „Unabhängig sind die Axiome, wenn keines von ihnen aus den anderen ableitbar ist“."

Hammer
Tr123 Auf diesen Beitrag antworten »

1. (p-> (q->p)) (Axiom1)
2. ((p--> (q-->p)) --> (p -> ((q ->p) -> p)) und (p -> ((q ->p) -> p) -->(p--> (q—>p)) (logisch wahr, muss also auch herleitbar sein, daher muss ich es annehmen können)
3. (p--> (q-->p)) --> (p -> ((q ->p) -> p)) Simplifikation aus 2
4. (p -> ((q ->p) --> p) Modus Ponens aus 1,3

Oder darf ich 2. nicht annehmen?
pseudo-nym Auf diesen Beitrag antworten »

Zitat:
Original von Tr123
Das System, um dem es bei Zoglauer geht, ist angeblich vollständig und korrekt. D.h. alle logisch wahren Sätze sind herleitbar und umgekehrt.

Es kann durchaus sein, dass in deinem Buch Korrektheit und Vollständigkeit für ein formales System gezeigt wird, Ein solches System hängt aber u.a. von den gewählten Axiomen und den erlaubten Schlussfolgerungen ab.
Du kannst also a priori nicht sagen, dass jedes formale System mit der Axiomenmenge vollständig und korrekt ist.
Tr123 Auf diesen Beitrag antworten »

Hallo,

erst mal Entschuldigung, weil ich mich im letzten Beitrag total vertan habe.

Die Axiome des beschriebenen Systems lauten:

1. p --> (q -->p)

2. (p --> (q --> r)) --> ((p --> q) --> (p --> r))

3. ( non p --> non q) --> (q --> p)

Das System hat zwei Schlussregeln:

1. Modus Ponens

2- Substitutionsregel (In jedem Ausdruck darf für jede Variable eine andere Aussagenvariable eingesetzt werden. Dabei ist zu beachten, dass eine solche Ersetzung an allen Stellen, wo die Variable auftritt, erfolgen muss.

Von diesem Sytem wird gesagt, dass es unabhängig, vollständig und widerspruchsfrei sei.

Die Aussage (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) ist logisch wahr. Wenn es richtig ist, dass das System vollständig ist, dann müsste diese Tautologie auch ein Theorem sein, also syntaktisch herleitbar sein. Daher kann ich es (s. unten 2.) annehmen.

1. p -> (q -> p) 1. Axiom
2. (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) Theorem, s.o.
3. (p -> (q -> r)) -> ((p -> q) -> (p -> r)) Modus Ponens aus 1, 2 (führt zu 2. Axiom)

Hätte ich damit aber nicht ein Axiom aus einem anderen Axiom und den Regeln hergeleitet und würde dies nicht gegen die Unabhängigkeit des Axiomensystems sprechen? Oder lässt sich das so nicht sagen, da es ja sozusagen nicht direkt hergeleitet ist, sondern nur mit Hilfe des Theorems?

Danke im Voraus für eine Gedankenklärung ;-)
 
 
pseudo-nym Auf diesen Beitrag antworten »

Zitat:
Original von Tr123
Die Aussage (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) ist logisch wahr. Wenn es richtig ist, dass das System vollständig ist, dann müsste diese Tautologie auch ein Theorem sein, also syntaktisch herleitbar sein. Daher kann ich es (s. unten 2.) annehmen.


Es seien deine Axiome mit A1, A2, A3 bezeichnet.
Hier liegt das Problem. Das System dessen Vollständigkeit du hier benutzt, beinhaltet auch A2. Um die Abhängigkeit von A2 zu zeigen, müsstest du statt dem von mir zitierten Schritt die stärkere Aussage

zeigen.

So wie er momentan formuliert ist, läuft dein Beweis auf hinaus und das ist trivial.
Tr123 Auf diesen Beitrag antworten »

"Um die Abhängigkeit von A2 zu zeigen, müsstest du statt dem von mir zitierten Schritt die stärkere Aussage

zeigen."

Die Abhängigkeit der A2 entsprechenden Aussage ließe sich zeigen (vorausgesetzt ich kann 2. wirklich als Theorem annehmen, aber m.E. ist das Axiomensystem auch ohne A2 vollständig, also müsste das gehen). Aber ich würde dann ja nicht mehr die Abhängigkeit eines Axioms zeigen, sondern eines Theorems, und damit wäre die Unabhängigkeit des Axiomensystems nicht "angetastet".

Falls ich das jetzt richtig verstanden habe kann ich nur sagen danke, danke, danke!
pseudo-nym Auf diesen Beitrag antworten »

Zitat:
Original von Tr123
Die Abhängigkeit der A2 entsprechenden Aussage ließe sich zeigen[...].

Ohne einen Beweis glaube ich dir kein Wort.

Zitat:
Original von Tr123
[...]vorausgesetzt ich kann 2. wirklich als Theorem annehmen[...]

Der Begriff des Theorems ist abhängig von formalen System und damit insbesondere von Axiomensystem. Da wir von mehreren Axiomensystemen reden (bisher {A1, A2, A3} und {A1, A3}, macht es keinen Sinn von Theoremen zu reden, ohne das formale System dazu anzugeben.

Zitat:
Original von Tr123
[A]ber m.E. ist das Axiomensystem auch ohne A2 vollständig[...].

Sagt wer?


Zitat:
Original von Tr123
Aber ich würde dann ja nicht mehr die Abhängigkeit eines Axioms zeigen, sondern eines Theorems, und damit wäre die Unabhängigkeit des Axiomensystems nicht "angetastet".

Das verstehe ich nicht ganz.
Mit Hilfe von Theoremen formuliert sagt Abhängigkeit von Axiomen, dass in einem formalen System ein Axiom genau dann unabhängig ist, wenn a kein Theorem von ist. a kann also nicht aus mit den Schlussregeln aus H hergeleitet werden. In Formeln
Tr123 Auf diesen Beitrag antworten »

Hallo,

so wie ich es verstanden habe, ist ein Theorem eine Aussage des formalen Systems, die aus den Axiomen und Regeln hergeleitet werden kann. Im Unterscheid zu Axiomen dieses Systems, die, sofern das System unabhängig ist, nicht aus Axiomen und den Regeln herleitbar sind.

Ich versuche weiter unten einmal den Beweis, "(p --> (q --> r)) --> ((p --> q) --> (p --> r))" aus dem Axiomensystem {A1, A3} herzuleiten (A2 habe ich rausgenommen).

Folgende Axiome hat das System:

1. p --> (q -->p)

3. ( non p --> non q) --> (q --> p)

Das System hat zwei Schlussregeln:

1. Modus Ponens

2. Substitutionsregel (In jedem Ausdruck darf für jede Variable eine andere Aussagenvariable eingesetzt werden. Dabei ist zu beachten, dass eine solche Ersetzung an allen Stellen, wo die Variable auftritt, erfolgen muss.

Die Beweisskizze für die Vollständigkeit des "alten" Systems (mit den drei Axiomen) geb ich hier gerne wieder (aus Zoglauer, S. 110). Der Beweis ist meines Erachtens auch für das "neue" System, wie es oben in diesem Post beschrieben wird, gültig.

Vollständigkeitssatz: Jede Tautologie ist ein Theorem, d.h. jede Tatutologie kann aus dem Axiomensystem abgeleitet werden. Damit ist das Axiomensystem vollständig.

Beweisskizze:

T sei eine Tautologie in dem fraglichen Axiomensystem. Zu zeigen ist:
A ist aus T herleitbar [mit A ist hier wohl nicht Axiom gemeint, sondern eine Aussage].
1. Schritt: Wandle T in eine konjunktive Normaform um: T --> KNF(T). T und KNF(T) sind syntaktisch äquivalent: T<--> KNF (T).
2. KNF(T) ist ebenfalls eine Tautologie, d.h. semantisch wahr, weil die verwendeten Schlussregeln wahrheitserhaltend sind.
3. KNF(T) hat die Form A1 und A2 und ... und An [1, 2 ... und n sollten hier tiefgestellt sein, gemeint sind hier "Aussage 1, Aussage 2 usw." nicht Axiome]. Wenn KNF (T) eine Tautologie ist, dann muss auch jedes Konjunktionsglied Ai eine Tatutologie sein.
4. Dies kann nur der Fall sein, wenn in jedem Konjunktionsglied Ai Terme der Form Alpha oder nicht Alpha vorkommen.
5. "Alpha oder nicht Alpha" ist ein Theorem in dem fraglichen Axiomensystem.
--> Daher ist auch jedes Konjunktionsglied Ai von KNF (T) ein Theorem in dem fraglichen Axiomnsystem. (Man braucht die fehlenden Disjunktionsglieder von Ai nur durch Disjunktionseinführung zu ergänzen.)
--> Damit ist auch KNF(T) ein Theorem in dem fraglichen Axiomensystem. (Konjunktionseinführung)
--> Weil T und KNF(T) syntaktisch äquivalent sind, muss auch T ein Theorem in dem fraglichen Axiomensystem sein. q.e.d.


Die Aussage (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) ist logisch wahr. Bei Vollständigkeit müsste diese Tautologie auch ein Theorem sein, also syntaktisch herleitbar sein. Daher kann ich es (s. unten 2.) annehmen.

1. p -> (q -> p) 1. Axiom
2. (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) Theorem, s.o.
3. (p -> (q -> r)) -> ((p -> q) -> (p -> r)) Modus Ponens aus 1, 2

Aber wie gesagt, indem ich 3. ableite, hätte ich damit nicht die Abhängigkeit eines Axioms des fraglichen Systems gezeigt, denn 3. ist in dem neuen System ja gar kein Axiom. Daher sagen meine Überlegungen nichts gegen die Unabhängigkeit des fraglichen Axiomensystems, und, so hoffe ich, mein Problem löst sich auf.

Ich hoffe, das war etwas nachvollziehbarer...
pseudo-nym Auf diesen Beitrag antworten »

Zitat:
Original von Tr123
Im Unterscheid zu Axiomen dieses Systems[...]

Nur um keine Missverständnisse aufkommen zu lassen:
Axiome (ob unabhängig oder nicht) sind Theoreme.

Zitat:
Original von Tr123
Die Beweisskizze für die Vollständigkeit des "alten" Systems (mit den drei Axiomen) geb ich hier gerne wieder
[...]
T sei eine Tautologie in dem fraglichen Axiomensystem. Zu zeigen ist:
A ist aus T herleitbar [mit A ist hier wohl nicht Axiom gemeint, sondern eine Aussage].
1. Schritt: Wandle T in eine konjunktive Normaform um: T --> KNF(T). T und KNF(T) sind syntaktisch äquivalent: T<--> KNF (T).
2. KNF(T) ist ebenfalls eine Tautologie, d.h. semantisch wahr, weil die verwendeten Schlussregeln wahrheitserhaltend sind.
3. KNF(T) hat die Form A1 und A2 und ... und An [1, 2 ... und n sollten hier tiefgestellt sein, gemeint sind hier "Aussage 1, Aussage 2 usw." nicht Axiome]. Wenn KNF (T) eine Tautologie ist, dann muss auch jedes Konjunktionsglied Ai eine Tatutologie sein.
4. Dies kann nur der Fall sein, wenn in jedem Konjunktionsglied Ai Terme der Form Alpha oder nicht Alpha vorkommen.
5. "Alpha oder nicht Alpha" ist ein Theorem in dem fraglichen Axiomensystem.
--> Daher ist auch jedes Konjunktionsglied Ai von KNF (T) ein Theorem in dem fraglichen Axiomnsystem. (Man braucht die fehlenden Disjunktionsglieder von Ai nur durch Disjunktionseinführung zu ergänzen.)
--> Damit ist auch KNF(T) ein Theorem in dem fraglichen Axiomensystem. (Konjunktionseinführung)
--> Weil T und KNF(T) syntaktisch äquivalent sind, muss auch T ein Theorem in dem fraglichen Axiomensystem sein. q.e.d.

Du sagst, das wäre der Beweis für Vollständigkeit für ein System mit der Axiomenmenge und die Herleitungsregeln Modus ponens und Substitution, allerdings werden weder eines der Axiome noch eine dieser Schlussregeln benutzt.
In der Tat werden in dem Beweis Schlussregeln benutzt, die garnicht in deinem System vorkommen (namentlich die Disjunktions- und Konjunktionseinführung).
Mir scheint es, dass du den Beweis für die Vollständigkeit der Aussagenlogik wie sie in deinem Buch eingeführt wurde zitiert hast.
Ich sehe nicht was das mit unseren Systemen zu tun hat insbesondere werden die dadurch nicht vollständig.
Tr123 Auf diesen Beitrag antworten »

Hallo,

"Nur um keine Missverständnisse aufkommen zu lassen:
Axiome (ob unabhängig oder nicht) sind Theoreme." O.K., dass hatte ich tatsächlich anders verstanden.

Darf es denn auch ein abhängiges Axiomensystem geben? Oder anders herum: warum wird die Unabhängigkeit von Axiomen gefordert?

Bezüglich des Vollständigkeits"beweises" gebe ich dir recht, dass dort andere Schlussregeln verwendet werden, das wundert mich jetzt auch. In dem Buch ist es aber definitiv als Beweis für das "alte" Axiomensystem (mit den 3 Axiomen) angeführt.

Nun ja, mir geht es eigentlich gar nicht so sehr darum, ob das System wirklich vollständig ist oder nicht. Sondern um folgendes: angenommen, es wäre vollständig: Mit meinem Herleitungsversuch hätte ich unter dieser Voraussetzung nicht widerlegen können, dass das Axiomensystem unabhängig ist. Wenn das stimmt, könnte ich schon ruhig schlafen :-)
pseudo-nym Auf diesen Beitrag antworten »

Zitat:
Original von Tr123
[W]arum wird die Unabhängigkeit von Axiomen gefordert?

Meistens möchte man sein Axiomensystem so klein wie möglich halten. Sonst könnte man ja einfach alles behaupten und sich das beweisen schenken. (Das ist zwar erlaubt aber nicht sonderlich ergiebig was Erkenntnisse angeht.)
Wirft man ein abhängiges Axiom A aus einem Axiomensystem hinaus, so erhält man ein formales System mit weniger Axiomen, allerdings bleibt die Menge der ableitbaren Aussagen gleich, da man ja A aus den restlichen schließen kann.

Zitat:
Original von Tr123
Nun ja, mir geht es eigentlich gar nicht so sehr darum, ob das System wirklich vollständig ist oder nicht. Sondern um folgendes: angenommen, es wäre vollständig:

Das kommt darauf an von welchem System du redest.
Tr123 Auf diesen Beitrag antworten »

Ich meine das System mit den zwei Axiomen und den zwei Regeln. Nehmen wir an es wäre vollständig.

Die Aussage (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) ist logisch wahr. Bei Vollständigkeit müsste diese Tautologie auch ein Theorem sein, also syntaktisch herleitbar sein. Daher kann ich es (s. unten 2.) annehmen.

1. p -> (q -> p) 1. Axiom
2. (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) Theorem, s.o.
3. (p -> (q -> r)) -> ((p -> q) -> (p -> r)) Modus Ponens aus 1, 2

Aber wie gesagt, indem ich 3. ableite, hätte ich damit nicht die Abhängigkeit eines Axioms des fraglichen Systems gezeigt, denn 3. ist in dem neuen System ja gar kein Axiom. Daher sagen meine Überlegungen nichts gegen die Unabhängigkeit des fraglichen Axiomensystems.

Wenn das System gar nicht vollständig ist, dürfte ich auch nicht einfach annehmen, dass (p -> (q -> p)) --> ((p -> (q -> r)) -> ((p -> q) -> (p -> r))) syntaktisch herleitbar ist.
pseudo-nym Auf diesen Beitrag antworten »

Ja, das ist okay.
Tr123 Auf diesen Beitrag antworten »

Mit Zunge
Neue Frage »
Antworten »



Verwandte Themen

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