Hier einige Hieroglyphen:. III. Figur und Hintergrund Proseminar Gödel, Escher, Bach - Kapitel III: Figur und Hintergrund - 1 Gliederung 1.Primzahlen

Hier einige Hieroglyphen:

III. Figur und Hintergrund

Proseminar Gödel, Escher, Bach - Kapitel III: Figur und Hintergrund - 1

Gliederung1. Primzahlen in formalen Systemen

1.1 Das mg-System1.2 Zeichenketten zusammengesetzter Zahlen1.3 Unzulässige Charakterisierung von

Primzahlen1.4 Primzahlen als positiv definierte Menge

2. Figur und Hintergrund

2.1 In der Kunst2.2 In der Musik2.3 Übertragung auf mathematische Theorien2.4 Rekursiv aufzählbare Mengen – rekursive

Mengen2.5 Gödels Satz und das Halteproblem

1. Primzahlen in formalen Systemen


Letzte Stunde: Addition in formalen Systemen

Ziel dieser Stunde: Primzahlendarstellung in einem formalen System

Satz: P----- (5)Kein Satz: P---- (4)

Zentrale Frage: Welche Axiome und Regeln sind notwendig?

1.1 Das mg-System


Primzahlen sind nur über die Multiplikation charakterisierbar

Daher: 1. Schritt: Ein formales System zur Darstellung der Multiplikation

„x mal y gleich z“ wird übersetzt in:xmygz

Axiom: xm-gx, wobei x eine Bindestrichkette istSchlussregel: xmygz ist ein Satz. Dann ist xmy-gzx ein neuer Satz, wobei x, y und z Bindestrichketten sind.

1.2 Zeichenketten zusammengesetzter Zahlen


Nächster Schritt: Definition der zusammengesetzten Zahlen

(= des Gegenteils der Primzahlen)

Regel: Wenn x-my-gz ein Satz ist, dann ist es auch Zz, wobei x, y und z Bindestrichketten sind

Das heißt: x+1 sowie y+1 vorgegeben => z ist zusammengesetzt

1.3 Unzulässige Charakterisierung


Formales System für das Gegenteil der Primzahlen ist bekannt

Vorschlag: Simple Umkehrung, um auf die Primzahlen zu kommen

Regelvorschlag: Wenn Zx kein Satz ist, dann ist Px ein Satz.

Nicht zulässig – diese Entscheidung kann nur außerhalb des Systems getroffen werden

Parallele zum MU-Rätsel – dort konnte der Nachweis genauso nur informell durchgeführt werden

1.4 Primzahlen als positiv definierte Menge


Zweiter Versuch über Nichtteilbarkeit

x „ist kein Teiler von“ y wird übersetzt in:

1.Axiom: xyIKTx1.Regel: Wenn xIKTy ein Satz ist, dann auch xIKTxy

Axiom richtig, da: y != 0

Regel richtig, da: Modulo von y:x == Modulo von (y+x):x



2.Regel: Wenn --IKTz ein Satz ist, dann auch zTF-- Diese Regel dreht den Ausdruck um, TF steht für „teilerfrei von“.



3.Regel: Wenn zTFx ein Satz ist, und ebenso x-IKTz, dann ist zTFx- ein Satz

Iterative Inkrementierung des TF-Ausdrucks mit Hilfe IKT-Regel

4.Regel: Wenn z-TFz ein Satz ist, dann ist Pz- ein Satz.

Wenn alle Zahlen bis zur mutmaßlichen Primzahl-1 keine Teiler sind, handelt es sich tatsächlich um eine Primzahl

Zwei ist aber auch eine Primzahl!? =>2.Axiom: P--

2. Figur und Hintergrund


In Punkt 1 fiel auf, dass die Primzahlen (gewissermaßen) das Gegenteil der zusammengesetzten Zahlen darstellen.

In graphischer Form hieße das:

2.1 Figur und Hintergrund in der Kunst


Hinter- und Vordergrund gibt es genauso in der Kunst

Hierzu zwei „fiktive“ Begriffe:

Kursiv zeichenbar (Hintergrund ist Nebenprodukt)Rekursiv zeichenbar (Hintergrund kann als eigene Figur aufgefasst werden)













Die gezeigten Bilder sind „ Rekursiv zeichenbar“

Die Definition dieser Begriffe ist aber ungenau

Ein „kursiv zeichenbares“ Bild:

2.2 Figur und Hintergrund in der Musik


Ähnliches Phänomen in der Musik:

Vorder- versus HintergrundMelodie versus Begleitung

J. S. Bach - Musikalisches Opfer - Ricercar, a 3 (Cembalo)

2.3 Übertragung auf math. Theorien


2.4 Rekursiv aufzählbare/rekursive Mengen


Die zunächst nur negativ definierten Primzahlen ließen sich positiv darstellen

Gilt das für alle formalen Systeme?Nein!

=> Es gibt rekursiv aufzählbare Mengen, die nicht rekursiv sind.

2.4 Rekursiv aufzählbare/rekursive Mengen


=> Es gibt rekursiv aufzählbare Mengen, die nicht rekursiv sind.

Wenn ein typographisches Entscheidungsverfahren existiert, kann man mittels dessen Hilfe ausgehend von einer positiv definierten Menge die korrespondierende Negativ-Menge charakterisieren.

=> Es gibt formale Systeme, für die es keine typographischen Entscheidungsverfahren gibt.

2.5 Gödels Satz und das Halteproblem


Diese Grundsätze wurden von Turing und Gödel aufgedeckt

Gödels Vollständigkeitssatz:Eine Aussage φ ist genau dann allgemeingültig, wenn sie formal beweisbar ist.

Das gilt allerdings nur für „einfache“ Systeme mit geringer Mächtigkeit.



Gödels Unvollständigkeitssatz:Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.

Vereinfachter Ansatz: Ein System, das Sätze konstruiert, die jeweils eine Nummer („ID“) haben und aussagen, dass sie sich selbst nicht beweisen lassen.

•Wenn einer dieser Sätze wahr ist, lässt er sich wirklich nicht beweisen. Man besitzt kein typographisches Entscheidungsverfahren – das System ist unvollständig.

•Wenn dieser Satz unwahr ist, lässt er sich beweisen – ein klarer Widerspruch, der auf das System zurückgeführt werden muss, was dann folglich widersprüchlich sein muss.



Turings Halteproblem:

Es ist unmöglich, ein zweites Programm überprüfen zu lassen, ob ein erstes Programm terminiert. Das bedeutet wiederum, dass es in jedem hinreichend komplexen System Aussagen gibt, die man nicht beweisen oder widerlegen kann, also dass ein solches System unvollständig ist.

Vielen Dank für Ihre Aufmerksamkeit!


Documents

Hier einige Hieroglyphen:. III. Figur und Hintergrund Proseminar Gödel, Escher, Bach - Kapitel III: Figur und Hintergrund - 1 Gliederung 1.Primzahlen