Unentscheidbarkeit und Wahrheit

27/08/2011 - 16:05 von carlox | Report spam
Hallo allerseits,
bevor ich meine Frage stelle, ein paar Bezeichnungen:

I)
1)
Peanosches Axiomensystem
2, 3, 4, ... sind Abkuerzungen fuer die Terme (der durch die
zweistelligen
Operanden + und * und der 0-stelligen Operanden 0 und 1 bestimmten
formalen Sprache):
(1+1) bzw. (1+1)+1) bzw. (((1+1)+1)+1), ...
N := {0, 1, 2, 3, 4, ...}

2)
Wenn man voraussetzt, dass ZFC widerspruchsfrei ist, besitzt ZFC ein
Modell.
Aus diesem Modell (so habe ich gelesen) kann man dann das
Standardmodell SM der naturlichen Zahlen konstruieren:
SM = (|N, ++, **) mit
Traegermenge |N := {0_ , 1_ , 2_ , 3_ , ...}
wobei ++ und ** die zu + und * zugehoerigen mathematischen Funktionen
darstellen.
und 0_ , 1_, 2_, 3_, ... die interpretierten Terme 0, 1, 2, 3, ...
darstellen, wobei gilt:
2_ = (1_ ++ 1_)
3_ = ((1_ ++ 1_) ++ 1_)
4_ = (((1_ ++ 1_) ++ 1_) ++ 1_)
...

Frage:
Was sind die natuerlichen Zahlen:
N oder |N ?


3)
|- bedeutet Beweisbarkeit
|= bedeutet Gueltigkeit
|S=A bedeutet "Die Formel A ist in der Struktur S gueltig bzw. S ist eine Modell von {A}
(d.h. fuer jede Belegung h ist der Wahrheitswert von A in S wahr).

Damit Goedelscher Vollstaendigkeitssatz:
G |= A <==> G |- A
(A ist in jedem Modell von G gueltig <==> A ist aus der Formelmenge G
beweisbar)

II)
1)
T ist die Menge aller Terme, die aus Elementen aus N bestehen, den
Operanden + und *.
Mit FM werde die Menge aller Formeln bezeichnet, die sich aus T
konstruieren lassen.
Beispiel (and bzw. or bedeuten das logische UND bzw. ODER)
(4+6)*8 = 2+9 and (3*6) = 18 or (2+2)=(2*2)
ist ein Element aus FM

Vermutung V (von mir):
Sei SM das Standardmodell des Peanoschen Axiomensystems PA und m ein
Element aus FM, dann gilt:
|SM= m <==> PA |- m

Beispiel:
7_ ** 7_ = 49_ <==> PA |- 7 * 7 = 49

Frage:
Ist diese Vermutung V von mir richtig?

Das wuerde bedeuten:
Koennte man von der Zahl 200_ zeigen, dass sie nicht Summe zweier
Primzahlen p1_ und p2_ ist, dann koennte man daraus schliessen:
PA |- 200 ist nicht Summe zweier Primzahlen p1 und p2

2)
Jetzt zu dem Zitat (aus Kapitel 5 Ungeloeste Raetsel 7
Unentscheidbarkeit und Wahrheit)

http://www.joergresag.privat.t-onli...chap57.htm

"Wenn A unentscheidbar ist, so gibt es Modelle der Peano-Arithmetik,
in denen A falsch ist. Aber auch in diesen Modellen ist A fuer alle
natuerlichen Zahlen (also fuer allen n-fachen Nachfolger der Null)
wahr, d.h. alle n-fachen Nachfolger der Null haben nicht die
Eigenschaft P(n)."

Der Satz:
"Wenn A unentscheidbar ist, so gibt es Modelle der Peano-Arithmetik,
in denen A falsch ist.", ist mir noch klar, aber ich verstehe nicht,
warum gilt:
"Aber auch in diesen Modellen ist A fuer alle natuerlichen Zahlen
(also
fuer allen n-fachen Nachfolger der Null) wahr, d.h. alle n-fachen
Nachfolger der Null haben nicht die Eigenschaft P(n)."

PMX sei irgendein Modell von PA mit folgender Interpretation:
+++ ist eine Interpretation von +
und es ist z.B.
4_ _ irgendeine Interpretation des Terms 4 mit
4_ _ = (((1_ _+++ 1_ _) +++ 1_ _) +++ 1_ _)
...

Warum muss dann P(4_ _) wahr sein?
Warum kann PMX nicht so konstruiert werden, dass P(4_ _) falsch ist ?


mfg
Ernst
 

Lesen sie die antworten

#1 Carsten Schultz
28/08/2011 - 08:49 | Warnen spam
Am 27.08.11 16:05, schrieb Ernst Baumann:
Vermutung V (von mir):
Sei SM das Standardmodell des Peanoschen Axiomensystems PA und m ein
Element aus FM, dann gilt:
|SM= m <==> PA |- m

Beispiel:
7_ ** 7_ = 49_ <==> PA |- 7 * 7 = 49

Frage:
Ist diese Vermutung V von mir richtig?



Nein, denn aus ihr folgt direkt die Vollstàndigkeit von PA.


Das wuerde bedeuten:
Koennte man von der Zahl 200_ zeigen, dass sie nicht Summe zweier
Primzahlen p1_ und p2_ ist, dann koennte man daraus schliessen:
PA |- 200 ist nicht Summe zweier Primzahlen p1 und p2




Ob 200 Summe zweier Primzahlen ist, làsst sich durch Aufzàhlung aller
Möglichkeiten entscheiden, diese Aussage ist daher in PA entscheidbar
und daher dort ableitbar genau dann, wenn sie wahr ist.


2)
Jetzt zu dem Zitat (aus Kapitel 5 Ungeloeste Raetsel 7
Unentscheidbarkeit und Wahrheit)

http://www.joergresag.privat.t-onli...chap57.htm

"Wenn A unentscheidbar ist, so gibt es Modelle der Peano-Arithmetik,
in denen A falsch ist. Aber auch in diesen Modellen ist A fuer alle
natuerlichen Zahlen (also fuer allen n-fachen Nachfolger der Null)
wahr, d.h. alle n-fachen Nachfolger der Null haben nicht die
Eigenschaft P(n)."



Dazu kann man nichts sagen ohne zu wissen, welcher Art A und P sind.

Gruß

Carsten

Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.

Ähnliche fragen