Die Mathe-Redaktion - 22.02.2018 11:29 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
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 oder den Newsletter bestellen.

Der Newsletter Okt. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Mathematik » Logik, Mengen & Beweistechnik » Peano unentscheidbar ?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Peano unentscheidbar ?
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-01-17


Hallo allerseits,
Jörg Resag schreibt auf seiner Website:
www.joerg-resag.de/mybk3htm/chap57.htm

"Woher kann man wissen, ob A in der Peano-Arithmetik unentscheidbar ist? Innerhalb der Peano-Arithmetik kann man das jedenfalls nicht beweisen, denn sonst hätte die Peano-Arithmetik ja bewiesen, dass es keine Gegenbeispiele in den natürlichen Zahlen gibt."

=====================================================
Es geht um Folgendes:
Angenommen eine zahlentheoretische Aussage A (wie z.B. die Goldbachsche Vermutung GB) wäre in der Peanoarithmetik (PA) unentscheidbar und man könnte die Unentscheidbarkeit von A _innerhalb_ von PA beweisen.
Wenn man ein Gegenbeispiel für A finden würde (z.B. die Zahl 100), dann (das kann man zeigen), kann man dieses Gegenbeispiel als Beweis formalisieren d.h. beweisen, daß non A ableitbar ist.

Leider verstehe ich das Argument von Jörg Resag nicht!
Angenommen, man hätte in der Peano-Arithmetik bewiesen, dass es keine Gegenbeispiele in den natürlichen Zahlen gibt.
Was hätte das zur Folge bzw. welchen Widerspruch hätte das zur Folge.
Wer kann mir da weiterhelfen?
Ich komme da nicht weiter.

Vor allem was würde sich an der Argumentation von Jörg Resag ändern, wenn man die Unentscheidbarkeit von PA außerhalb von PA zeigen könnte.
Dann funktioniert sein Argument vermutlich nicht mehr. Warum ?

mfg
cx











  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-01-19


In der Berechenbarkeitstheorie bezeichnet man eine Teilmenge M von ℕ als entscheidbar, falls es ein algorithmisches Verfahren gibt, daß gestartet mit einem beliebigen n ∈ ℕ (als Eingabe) immer ein Ergebnis berechnet, und zwar "1" gdw. n ∈ M.

Puristen lesen "Turingmaschine" für "algorithmisches Verfahren", alle anderen lesen einfach "Programm in einer gängigen Programmiersprache".

Die Ausgabe "1" ist natürlich willkürlich, es kann auch "ja" oder "stimmt!" oder sonstwas heißen.

Die Beschränkung auf Teilmengen von ℕ reduziert die Angelegenheit auf ihren mathematischen Kern. Natürlich kann man auch andere Mengen betrachten. Rein formal muß man sich dann mit Gödelnummern behelfen, um die Fragestellung wieder auf ℕ zu reduzieren.

Das mal als Vorbemerkung zu den gestellten Fragen, die nicht beantworten kann, da ich sie nicht verstehe.

2018-01-17 20:15 - carlox im Themenstart schreibt:
Angenommen eine zahlentheoretische Aussage A (wie z.B. die Goldbachsche Vermutung GB) wäre in der Peanoarithmetik (PA) unentscheidbar und man könnte die Unentscheidbarkeit von A _innerhalb_ von PA beweisen.

Was soll denn jetzt heißen "Eine >Aussage< ist (un)entscheidbar"? Das ist ja genauso als wenn man nicht fragt, ob M ⊂ ℕ entscheidbar ist, sondern ob n ∈ ℕ entscheidbar ist ???  

Und was soll Entscheidbarkeit >in der Peano-Arithmetik< bedeuten?  

2018-01-17 20:15 - carlox im Themenstart schreibt:
Vor allem was würde sich an der Argumentation von Jörg Resag ändern, wenn man die Unentscheidbarkeit von PA außerhalb von PA zeigen könnte.

Der 1. Gödelsche Unvollständigkeitssatz besagt, daß für jeden (korrekten!) Kalkül K von PA eine Formel ϕ(K) existiert, so daß ϕ(K) bzgl. der Semantik von PA wahr ist (also eine >wahre< arithmetische Aussage ist), jedoch in K nicht herleitbar ist.

In Termini der Berechenbarkeitstheorie heißt das: Die Menge der wahren arithmetischen Formeln ist nicht rekursiv aufzählbar und damit kann diese insbesondere auch nicht entscheidbar sein.

Kurzum, die Unentscheidbarkeit von PA ist ja eine einfache Folgerung des Gödelsatzes und damit bewiesen. Was soll jetzt  "Unentscheidbarkeit von PA außerhalb von PA zeigen" bedeuten?



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-01-21


Hallo Zwerg_Allwissend,
2018-01-19 23:14 - Zwerg_Allwissend in Beitrag No. 1 schreibt:
Was soll denn jetzt heißen "Eine >Aussage< ist (un)entscheidbar"? Das ist ja genauso als wenn man nicht fragt, ob M ⊂ ℕ entscheidbar ist, sondern ob n ∈ ℕ entscheidbar ist ???  
Eine Aussage A heißt unentscheidbar gdw sowohl A als auch non A nicht aus dem Beweiskalkül abgeleitet werden kann.

Bem:
Der Begriff unentscheidbar wird aber auch (siehe dein Posting) in der Berechenbarkeitstheorie benutzt. Also ist er doppeldeutig. Keine Ahnung, warum das so gemacht wird.


Und was soll Entscheidbarkeit >in der Peano-Arithmetik< bedeuten?  
Der Beweis, daß sowohl A als auch non A nicht aus dem PA-Kalkül ableitbar ist, muß innerhalb (also mit den Mitteln von PA) formuliert werden.


Kurzum, die Unentscheidbarkeit von PA ist ja eine einfache Folgerung des Gödelsatzes und damit bewiesen.
Aber nicht, wenn du die von mir verwendete Bedeutung des Begriffs Unentscheidbarkeit verwendest.


Was soll jetzt  "Unentscheidbarkeit von PA außerhalb von PA zeigen" bedeuten?
Der Beweis, daß sowohl A als auch non A nicht aus dem PA-Kalkül ableitbar ist, wird  außerhalb von PA formuliert:
zum Beispiel wird innerhalb von ZFC  PA in ZFC formuliert (mit
den Mitteln von ZFC) und in ZFC die Unentscheidbarkeit bewiesen.

mfg
cx









  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-01-22


OK, aber trotzdem geht hier etwas durcheinander. Damit wir im folgenden nicht die Begriffe verwechseln, verwende ich "entscheidbar" so, wie ich es in #1 definiert habe, Entscheidbarkeit im Sinne von "weder Formel noch deren Negat herleitbar" nenne ich mal "unabhängig (vom betrachteten Kalkül)".

2018-01-21 10:27 - carlox in Beitrag No. 2 schreibt:
Hallo Zwerg_Allwissend,

Kurzum, die Unentscheidbarkeit von PA ist ja eine einfache Folgerung des Gödelsatzes und damit bewiesen.
Aber nicht, wenn du die von mir verwendete Bedeutung des Begriffs Unentscheidbarkeit verwendest.

Doch, dann erst recht. Dann ist das keine "einfache Folgerung" des Gödelsatzes, sondern dann IST das der Gödelsatz. Der lautet ja mit diesen Begriffsbildungen:

Für jeden korrekten Kalkül der Peano Arithmetik existiert eine unabhängige Formel.

Und zur Eingangsfrage des Postings:

Wenn man mit dem Begriff "Gegenbeispiel" operiert, dann muß erst mal formal sauber definiert werden, was das genau sein soll. Man kann nicht einen informellen Begriff in eine präzis definierte mathematische Theorie einführen und dann erwarten, daß man belastbare Aussagen erhält.

Man braucht "Gegenbeispiel" aber auch gar nicht.

2018-01-17 20:15 - carlox im Themenstart schreibt:
Angenommen eine zahlentheoretische Aussage A (wie z.B. die Goldbachsche Vermutung GB) wäre in der Peanoarithmetik (PA) unentscheidbar und man könnte die Unentscheidbarkeit von A _innerhalb_ von PA beweisen.
Wenn man ein Gegenbeispiel für A finden würde (z.B. die Zahl 100), dann (das kann man zeigen), kann man dieses Gegenbeispiel als Beweis formalisieren d.h. beweisen, daß non A ableitbar ist.

Die Annahmen sind ja offensichtlich widersprüchlich! Wenn gezeigt wurde, daß A unabhängig ist, so kann es keinen Beweis für non-A geben. Denn gäbe es einen, so wäre A nicht unabhängig.

Man sieht: Das Gewurschtel mit "Gegenbeispiel" verschleiert den Blick auf die Sache.  



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-01-22


Hallo Zwerg_Allwissend,
erst mal recht herzlichen Dank für dein Feedback.

1)
2018-01-22 00:48 - Zwerg_Allwissend in Beitrag No. 3 schreibt:
OK, aber trotzdem geht hier etwas durcheinander. Damit wir im folgenden nicht die Begriffe verwechseln, verwende ich "entscheidbar" so, wie ich es in #1 definiert habe, Entscheidbarkeit im Sinne von "weder Formel noch deren Negat herleitbar" nenne ich mal "unabhängig (vom betrachteten Kalkül)".
Vermutlich habe ich den Begriff "entscheidbar" unreflektiert so übernommen, wie ich ihn in meiner Quelle angetroffen habe.
Im Folgenden werde ich den Begriff "unabhängig" (vom betrachteten Beweissystem) so verwenden wie du ihn benutzt, also im Sinne von weder Formel noch deren Negat herleitbar.
Kurze Frage: Ist das der offizielle Begriff?


2)

Und zur Eingangsfrage des Postings:
Wenn man mit dem Begriff "Gegenbeispiel" operiert, dann muß erst mal formal sauber definiert werden, was das genau sein soll. Man kann nicht einen informellen Begriff in eine präzis definierte mathematische Theorie einführen und dann erwarten, daß man belastbare Aussagen erhält.
Du hast Recht! Deswegen hier meine Definition von Gegenbeispiel:
Ein Gegenbeispiel zu einer zahlentheoretischen Vermutung A ist die Benennung einer natürlichen Zahl, für die A im Standardmodell von PA falsch wird.

3)

Man braucht "Gegenbeispiel" aber auch gar nicht.

2018-01-17 20:15 - carlox im Themenstart schreibt:
Angenommen eine zahlentheoretische Aussage A (wie z.B. die Goldbachsche Vermutung GB) wäre in der Peanoarithmetik (PA) unentscheidbar und man könnte die Unentscheidbarkeit von A _innerhalb_ von PA beweisen.
Wenn man ein Gegenbeispiel für A finden würde (z.B. die Zahl 100), dann (das kann man zeigen), kann man dieses Gegenbeispiel als Beweis formalisieren d.h. beweisen, daß non A ableitbar ist.

Die Annahmen sind ja offensichtlich widersprüchlich! Wenn gezeigt wurde, daß A unabhängig ist, so kann es keinen Beweis für non-A geben. Denn gäbe es einen, so wäre A nicht unabhängig.

Genau: Deshalb kann es kein Gegenbeispiel geben. Also ist A im Standardmodell von PA wahr!

Deswegen folgt insgesamt:
Wenn die obige zahlentheoretische Aussage A unabhängig von PA ist, dann muß A im Standardmodell von PA wahr sein.

Bist du damit einverstanden ?

mfg
cx





  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-01-22


2018-01-22 08:17 - carlox in Beitrag No. 4 schreibt:
1)
2018-01-22 00:48 - Zwerg_Allwissend in Beitrag No. 3 schreibt:
OK, aber trotzdem geht hier etwas durcheinander. Damit wir im folgenden nicht die Begriffe verwechseln, verwende ich "entscheidbar" so, wie ich es in #1 definiert habe, Entscheidbarkeit im Sinne von "weder Formel noch deren Negat herleitbar" nenne ich mal "unabhängig (vom betrachteten Kalkül)".
2018-01-22 08:17 - carlox in Beitrag No. 4 schreibt:
Vermutlich habe ich den Begriff "entscheidbar" unreflektiert so übernommen, wie ich ihn in meiner Quelle angetroffen habe.
Im Folgenden werde ich den Begriff "unabhängig" (vom betrachteten Beweissystem) so verwenden wie du ihn benutzt, also im Sinne von weder Formel noch deren Negat herleitbar.
Kurze Frage: Ist das der offizielle Begriff?

Weiss ich nicht.

2018-01-22 08:17 - carlox in Beitrag No. 4 schreibt:
2)

Und zur Eingangsfrage des Postings:
Wenn man mit dem Begriff "Gegenbeispiel" operiert, dann muß erst mal formal sauber definiert werden, was das genau sein soll. Man kann nicht einen informellen Begriff in eine präzis definierte mathematische Theorie einführen und dann erwarten, daß man belastbare Aussagen erhält.
Du hast Recht! Deswegen hier meine Definition von Gegenbeispiel:
Ein Gegenbeispiel zu einer zahlentheoretischen Vermutung A ist die Benennung einer natürlichen Zahl, für die A im Standardmodell von PA falsch wird.

Aha. Und wie sieht das dann bei einer Formel wie
 
fed-Code einblenden
aus?



2018-01-22 08:17 - carlox in Beitrag No. 4 schreibt:
3)

Man braucht "Gegenbeispiel" aber auch gar nicht.

2018-01-17 20:15 - carlox im Themenstart schreibt:
Angenommen eine zahlentheoretische Aussage A (wie z.B. die Goldbachsche Vermutung GB) wäre in der Peanoarithmetik (PA) unentscheidbar und man könnte die Unentscheidbarkeit von A _innerhalb_ von PA beweisen.
Wenn man ein Gegenbeispiel für A finden würde (z.B. die Zahl 100), dann (das kann man zeigen), kann man dieses Gegenbeispiel als Beweis formalisieren d.h. beweisen, daß non A ableitbar ist.

Die Annahmen sind ja offensichtlich widersprüchlich! Wenn gezeigt wurde, daß A unabhängig ist, so kann es keinen Beweis für non-A geben. Denn gäbe es einen, so wäre A nicht unabhängig.
Genau: Deshalb kann es kein Gegenbeispiel geben. Also ist A im Standardmodell von PA wahr!

Deswegen folgt insgesamt:
Wenn die obige zahlentheoretische Aussage A unabhängig von PA ist, dann muß A im Standardmodell von PA wahr sein.

Bist du damit einverstanden ?

Nein. Es muß heißen: ... muß entweder A oder ~A im Standardmodell von PA wahr sein. Das gilt aber trivialerweise für jede zahlentheoretische Aussage A, egal ob diese unabhängig ist oder nicht.

Für jede zahlentheoretische Aussage gilt: A ist wahr oder ~A ist wahr. Damit auch: A ist falsch oder ~A ist falsch. Damit auch: Es gibt entweder ein Gegenbeispiel für A oder es gibt ein Gegenbeispiel für ~A.

Wie ich schon schrieb, entsteht die Verwirrung durch den informellen Begriff "Gegenbeispiel" mittels dessen dann Behauptungen über (nicht-)Herleitbarkeit irgendwelcher Formeln postuliert werden.

Ich kenne kein Buch über formale Logik, in dem der Begriff "Gegenbeispiel" formalisiert wird und dann Sätze darüber bewiesen werden. Was ja nicht heißt, daß man das nicht machen kann. Aber da ich sowas noch nie gesehen habe, braucht man es wohl nicht.



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-01-22


I)

Du hast Recht! Deswegen hier meine Definition von Gegenbeispiel:
Ein Gegenbeispiel zu einer zahlentheoretischen Vermutung A ist die Benennung einer natürlichen Zahl, für die A im Standardmodell von PA falsch wird.

Aha. Und wie sieht das dann bei einer Formel wie
fed-Code einblenden
aus?

Hiermit ziehe ich meine Formalisierung des Begriffs "Gegenbeispiel" zurück.
Es kann auch sein, daß es keine "Gegenbeispiele" gibt.
Statt einer Formalisierung ein intuitives Beispiel für "Gegenbeispiel"
1) "Silberbachsche Vermutung":
Jede gerade Zahl n>2 kann als Summe zweier ungleicher Primzahlen dargestellt werden.
Gegenbeispiel:
n=6

Bemerkung:
Wenn man ein Gegenbeispiel zu einer zahlentheoretischen Aussage A angeben kann, kann man ~A in PA ableiten.

2) "Kupferbachsche Vermutung":
Jede gerade Zahl n>2 kann als Differenz zweier ungerader Primzahlen dargestellt werden.
Da kann ich dir leider kein Gegenbeispiel liefern, da man bei jeder geraden Zahl unendlich vielen Möglichkeiten durchsuchen muß (im Gegensatz zur "Silberbachsche Vermutung": da muß man bei jeder geraden Zahl nur endlich viele Möglichkeiten durchsuchen muß).

II)

Deswegen folgt insgesamt:
Wenn die obige zahlentheoretische Aussage A unabhängig von PA ist, dann muß A im Standardmodell von PA wahr sein.

Bist du damit einverstanden ?
Nein. Es muß heißen: ... muß entweder A oder ~A im Standardmodell von PA wahr sein. Das gilt aber trivialerweise für jede zahlentheoretische Aussage A, egal ob diese unabhängig ist oder nicht.
Ich bestehe weiterhin auf meiner Behauptung:
Wenn eine zahlentheoretische Aussage A unabhängig von PA ist, dann muß A im Standardmodell von PA wahr sein.
Beweis:
Wenn A unabhängig von PA ist, dann gibt es ein Modell, in dem falsch ist und ein Modell, in dem A wahr ist.
Annahme: Das Standardmodell sei ein Modell, in dem A falsch ist. Dann wäre A auch jedem anderen Modell falsch, da das Standardmodell ja Anfangsmodell jedes anderen Modells ist.
Dann wäre A aber in jedem Modell falsch. Also wäre A in PA beweisbar. Dies steht im Widerspruch zur Unabhängigkeit der Aussage A von PA.

Bist du damit einverstanden ?

mfg
cx






  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-01-22


2018-01-22 20:51 - carlox in Beitrag No. 6 schreibt:
I)
Hiermit ziehe ich meine Formalisierung des Begriffs "Gegenbeispiel" zurück.
Es kann auch sein, daß es keine "Gegenbeispiele" gibt.
Statt einer Formalisierung ein intuitives Beispiel für "Gegenbeispiel"

Beispiele für Gegenbeispiele - sehr schön!

Wäre aber nicht nötig gewesen. Mir ist schon klar, was man (informell) unter einem Gegenbeispiel versteht. Ich habe mich an der Behauptung gestört, daß aus der Existenz eines Gegenbeispiels für A einen Beweis für ~A konstruiert werden kann. Dazu muß man (1) mathematisch definieren, was unter einem formalen Gegenbeispiel genau zu verstehen ist, und damit dann (2) die angegebene Behauptung beweisen. Andernfalls ist das Hokuspokus.

Wie ich schon in #3 geschrieben habe: Man kann nicht einen informellen Begriff in eine präzis definierte mathematische Theorie einführen und dann erwarten, daß man belastbare Aussagen erhält.


Ich bestehe weiterhin auf meiner Behauptung:
Wenn eine zahlentheoretische Aussage A unabhängig von PA ist, dann muß A im Standardmodell von PA wahr sein.
Beweis:
Wenn A unabhängig von PA ist, dann gibt es ein Modell, in dem falsch ist und ein Modell, in dem A wahr ist.
Annahme: Das Standardmodell sei ein Modell, in dem A falsch ist. Dann wäre A auch jedem anderen Modell falsch, da das Standardmodell ja Anfangsmodell jedes anderen Modells ist.
Dann wäre A aber in jedem Modell falsch. Also wäre A in PA beweisbar. Dies steht im Widerspruch zur Unabhängigkeit der Aussage A von PA.

Bist du damit einverstanden ?

Nein. Vor ein paar Jahrhunderten wärst Du für Deine Hartnäckigkeit auf dem Scheiterhaufen gelandet.

"A in jedem Modell [der Peanoarithmetik] falsch" => "A in PA beweisbar"

Warum? In diesem Schritt steckt das Problem.


PS: Vermeide Privatbegriffe und suche in Lehrbüchern nach Standard-Begriffen, mit denen Du Deine Gedanken formulieren kannst.

Beispiel: Anfangsmodell, was soll das sein? "... das Standardmodell ja Anfangsmodell jedes anderen Modells ist" - was Du hier sagen willst kann man mit dem Begriff der Theorie einer Interpretation ausdrücken. Wenn man mit schwammigen, informellen Begriffen hantiert, kommt man leicht zu merkwürdigen Ergebnissen.      



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-01-23



Nein. Vor ein paar Jahrhunderten wärst Du für Deine Hartnäckigkeit auf dem Scheiterhaufen gelandet.
Vermutlich werde ich dich nicht überzeugen können.
Deswegen verweise ich auf:
matheplanet.com/default3.html?topic=217999=1718
Beitrag Nr. 6
Betreff:
Gegenbeispiel zur Goldbachschen Vermutung impliziert Beweis
Hat dich das überzeugt?



PS: Vermeide Privatbegriffe und suche in Lehrbüchern nach Standard-Begriffen, mit denen Du Deine Gedanken formulieren kannst.
Beispiel: Anfangsmodell, was soll das sein? "... das Standardmodell ja Anfangsmodell jedes anderen Modells ist" - was Du hier sagen willst kann man mit dem Begriff der Theorie einer Interpretation ausdrücken. Wenn man mit schwammigen, informellen Begriffen hantiert, kommt man leicht zu merkwürdigen Ergebnissen.      
Ich habe mich falsch ausgedrückt: Es sollte Anfangsstück heißen.

mfg
cx





  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-01-23


2018-01-23 06:52 - carlox in Beitrag No. 8 schreibt:
Vermutlich werde ich dich nicht überzeugen können.
Deswegen verweise ich auf:
matheplanet.com/default3.html?topic=217999=1718
Beitrag Nr. 6
Betreff:
Gegenbeispiel zur Goldbachschen Vermutung impliziert Beweis
Hat dich das überzeugt?

In diesem Thread wird in #12 ein Link math.stackexchange.com/q/1082723 angegeben, in dem man einen sauber aufgeschriebenen Beweis ohne undefinierte Begriffe wie "Gegenbeispiel" etc. findet. Die bewiesene Behauptung bezieht sich auf die Goldbach Vermutung und kann wie folgt verallgemeinert werden:

Sei fed-Code einblenden eine Formel der Arithmetik. Dann gilt:
Wenn fed-Code einblenden unabhängig ist, so ist fed-Code einblenden wahr (wird vom Standardmodell erfüllt).

Man sieht sofort im Beweis, daß dieser nur funktioniert wenn der äußerste Quantor einer Behauptung universell ist.  
 
(2018-01-22 20:51 - carlox in <a href=viewtopic.php?
Ich bestehe weiterhin auf meiner Behauptung:
Wenn eine zahlentheoretische Aussage A unabhängig von PA ist, dann muß A im Standardmodell von PA wahr sein.
Beweis:
Wenn A unabhängig von PA ist, dann gibt es ein Modell, in dem falsch ist und ein Modell, in dem A wahr ist.
Annahme: Das Standardmodell sei ein Modell, in dem A falsch ist. Dann wäre A auch jedem anderen Modell falsch, da das Standardmodell ja Anfangsmodell jedes anderen Modells ist.
Dann wäre A aber in jedem Modell falsch. Also wäre A in PA beweisbar. Dies steht im Widerspruch zur Unabhängigkeit der Aussage A von PA.

Es wäre besser, wenn Du einen sauber aufgeschriebenen Beweis ohne undefinierte Begriffe genau so wie in dem o.a. Link posten würdest. Den könnte man sich dann anschauen und feststellen, ob er stimmt.

Für beliebige Aussagen funktioniert der Beweis aus math.stackexchange.com/q/1082723  jedenfalls nicht. Man bekommt nur:

Sei fed-Code einblenden eine Formel der Arithmetik. Dann gilt:
Wenn fed-Code einblenden unabhängig ist, so ist fed-Code einblenden wahr (wird vom Standardmodell erfüllt).

bzw.

Sei fed-Code einblenden eine Formel der Arithmetik. Dann gilt:
Wenn fed-Code einblenden unabhängig ist, so ist fed-Code einblenden falsch (wird vom Standardmodell nicht erfüllt).

Nach Deinem Verweis auf den anderen Thread (der mir einige Zeit erspart hätte) frage ich mich jetzt, was hier eigentlich Dein Problem ist? In dem anderen Thread wurde die Sache doch schon geklärt?!  



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-01-23


2 Korrekturen zu #9  + 2 zusätzliche Anmerkungen:

2018-01-23 13:56 - Zwerg_Allwissend in Beitrag No. 9 schreibt:
In diesem Thread wird in #12 ein Link math.stackexchange.com/q/1082723 angegeben, in dem ...

Muß heißen: In diesem Thread wird in #14 ein Link math.stackexchange.com/q/1082723 angegeben, in dem ...

2018-01-23 13:56 - Zwerg_Allwissend in Beitrag No. 9 schreibt:
2018-01-23 06:52 - carlox in Beitrag No. 8 schreibt:
Ich bestehe weiterhin auf meiner Behauptung:
Wenn eine zahlentheoretische Aussage A unabhängig von PA ist, dann muß A im Standardmodell von PA wahr sein.

Es wäre besser, wenn Du einen sauber aufgeschriebenen Beweis ohne undefinierte Begriffe genau so wie in dem o.a. Link posten würdest. Den könnte man sich dann anschauen und feststellen, ob er stimmt.

Muß heißen: Die Behauptung ist falsch. Wenn A die Form fed-Code einblenden hat, so ist A im Standardmodell von PA falsch (Beweis siehe Beitrag #9).


Noch zwei Anmerkungen: Es gilt

(1) A unabhängig gdw. ~A unabhängig.
(2) A wahr im Standardmodell oder ~A wahr im Standardmodell

Hier ist es erst mal völlig egal ob, A die Form fed-Code einblenden oder die Form fed-Code einblenden hat, das ist sozusagen "symmetrisch".

Aber bei der Behauptung aus #9 hört die Symmetrie auf, denn fed-Code einblenden ist wahr und fed-Code einblenden ist falsch (jeweils im Standardmodell). Interessante Erkenntnis.

Für den Beweis oder die Widerlegung der Goldbach Vermutung hat das Ganze jedoch keine praktischen Konsequenzen:

Arbeitet man "direkt", so muß man sich mit jeder Menge Zahlentheorie inkl. Primzahlen herumschlagen. Das ist offenbar nicht einfach, denn bisher haben sich schon viele Leute daran die Zähne ausgebissen.

Mit dem Nachweis der Unabhängigkeit ist nichts gewonnen, d.h. es wird noch mühsamer. Jetzt muß man 2 Beweise führen, A nicht herleitbar und auch ~A nicht herleitbar. Und generisch geht das nicht, d.h. man muß sich trotzdem noch mit jeder Menge Zahlentheorie inkl. Primzahlen herumschlagen.



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2018-01-24


Hallo Zwerg_Allwissend,
vielen Dank für dein wertvolles Feedback und für deine Zeit.
Ich habe mir - aufgrund deiner Argumente - ewig lang den Beweis
math.stackexchange.com/q/1082723
angeschaut und komme an einem Punkt leider nicht weiter:
... also existiert ein a aus |N so daß für alle Primzahlen p,q aus |N gilt a != p+q
Daraus wird dann gefolgert, dass für ein beliebiges Modell M1 von PA gilt:
es existiert ein a aus M1 so daß für alle Primzahlen p,q aus M1 gilt a != p+q.
Diese Folgerung verstehe ich nicht.
Da a aus |N ist, ist a auch aus M1. Das ist mir noch klar (weil |N Teilmenge von der Trägermenge eines jeden Modells von PA ist).
Aber warum kann es keine zwei Primzahlen p,q _aus_ M1 (z.B. übernatürliche Zahlen!) geben, so daß a != p + q ?
Man kann doch nicht sagen, wenn es für alle p,q aus |N nicht möglich ist, ist es auch nicht für alle p,q aus M1 möglich (M1 beeinhaltet ja viel mehr Elemente als |N)
Vielleicht hängt dieser Schluss hier noch speziell mit der GC zusammen, aber wie kann man das allgemein begründen, d.h:
Allgemeiner gefragt (weil du den Beweis verallgemeinert hast):
Angenommen, es existiert ein a aus |N so daß für alle b, c aus |N gilt B(a,b, c).
Wie kann man daraus folgen:
es existiert ein a aus M1 so daß für alle b, c aus M1 gilt B(a,b, c) ?
Das ist mir nicht klar!
Es könnte doch b, c (z.B. 2 übernatürliche Zahlen) aus M1 geben, so daß B(a,b,c) falsch wird !
Und dann gilt es nicht mehr für alle a,b aus M1 !
Wo ist mein Denkfehler?

mfg
cx



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2018-01-24





  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-01-24


2018-01-24 18:35 - carlox in Beitrag No. 11 schreibt:
Hallo Zwerg_Allwissend,
vielen Dank für dein wertvolles Feedback und für deine Zeit.
Ich habe mir - aufgrund deiner Argumente - ewig lang den Beweis
math.stackexchange.com/q/1082723
angeschaut und komme an einem Punkt leider nicht weiter:
... also existiert ein a aus |N so daß für alle Primzahlen p,q aus |N gilt a != p+q
Daraus wird dann gefolgert, dass für ein beliebiges Modell M1 von PA gilt:
es existiert ein a aus M1 so daß für alle Primzahlen p,q aus M1 gilt a != p+q.
Diese Folgerung verstehe ich nicht.
Da a aus |N ist, ist a auch aus M1. Das ist mir noch klar (weil |N Teilmenge von der Trägermenge eines jeden Modells von PA ist).
Aber warum kann es keine zwei Primzahlen p,q _aus_ M1 (z.B. übernatürliche Zahlen!) geben, so daß a != p + q ?
Man kann doch nicht sagen, wenn es für alle p,q aus |N nicht möglich ist, ist es auch nicht für alle p,q aus M1 möglich (M1 beeinhaltet ja viel mehr Elemente als |N)
Vielleicht hängt dieser Schluss hier noch speziell mit der GC zusammen, aber wie kann man das allgemein begründen, d.h:
Allgemeiner gefragt (weil du den Beweis verallgemeinert hast):
Angenommen, es existiert ein a aus |N so daß für alle b, c aus |N gilt B(a,b, c).
Wie kann man daraus folgen:
es existiert ein a aus M1 so daß für alle b, c aus M1 gilt B(a,b, c) ?
Das ist mir nicht klar!
Es könnte doch b, c (z.B. 2 übernatürliche Zahlen) aus M1 geben, so daß B(a,b,c) falsch wird !
Und dann gilt es nicht mehr für alle a,b aus M1 !
Wo ist mein Denkfehler?

mfg
cx


Ersetze fed-Code einblenden in dem Beweis durch fed-Code einblenden und fed-Code einblenden durch fed-Code einblenden . fed-Code einblenden ist eine beliebige Formel der Arithmetik, in der genau x frei vorkommt. Mehr wissen wir nicht über fed-Code einblenden . Wir wollen zeigen, daß fed-Code einblenden in fed-Code einblenden gilt, wobei fed-Code einblenden das Standardmodell von PA bezeichnet. Dazu wird ein Widerspruchsbeweis geführt, also angenommen daß fed-Code einblenden in fed-Code einblenden gilt. Es gibt dann eine Variablenbelegung fed-Code einblenden , die x eine natürliche Zahl n zuordnet, so daß fed-Code einblenden in fed-Code einblenden wahr ist. Die natürliche Zahl n ist Element der Trägermenge fed-Code einblenden von fed-Code einblenden , also ein Objekt der Semantik. In der Arithmetik können wir aber jedem Element n der Trägermenge einen Term a zuordnen, so daß die Deutung von a unter fed-Code einblenden gleich n ist. Der Term a ist ein syntaktisches Objekt, also ist fed-Code einblenden eine syntaktische korrekte PA-Formel, die in fed-Code einblenden wahr ist.

Jetzt wendet man ein Ergebnis der Modelltheorie an, daß ich mal zur Kenntnis nehme, da ich über dieses Gebiet nichts weiß. Ich habe mich daher bei Wikipedia unter den Stichworten "Prime model" und "Elementary embeddings" erst schlau machen müssen. Die Schlußweise ist Folgende:

Ist fed-Code einblenden im Standardmodell fed-Code einblenden von PA wahr und ist M1 ein Modell von PA, so gibt es einen Term fed-Code einblenden , so daß fed-Code einblenden in M1 wahr ist. Damit ist trivialerweise M1 auch ein Modell von fed-Code einblenden .

Damit haben wir einen Widerspruch, denn zuvor wurde ja schon angenommen, daß M1 ein Modell von fed-Code einblenden ist. Folglich ist die Annahme, daß fed-Code einblenden in fed-Code einblenden gilt, widersprüchlich und daher muß fed-Code einblenden in fed-Code einblenden gelten.

Das hat also mit der Goldbachvermutung und Primzahlen nichts zu tun, denn der Beweis wurde für eine beliebige Formel fed-Code einblenden der Arithmetik, in der genau x frei vorkommt, geführt.

Man muß sich hier noch folgendes klar machen. Die Standardmodelle von PA (es gibt ja unendlich viele, die jedoch alle isomorph zueinander sind), sind formal "erzeugte Algebren". Anschaulich heißt das, daß jedes Element der Trägermenge durch einen Term der Sprache, also durch ein syntaktisches Objekt dargestellt/bezeichnet werden kann. Man darf ja oben im Beweis nicht einfach fed-Code einblenden anstatt fed-Code einblenden schreiben, denn fed-Code einblenden ist keine syntaktisch korrekte PA-Formel.
   
Ein nicht-Standardmodell M ist dagegen keine erzeugte Algebra, da M nicht isomorph zu den Standardmodellen ist (sonst wäre es ja kein nicht-Standardmodell). Insbesondere kann die Trägermenge von M überabzählbar sein. Daraus folgt, daß nicht jedes Element der Trägermenge durch einen Ausdruck der Sprache dargestellt/bezeichnet werden kann, denn es gibt nur abzählbar viele Terme. Genaugenommen gibt es überabzählbar viele Elemente der Trägermenge, die nicht durch einen Ausdruck der Sprache dargestellt/bezeichnet werden können.

Daher braucht man im Beweis das "elementary embedding", daß die Existenz eines sprachlichen Ausdrucks fed-Code einblenden mit den gewünschten Eigenschaften postuliert. D.h. mittels des "elementary embeddings" weiß man, daß es eine Variablenbelegung fed-Code einblenden zu M1 gibt, die x eine natürliche Zahl m (und eben keine "übernatürliche" Zahl!) zuordnet, so daß fed-Code einblenden in fed-Code einblenden wahr ist.



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2018-01-27 10:36


Hallo Zwerg_Allwissend,
I)
vielen Dank für deinen Beweis und deine Links zur Modelltheorie.
Ich kann leider jetzt erst auf deinen Beitrag posten, da ich viel Zeit zum Nachdenken und Recherchieren verwenden musste, wie z.B:
Stefan Geschke
www.math.uni-hamburg.de/home/geschke/teaching/ELskript.pdf
und
en.wikipedia.org/wiki/Prime_model

Frage:
Die Definition eines Standardmodells, die ich verwende (und auch du  - so verstehe ich dich zumindest) wird beim Beweis auf stackexchaneg verwendet bzw. definiert (siehe unten):
math.stackexchange.com/questions/1055381/goldbachs-conjecture-cant-be-proved-to-be-undecidable/1082723#1082723
Diese Definition ist aber nicht äquivalent zur Definition im englischen Wikipedia:
en.wikipedia.org/wiki/Prime_model
Welche Definition ist die Übliche ?

II)
Ich habe mich erst mal auf die "elementare Einbettung" in dem Beweis konzentriert und diesen Teil im " Lemma Existenzquantoren und Standardmodell" formuliert.
Bist du mit meinen Formulierungen und Darstellungen einverstanden?
Wenn ja, kann ich mit der Formulierung des vollständigen Beweises weitermachen.

1)
Definition elementare Einbettung (siehe Geschke):
<math>S_1=(T_1, ...) </math> und <math>S_2=(T_2, ...) </math> seien 2 S-Strukturen mit den Trägermengen <math>T_1</math>  und <math>T_2</math>
Die Punkte ... stehen für die dazugehörigen gleichen interpretierenden Funktions - und Relationsstrukturen.
Eine Abbildung <math>e: T_1 \rightarrow T_2</math> heißt elementare Einbettung von <math>S_1</math> in <math>S_2</math> gdw
<math>\forall a_1, .. , a_n \in T_1</math> und alle S-Formeln <math>B(x_1, ... , x_n) </math> gilt:
<math>S_1 \models B[a_1, ... , a_n]</math>  <==> <math>S_2 \models B[e(a_1), ..., e(a_n)]</math>

2)
Definition Standardmodell:
P ist ein Standardmodell von <math>\Sigma</math> gdw
Für alle Modelle M von <math>\Sigma</math> existiert eine elementare Einbettung von  P in M.

3)
Satz vom Standardmodell:
<math>\mathfrak{N}</math> ist ein Standardmodell von PA. Man bezeichnet es als das Standardmodell ||N von PA.
Es gilt also:
<math>\mathfrak{N}</math> ist das Standardmodell von PA, d.h:
Für ein beliebiges Modell M von PA gilt für alle freie Variablen <math>x_1, ..., x_n</math>:
<math>\mathfrak{N} \models B[a_1, ..., a_n]</math>  <==>  <math> M \models B[e(a_1), ..., e(a_n)]</math>

4)
Lemma Existenzquantoren und Standardmodell:
<math>\mathfrak{N}</math> ist das Standardmodell von PA und M = (T, ...) sei ein beliebiges Modell von PA.
Dann gilt:
<math>\mathfrak{N} \models  \exists x A(x)</math>  ==>  <math>M \models \exists x A(x)</math>

Beweis:
<math>\mathfrak{N} \models  \exists x A(x)</math>    gdw  
es existiert ein <math>\mathfrak{N} \models A[x]</math>  gdw  
<math>M \models A[e(x)] </math> also
<math>M  \models  \exists x A(x)</math>    

mfg
cx














  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-01-27 15:37


2018-01-27 10:36 - carlox in Beitrag No. 14 schreibt:
Hallo Zwerg_Allwissend,
I)
vielen Dank für deinen Beweis und deine Links zur Modelltheorie.
Ich kann leider jetzt erst auf deinen Beitrag posten, da ich viel Zeit zum Nachdenken und Recherchieren verwenden musste, wie z.B:
Stefan Geschke
www.math.uni-hamburg.de/home/geschke/teaching/ELskript.pdf
und
en.wikipedia.org/wiki/Prime_model

Frage:
Die Definition eines Standardmodells, die ich verwende (und auch du  - so verstehe ich dich zumindest) wird beim Beweis auf stackexchaneg verwendet bzw. definiert (siehe unten):
math.stackexchange.com/questions/1055381/goldbachs-conjecture-cant-be-proved-to-be-undecidable/1082723#1082723
Diese Definition ist aber nicht äquivalent zur Definition im englischen Wikipedia:
en.wikipedia.org/wiki/Prime_model
Welche Definition ist die Übliche ?

II)
Ich habe mich erst mal auf die "elementare Einbettung" in dem Beweis konzentriert und diesen Teil im " Lemma Existenzquantoren und Standardmodell" formuliert.
Bist du mit meinen Formulierungen und Darstellungen einverstanden?
Wenn ja, kann ich mit der Formulierung des vollständigen Beweises weitermachen.

1)
Definition elementare Einbettung (siehe Geschke):
<math>S_1=(T_1, ...) </math> und <math>S_2=(T_2, ...) </math> seien 2 S-Strukturen mit den Trägermengen <math>T_1</math>  und <math>T_2</math>
Die Punkte ... stehen für die dazugehörigen gleichen interpretierenden Funktions - und Relationsstrukturen.
Eine Abbildung <math>e: T_1 \rightarrow T_2</math> heißt elementare Einbettung von <math>S_1</math> in <math>S_2</math> gdw
<math>\forall a_1, .. , a_n \in T_1</math> und alle S-Formeln <math>B(x_1, ... , x_n) </math> gilt:
<math>S_1 \models B[a_1, ... , a_n]</math>  <==> <math>S_2 \models B[e(a_1), ..., e(a_n)]</math>

2)
Definition Standardmodell:
P ist ein Standardmodell von <math>\Sigma</math> gdw
Für alle Modelle M von <math>\Sigma</math> existiert eine elementare Einbettung von  P in M.

3)
Satz vom Standardmodell:
<math>\mathfrak{N}</math> ist ein Standardmodell von PA. Man bezeichnet es als das Standardmodell ||N von PA.
Es gilt also:
<math>\mathfrak{N}</math> ist das Standardmodell von PA, d.h:
Für ein beliebiges Modell M von PA gilt für alle freie Variablen <math>x_1, ..., x_n</math>:
<math>\mathfrak{N} \models B[a_1, ..., a_n]</math>  <==>  <math> M \models B[e(a_1), ..., e(a_n)]</math>

4)
Lemma Existenzquantoren und Standardmodell:
<math>\mathfrak{N}</math> ist das Standardmodell von PA und M = (T, ...) sei ein beliebiges Modell von PA.
Dann gilt:
<math>\mathfrak{N} \models  \exists x A(x)</math>  ==>  <math>M \models \exists x A(x)</math>

Beweis:
<math>\mathfrak{N} \models  \exists x A(x)</math>    gdw  
es existiert ein <math>\mathfrak{N} \models A[x]</math>  gdw  
<math>M \models A[e(x)] </math> also
<math>M  \models  \exists x A(x)</math>    

mfg
cx

Hier werden sich unsere Wege wohl trennen müssen. Wie ich schon weiter oben schrieb, weiß ich über Modelltheorie nichts. Ich müßte mich um Fragen darüber zu beantworten erst in dieses Gebiet einarbeiten. Warum fragst Du nicht einfach den Autor des Skripts von der Uni Hamburg?

Ich denke, man kann nicht von einer "üblichen" Definition eines Standardmodells von PA sprechen. Wie oft in der Mathematik hängt das davon ab, wen man fragt bzw. in welches Buch man schaut. Allen Definitionen sollte jedoch gemeinsam sein, daß sie äquivalent sind. Eine einfache Definition, die mir jetzt so spontan einfällt, wäre: Standardmodell von PA = Modell von PA dessen Trägermenge die gleiche Kardinalität wie |N hat.

Was meinen verallgemeinerten Beweis aus #13 angeht, so ist das eine Skizze. Man muß noch etwas mehr fordern als fed-Code einblenden ist eine beliebige Formel der Arithmetik, in der genau x frei vorkommt". Man kann ja eine Formel fed-Code einblenden äquivalent durch fed-Code einblenden ersetzen und hat dann aus einer Formel mit führendem Existenzquantor eine Formel mit führendem Allquantor gebastelt. Nach dem, was ich in #9 geschrieben habe, müßte dann (bei Unabhängigkeit der Formeln) fed-Code einblenden im Standardmodell wahr und fed-Code einblenden im Standardmodell falsch sein, und man hat einen Widerspruch.

Es fehlt also noch ein Kriterium für fed-Code einblenden mittels dessen solche "Kunststücke" ausgeschlossen werden. Wie dieses Kriterium genau aussieht stellt man fest, wenn man den Beweis sauber ausarbeitet.

Die Goldbachvermutung GC erfüllt jedenfalls dieses Kriterium. Interessant dabei ist noch Folgendes: Es wurde ja gezeigt, daß GC im Standardmodell wahr ist, falls weder GC noch ~GC aus PA herleitbar ist. Das ist nur dann nicht widersprüchlich, wenn der Nachweis "weder GC noch ~GC aus PA herleitbar" nicht in PA oder aber der Beweis, daß aus Unabhängigkeit von GC die Gültigkeit im Standardmodell folgt, nicht in PA geführt werden kann. Denn andernfalls kann GC in PA bewiesen werden, wenn man in PA beweisen kann, daß weder GC noch ~GC in PA beweisbar sind.


   



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2018-01-27 19:32


Hallo Zwerg_Allwissend,
danke für deine interessanten Infos.

(2018-01-27 15:37 - Zwerg_Allwissend in <a
Die Goldbachvermutung GC erfüllt jedenfalls dieses Kriterium. Interessant dabei ist noch Folgendes: Es wurde ja gezeigt, daß GC im Standardmodell wahr ist, falls weder GC noch ~GC aus PA herleitbar ist. Das ist nur dann nicht widersprüchlich, wenn der Nachweis "weder GC noch ~GC aus PA herleitbar" nicht in PA oder aber der Beweis, daß aus Unabhängigkeit von GC die Gültigkeit im Standardmodell folgt, nicht in PA geführt werden kann. Denn andernfalls kann GC in PA bewiesen werden, wenn man in PA beweisen kann, daß weder GC noch ~GC in PA beweisbar sind.
Genau zu diesem Punkt habe ich schon viele Überlegungen gemacht, kann aber obige Argumentation nicht nachvollziehen:
"...Denn andernfalls kann GC in PA bewiesen werden, wenn man in PA beweisen kann, daß weder GC noch ~GC in PA beweisbar sind."
Warum kann GC in PA beweisen werden, wenn man in PA beweisen kann, daß  
"daß weder GC noch ~GC in PA beweisbar sind"?
Wenn man in PA gezeigt hat, daß "daß weder GC noch ~GC in PA beweisbar sind", dann ist doch GC in PA nicht beweisbar. Warum soll es dann beweisbar sein ?
Kannst du mich da aufklären?
Ich kann das leider nicht nachvollziehen.

mfg
cx








  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2018-01-27 21:31


2018-01-27 19:32 - carlox in Beitrag No. 16 schreibt:
Hallo Zwerg_Allwissend,
danke für deine interessanten Infos.

(2018-01-27 15:37 - Zwerg_Allwissend in <a
Die Goldbachvermutung GC erfüllt jedenfalls dieses Kriterium. Interessant dabei ist noch Folgendes: Es wurde ja gezeigt, daß GC im Standardmodell wahr ist, falls weder GC noch ~GC aus PA herleitbar ist. Das ist nur dann nicht widersprüchlich, wenn der Nachweis "weder GC noch ~GC aus PA herleitbar" nicht in PA oder aber der Beweis, daß aus Unabhängigkeit von GC die Gültigkeit im Standardmodell folgt, nicht in PA geführt werden kann. Denn andernfalls kann GC in PA bewiesen werden, wenn man in PA beweisen kann, daß weder GC noch ~GC in PA beweisbar sind.
Genau zu diesem Punkt habe ich schon viele Überlegungen gemacht, kann aber obige Argumentation nicht nachvollziehen:
"...Denn andernfalls kann GC in PA bewiesen werden, wenn man in PA beweisen kann, daß weder GC noch ~GC in PA beweisbar sind."
Warum kann GC in PA beweisen werden, wenn man in PA beweisen kann, daß  
"daß weder GC noch ~GC in PA beweisbar sind"?
Wenn man in PA gezeigt hat, daß "daß weder GC noch ~GC in PA beweisbar sind", dann ist doch GC in PA nicht beweisbar. Warum soll es dann beweisbar sein ?
Kannst du mich da aufklären?
Ich kann das leider nicht nachvollziehen.

Das gilt nur, wenn auch der Beweis, daß aus der Unabhängigkeit von GC die Gültigkeit im Standardmodell folgt, ebenfalls in PA geführt werden kann. Denn dann wurden ALLE Beweise in PA geführt, also sowohl der Beweis, daß GC in PA nicht herleitbar ist, als auch, daß PA im Standardmodell wahr ist. Letzeres wurde wegen "ALLE Beweise in PA" dann ja auch in PA geführt, also wurde die Herleitbarkeit von GC in PA bewiesen.

Allgemein: Zeige ich IN PA, daß eine Formel A im Standardmodell wahr ist, dann habe ich die Formel IN PA hergeleitet.  

Das heißt also: Entweder kann die Unabhängigkeit von GC nicht in PA gezeigt werden oder der Beweis, daß aus der Unabhängigkeit von GC die Gültigkeit im Standardmodell folgt, kann nicht in PA bewiesen werden (also der Beweis der Korrektheit des Elementary Embeddings). Beide Beweise in PA ist nicht möglich, da man andernfalls den o.a. Widerspruch erhält.



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2018-01-27 22:24



Allgemein: Zeige ich IN PA, daß eine Formel A im Standardmodell wahr ist, dann habe ich die Formel IN PA hergeleitet.  
Behauptung:
"Zeigt man IN PA, daß eine Formel A im Standardmodell wahr ist, dann hat man die Formel IN PA hergeleitet."
Wie beweist du diese Behauptung? (formal oder informal)?
Braucht man dazu den Satz von Tarski (Weil es "keine Wahrheitsdefinition der Arithmetik in der Arithmetik gibt")?
(Satz von Tarski Ebbinghaus S.195 Einführung in die mathematische Logik)
Oder wie argumentierst du um die Behauptung zu beweisen?

mfg
cx



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2018-01-28 00:00


2018-01-27 22:24 - carlox in Beitrag No. 18 schreibt:

Allgemein: Zeige ich IN PA, daß eine Formel A im Standardmodell wahr ist, dann habe ich die Formel IN PA hergeleitet.  
Behauptung:
"Zeigt man IN PA, daß eine Formel A im Standardmodell wahr ist, dann hat man die Formel IN PA hergeleitet."
Wie beweist du diese Behauptung? (formal oder informal)?
Braucht man dazu den Satz von Tarski (Weil es "keine Wahrheitsdefinition der Arithmetik in der Arithmetik gibt")?
(Satz von Tarski Ebbinghaus S.195 Einführung in die mathematische Logik)
Oder wie argumentierst du um die Behauptung zu beweisen?

Genaugenommen ist die Behauptung tautologisch. Vielleicht irritiert die Wortwahl. Mit "hergeleitet" ist ja nicht gemeint, daß die Formel wie in einem Hilbert-Typ Kalkül ausgehend von Axiomen durch Regelanwendungen "erzeugt" wird, so wie man ein Wort einer ktf-Sprache ausgehend vom Startsymbol durch Regelanwendungen erzeugt (obwohl das natürlich möglich ist).

Vielleicht hilft es "hergeleitet" durch "bewiesen" zu ersetzen. Also:

"Hat man IN PA bewiesen, daß eine Formel A im Standardmodell wahr ist, dann hat man die Formel IN PA bewiesen."

Mit "A in PA bewiesen" ist gemeint, daß man A mit Mitteln 1. Stufe (d.h. mit irgendeinem Kalkül der Prädikatenlogik) allein unter Verwendung der Peano-Axiome beweist.

Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik) oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln, also Zeichenreihen, manipuliert durch Schlußregeln, die Formeln, also Zeichenreihen, in Formeln, also Zeichenreihen, umformen) nachzuweisen. Man bekommt dann (bei Erfolg) einen formalen Beweis als endliche Folge von Formeln, also Zeichenreihen, mit einer bestimmten Eigenschaft. Im Hilbert-Typ Kalkül ist A die letzte Formel der Folge, im Resolutionskalkül die leere Klausel, usw.

Kurzum, man hat lediglich Texte in Texte umgeformt, mehr nicht. Erst mit dem Korrektheitssatz des verwendeten Kalküls weiß man dann: A gilt im Standardmodell bzw. in allen Modellen meiner Axiomatisierung.

"Zeige ich IN PA, daß eine Formel A im Standardmodell wahr ist, dann habe ich die Formel IN PA hergeleitet."

heißt damit nichts anderes als

"Gibt es einen formalen Beweis für A mittels irgendeines Kalküls der Prädikatenlogik allein unter Verwendung der Peano-Axiome, so gibt es einen formalen Beweis für A mittels irgendeines Kalküls der Prädikatenlogik allein unter Verwendung der Peano-Axiome."



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2018-01-29 19:06



Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik)
oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln,

1)
Ich meine, daß dies nichts mit Modellen (also der Semantik) zu tun hat (sondern nur der Syntax). Richtig müßte es m.M. nach heißen:
Eine Formel A aus einer Formelmenge <math>\Sigma</math> (z.B. PA) abzuleiten (ich benutze im Folgenden - zur Unterscheidung vom Begriff "beweisen" - lieber den Begriff ableiten, kurz: <math>\Sigma</math> |- A) bedeutet eine endliche Folge zu finden, die die von dir beschriebenen Eigenschaften hat.

2)
Dann habe ich dich wie folgt verstanden (ich formuliere es mit meinen Worten):
Will man beweisen, daß eine Formel A im Standardmodell wahr ist, dann bleibt einem Wesen nichtgöttlicher Natur nichts anderes übrig, als eine Ableitung für A aus PA zu finden.
Mit dem Argument, daß die Axiome aus PA (im Standardmodell) wahr sind und die Schlussregeln von PA wahrheitserhaltend sind, folgt dann (metalogisch), daß A im Standardmodell) wahr ist.
Das ist für ein Wesen nichtgöttlicher Natur (in einem Beweiskalkül) die _einzige_ Methode, die Wahrheit einer Aussage A zu bekommen.
Bist du damit einverstanden ?

3)
Wenn man zeigt:
[PA |- GC ist unabhängig von PA]  und
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]
dann hat man einen Widerspruch.
Begründung:
Um
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]
zu zeigen, muß ein nichtgöttliches Wesen wie der Mensch in PA das Folgende ableiten:
[PA |- GC ist unabhängig von PA --> GC]
Da aber auch gilt:
[PA |- GC ist unabhängig von PA]  
folgt:
[PA |- GC]  
Aus
[PA |- GC ist unabhängig von PA]  
folgt aber:
Nicht [PA |- GC]  
Damit hat man einen Widerspruch.

4)
Also folgt:
Entweder [PA |- GC ist unabhängig von PA]  oder
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]
Bist du damit einverstanden ?

5)
Ein Problem habe ich noch:

Kurzum, man hat lediglich Texte in Texte umgeformt, mehr nicht. Erst mit dem Korrektheitssatz des verwendeten Kalküls weiß man dann: A gilt im Standardmodell bzw. in allen Modellen meiner Axiomatisierung.
Wenn man in PA eine Formel A abgeleitet hat, also: [PA |- A] gezeigt hat  
dann gilt A nicht nur im Standardmodell von PA, sondern in _allen_ Modellen von PA.
Der folgende Satz
PA |- GC ist unabhängig von PA ==> GC ist wahr im Standardmodell
bezieht sich aber auf das Standardmodell und ist _falsch_ für alle Modelle.
Wo ist mein Denkfehler ?

mfg
cx



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2018-01-29 23:23


2018-01-29 19:06 - carlox in Beitrag No. 20 schreibt:

Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik)
oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln,

1)
Ich meine, daß dies nichts mit Modellen (also der Semantik) zu tun hat (sondern nur der Syntax). Richtig müßte es m.M. nach heißen:
Eine Formel A aus einer Formelmenge <math>\Sigma</math> (z.B. PA) abzuleiten (ich benutze im Folgenden - zur Unterscheidung vom Begriff "beweisen" - lieber den Begriff ableiten, kurz: <math>\Sigma</math> |- A) bedeutet eine endliche Folge zu finden, die die von dir beschriebenen Eigenschaften hat.

Na ja, dann hat man eben nur eine endliche Folge von Texten, so what? Ohne Semantik ist die ganze Sache nutzlos. Das ist dann genauso wie das Protokoll einer Schachpartie. Da kann man dann sagen: Die beiden Spieler haben sich tatsächlich an die Regeln gehalten. Oder einer der Spieler war cleverer als der andere, denn sonst hätte er nicht gewonnen. Aber darüberhinaus gibt es keine Erkenntnis. Erst mit dem Korrektheitssatz des verwendeten Kalküls erhalte ich eine Aussage über alle mathematischen Strukturen, die die Axiome erfüllen.


2)
Dann habe ich dich wie folgt verstanden (ich formuliere es mit meinen Worten):
Will man beweisen, daß eine Formel A im Standardmodell wahr ist, dann bleibt einem Wesen nichtgöttlicher Natur nichts anderes übrig, als eine Ableitung für A aus PA zu finden.
Mit dem Argument, daß die Axiome aus PA (im Standardmodell) wahr sind und die Schlussregeln von PA wahrheitserhaltend sind, folgt dann (metalogisch), daß A im Standardmodell) wahr ist.
Das ist für ein Wesen nichtgöttlicher Natur (in einem Beweiskalkül) die _einzige_ Methode, die Wahrheit einer Aussage A zu bekommen.
Bist du damit einverstanden ?

Ja, soweit man sich auf formales Beweisen mittels Kalkülen beschränkt. Man kann auch informell argumentieren (mit dem Vorteil der Verständlichkeit aber mit dem Risiko von Fehlern), das ist ja der Standard in Fachartikeln und Büchern.

 

3)
Wenn man zeigt:
[PA |- GC ist unabhängig von PA]  und
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]
dann hat man einen Widerspruch.
Begründung:
Um
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]
zu zeigen, muß ein nichtgöttliches Wesen wie der Mensch in PA das Folgende ableiten:
[PA |- GC ist unabhängig von PA --> GC]
Da aber auch gilt:
[PA |- GC ist unabhängig von PA]  
folgt:
[PA |- GC]  
Aus
[PA |- GC ist unabhängig von PA]  
folgt aber:
Nicht [PA |- GC]  
Damit hat man einen Widerspruch.

Def. [GC ist unabhängig von PA <--> ([PA |-/- GC] & [PA |-/- ~GC])]

Damit:

Annahme (i) [PA |-- ([PA |-/- GC] & [PA |-/- ~GC])] % GC unabhängig in PA sei in PA beweisbar %

Annahme (ii) [PA |-- [[PA |-/- GC] & [PA |-/- ~GC] --> GC]] % Elementary Embedding sei in PA beweisbar %

Konsequenz (iii) [PA |-- GC] % Modus Ponens mit (i) und (ii) %

Konsequenz (iv) Jedes Modell von PA erfüllt GC % wegen (iii) und Korrektheit von |-- %

Konsequenz (v) [PA |-- [PA |-/- GC]] % Triviale Folgerung aus (i) %

Konsequenz (vi) Es gibt ein Modell von PA, das nicht GC erfüllt % mit Vollständigkeit von |-- und [PA |-/- GC] aus (v) %

Konsequenz (vii) Es gibt ein Modell von PA, das ~GC erfüllt % wegen (vi) und damit Widerspruch zu (iv).

Ich sehe nicht, wie man hier ohne Semantik argumentieren kann. Obendrein konstituiert [PA |-- GC] und [PA |-- ~GC] nur dann einen Widerspruch, wenn |-- korrekt ist, und in der Definition von "korrekt" steckt die Semantik.


4)
Also folgt:
Entweder [PA |- GC ist unabhängig von PA]  oder
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]
Bist du damit einverstanden ?

Nur wenn einer der beiden Beweise erbracht ist. Aus dem Widerspruch in (3) kann man lediglich schließen, daß (mindestens) eine der beiden Annahmen falsch ist, und man erhält:

[PA |-/- [PA |-- GC ist unabhängig von PA]]  oder
[PA |-/- [PA |-- GC ist unabhängig von PA --> GC]

D.h. entweder kann man die Unabhängigkeit von GC (von/in PA) nicht innerhalb von PA nachweisen oder man kann nicht innerhalb von PA nachweisen, daß GC aus der Unabhängigkeit von GC (von/in PA) folgt.  


5)
Ein Problem habe ich noch:
Kurzum, man hat lediglich Texte in Texte umgeformt, mehr nicht. Erst mit dem Korrektheitssatz des verwendeten Kalküls weiß man dann: A gilt im Standardmodell bzw. in allen Modellen meiner Axiomatisierung.
Wenn man in PA eine Formel A abgeleitet hat, also: [PA |- A] gezeigt hat  
dann gilt A nicht nur im Standardmodell von PA, sondern in _allen_ Modellen von PA.
Der folgende Satz
PA |- GC ist unabhängig von PA ==> GC ist wahr im Standardmodell
bezieht sich aber auf das Standardmodell und ist _falsch_ für alle Modelle.
Wo ist mein Denkfehler ?

In der Annahme, daß der Satz stimmt. In dem Beweis aus

math.stackexchange.com/questions/1055381/goldbachs-conjecture-cant-be-proved-to-be-undecidable

wurde ja nicht behauptet, daß "GC ist unabhängig von PA ==> GC ist wahr im Standardmodell" in PA beweisbar ist.



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, vom Themenstarter, eingetragen 2018-02-01 21:17


2018-01-29 23:23 - Zwerg_Allwissend in Beitrag No. 21 schreibt:
Ich beziehe mich auf folgendes Zitat von dir:
"Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik) oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln, also Zeichenreihen, manipuliert durch Schlußregeln, die Formeln, also Zeichenreihen, in Formeln, also Zeichenreihen, umformen) nachzuweisen. Man bekommt dann (bei Erfolg) einen formalen Beweis als endliche Folge von Formeln, also Zeichenreihen, mit einer bestimmten Eigenschaft. Im Hilbert-Typ Kalkül ist A die letzte Formel der Folge, im Resolutionskalkül die leere Klausel, usw."
Richtigerweise müßte es meiner Meinung nach heißen:
(ich habe es auch noch in keinem Buch über Prädikatenlogik anders gesehen)
Eine Formel A formal zu beweisen heißt doch die Formel A aus einer Formelmenge <math>\Sigma</math> abzuleiten (kurz: <math>\Sigma</math>|= A). Und dies allein mit syntaktischen Mitteln (Formeln, also Zeichenreihen, manipuliert durch Schlußregeln, die Formeln, also Zeichenreihen, in Formeln, also Zeichenreihen, umformen) nachzuweisen. Man bekommt dann (bei Erfolg) einen formalen Beweis als endliche Folge von Formeln, also Zeichenreihen, mit einer bestimmten Eigenschaft. Im Hilbert-Typ Kalkül ist A die letzte Formel der Folge, im Resolutionskalkül die leere Klausel, usw.
Ein Beweis in einem Kalkül ist - so wie du schreibst - also eine rein syntaktische Sache. Er hat nichts mit Modellen und Semantik zu tun.
Bist du damit einverstanden.


Def. [GC ist unabhängig von PA <--> ([PA |-/- GC] & [PA |-/- ~GC])]

Damit:

Annahme (i) [PA |-- ([PA |-/- GC] & [PA |-/- ~GC])] % GC unabhängig in PA sei in PA beweisbar %

Annahme (ii) [PA |-- [[PA |-/- GC] & [PA |-/- ~GC] --> GC]] % Elementary Embedding sei in PA beweisbar %

Konsequenz (iii) [PA |-- GC] % Modus Ponens mit (i) und (ii) %

Konsequenz (iv) Jedes Modell von PA erfüllt GC % wegen (iii) und Korrektheit von |-- %

Konsequenz (v) [PA |-- [PA |-/- GC]] % Triviale Folgerung aus (i) %
Aus Konsequenz (v) folgt doch sofort (wie in meinem Beweis in meinem letzten Posting bei 3)):
[PA |-/- GC]
also
nicht [PA |-- GC]   (*)
Mit (iii) ergibt sich dann:
[PA |-- GC]     (**)
Aus (*) und (**) folgt dann sofort ein Widerspruch.
Bist du damit einverstanden ?
Man braucht damit also keine Semantik.
Deswegen nochmals die Frage:
Was ist in meinem letzten Posting im Beweis bei 3) falsch ?


Konsequenz (vi) Es gibt ein Modell von PA, das nicht GC erfüllt % mit Vollständigkeit von |-- und [PA |-/- GC] aus (v) %
Wie folgt das und was meinst du mit "Vollständigkeit von |--"


Nur wenn einer der beiden Beweise erbracht ist. Aus dem Widerspruch in (3) kann man lediglich schließen, daß (mindestens) eine der beiden Annahmen falsch ist, und man erhält:
[PA |-/- [PA |-- GC ist unabhängig von PA]]  oder
[PA |-/- [PA |-- GC ist unabhängig von PA --> GC]
genau

D.h. entweder kann man die Unabhängigkeit von GC (von/in PA) nicht innerhalb von PA nachweisen oder man kann nicht innerhalb von PA nachweisen, daß GC aus der Unabhängigkeit von GC (von/in PA) folgt.  
Das entweder muß weg.
Es muß "oder" heißen.
Bist du damit einverstanden ?

mfg
cx





  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2018-02-02 21:10


2018-02-01 21:17 - carlox in Beitrag No. 22 schreibt:
Ein Beweis in einem Kalkül ist - so wie du schreibst - also eine rein syntaktische Sache. Er hat nichts mit Modellen und Semantik zu tun.
So isses.

2018-02-01 21:17 - carlox in Beitrag No. 22 schreibt:

Def. [GC ist unabhängig von PA <--> ([PA |-/- GC] & [PA |-/- ~GC])]

Damit:

Annahme (i) [PA |-- ([PA |-/- GC] & [PA |-/- ~GC])] % GC unabhängig in PA sei in PA beweisbar %

Annahme (ii) [PA |-- [[PA |-/- GC] & [PA |-/- ~GC] --> GC]] % Elementary Embedding sei in PA beweisbar %

Konsequenz (iii) [PA |-- GC] % Modus Ponens mit (i) und (ii) %

Konsequenz (iv) Jedes Modell von PA erfüllt GC % wegen (iii) und Korrektheit von |-- %

Konsequenz (v) [PA |-- [PA |-/- GC]] % Triviale Folgerung aus (i) %
Aus Konsequenz (v) folgt doch sofort (wie in meinem Beweis in meinem letzten Posting bei 3)):
[PA |-/- GC]
also
nicht [PA |-- GC]   (*)
Mit (iii) ergibt sich dann:
[PA |-- GC]     (**)
Aus (*) und (**) folgt dann sofort ein Widerspruch.
Bist du damit einverstanden ?
Man braucht damit also keine Semantik.
Deswegen nochmals die Frage:
Was ist in meinem letzten Posting im Beweis bei 3) falsch ?

Der Schluß " aus PA |-- [PA |-/- GC] folgt PA |-/- GC " ist nur in einem korrekten Kalkül gültig. Ein Kalkül, in dem jede Formel herleitbar ist, ist vollständig aber nicht korrekt. In so einem Kalkül kann man [PA |-/- GC] sowie GC herleiten, denn jede Formel ist herleitbar, und damit ist PA |-/- GC falsch.

Die Semantik steckt in der Forderung nach der Korrektheit des verwendeten Kalküls.

2018-02-01 21:17 - carlox in Beitrag No. 22 schreibt:

Konsequenz (vi) Es gibt ein Modell von PA, das nicht GC erfüllt % mit Vollständigkeit von |-- und [PA |-/- GC] aus (v) %
Wie folgt das und was meinst du mit "Vollständigkeit von |--"

Wenn alle Modelle von PA die Formel GC erfüllen, so gilt PA |-- GC mit der Vollständigkeit von |--. Kontraposition: Wenn PA |-/- GC so gibt es ein Modell von PA, das nicht GC erfüllt.

"Vollständigkeit von |--" bedeutet Vollständigkeit des Kalküls dessen Herleitungen mit " |-- " bezeichnet werden.  

2018-02-01 21:17 - carlox in Beitrag No. 22 schreibt:

D.h. entweder kann man die Unabhängigkeit von GC (von/in PA) nicht innerhalb von PA nachweisen oder man kann nicht innerhalb von PA nachweisen, daß GC aus der Unabhängigkeit von GC (von/in PA) folgt.  
Das entweder muß weg.
Es muß "oder" heißen.
Bist du damit einverstanden ?

Ja, so war es gemeint.


  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, vom Themenstarter, eingetragen 2018-02-07 13:57


Hallo Zwerg_Allwissend,
Du hast folgenden Satz formuliert (wenn ich dich richtig verstanden habe):
Satz:
Es gilt nicht:
[PA |- GC ist unabhängig von PA]  und
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]

Du hast kritisiert, daß ich in meinem Beweis nicht den Fall berücksichtige, daß der Kalkül inkorrekt sein kann. In so einem Kalkül sei dann jede Formel herleitbar.


Der Schluß " aus PA |-- [PA |-/- GC] folgt PA |-/- GC " ist nur in einem korrekten Kalkül gültig. Ein Kalkül, in dem jede Formel herleitbar ist, ist vollständig aber nicht korrekt. In so einem Kalkül kann man [PA |-/- GC] sowie GC herleiten, denn jede Formel ist herleitbar, und damit ist PA |-/- GC falsch.

Wenn man voraussetzt, daß der Beweiskalkül inkorrekt sein darf, dann  
kann man jede Formel ableiten, speziell also auch:

[PA |- GC ist unabhängig von PA]  und
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]

Daraus folgt dann, daß der von dir formulierte Satz falsch ist.
Wo ist mein Denkfehler?

mfg
cx

PS:
Es wäre meiner Meinung nach besser statt von Korrektheit besser von der Widerspruchsfreiheit zu sprechen..
Denn korrekt sollten alle Kalküle sein.
Wenn ein Axiomensystem nicht wiederspruchsfrei ist, kann man jede Formel
ableiten.





  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2018-02-08 00:05


2018-02-07 13:57 - carlox in Beitrag No. 24 schreibt:
Hallo Zwerg_Allwissend,
Du hast folgenden Satz formuliert (wenn ich dich richtig verstanden habe):
Satz:
Es gilt nicht:
[PA |- GC ist unabhängig von PA]  und
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]

Du hast kritisiert, daß ich in meinem Beweis nicht den Fall berücksichtige, daß der Kalkül inkorrekt sein kann. In so einem Kalkül sei dann jede Formel herleitbar.


Der Schluß " aus PA |-- [PA |-/- GC] folgt PA |-/- GC " ist nur in einem korrekten Kalkül gültig. Ein Kalkül, in dem jede Formel herleitbar ist, ist vollständig aber nicht korrekt. In so einem Kalkül kann man [PA |-/- GC] sowie GC herleiten, denn jede Formel ist herleitbar, und damit ist PA |-/- GC falsch.

Wenn man voraussetzt, daß der Beweiskalkül inkorrekt sein darf, dann  
kann man jede Formel ableiten, speziell also auch:

[PA |- GC ist unabhängig von PA]  und
[PA |- GC ist unabhängig von PA --> GC ist wahr im Standardmodell]

Daraus folgt dann, daß der von dir formulierte Satz falsch ist.
Wo ist mein Denkfehler?

Man kann mit unvollständigen Kalkülen arbeiten, wenn es sein muß. Aber mit inkorrekten Kalkülen zu arbeiten ist grober Unfug.

Dein Problem ist, daß Du nicht erkennst, daß man aus der Existenz von formalen Beweisen nur dann Erkenntnisse über mathematische Strukturen gewinnt, wenn man eine Semantik für die verwendeten syntaktischen Objekte (= Formeln im Beweis) hat.

Hier geht es um Herleitungen und nicht-herleitbare Formeln mittels eines Kalküls der Prädikatenlogik, um Erkenntnisse über die Arithmetik (= die Goldbach Vermutung ist wahr) zu gewinnen.

Ohne Semantik, kann man aber nicht von der Existenz eines Beweises auf Gegebenheiten einer mathematischen Struktur schließen.

Im konkreten Fall geht es um Deine Behauptung

(1) PA |-- [PA |-/- GC] => PA |-/- GC

mit der Du dann einen Widerspruch baust, wenn

(2) PA |-- [PA |-/- GC] sowie
(3) PA |-- GC

angenommen werden. Tatsächlich ist die Formelmenge {(1), (2), (3)} inkonsistent (bezgl. eines Kalküls, der sowas wie Modus Ponens kennt), um dies nachzuweisen ist keine Semantik erforderlich.

In Deiner Argumentation gibt es jedoch keine Rechtfertigung für (1), lediglich die Behauptung "folgt doch sofort". Das ist ein Postulat, aber kein Beweis. Man muß noch eine weitere Annahme treffen, nämlich daß der verwendete Kalkül korrekt ist.

Mein Bespiel mit dem inkorrekten Kalkül war kein Aufforderung Herleitungen mit solchen Kalkülen ebenfalls zu betrachten, sondern der Nachweis, daß Behauptung (1) i.A. nicht gilt, d.h. "folgt doch sofort" ist falsch.

Eine Fallunterscheidung nach |-- ist korrekt / ist nicht korrekt entkräftet nicht mein Argument, daß es ohne Semantik nicht geht (denn die Semantik steckt in der Definition von "korrekt" - hatte ich wohl schon mal gesagt).

2018-02-07 13:57 - carlox in Beitrag No. 24 schreibt:
Es wäre meiner Meinung nach besser statt von Korrektheit besser von der Widerspruchsfreiheit zu sprechen.

"Korrektheit" ist eine Eigenschaft von Kalkülen, "Widerspruchsfreiheit" eine Eigenschaft von Formelmengen F relativ zu einem Kalkül mittels dessen weitere Formeln aus dieser Formelmenge hergeleitet werden. Der Begriff "widerspruchsfrei" ist daher nur in Zusammenhang mit einem korrekten Kalkül sinnvoll verwendbar. Die Formelmenge F = {a} ist offenbar nicht widerspruchsfrei, wenn man einen Kalkül verwendet, in dem jede Formel herleitbar ist. Um die Korrektheit kommt man also nicht herum.

2018-02-07 13:57 - carlox in Beitrag No. 24 schreibt:
Wenn ein Axiomensystem nicht wiederspruchsfrei ist, kann man jede Formel
ableiten.

Nein. Betrachte F = {a, ~a} und einen Kalkül, mit der einzigen Regel, daß nur Elemente der Axiomenmenge F herleitbar sind. Dann kann man a sowie ~a herleiten, und damit ist F nicht widerspruchsfrei. Aber weiteres kann man aus F nicht herleiten.



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, vom Themenstarter, eingetragen 2018-02-08 10:44


Hallo Z_A,
Da ich komplett auf dem Schlauch stehe (bzw. mein ganzes mathematisches Weltbild zusammen zu brechen droht :)) , habe ich mir nochmals die folgende Aussage von dir angeschaut.


Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik) oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln, also Zeichenreihen, manipuliert durch Schlußregeln, die Formeln, also Zeichenreihen, in Formeln, also Zeichenreihen, umformen) nachzuweisen. Man bekommt dann (bei Erfolg) einen formalen Beweis als endliche Folge von Formeln, also Zeichenreihen, mit einer bestimmten Eigenschaft. Im Hilbert-Typ Kalkül ist A die letzte Formel der Folge, im Resolutionskalkül die leere Klausel, usw.,


Da ich bin jetzt ziemlich verwirrt. Deshalb habe ich mir nochmals das Buch „Einführung in die mathematische Logik“ von Ebbinghaus angeschaut.
Dort gibt es nur den Begriff des Beweises bzgl. einem Axiomensystem (=Formelmenge) in einer Sprache L der Prädikatenlogik 1. Stufe (PL1).
Bei der Definition eines Beweises wird dort nirgendwo auf ein Modell Bezug genommen.
„Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell“
Diesen Zusammenhang
"beweisen- Gültigkeit in einem Modell"
gibt es dort nicht.
Ich habe dies auch noch nie irgendwo gesehen.

Kannst du mir da weiterhelfen?


...
Die Formelmenge F = {a} ist offenbar nicht widerspruchsfrei, wenn man einen Kalkül verwendet, in dem jede Formel herleitbar ist. Um die Korrektheit kommt man also nicht herum.
Das ist der nächste Punkt, wo es mir den Deckel lupft:
"wenn man einen Kalkül verwendet, in dem jede Formel herleitbar ist"
Der Kalkül der PL1 ist doch vorgegeben (zumindest kann man nicht jeden x-beliebigen selbst gebastelten verwenden), zumindest so, daß der Korrektheitssatz und der Vollständigkeitssatz gelten muss:
Sigma |- A  gdw  Sigma |= A
Ich kann mich nicht daran erinnern, daß wir in einer PL1-Vorlesung den Kalkül frei wählen durften. Der war vorgegeben. Auch bei Ebbinghaus.
???


Wenn ein Axiomensystem nicht wiederspruchsfrei ist, kann man jede Formel
ableiten.

Nein. Betrachte F = {a, ~a} und einen Kalkül, mit der einzigen Regel, daß nur Elemente der Axiomenmenge F herleitbar sind. Dann kann man a sowie ~a herleiten, und damit ist F nicht widerspruchsfrei. Aber weiteres kann man aus F nicht herleiten.

Genau das gleiche Problem:
Wir konnten in einer PL1-Vorlesung den Kalkül _nicht_ frei wählen.
Im Gegenteil: Wir hatten dort gezeigt, daß man in einem widerspruchsvollen Axiomensystem jede Formel ableiten kann.

Oder arbeitest du nicht mit PL1?

Mit komplett verwirrten Grüßen
cx



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2018-02-08 13:38


2018-02-08 10:44 - carlox in Beitrag No. 26 schreibt:
Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik) oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln, also Zeichenreihen, manipuliert durch Schlußregeln, die Formeln, also Zeichenreihen, in Formeln, also Zeichenreihen, umformen) nachzuweisen. Man bekommt dann (bei Erfolg) einen formalen Beweis als endliche Folge von Formeln, also Zeichenreihen, mit einer bestimmten Eigenschaft. Im Hilbert-Typ Kalkül ist A die letzte Formel der Folge, im Resolutionskalkül die leere Klausel, usw.,

Deshalb habe ich mir nochmals das Buch „Einführung in die mathematische Logik“ von Ebbinghaus angeschaut.
Dort gibt es nur den Begriff des Beweises bzgl. einem Axiomensystem (=Formelmenge) in einer Sprache L der Prädikatenlogik 1. Stufe (PL1).
Bei der Definition eines Beweises wird dort nirgendwo auf ein Modell Bezug genommen.

Ja, so ist's richtig.

2018-02-08 10:44 - carlox in Beitrag No. 26 schreibt:
„Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell beweisen - "Gültigkeit in einem Modell" gibt es dort nicht.

Tatsächlich? Ich vermute stark, daß es in diesem Buch auch Abschnitte über die Semantik von Formeln des dort behandelten Kalküls gibt, sowie Beweise von Korrektheit und Vollständigkeit des Kalküls. Habe ich recht?

Du kannst Dich auch mal selbst fragen: Wozu dient eigentlich ein formaler Beweis? Das ist doch nur eine Folge von Symbolen, mehr nicht.



Die Formelmenge F = {a} ist offenbar nicht widerspruchsfrei, wenn man einen Kalkül verwendet, in dem jede Formel herleitbar ist. Um die Korrektheit kommt man also nicht herum.

Der Kalkül der PL1 ist doch vorgegeben (zumindest kann man nicht jeden x-beliebigen selbst gebastelten verwenden), zumindest so, daß der Korrektheitssatz und der Vollständigkeitssatz gelten muss:
Sigma |- A  gdw  Sigma |= A

Du hast nirgends geschrieben, daß sich Deine Behauptungen auf einen korrekten und vollständigen Kalkül beziehen. Das ist jetzt nicht spitzfindig gemeint, sondern zeigt vielmehr daß "offenbar wahre" Aussagen ohne Berücksichtigung der Semantik (=> korrekt, => vollständig) nicht gelten.
 

Ich kann mich nicht daran erinnern, daß wir in einer PL1-Vorlesung den Kalkül frei wählen durften. Der war vorgegeben. Auch bei Ebbinghaus.

Das ist ja wie in Nordkorea! Bei uns darf man sicher frei wählen, ob man formale Beweise mit einem Hilbert-Typ Kalkül, Sequenzenkalkül, Resolutionskalkül, ... führt.

Wir können uns sinnvollerweise darauf verständigen, daß |-- die Herleitbarkeit von Formeln in einem korrekten und vollständigen Kalkül bezeichnet.

Dann ist aber die Semantik mit an Bord (wogegen Du ja behauptet hast, ein Widerspruch im Beispiel oben ergibt sich auch ohne Semantik).

Dein prinzipielles Verständnisproblem ist Folgendes:

Du hast noch nicht begriffen, daß aus einem formalen Beweis (= Folge von Symbolen) genausowenig Erkenntnis jenseits der Symbolfolge gewonnen wird wie aus dem Protokoll einer Schachpartie.  



  Profil  Quote  Link auf diesen Beitrag Link
mire2
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 29.08.2006
Mitteilungen: 3960
Aus: Köln-Koblenz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2018-02-08 14:05


Hallo Ihr Lieben!  smile

Ich möchte mich gar nicht an dieser Diskussion beteiligen, sondern nur, weil ich jetzt immer wieder von carlox den Verweis auf den Ebbinghaus lese, auf das Buch Grenzen der Mathematik hinweisen.

Zwerg_Allwissend macht das hier ja wirklich toll und mit Hingabe und seine deutlichen Hinweise auf "Korrektheit", "Widerspruchsfreiheit" haben mich darin bestärkt, dass das oben genannte Buch vielleicht eine geeignetere Lektüre für carlox sein könnte.

Ich will diese Diskussion gar nicht abwürgen, sondern wollte nur den Buchtipp loswerden.

Grüße und feiert noch schön Wieverfastelovend  biggrin
mire2


-----------------
Beherrscher der Meta-Sprache
Narr und Weiser des Clans
Einziges Mitglied des Ältestenrates
Bester Freund Metas



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, vom Themenstarter, eingetragen 2018-02-08 14:37


Hallo Z_A



„Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell beweisen - "Gültigkeit in einem Modell" gibt es dort nicht.
Tatsächlich? Ich vermute stark, daß es in diesem Buch auch Abschnitte über die Semantik von Formeln des dort behandelten Kalküls gibt, sowie Beweise von Korrektheit und Vollständigkeit des Kalküls. Habe ich recht?

Du hast mich nicht richtig zitiert.
Ich habe nicht geschrieben:
 --> "Gültigkeit in einem Modell" gibt es dort nicht. <--
Sondern:
---------------------------------------------
Diesen Zusammenhang
"beweisen- Gültigkeit in einem Modell"
gibt es dort nicht.
---------------------------------------------


Tatsächlich? Ich vermute stark, daß es in diesem Buch auch Abschnitte über die Semantik von Formeln des dort behandelten Kalküls gibt, sowie Beweise von Korrektheit und Vollständigkeit des Kalküls. Habe ich recht?
Du hast recht:
Natürlich gibt es in dem Buch einen Abschnitt über die Semantik |=
ABER:
Die Modellbeziehung (M ist eine Interpretation und A eine Formel)
M |= A
wird induktiv definiert und hat nichts mit einem Beweis (wie in einem Beweiskalkül) zu tun.
Ich habe keinen Zusammenhang zwischen:
"beweisen- Gültigkeit in einem Modell"
gefunden.
Was meinst du dazu ?
 

Wir können uns sinnvollerweise darauf verständigen, daß |-- die Herleitbarkeit von Formeln in einem korrekten und vollständigen Kalkül bezeichnet.

Genau!
Ich beziehe mich auf einen korrekten und vollständigen Kalkül in PL1! (*)

Wenn ich von einem korrekten und vollständigen Kalkül in PL1 ausgehe,
(diesen voraussetze), wo ist dann _konkret_ der Denkfehler in meiner Arumentation ?
Du hast ja geschrieben:


Der Schluß " aus PA |-- [PA |-/- GC] folgt PA |-/- GC " ist nur in einem korrekten Kalkül gültig. Ein Kalkül, in dem jede Formel herleitbar ist, ist vollständig aber nicht korrekt. In so einem Kalkül kann man [PA |-/- GC] sowie GC herleiten, denn jede Formel ist herleitbar, und damit ist PA |-/- GC falsch

Ich gehe doch aber von einem korrekten und vollständigen Kalkül in PL1 aus!!  Siehe (*). Das ist doch unsere gemeinsame Voraussetzung!
Wo soll da jetzt in meiner Argumentation _konkret_ der Denkfehler liegen ?
Du kannst jetzt ja nicht mehr argumentieren
-------------------------------------------
Der Schluß " aus PA |-- [PA |-/- GC] folgt PA |-/- GC " ist nur in einem korrekten Kalkül gültig
--------------------------------------------
da der Kalkül korrekt ist!

mfg und immer noch verwirrt
cx




[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, vom Themenstarter, eingetragen 2018-02-08 15:00


2018-02-08 14:05 - mire2 in Beitrag No. 28 schreibt:
Ich möchte mich gar nicht an dieser Diskussion beteiligen, sondern nur, weil ich jetzt immer wieder von carlox den Verweis auf den Ebbinghaus lese, auf das Buch Grenzen der Mathematik hinweisen.

Zwerg_Allwissend macht das hier ja wirklich toll und mit Hingabe und seine deutlichen Hinweise auf "Korrektheit", "Widerspruchsfreiheit" haben mich darin bestärkt, dass das oben genannte Buch vielleicht eine geeignetere Lektüre für carlox sein könnte.
Wollte das Buch vor ein paar Wochen bestellen.
Es wird nicht mehr geliefert.
Ich soll auf die Neuauflage warten.
Das wurde mir mitgeteilt.

mfg
cx



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, eingetragen 2018-02-10 22:42


Ich kann mich nur noch wiederholen, d.h. meine Wiederholungen wiederholen. Das bringt uns offenbar nicht weiter.

Das ist ja auch keine einfache Materie, wenn man beginnt sich da einzuarbeiten. Alles sehr abstrakt.

Ich habe mehrfach festgestellt, daß Leute eine Sache nicht begreifen, weil sie den Sachverhalt für selbstverständlich halten. Dann hiess es z.B.: Was soll man denn hier beweisen, der Satz stimmt doch!

Vielleicht ist das hier auch so.

Wenn ich mich eine zeitlang mit einer Sache beschäftigt habe ohne weiterzukommen, dann lege ich das für eine Weile zur Seite. Man gewinnt so oft einen neuen Blick auf die Sachen wenn man sich das später wieder anschaut.

Laß es doch jetzt einfach sein, und lese Dir diesen Thread in 4 Wochen oder so noch mal durch - das könnte vielleicht weiterhelfen.

2018-02-08 15:00 - carlox in Beitrag No. 30 schreibt:
Wollte das Buch vor ein paar Wochen bestellen.
Es wird nicht mehr geliefert.
Ich soll auf die Neuauflage warten.
Das wurde mir mitgeteilt.

Ich kenne das Buch nicht, aber vom Inhaltsverzeichnis her sieht das gut aus. Schreib doch einfach dem Autor eine Email und frag ihn, ob er ein Exemplar hat, daß er Dir verkaufen kann. Vielleicht sogar als Ebook - dann kannst Du mir eine Kopie als Dank für den Tipp zukommen lassen. Die Unileute freuen sich immer, wenn sich jemand für ihre Arbeit interessiert. Und Autorenhonorar gibt es praktisch nicht, aber Belegexemplare.  




  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.32, vom Themenstarter, eingetragen 2018-02-11 07:23


Hallo Z_A,
danke, daß du noch antwortest.

Ich habe mehrfach festgestellt, daß Leute eine Sache nicht begreifen, weil sie den Sachverhalt für selbstverständlich halten. Dann hiess es z.B.: Was soll man denn hier beweisen, der Satz stimmt doch!
Vielleicht ist das hier auch so.
Vermutlich hast du recht: ich stecke in einer Endlos-Schleife.
Kannst du mir trotzdem noch auf 2 Argumnete von mir eingehen:
1)

Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik) oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln, also Zeichenreihen, manipuliert durch Schlußregeln, die Formeln, also Zeichenreihen, in Formeln, also Zeichenreihen, umformen) nachzuweisen.
Und zwar nur den Teil:
"Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik)"
Und zwar die Aussage "in einem Modell"
In allen Büchern der Prädiaktenlogik, die ich bisher angeschaut habe,
gibt es den Begriff des Beweises (Ableitung) mit Hilfe von Regeln.
Da sind wir vermutlich noch einer Meinung.
Dann gibt es dort den Korrektheits- und Vollständigkeitssatz:
Sigma |-A gdw Sigma |= A
Der sagt aber dann aus:
Wenn man A aus Sigma ableiten kann, dann ist er in ALLEN Modellen gültig.
Wie kommst du dann zur Behauptung: "in einem Modell".
Das hat mich ziemlich verwirrt.
Und auf diesen Einwand bist du bis jetzt nicht eingegangen.

2)
Die Behauptung von mir:
aus PA |-- [PA |-/- GC] folgt PA |-/- GC
Begründung:
PA ist korrekt:
Das bedeutet doch:
Die Ableitung [PA |-/- GC]
ist in allen Modellen von PA gültig.
also
PA |-/- GC
An welcher Stelle ist die Argumentation falsch ?

PS:
Wenn ich das Buch in elektronischer Form habe, werde ich dir es natürlich zukommen lassen. Ich warte aber erstmal auf dei Neuauflage (dort werden alte Fehler beseitigt).

mfg
cx



  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.33, eingetragen 2018-02-11 17:27


2018-02-11 07:23 - carlox in Beitrag No. 32 schreibt:

Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik) oder in allen Modellen (Prädikatenlogik 1. Stufe) allein mit syntaktischen Mitteln (Formeln, also Zeichenreihen, manipuliert durch Schlußregeln, die Formeln, also Zeichenreihen, in Formeln, also Zeichenreihen, umformen) nachzuweisen.
Und zwar nur den Teil:
"Eine Formel A formal zu beweisen heißt doch die Gültigkeit in einem Modell (Arithmetik)"
Und zwar die Aussage "in einem Modell"
In allen Büchern der Prädiaktenlogik, die ich bisher angeschaut habe,
gibt es den Begriff des Beweises (Ableitung) mit Hilfe von Regeln.
Da sind wir vermutlich noch einer Meinung.
Dann gibt es dort den Korrektheits- und Vollständigkeitssatz:
Sigma |-A gdw Sigma |= A
Der sagt aber dann aus:
Wenn man A aus Sigma ableiten kann, dann ist er in ALLEN Modellen gültig.
Wie kommst du dann zur Behauptung: "in einem Modell".
Das hat mich ziemlich verwirrt.
Und auf diesen Einwand bist du bis jetzt nicht eingegangen.

Das ist nur ein Mißverständnis: Natürlich ist A in ALLEN Modellen der Peano Axiome gültig, aber die Intention einen formalen Beweis zu führen ist zu zeigen, daß A eine wahre Aussage der Arithmetik ist, also in EINEM Modell, nämlich dem Standardmodell, gilt. Natürlich gilt A dann auch in allen nicht-Standardmodellen, aber dieser Nachweis ist sozusagen der Beifang.

2018-02-11 07:23 - carlox in Beitrag No. 32 schreibt:
2)
Die Behauptung von mir:
aus PA |-- [PA |-/- GC] folgt PA |-/- GC
Begründung:
PA ist korrekt:
Das bedeutet doch:
Die Ableitung [PA |-/- GC]
ist in allen Modellen von PA gültig.
also
PA |-/- GC
An welcher Stelle ist die Argumentation falsch ?

Diese Behauptung ist richtig. Aber Du hast Dich selbst nicht korrekt zitiert. Ursprünglich war in Deiner Behauptung nicht von einem >korrekten< Kalkül die Rede. Statt dessen hast Du behauptet, daß

(i) PA |-- [PA |-/- GC] => PA |-/- GC "offensichtlich gilt", und dann damit
(ii) einen Widerspruch der Form PA |-- GC & PA |-/- GC gebastelt

um zu zeigen, daß die Verwendung der Semantik in meiner Beweisskizze überflüssig ist.

Jetzt hast Du nachgebessert, und von einem >korrekten< Kalkül gesprochen. Dann ist alles OK, aber damit hast Du Deine ursprüngliche Behauptung, einen Widerspruch ohne Einbeziehung der Semantik zu zeigen, selbst widerlegt. Denn ohne Sementik kann man nicht definieren, wann ein Kalkül "korrekt" ist.

OK, das war jetzt die n.te Wiederholung mit n ~ 5. Das sollte jetzt reichen!



  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.34, vom Themenstarter, eingetragen 2018-02-15 18:49



Diese Behauptung ist richtig. Aber Du hast Dich selbst nicht korrekt zitiert. Ursprünglich war in Deiner Behauptung nicht von einem >korrekten< Kalkül die Rede. Statt dessen hast Du behauptet, daß

(i) PA |-- [PA |-/- GC] => PA |-/- GC "offensichtlich gilt", und dann damit
(ii) einen Widerspruch der Form PA |-- GC & PA |-/- GC gebastelt

um zu zeigen, daß die Verwendung der Semantik in meiner Beweisskizze überflüssig ist.

Jetzt hast Du nachgebessert, und von einem >korrekten< Kalkül gesprochen. Dann ist alles OK, ...

aber damit hast Du Deine ursprüngliche Behauptung, einen Widerspruch ohne Einbeziehung der Semantik zu zeigen, selbst widerlegt. Denn ohne Sementik kann man nicht definieren, wann ein Kalkül "korrekt" ist.

Hallo Z_A
Du hast Recht, man braucht die Semantik (Korrektheit).
Begründung folgt:

1)
nochmals vielen Dank für deine wertvollen Antworten.
Ich meine jetzt zu wissen, wo mein Denkfehler war:
wenn man [PA |-/- GC] mit X abkürzt, war meine Schlussweise:
aus PA |-- X folgt X.
Das ist extrem falsch, weil syntaktisch fehlgeformt.
Ich kann nur folgern (weil PA korrekt):
aus PA |-- X folgt PA |= X

2)
Konkret auf unsern Fall angewendet:
aus PA |-- [PA |-/- GC] folgt (weil PA korrekt):
PA |= [PA |-/- GC]
d.h. im Standardmodell von PA ist
[PA |-/- GC] gültig.
Das bedeutet, daß man GC aus PA ableiten kann.
Damit folgt (da PA korrekt), daß GC in PA gültig (wahr) ist

Bist du damit einverstanden ?

mfg
cx









  Profil  Quote  Link auf diesen Beitrag Link
carlox
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2007
Mitteilungen: 798
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.35, vom Themenstarter, eingetragen 2018-02-18 08:53



Was meinen verallgemeinerten Beweis aus #13 angeht, so ist das eine Skizze. Man muß noch etwas mehr fordern als fed-Code einblenden ist eine beliebige Formel der Arithmetik, in der genau x frei vorkommt". Man kann ja eine Formel fed-Code einblenden äquivalent durch fed-Code einblenden ersetzen und hat dann aus einer Formel mit führendem Existenzquantor eine Formel mit führendem Allquantor gebastelt. Nach dem, was ich in #9 geschrieben habe, müßte dann (bei Unabhängigkeit der Formeln) fed-Code einblenden im Standardmodell wahr und fed-Code einblenden im Standardmodell falsch sein, und man hat einen Widerspruch.

Es fehlt also noch ein Kriterium für fed-Code einblenden mittels dessen solche "Kunststücke" ausgeschlossen werden. Wie dieses Kriterium genau aussieht stellt man fest, wenn man den Beweis sauber ausarbeitet.

Hallo allerseits,
Zu dem Beweis auf Stackexchange:
math.stackexchange.com/questions/1055381/goldbachs-conjecture-cant-be-proved-to-be-undecidable
---------------------------------------------
If the Goldbach conjecture is undecidable (independent) of PA, then it is true for the standard model of arithmetic, i.e. the model (N,+,×,0,1,<)
Proof: Recall that N is the prime model of PA, (i.e. it embeds into every model M such that M⊨ PA). Further more, N is the initial segment of all models of PA. Assuming that GC is independent of PA, we note that PA + GC and PA + ¬GC are consistent. Then, by Gödel's completeness theorem, there exists models M1 and M2 such that M1⊨ PA + GC and M2⊨ PA + ¬GC. Suppose that N⊨ PA + ¬GC. Then, there exists some element a∈N such that a cannot be written as the sum of two primes. Since N is the prime model of PA, we recall the fact that N embeds into all models of arithemtic. Therefore, if φ(x)≡ "x cannot be written as the sum of two primes", and N⊨φ(a)
By above, we showed there exist an M1 such that M1⊨ PA + GC. However, since N embeds into M1, we note that M1⊨φ(π(a)) (where π is the embedding). However this implies that M1⊨¬GC
which is a contradiction.
Thus, if GC is independent of PA, then N⊨GC.
-------------------------------------------

Mit embeds (ohne Adjektiv elemantar) ist Folgendes gemeint:
Definition:
S1 = (T1, ...) und S2 = (T2, ...)  seien 2 S-Strukturen mit den Trägermengen T1, T2.
Die danach folgenden Punkte stehen für die dazugehörigen gleichen interpretierenden Funktions - und Relationsstrukturen.
Eine Abbildung e: T1 --> T2 heißt Einbettung von S1 in S2 gdw
für alle a1, .., an aus T1 und alle quantorenfreien S-Formeln B(x1, ... , xn) gilt:
S1 |= B[a1, ..., an]  <==>  S2 |= B[e(a1), ..., e(an)]


In diesem Beweis verstehe ich dann den folgenden Punkt nicht:
1)
Zu dem folgenden Teil des Beweises (in Deutsch übersetzt):
-------------------------------------
Annahme: |N |=PA + non GC
Also: |N |= ~ GC
Dann existiert ein Element a aus |N so daß a nicht als Summe zweier Primzahlen dargestellt werden kann.
------------------------------------
Genauer müßte es heißen:
Dann existiert ein Element a aus |N so daß für alle p für alle q gilt:
~(a = p+q und p ist prim und q ist prim)
Man hat also eine Formel, in der Quantoren vorkommen (Allquantoren).
Zusätzlich stecken in der Formulierung "p ist prim" auch noch (mindestens) ein Quantor.
Damit ist die Definition des "Einbettens" nicht erfüllt.
Wie kann man den Beweis trotzdem noch reparieren ?

mfg
cx





  Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.12.2013
Mitteilungen: 142
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.36, eingetragen 2018-02-20 00:01


2018-02-15 18:49 - carlox in Beitrag No. 34 schreibt:
2)
Konkret auf unsern Fall angewendet:
aus PA |-- [PA |-/- GC] folgt (weil PA korrekt):
PA |= [PA |-/- GC]
d.h. im Standardmodell von PA ist
[PA |-/- GC] gültig.
Das bedeutet, daß man GC aus PA ableiten kann.
Damit folgt (da PA korrekt), daß GC in PA gültig (wahr) ist

Verstehe ich nicht, vielleicht nur ein Schreibfehler.

Damit wir uns richtig verstehen: [PA |-/- GC] soll eine Formel sein, die sinngemäß aussagt, daß GC nicht aus PA herleitbar ist. Dann hat man in einem korrekten Kalkül:

PA |-- [PA |-/- GC] => PA |-/- GC,

denn andernfalls würde

PA |-- [PA |-/- GC] & PA |-- GC

gelten. Dann wäre aber die Formel

[PA |-/- GC]

falsch und man hat einen Widerspruch, denn da |-- korrekt ist, sind nur wahre Formeln aus PA herleitbar.

2018-02-18 08:53 - carlox in Beitrag No. 35 schreibt:
In diesem Beweis verstehe ich dann den folgenden Punkt nicht:
1)
Zu dem folgenden Teil des Beweises (in Deutsch übersetzt):
-------------------------------------
Annahme: |N |=PA + non GC
Also: |N |= ~ GC
Dann existiert ein Element a aus |N so daß a nicht als Summe zweier Primzahlen dargestellt werden kann.
------------------------------------
Genauer müßte es heißen:
Dann existiert ein Element a aus |N so daß für alle p für alle q gilt:
~(a = p+q und p ist prim und q ist prim)
Man hat also eine Formel, in der Quantoren vorkommen (Allquantoren).
Zusätzlich stecken in der Formulierung "p ist prim" auch noch (mindestens) ein Quantor.
Damit ist die Definition des "Einbettens" nicht erfüllt.
Wie kann man den Beweis trotzdem noch reparieren ?

Frag doch den Autor des Beweises - er müßte das ja erläutern können.

2018-02-15 18:49 - carlox in Beitrag No. 34 schreibt:
Zusätzlich stecken in der Formulierung "p ist prim" auch noch (mindestens) ein Quantor.

Das muß nicht sein - man kann Quantoren auch durch Rekursion eliminieren.



  Profil  Quote  Link auf diesen Beitrag Link
carlox hat die Antworten auf ihre/seine Frage gesehen.
carlox 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-2018 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]