Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Gödel Unvollständigkeitstheorem
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Gödel Unvollständigkeitstheorem
 
Autor Nachricht
mathegyx7
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2011
Beiträge: 7

BeitragVerfasst am: 04 Sep 2011 - 20:06:35    Titel: Gödel Unvollständigkeitstheorem

Zitat aus „Mathematik“,T.Arens u.a.:
"….Kurt Gödel, den Todesstoß,
indem er das folgenschwere Unvollständigkeitstheorem
bewies:
In jedem Axiomensystem, das in der Lage
ist, die Arithmetik der natürlichen Zahlen zu beschreiben,
können Aussagen formuliert werden, die man innerhalb
dieses Systems weder beweisen noch widerlegen kann."

Mein Problem :
Die Menge der reelen Zahlen R bildet einen Körper.
Damit gelten hier die Körperaxiome und somit ist auch die Arithmetik
der natürlichen Zahlen beschrieben.
Wie schaut jetzt konkret so eine Aussage aus, die man innerhalb
dieses Systems weder beweisen noch widerlegen kann. ?
Grüße gyx !
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 04 Sep 2011 - 20:28:09    Titel:

Du brauchst noch etwas mehr, um Aussagen zu formulieren. Beispielsweise die Sprache der Aussagen-Logik. Denn sonst könntest du keine Implikationen "Aus A folgt B" formulieren. Auch möchtest du die Prädikaten-Logik verwenden, um Eigenschaften auszudrücken, wie z.B. "ist positiv".

Der wesentliche Gag ist die Selbstbezüglichkeit. Wie es keine Menge geben kann, die alle Mengen als Elemente enthält, die sich nicht selbst enthalten (Russelsche Antinomie), kann man auch eine Aussage q basteln, die i.W. "Die Aussage q ist nicht beweisbar" lautet.


Wäre q falsch, dann wäre eine falsche Aussage beweisbar, d.h. die Theorie wäre inkonsistent (was man normalerweise ausschließt, da inkonsistente Theorien langweilig sind, da in ihnen JEDE Aussage, egal ob wahr oder falsch beweisbar ist). Also muss q wahr, und damit (innerhalb der Theorie) nicht beweisbar sein...


Dies ist alles ziemlich informell. Was man übrigens meistens vergisst, ist, dass es auch einen Gödelschen Vollständigkeitssatz gibt. Dieser sagt aus, dass die Prädikatenlogik erster Ordnung eben vollständig ist, d.h. jede wahre (und auch nur genau diese) Aussagen dort auch beweisbar sind.

Der wesentliche Unterschied zwischen diesen beiden Sätzen ist, dass ein System, welches die formale Zahlentheorie enthält, die Möglichkeit hat, Aussagen über Aussagen zu machen: Man ordnet jeder Aussage eine Nummer zu, und kann indirekt über die Nummer eine Aussage über die der Nummer zu Grunde liegende Aussage machen.

So kann man das Prädikat "Beweisbar" definieren: Eine natürliche Zahl erfülle die Eigenschaft "Beweisbar", wenn es eine Aussage gibt, der diese natürlichen Zahl zugeordnet wurde, welche eben beweisbar ist.

Dadurch werden dann selbstbezügliche Aussagen möglich, die dann den schon altbekannten "Widerspruch" wie bei der Russelschen Antinomie liefert.


(Man muss hier schon noch um einiges formaler arbeiten, aber das mal als Idee, in welche Richtung es geht.)
Cyrix
mathegyx7
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2011
Beiträge: 7

BeitragVerfasst am: 05 Sep 2011 - 10:44:43    Titel:

Hallo Cyrix !

Zu Deinem : „..Man muss hier schon noch um einiges formaler arbeiten, aber....“
Glaube ich sofort, trotzdem zur Verdeutlichung :

K sei ein Körper.
Dann gibt's die Aussage A: = „ Für alle x aus K \{0} gilt :
x^-1 != 0 '' ( 0 ist neutrales Elem bzgl. addit.Verknüpfung)
A läßt sich mit Körperaxiomen und log.Operatoren beweisen (hab's gemacht),
es gilt also : „A ist wahr“ =: A(w).

Gibt es jetzt eine analog aufgebaute Aussage A mit A(w), die aber eben mit den Körperaxiomen und log. Verknüpfungen weder bewiesen noch widerlegt werden kann ?
Wenn ja, wie schaut so eine Aussage aus,
wenn nein, wozu soll dann die ganze „Gödelei“ gut sein ?

Grüße mathegyx7
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 05 Sep 2011 - 13:53:31    Titel:

Du befindest dich mit deiner Aussage A schon in der Prädikatenlogik. Du hast nämlich (implizit) das Prädikat B(x) gebildet, was da lautet: x^(-1) != 0. Insofern ist neben der Aussagenlogik für die Beschreibung hier auch schon die Prädikatenlogik relevant.

Wenn wir jetzt noch irgendwie (und da brauchen wir schon unendlich viele) Zahlen beschreiben können, z.B. indem wir uns einen konkreten, unendlichen Körper hernehmen und seine Elemente, sowie, wie man mit diesen rechnen kann, als Axiome hernehmen, dann können wir auch die entsprechenden Aussagen Gödels nachvollziehen.


Am einfachsten kann man Zeichenketten Gödelisieren, indem wir jedem möglichen Zeichen eine pos. natürliche Zahl zuordnen. Z.B. x--> 1; und --> 2 usw. Dann kodieren wir eine Zeichenkette z.B. durch die Zahl

2^(Nr. erstes Zeichen) * 3^(Nr. zweites Zeichen) * 5^(Nr. drittes Zeichen) * ...


Auf diese Weise können wir berechenbar jeder Zeichenkette eine nat. Zahl zuordnen (und umgekehrt dekodieren, ob eine Zahl einer solchen Zeichenkette entspricht, und wenn ja, welcher). Dann muss man noch ein bisschen arbeiten, um auch die "sinnvollen" Zeichenketten zu finden (also das Prädikat "die Zahl kodiert eine sinnvolle Zeichenkette" sinnvoll, d.h. primitiv-rekursiv berechenbar; aber das führt jetzt zu weit, zu definieren), usw. Schließlich kann man auch das zweistellige Prädikat Proof(x,y) definieren, was aussagt, dass x die Nummer einer Zeichenkette ist, die Beweis der Zeichenkette (Aussage) y ist.

Und man kann nun auch das Prädikat X(y): Für alle x gilt nicht Proof(x,y) formulieren.

Mit ein bisschen Anstrengung findet man weiterhin nun eine Aussage alpha, sodass alpha (innerhalb des Systems) beweisbar äquivalent zu X("Nr. von alpha") ist.


Dann ist alpha aber selbst (wieder die Konsistenz des systems angenommen) wahr und unbeweisbar.


Natürlich ist dieses alpha ein abstraktes Konstrukt; und nichts "Schönes, Handfestes". Aber es existiert. So ist das eben bei Diagonalisierungsbeweisen...


Analog kann man auch zeigen, dass es unentscheidbare Aussagen über dem Standard-Axiomensystem der Mengenlehre ZF (bzw. ZFC, wenn du das Auswahlaxiom mitnimmst) gibt. Hier gibt es sogar "echte", d.h. relevante Aussagen, von denen das bekannt ist. Für den Nachweis dieser Unentscheidbarkeit gab es dann auch die Fields-Medaille (Cohen):

So ist z.B. die Kontinuumshypothese (es gibt keine Menge, die mächtiger ist als die natürlichen, aber weniger mächtig als die reellen Zahlen) eine solche unentscheidbare Aussage (d.h. weder sie, noch ihr Verneinung sind über dem jeweiligen Axiomensystem beweisbar). Oder auch das Auswahlaxiom (dann natürlich nur über ZF betrachtet) selbst...

Cyrix
mathegyx7
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2011
Beiträge: 7

BeitragVerfasst am: 06 Sep 2011 - 21:58:11    Titel:

Versuche mal diese Zeichenkette zu Gödelisieren :
x^(-1) != 0

x → 1
^ → 2
( → 3
- → 4
) → 5
1 → 6
!= → 7
= → 8
0 → 9

Jetzt Zeichenkette kodieren
( ''2^(Nr. erstes Zeichen) * 3^(Nr. zweites Zeichen) * 5^(Nr. drittes Zeichen) * ... ''
nehme an, daß die Zahlen vor dem ^ aufsteigende Primzahlen sein sollen; wenn ja, warum? ) :

2^1 * 3^2 * 5^3 * 7^4 * 11^5 * 13^6 * 17^7 * 19^8 *23^9 = n ...irrsinnig hohe nat Zahl !

Stimmt's bisher ?
Grüße mathegyx7
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 06 Sep 2011 - 21:59:42    Titel:

Ja, die Zahl wird groß. Warum die Primzahlen? Weil man mit der eindeutigen Primfaktorzerlegung so eindeutig wieder an die Exponenten kommt...


Cyrix
mathegyx7
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2011
Beiträge: 7

BeitragVerfasst am: 08 Sep 2011 - 19:45:56    Titel:

Hallo Cyrix !

Zu Deinem :
'' Auf diese Weise können wir berechenbar jeder Zeichenkette eine nat. Zahl zuordnen (und umgekehrt dekodieren, ob eine Zahl einer solchen Zeichenkette entspricht, und wenn ja, welcher). Dann …...So ist das eben bei Diagonalisierungsbeweisen... ''

Kennst Du ein Buch, Artikel, Link ,.... in dem diesbezüglich ausführlich durchgearbeitete Beispiele vorgestellt werden ?

Grüße mathegyx7
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 08 Sep 2011 - 19:57:22    Titel:

Die Logik-Vorlesung, die ich gehört habe, findest du unter http://uni-skripte.lug-jena.de/mundhenk-logik.pdf

Cyrix
mathegyx7
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.09.2011
Beiträge: 7

BeitragVerfasst am: 12 Sep 2011 - 08:49:27    Titel:

Hallo Cyrix .

Danke für die Info !
Habe die pdf runtergeladen und werde sie durcharbeiten,

Grüße mathegyx7 !
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Gödel Unvollständigkeitstheorem
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum