Die Mathe-Redaktion - 19.02.2020 04:43 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 826 Gäste und 4 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Prädikatenlogik » Warum ist Peano-Arithmetik in PL1 unvollständig, wenn PL1 vollständig?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Warum ist Peano-Arithmetik in PL1 unvollständig, wenn PL1 vollständig?
YummyBear
Junior Letzter Besuch: im letzten Monat
Dabei seit: 15.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-01-15


Hallo,

kann mir jemand in einfachen Worten erklären, warum es kein Widerspruch ist, dass die PL1 vollständig ist und die Peano-Arithmetik in der PL1 unvollständig?

VG



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5485
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-01-15


Hallo YummyBear,

willkommen auf dem Matheplaneten!

Wahrscheinlich wird dir so tiefliegende Dinge niemand "in einfachen Worten" erklären können.

Aber vielleicht zunächst mal eine Gegenfrage: Kannst du in einfachen Worten darlegen, was "Peano-Arithmetik in der PL1" ist und was es bedeutet, dass diese unvollständig ist?

Oder bringst du vielleicht auch etwas durcheinander?



  Profil  Quote  Link auf diesen Beitrag Link
YummyBear
Junior Letzter Besuch: im letzten Monat
Dabei seit: 15.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-01-16


Hallo auch StrgAltEntf,

okay, also ich habe den Vollständigkeitssatz von Gödel so verstanden:

Die PL1 ist insofern vollständig, als dass es einen Kalkül der Prädikatenlogik erster Stufe geben kann (z. B. den Hilbert-Kalkül), so dass für jede Formelmenge Γ und für jede Formel phi gilt, dass phi aus Γ folg, wenn phi aus Γ ableitbar ist.

Und den ersten Unvollständigkeitssatz von Gödel verstehe ich so:

Gibt es ein formales System, das ausdrucksstark genug ist, die Peano-Arithmetik (also die natürlichen Zahlen und die Additions- und Multiplikations-Operationen) zu formalisieren, so gibt es auch eine Formel, die zwar wahr ist, aber sich nicht beweisen lässt.

Zusammen genommen könnte sich der Widerspruch so auflösen, dass es laut Vollständigkeitssatz Systeme in der PL1 gibt, die vollständig sind. Die Peano-Arithmetik ist aber nicht derlei Gestalt, denn in ihr gibt es wahre Aussagen, die sich nicht beweisen lassen. Denn die Peano-Arithmetik ist ja auch ausdrucksstärker als der Hilbert-Kalkül.

Oder bringe ich jetzt etwas durcheinander?

Viele Grüße

Achso und um deine Frage noch zu beantworten: Die Peano-Arithmetik in der PL1 bedeutet, dass die Ausdrucksstärke der Peano-Arithmetik mit den vorhandenen Mitteln der PL1 definiert ist.



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 215
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-01-17


2020-01-16 23:21 - YummyBear in Beitrag No. 2 schreibt:
okay, also ich habe den Vollständigkeitssatz von Gödel so verstanden: ...

Und den ersten Unvollständigkeitssatz von Gödel verstehe ich so: ...

Das hast Du richtig verstanden. Allerdings muß man für ein formales System für die Peano-Arithmetik noch dessen Korrektheit fordern.

Der Unterschied ist, daß man bei PL1 alle Modelle betrachtet, bei der Peano-Arithmetik jedoch nur eines (modulo Isomorphismus).

2020-01-16 23:21 - YummyBear in Beitrag No. 2 schreibt: Die Peano-Arithmetik in der PL1 bedeutet, dass die Ausdrucksstärke der Peano-Arithmetik mit den vorhandenen Mitteln der PL1 definiert ist.

Hier gibt es das Problem, daß das Induktionsaxiom der Peano-Arithmetik

(1) ∀ M. 0 ∈ M ∧ (∀ n. n ∈ M → n+1 ∈ M) → M = ℕ

nicht in PL1 formulierbar ist. Man kann sich mit der PL1-Version

(2) ∀ φ. φ[0] ∧ (∀ n ∈ ℕ. φ[n] → φ[n+1]) → ∀ n ∈ ℕ. φ[n]

behelfen. Da es überabzählbar viele Teilmengen von ℕ gibt, aber nur abzählbar viele Formeln φ, ist (2) schwächer als (1). D.h. es gibt (seltene) Fälle, in denen ein Beweis mit (1) aber nicht mit (2) geführt werden kann (=> en.wikipedia.org/wiki/Goodstein%27s_theorem ) .



  Profil  Quote  Link auf diesen Beitrag Link
index_razor
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 06.03.2016
Mitteilungen: 177
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-01-17


2020-01-16 23:21 - YummyBear in Beitrag No. 2 schreibt:
Zusammen genommen könnte sich der Widerspruch so auflösen, dass es laut Vollständigkeitssatz Systeme in der PL1 gibt, die vollständig sind. Die Peano-Arithmetik ist aber nicht derlei Gestalt, denn in ihr gibt es wahre Aussagen, die sich nicht beweisen lassen. Denn die Peano-Arithmetik ist ja auch ausdrucksstärker als der Hilbert-Kalkül.

Oder bringe ich jetzt etwas durcheinander?

Hm, also ich habe das etwas anders verstanden.

Es handelt sich m.E. einfach um verschiedene Bedeutungen von "vollständig".  Auch für jede Folgerung aus den Peano-Axiomen kannst du einen formalen Beweis finden (soll heißen: es existiert einer).  In dem Sinne ist auch die Peano-Arithmetik vollständig.

Es gibt aber arithmetische Sätze, die im Standardmodell wahr sind und trotzdem nicht innerhalb der Peano-Arithmetik beweisbar.  In diesem Sinne ist sie unvollständig.  Solche Sätze sind dann, wegen des Vollständigkeitssatzes, natürlich auch keine Folgerungen aus den Peano-Axiomen.  Es gibt also Modelle der Peano-Axiome, in denen sie nicht gelten.  Das sind dann Nichtstandardmodelle der Arithmetik.




  Profil  Quote  Link auf diesen Beitrag Link
YummyBear
Junior Letzter Besuch: im letzten Monat
Dabei seit: 15.01.2020
Mitteilungen: 12
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-01-19


2020-01-17 13:38 - index_razor in Beitrag No. 4 schreibt:

Es gibt aber arithmetische Sätze, die im Standardmodell wahr sind und trotzdem nicht innerhalb der Peano-Arithmetik beweisbar.  In diesem Sinne ist sie unvollständig.  Solche Sätze sind dann, wegen des Vollständigkeitssatzes, natürlich auch keine Folgerungen aus den Peano-Axiomen.  Es gibt also Modelle der Peano-Axiome, in denen sie nicht gelten.  Das sind dann Nichtstandardmodelle der Arithmetik.



Das verstehe ich nicht ganz, könntest Du das ein bisschen weiter ausführen?




  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
index_razor
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 06.03.2016
Mitteilungen: 177
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-01-24 20:24


2020-01-19 23:42 - YummyBear in Beitrag No. 5 schreibt:
2020-01-17 13:38 - index_razor in Beitrag No. 4 schreibt:

Es gibt aber arithmetische Sätze, die im Standardmodell wahr sind und trotzdem nicht innerhalb der Peano-Arithmetik beweisbar.  In diesem Sinne ist sie unvollständig.  Solche Sätze sind dann, wegen des Vollständigkeitssatzes, natürlich auch keine Folgerungen aus den Peano-Axiomen.  Es gibt also Modelle der Peano-Axiome, in denen sie nicht gelten.  Das sind dann Nichtstandardmodelle der Arithmetik.



Das verstehe ich nicht ganz, könntest Du das ein bisschen weiter ausführen?

Was genau meinst du denn?  Also wir haben einerseits die Peano-Axiome samt deren Folgerungen.  Die Folgerungen gelten natürlich in jedem Modell.  Das ist einfach was das Wort "Folgerung" bedeutet.  Nach dem Vollständigkeitssatz existiert für jede dieser Folgerungen ein formaler Beweis.  

Die Peano-Axiome samt ihren Folgerungen ergeben aber nicht alle wahren arithmetischen Aussagen.  Das ist die anschauliche Bedeutung des Unvollständigkeitssatzes.  Da besteht kein Widerspruch.



  Profil  Quote  Link auf diesen Beitrag Link
YummyBear wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]