Gibt es mehr wahre als falsche Aussagen?

[Christoph]

logisch, ne? schrieb:

Christoph schrieb:

...und weil Logik erster Stufe unvollständig ist...

1921 wurde bewiesen, daß die Aussagenlogik vollständig und wiederspruchsfrei ist.
1928 bewiesen Hilbert und Ackermann, daß die Prädikatenlogik (erster Stufe) widerspruchsfrei ist, 1931 bewies Gödel, daß sie vollständig ist.

Das stimmt. Das ist leider sehr verwirrend, aber der Gödelsche Vollständigkeitssatz und der Gödelsche Unvollständigkeitssatz meinen mit "Vollständigkeit" unterschiedliche Konzepte. Relevant ist hier die "Vollständigkeit" im Sinne des Unvollständigkeitssatzes.

[Christoph]

DerBaer schrieb:

Nochwas:
folgender Satz ist sicherlich wahr:

"Dieser Satz enthält 30 Zeichen"
oder noch besser:
"Das ist ein Satz"

Aber was passiert wenn ich ihn negiere? Bzw. wie muss ich ihn negieren, damit er nicht mehr wahr ist?

Fazit(wie schon manchmal gesagt):
Man muss sich erstmal einigen was eine Aussage ist, wann sie wahr ist, ...

Genau das ist der Punkt: Man muss formal definieren, was eine "Aussage" sein soll, bevor man irgendwie über die Mächtigkeiten von "wahren" und "falschen" Aussagen reden kann. Warum das aber nicht so einfach ist, habe ich in meinem langen Posting vorhin ausführlicher beschrieben.

[knivil]

"Das ist ein Satz"

Selbstreferenz wurde doch schon durch das Barbierbeispiel gegeben. Sie wird im Allgemeinen in der Logik vermieden.

[Bashar]

Christoph schrieb:

Das stimmt. Das ist leider sehr verwirrend, aber der Gödelsche Vollständigkeitssatz und der Gödelsche Unvollständigkeitssatz meinen mit "Vollständigkeit" unterschiedliche Konzepte. Relevant ist hier die "Vollständigkeit" im Sinne des Unvollständigkeitssatzes.

Was ist denn der Unterschied? Vollständigkeit kenn ich als die Implikation "wahr => beweisbar", und dass das in der Prädikatenlogik 1. Stufe so ist, hat Gödel bewiesen.
Geh ich auf http://de.wikipedia.org/wiki/Gödelscher_Unvollständigkeitssatz so finde ich da den gleichen Vollständigkeitsbegriff. Das was du zuerst als Unvollständigkeit bezeichnet hast, also dass eine Aussage kein "Modell spezifizieren" kann, kommt mir vage bekannt vor, aber in die Schublade Vollständigkeit würde ich es erstmal nicht ohne weiteres einordnen. Kannst du das aufklären?

[Jester]

Christoph schrieb:

Nimm z.B. Jesters Aussage von vorhin etwas verallgemeinert "A und A^2 sind gleichmächtig, wenn A unendlich ist". In der Mengenlehre ohne Auswahlaxiom ist das nicht beweisbar. Nimmt man also das Auswahlaxiom dazu?

Sicher? Braucht man das nicht erst wenn man unendliche Produkte anschaut?

[Christoph]

Jester schrieb:

Christoph schrieb:

Nimm z.B. Jesters Aussage von vorhin etwas verallgemeinert "A und A^2 sind gleichmächtig, wenn A unendlich ist". In der Mengenlehre ohne Auswahlaxiom ist das nicht beweisbar. Nimmt man also das Auswahlaxiom dazu?

Sicher? Braucht man das nicht erst wenn man unendliche Produkte anschaut?

Ja, sicher. Die Aussage "A ist gleichmächtig zu A^2 für alle unendlichen Mengen A" ist äquivalent zum Auswahlaxiom.

Beweisskizze: Angenommen |A| = |A^2| für unendlich große A. Sei X eine unendliche Menge. Gesucht ist eine Wohlordnung von X. Sei a eine Ordinalzahl, sodass es keine Injektion a -> X gibt (so eine Ordinalzahl muss es geben auch ohne Auswahlaxiom. Gäbe es sie nicht, wäre die Klasse der Ordinalzahlen eine Menge). Betrachte (X + a) \times (X + a). Nach Voraussetzung gibt es eine Injektion f: (X + a) \times (X + a) -> (X + a). Wähle x \in X beliebig. Dann gibt es eine Ordinalzahl b, sowass f(x, b) \in a. Andernfalls wäre f(x, b) \in X für alle b \in a, ein Widerspruch dazu, dass es keine Injektion a -> X gibt. Sei b_x die minimale Ordinalzahl b \in a, sodass f(x,b) \in a. Betrachte die Menge S = { b_x | x \in X } und schränke f ein auf X \times S. f ist eine Injektion, d.h. f(x, b_x) ist für jedes x eine andere Ordinalzahl. Damit hat man eine Injektion von X -> a gefunden, d.h. man hat X wohlgeordnet.

edit: Für zwei Mengen X, Y meine ich mit X+Y die disjunkte Vereinigung.

[Christoph]

Bashar schrieb:

Christoph schrieb:

Das stimmt. Das ist leider sehr verwirrend, aber der Gödelsche Vollständigkeitssatz und der Gödelsche Unvollständigkeitssatz meinen mit "Vollständigkeit" unterschiedliche Konzepte. Relevant ist hier die "Vollständigkeit" im Sinne des Unvollständigkeitssatzes.

Was ist denn der Unterschied? Vollständigkeit kenn ich als die Implikation "wahr => beweisbar", und dass das in der Prädikatenlogik 1. Stufe so ist, hat Gödel bewiesen.
Geh ich auf http://de.wikipedia.org/wiki/Gödelscher_Unvollständigkeitssatz so finde ich da den gleichen Vollständigkeitsbegriff. Das was du zuerst als Unvollständigkeit bezeichnet hast, also dass eine Aussage kein "Modell spezifizieren" kann, kommt mir vage bekannt vor, aber in die Schublade Vollständigkeit würde ich es erstmal nicht ohne weiteres einordnen. Kannst du das aufklären?

Der Vollständigkeitssatz zeigt, dass jede wahre Aussage beweisbar ist. Er benutzt dabei "wahr" im (üblichen) Sinne von "allgemeingültig".

Der Unvollständigkeitssatz dagegen beweist die Existenz eines Satzes phi, sodass weder phi noch !phi beweisbar ist. In Kombination mit dem Vollständigkeitssatz folgt daraus aber sofort, dass dann weder phi noch !phi wahr sein können (sonst wäre phi bzw. !phi beweisbar).

Der Beweiskalkül ist vollständig in dem Sinne, dass alle allgemeingültige Aussagen bewiesen werden können.
Der Beweiskalkül ist unvollständig in dem Sinne, dass es Aussagen gibt, die von dem Kalkül weder bewiesen noch widerlegt werden können. Solche Aussagen sind dann weder "wahr" noch "falsch" (im Sinne von "allgemeingültig").

edit: Anders formuliert: Der Unvollständigkeitssatz garantiert die Existenz eines Satzes phi mit der Eigenschaft, dass weder phi noch !phi im Kalkül beweisbar ist. Dann muss es zwangsläufig ein Modell geben, in dem phi falsch ist und ein anderes Modell, in dem !phi falsch ist. Ansonsten wäre phi bzw. !phi allgemeingültig und laut dem Vollständigkeitssatz beweisbar.

edit2: Der Unvollständigkeitssatz sagt insbesondere nicht, dass es einen wahren Satz gibt, der nicht beweisbar ist. Das wäre die Umkehrung vom Vollständigkeitssatz und würde damit im Widerspruch dazu stehen. Das meinte ich damit, als ich sagte, dass der Vollständigkeits- und der Unvollständigkeitssatz über unterschiedliche Konzepte von "Vollständigkeit" reden.

[Ein ehemaliger Benutzer]

nwp2 schrieb:

Das erinnert mich an einen lustigen Beweis:

Für g = gerade Zahl, u = ungerade Zahl:
g * g = g
g * u = g
u * g = g
u * u = u
Folgerung: Es gibt dreimal soviele gerade wie ungerade Zahlen.

Was ist denn das für ein Mist?^^

[Bashar]

@Christoph,
"eigentlich" ist das doch dann eine sehr triviale Aussage. Man nehme die Gruppentheorie mit ihren 3 oder 4 Axiomen (e sei das Funktionssymbol für das neutrale Element) und formuliere eine Aussage wie $$\forall x x = e$$. Das ist für Gruppen mit genau 1 Element eine wahre Aussage und sonst eine falsche Aussage. Weder die Aussage noch ihre Negation ist allgemeingültig, also gibt es auch keine Beweise dafür.

Nun war ich immer der Ansicht, der Gödelsche Unvollständigkeitssatz bräuchte "hinreichend mächtige" Systeme, um selbstbezügliche Aussagen zu formulieren. Das ist ja hier nicht der Fall. Wo ist der Denkfehler?

[Christoph]

Bashar schrieb:

@Christoph,
"eigentlich" ist das doch dann eine sehr triviale Aussage. Man nehme die Gruppentheorie mit ihren 3 oder 4 Axiomen (e sei das Funktionssymbol für das neutrale Element) und formuliere eine Aussage wie $$\forall x x = e$$. Das ist für Gruppen mit genau 1 Element eine wahre Aussage und sonst eine falsche Aussage. Weder die Aussage noch ihre Negation ist allgemeingültig, also gibt es auch keine Beweise dafür.

Nun war ich immer der Ansicht, der Gödelsche Unvollständigkeitssatz bräuchte "hinreichend mächtige" Systeme, um selbstbezügliche Aussagen zu formulieren. Das ist ja hier nicht der Fall. Wo ist der Denkfehler?

Ich würde sagen da ist kein Denkfehler: Du hast gerade gezeigt, dass das Axiomensystem der Gruppen unvollständig ist.

Das faszinierende am Gödelschen Unvollständigkeitssatz ist aber, dass er das nicht nur für bestimmte konkrete Axiomensysteme zeigt, sondern für alle hinreichend mächtigen. Man könnte ja vermuten, dass man das Axiomensystem der Gruppen nur hinreichend oft erweitern müsste, um irgendwann ein vollständiges System zu haben. Das klappt in vielen anderen Gebieten, z.B. algebraisch abgeschlossene Körper werden dadurch konstruiert, dass man einen gegebenen Körper "oft genug" erweitert, solange bis er algebraisch abgeschlossen ist. Gödel hat gezeigt, dass egal wie oft man ein hinreichend mächtiges Axiomensystem auch erweitert, es immer unvollständig sein wird.

[Big Brother]

Ich würde sagen, dass es mehr falsche als wahre Aussagen gibt, weil man z.B. über ein konkretes Objekt i.d.R. mehr nicht zutreffende Aussagen formulieren kann, als dieses an Eigenschaften aufweist.

[knivil]

Gödel hat gezeigt, dass egal wie oft man ein hinreichend mächtiges Axiomensystem auch erweitert, es immer unvollständig sein wird.

Nein, das ist falsch. Es wird nur widerspruechlich.

Ich würde sagen, dass es mehr falsche als wahre Aussagen gibt, weil man z.B. über ein konkretes Objekt i.d.R. mehr nicht zutreffende Aussagen formulieren kann, als dieses an Eigenschaften aufweist.

Als ob Mathematik was mit Meinung oder Demokratie zu tun haette. Wer ist dafuer, dass 5 + 5 = 13 ist? 43% fuer Nein, 51% fuer Ja, 5% Enthaltung, 1% ungueltige Stimmen. So ein Quatsch.

[Christoph]

knivil schrieb:

Gödel hat gezeigt, dass egal wie oft man ein hinreichend mächtiges Axiomensystem auch erweitert, es immer unvollständig sein wird.

Nein, das ist falsch. Es wird nur widerspruechlich.

Nagut.
Dann eben: Gödel hat gezeigt, dass egal wie oft man ein hinreichend mächtiges widerspruchfreies Axiomensystem auch widerspruchsfrei erweitert, es immer unvollständig sein wird.

Widerspruchsvolle Axiomensysteme betrachtet man normalerweise erst gar nicht, aber ganz genau genommen hast du natürlich Recht.

[otze]

Christoph schrieb:

Widerspruchsvolle Axiomensysteme betrachtet man normalerweise erst gar nicht, aber ganz genau genommen hast du natürlich Recht.

Es ist nicht so, dass unser Axiomensystem gänzlich Widerspruchsfrei ist. Insbesondere das Auswahlaxiom macht ganz komische Dinge.

[knivil]

Naja, wir wissen nicht, ob es widerspruchsfrei ist. Mein alter Matheprof. glaubt nicht mehr an das Auswahlaxiom und hadert immer, wenn er es nehmen muss. http://abstrusegoose.com/133

[Bashar]

Moment mal, ein Axiomensystem (ich sag dazu Theorie, oder ist das nicht das gleiche? Theorie ist Sprache + Axiome) ist widersprüchlich genau dann, wenn in ihm der elementare Widerspruch ("falsum", $$\bot$$) ableitbar ist (oder irgendeine äquivalente Formulierung). Nicht aufgrund irgendwelcher Probleme in der Magengegend, die einem z.B. das Banach-Tarski-Paradoxon bereiten könnte.

[Christoph]

knivil schrieb:

Naja, wir wissen nicht, ob es widerspruchsfrei ist. Mein alter Matheprof. glaubt nicht mehr an das Auswahlaxiom und hadert immer, wenn er es nehmen muss. http://abstrusegoose.com/133

Wenn die Mengenlehre (d.h., "ZF") widerspruchsfrei ist, dann ist auch "ZF mit Auswahlaxiom" widerspruchsfrei. Das ist ein Theorem der Mengenlehre.

Insofern kann man durch das Auswahlaxiom garantiert keine Widersprüche bekommen, außer man hatte schon ohne Auswahlaxiom welche.

Bashar schrieb:

Moment mal, ein Axiomensystem (ich sag dazu Theorie, oder ist das nicht das gleiche? Theorie ist Sprache + Axiome) ist widersprüchlich genau dann, wenn in ihm der elementare Widerspruch ("falsum", $$\bot$$) ableitbar ist (oder irgendeine äquivalente Formulierung). Nicht aufgrund irgendwelcher Probleme in der Magengegend, die einem z.B. das Banach-Tarski-Paradoxon bereiten könnte.

Stimmt. Vor allem ist Widerspruchsfreiheit eine syntaktische Angelegenheit, keine semantische, denn es geht darum, einen Widerspruch abzuleiten. Das ist vor allem deswegen wichtig, weil Widerspruchsfreiheit dadurch zu einer endlichen Angelegenheit wird: Wenn man einen Widerspruch ableiten kann, dann muss der Ableitungsbaum per Definition endlich sein (in üblichen Logiken).

[knivil]

Ich verweise nur auf die Kritik bei Wikipedia, selbst halte ich mich da raus.

[otze]

Christoph schrieb:

Wenn die Mengenlehre (d.h., "ZF") widerspruchsfrei ist, dann ist auch "ZF mit Auswahlaxiom" widerspruchsfrei. Das ist ein Theorem der Mengenlehre.

das würde mich ja interessieren. Mir ist bekannt, dass sich Eigenschaft von Mengen auf ihre Untermengen vererben "wenn ZFC widerspruchsfrei ist, dann ist auch ZF widerspruchsfrei". Aber umgekehrt gilt diese Eigenschaft im Allgemeinen nicht.

Ich finde es auch sehr komisch, weil ZFC nicht aus ZF ableitbar ist. Es gibt also etwas, was definitiv neu ist und dadurch potentielle Widersprüche erzeugen kann. Das folgt doch schlichtweg aus der Tatsache, dass man mit ZFC dinge beweisen kann, die mit ZF nicht beweisbar sind. Und da halte ich es schon für eine gewagte Aussage, dass jede mit ZFC beweisbare Aussage widerspruchsfrei zu ZF ist.

[Christoph]

otze schrieb:

Christoph schrieb:

Wenn die Mengenlehre (d.h., "ZF") widerspruchsfrei ist, dann ist auch "ZF mit Auswahlaxiom" widerspruchsfrei. Das ist ein Theorem der Mengenlehre.

das würde mich ja interessieren. Mir ist bekannt, dass sich Eigenschaft von Mengen auf ihre Untermengen vererben "wenn ZFC widerspruchsfrei ist, dann ist auch ZF widerspruchsfrei". Aber umgekehrt gilt diese Eigenschaft im Allgemeinen nicht.

Das stimmt. "ZFC widerspruchsfrei" => "ZF widerspruchsfrei" ist trivial.

otze schrieb:

Ich finde es auch sehr komisch, weil ZFC nicht aus ZF ableitbar ist. Es gibt also etwas, was definitiv neu ist und dadurch potentielle Widersprüche erzeugen kann. Das folgt doch schlichtweg aus der Tatsache, dass man mit ZFC dinge beweisen kann, die mit ZF nicht beweisbar sind. Und da halte ich es schon für eine gewagte Aussage, dass jede mit ZFC beweisbare Aussage widerspruchsfrei zu ZF ist.

Es ist ein überraschendes Ergebnis, keine Frage. Vielleicht wird es klarer, wenn ich die Beweisidee ganz grob skizziere.

Wenn X ein Axiomensystem ist, wie kann man "X ist widerspruchsfrei" zeigen? Man kann sicher nicht alle möglichen Ableitungen ausprobieren, davon gibt es viel zu viele. Stattdessen kann man ein Modell von X angeben. Ein Modell besteht aus einer Menge A und Interpretationen für die Funktions-, Relationssymbole und Konstanten in der Sprache. Ein Modell ist ein Modell von X, wenn alle Axiome, die in X stehen, darin wahr sind.

Wenn es ein Modell von X gibt, dann muss X widerspruchsfrei sein, das ist klar (denn in einem konkreten Modell kann kein Widerspruch existieren). Andersrum sagt der Kompaktheitssatz: Wenn X widerspruchsfrei ist, dann gibt es ein Modell von X.

Also ist die Aussage "X ist widerspruchsfrei" äquivalent zu "es gibt ein Modell von X".

Es geht jetzt darum, die Aussage "ZF widerspruchsfrei => ZFC widerspruchsfrei" zu zeigen. Wir zeigen stattdessen die äquivalente Aussage "ZF hat ein Modell => ZFC hat ein Modell".

Wir nehmen also an, M ist ein Modell von ZF. Wie dieses Modell konkret aussieht, wissen wir nicht. Es könnte sein, dass M schon ein Modell von ZFC ist, aber das wissen wir auch nicht.

Das nächste Ziel ist jetzt, aus dem Modell M ein neues Modell M' zu basteln, sodass M' ein Modell von ZFC ist. Für diese Konstruktion gibt es verschiedene Möglichkeiten, eine sehr allgemeine (und komplizierte) Möglichkeit nennt sich "Forcing". Mit Forcing funktioniert es auf jeden Fall, aber ich meine, dass man ein ZFC-Modell auch ohne Forcing basteln kann, und zwar so:
Man definiere M' = { x \in M | x konstruierbar } wobei "x konstruierbar" in diesem Sinne zu verstehen ist. Der relevante Punkt dabei ist, dass die Potenzmengen-Operation P(X) nicht mehr die Menge *aller* Teilmengen von X ist, sondern nur noch die Menge aller Teilmengen von X, die auch durch eine Formel definierbar sind.

Jedenfalls ist M' ein Modell. Jetzt kann man nachrechnen, dass M' immer noch ein Modell von ZF ist, obwohl in M' im allgemeinen weniger Mengen sind als in M. Der Knackpunkt ist aber, dass in M' sogar das Auswahlaxiom wahr ist. Damit ist M' ein Modell von ZFC.

Da ZFC dann ein Modell hat, muss ZFC widerspruchsfrei sein.

edit: Ganz entscheidend ist hierbei die Annahme "ZF widerspruchsfrei". Es ist (nach derzeitigem Stand) unmöglich zu zeigen, dass ZFC widerspruchsfrei ist, ohne eine solche oder ähnliche Annahme. Könnte man die Widerspruchsfreiheit von ZFC ohne weitere Annahmen zeigen, wäre ZFC nicht widerspruchsfrei. Das ist wieder der gödelsche Unvollständigkeitssatz, der dahinter steckt (Link).