Sie sind nicht angemeldet.

Sinan

Senior Schreiberling

  • »Sinan« ist männlich
  • »Sinan« ist der Autor dieses Themas

Beiträge: 1 019

Registrierungsdatum: 5. Juli 2003

Wohnort: Hannover

Beruf: M.Sc. Informatik --> Deutsches Zentrum für Luft- und Raumfahrt

1

Donnerstag, 26. Juli 2007, 17:40

Fragen zu Berechenbarkeit und Logik

Hallo,

Habe (erstmal) zwei Fragen:

1. Im Skript Seite 5: Satz (von Reis):

Zitat


Seit F = ...
Dann ist C(F) = ... nicht rekursiv.

Nach dem Beweis kommt

Zitat


Korollar: Sei F wie oben. Dann ist C(F) nicht entscheidbar

"rekursiv" und "entscheidbar" sind doch zwei Begriffe für eins und dasselbe! ?( oder sehe ich da was nicht?

2. Seite 7:

Zitat


Beispiel: Formeln über L*:

die zweite Formel: wieso existiert da nicht so ein z?
Beispiel:
x = 1, x' = 3, z = 2.

dann ist x < x` und x < z und z < x'

Danke im Voraus
Salsasüchtig!
Scharf wie die Soße, heiß wie der Rhythmus!


kann ich auch... in 10 Jahren
hier flipp ich aus

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Donnerstag, 26. Juli 2007, 19:13

RE: Fragen zu Berechenbarkeit und Logik

Zitat

Original von Sinan
"rekursiv" und "entscheidbar" sind doch zwei Begriffe für eins und dasselbe! ?( oder sehe ich da was nicht?
Ist dasselbe.

Zitat

2. Seite 7:

Zitat


Beispiel: Formeln über L*:

die zweite Formel: wieso existiert da nicht so ein z?
Es hat niemand behauptet, daß diese Formel wahr ist (also ein sogenannter Satz ist). Es wurde lediglich behauptet, daß es sich um Formeln handelt (also daß die syntaktische Korrektheit gewährleistet ist).
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Joachim« (26. Juli 2007, 19:17)


Sinan

Senior Schreiberling

  • »Sinan« ist männlich
  • »Sinan« ist der Autor dieses Themas

Beiträge: 1 019

Registrierungsdatum: 5. Juli 2003

Wohnort: Hannover

Beruf: M.Sc. Informatik --> Deutsches Zentrum für Luft- und Raumfahrt

3

Freitag, 27. Juli 2007, 09:58

RE: Fragen zu Berechenbarkeit und Logik

Zitat

Original von Joachim
Es hat niemand behauptet, daß diese Formel wahr ist (also ein sogenannter Satz ist).

8 Zeilen tiefer.

Zitat


Die Formeln (*) aus obigem Beispiel sind Sätze.

Oder hat der Begriff "Satz" hier eine Doppelbedeutung? Es wurde im Skript auch definiert: "ein Satz ist eine Formel ohne freie Variablen".
Salsasüchtig!
Scharf wie die Soße, heiß wie der Rhythmus!


kann ich auch... in 10 Jahren
hier flipp ich aus

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

Freitag, 27. Juli 2007, 10:27

RE: Fragen zu Berechenbarkeit und Logik

Zitat

Original von Sinan
Oder hat der Begriff "Satz" hier eine Doppelbedeutung? Es wurde im Skript auch definiert: "ein Satz ist eine Formel ohne freie Variablen".
Sorry, da hab ich ewas durcheinander gebracht. Jetzt aber korrekt:

Term (term): "syntaktisch korrekte" Kombination von Konstantensymbolen, Variablensymbolen und Funktionssymbolen

Formel (formula): "syntaktisch korrekte" Kombination von Termen, Prädikatsymbolen, logischen Operatoren und Quantoren.

Satz (sentence): Formel ohne freie Variablen (auch geschlossene Formel genannt, engl. closed formula)

Was genau mit "syntaktisch korrekt" gemeint ist, sollte klar sein. Auf http://en.wikipedia.org/wiki/First-order…Formation_rules findet sich eine Übersicht.

Von wahren und falschen Sätzen kann man erst sprechen, wenn man eine zur Sprache passende Interpretation festlegt. Je nach gewählter Interpretation kann ein und derselbe Satz mal wahr und mal falsch sein.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Joachim« (27. Juli 2007, 10:32)


Sinan

Senior Schreiberling

  • »Sinan« ist männlich
  • »Sinan« ist der Autor dieses Themas

Beiträge: 1 019

Registrierungsdatum: 5. Juli 2003

Wohnort: Hannover

Beruf: M.Sc. Informatik --> Deutsches Zentrum für Luft- und Raumfahrt

5

Freitag, 27. Juli 2007, 18:19

RE: Fragen zu Berechenbarkeit und Logik

Jo, super, so ist alles klar :)
zunächst...

Was mich jetzt durcheinander bringt ist der Gödelische Unvollständigkeitsatz (im Zusammenhang mit der Arithmetik). Un zwar:
Seite 18 dritte Zeile von unten:
"Th(N*) ist vollständig"

Seite 19 vierte Zeile von oben:
"wesentliche Aussage des Gödelischen Unvollständigkeitssatzes: Jedes Axiomensystem für Th(N*) ist unvollständig" ?(

Laut Wikipedia:
"Für die Arithmetik gilt der Gödelsche Unvollständigkeitssatz: ist sie widerspruchsfrei, dann ist sie unvollständig; ist sie vollständig, dann kann ihre Widerspruchsfreiheit nicht bewiesen werden."

„Die angesprochene Unvollständigkeit der Arithmetik beispielsweise bedeutet folgendes: Für jede nur denkbare Formalisierung der elementaren Arithmetik gilt, dass es in ihr Sätze gibt, die in dieser Formulierung weder beweisbar noch widerlegbar sind. Mit anderen Worten: Es gibt in jeder dieser Formalisierungen Sätze A mit der Eigenschaft, dass sich weder A noch ¬ A beweisen lässt.""

Ist die Arithmetik nun vollständig oder nicht?
wenn vollständig, dann lässt sich ihre Widerspruchsfreiheit (korrektheit) nicht beweisen?

Und was besagt der Gödelische Unvollständigkeitssatz?
Laut Skript Seite 27:
"Es gibt keine vollständige, axiomatisierbare Theorie T mit Q Teilnemge T"
Wikipedia
"Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.."
Ich nehme an, dass es nur "oder" heißen soll und nicht "entweder ... oder"! Richtig? und was ist mit axiomatisierbar?
oder
"In jedem formalen System der Zahlen, das zumindest eine Theorie der natürlichen Zahlen N enthält, gibt es einen unentscheidbaren Satz"
Im Skript wird immer von der Menge der rationalen Zahlen Q gesprochen. also wieder ein ?(


Ich weiß ich weiß, es sind viele Fragen geworden, aber wenn ich das verstehe, dann ist die Welt für mich wieder in Ordnung :)
zunächst...
Salsasüchtig!
Scharf wie die Soße, heiß wie der Rhythmus!


kann ich auch... in 10 Jahren
hier flipp ich aus

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

6

Freitag, 27. Juli 2007, 22:59

RE: Fragen zu Berechenbarkeit und Logik

Zitat

Original von Sinan
[Eine ganze Menge Fragen]
OK, fangen wir vorne an.

Die Begriffe Symbolmenge, Term, Formel und Satz kennen wir ja nun. Zudem nehme ich an, daß Dir der Begriff Interpretation aus der Vorlesung bekannt ist.

Ein Satz ist alleine erstmal weder wahr noch falsch. Erst wenn er in Beziehung zu einer Interpretation gesetzt wird, ist er bezüglich dieser Interpretation wahr oder falsch. (Das klappt natürlich nur, wenn die Interpretation zum Satz kompatibel ist, d. h. auf derselben Symbolmenge definiert ist. Davon gehe ich hier und im folgenden aber mal aus.) Ist M eine Interpretation und F ein Satz, so ist F unter M entweder wahr oder falsch. (Frage an dich: Warum? Und wovon hängt es ab, ob F unter M wahr oder falsch ist?)

Nun kommen wir zur logischen Implikation. Es gibt Sätze, die immer dann wahr sind, wenn auch andere Sätze wahr sind, und zwar unter jeder beliebigen Interpretation. Ist G ein Satz, der immer dann wahr ist, wenn der Satz F wahr ist (unter jeder Interpretation!), so schreiben wir F |= G. Man sagt, daß F den Satz G impliziert. Die Implikation läßt sich auch für Mengen von Sätzen definieren. Ist Gamma eine Menge von Sätzen und G ein Satz, so sagen wir, daß Gamma den Satz G impliziert (in Zeichen: Gamma |= G), falls F |= G für alle F aus Gamma gilt. Noch eine letzte Schreibweise: Ist Gamma eine Menge von Sätzen, so bezeichnen wir mit Gamma^(|=) die Menge aller Sätze, die von Gamma impliziert werden. (Man sagt auch, daß Gamma^(|=) der Abschluß von Gamma unter der logischen Implikation ist.)

Erstaunlicherweise kann man die Implikation auch etwas "handlicher" definieren als mit dem Umweg über alle möglichen Interpretationen. In Kapitel 4 des Skriptes wird beschrieben, daß die Implikation sich auch völlig losgelöst von Interpretationen definieren läßt, nämlich über sogenannte Logikkalküle (auch Schlußregeln genannt). Mit diesen Regeln läßt sich auf rein syntaktischer Ebene (also ohne sich überhaupt mit Interpretationen beschäftigen zu müssen) eine Relation |- zwischen Sätzen festlegen. Und zwar gilt für Sätze F und G genau dann F |- G, wenn auch F |= G gilt. Wie das genau geht, ist aber nicht das Thema dieser Vorlesung. Von nun an können wir jedenfalls mit dem Begriff der Implikation arbeiten ohne uns mit Interpretationen beschäftigen zu müssen. Es ist also möglich, zu beweisen, daß der Satz F den Satz G impliziert, indem man eine Kette von Implikationen |- angibt, die bei F startet und bei G endet. Auf diese Weise werden Beweise in der Mathematik geführt. Man geht von Sätzen aus, die man bereits als wahr (unter einer bestimmten Interpretation) bewiesen hat und zeigt mittels der Schlußregeln, die |- ausmachen, daß dann auch andere Sätze (unter derselben Interpretation) wahr sein müssen.

Nun kommen wir zum Kern der Vorlesung. Dazu etwas Vorgeschichte: Ein spezielles (und ein historisch besonders bedeutsames) Gebiet der Mathematik ist die sogenannte Zahlentheorie. Sie beschäftigt sich (grob gesagt) mit Aussagen über die Menge der natürlichen Zahlen (Beispiel: "Es gibt unendlich viele Primzahlen"). Man versucht in der Zahlentheorie also für bestimmte Sätze über der Symbolmenge L* der Arithmetik zu beweisen, ob sie unter der Standardinterpretation N* der Arithmetik wahr oder falsch sind. (Das obige Beispiel läßt sich beispielsweise als Satz über L* formulieren. Dieser Satz ist sogar wahr in der Interpretation N*.)

Bis zu den 1930er-Jahren war man in der Mathematik davon überzeugt, daß man für jeden Satz über L*, der unter N* wahr ist, auch beweisen kann, daß dieser wahr ist. Die Idee ist dabei die folgende: Man geht von einer Menge von Sätzen über L* aus, von denen man weiß, daß sie wahr unter L* sind. Aus diesen Sätzen erzeugt man nun mittels der logischen Implikation immer wieder neue (wahre) Sätze bis man den zu beweisenden Satz erreicht hat. Um dieses Vorgehen zu vereinfachen, haben sich Russell and Whitehead in den 1920er- und 1930er-Jahren zusammengesetzt und versucht, eine geeignete Menge von wahren Sätzen zu finden, von denen man bei Beweisen als Startpunkt ausgehen kann. Solche Mengen von Sätzen nennt man Axiome, in der Zahlentheorie wäre zum Beispiel der Satz "Jede Zahl hat einen Nachfolger" ein solches Axiom.

Zusammengefaßt: Gesucht wurde also eine Menge Gamma von Sätzen über L*, so daß Gamma^(|-) genau die Menge der wahren Sätze unter N* ist.

Die Auswahl von Gamma ist nicht einfach.

Zum einen kann es passieren, daß man eine Menge Gamma auswählt, die zu "klein" ist, Gamma^(|-) ist dann eine echte Teilmenge der Menge aller wahren Sätze unter N* (in diesem Fall nennen wir Gamma unvollständig, weil wir damit ja die Menge der wahren Sätze unter N* nicht vollständig durch Implikation erzeugen können). Es gibt dann also Sätze über L*, von denen mittels Gamma weder bewiesen werden kann, daß sie in N* wahr sind, noch daß sie in N* falsch sind. (Frage an dich: Warum ist das so?)

Andererseits kann es aber auch sein, daß Gamma widersprüchlich ist, daß heißt, daß Gamma sowohl einen Satz F als auch seine Negation NOT F enthält. In diesem Fall wäre Gamma^(|-) identisch mit der Menge aller Sätze über L* (Frage an dich: Warum?).

Aus den obigen Betrachtungen ergibt sich der Begriff der Theorie. Eine Theorie ist eine Menge von Sätzen, die unter der Implikation abgeschlossen ist. Eine Theorie ist also immer von der Form Gamma^(|-), wobei Gamma eine Menge von Sätzen ist. Eine spezielle Theorie ist die Menge aller wahren Sätze unter einer Interpretation M, kurz mit Th(M) bezeichnet. Wir nennen eine Theorie T vollständig, falls für jeden Satz F gilt, daß F oder NOT F in T enthalten ist. Gibt es eine Formel F, so daß sowohl F als auch NOT F in T enthalten sind, so nennen wir T widersprüchlich. Man beachte: Vollständigkeit von Mengen von Sätzen ist etwas anderes als Vollständigkeit von Theorien. (Frage an dich: Was ist der Unterschied?) Man kann zeigen, daß für jede Interpretation M gilt, daß Th(M) vollständig ist. (Frage an dich: Warum ist das so?)

Die Menge aller unter N* wahren Sätze in L* nennen wir Arithmetik (das ist übrigens dasselbe wie Th(N*)).

Zurück zu dem Problem der Herren Russell und Whitehead. Mit unseren neuen Begriffen lautet das Problem also: "Gesucht wird eine Menge Gamma, so daß Gamma^(|-) = Th(N*) gilt." Genauer gesagt, suchen wir nicht irgendeine solche Menge, sondern eine entscheidbare (sonst könnten wir ja direkt Gamma als Th(N*) definieren). Entscheidbar deswegen, weil wir natürlich feststellen müssen, welche Sätze wir als wahr annehmen können und welche nicht. Noch besser wäre es natürlich, wenn Gamma eine endliche Menge wäre, dann könnten wir uns unsere Menge von wahren Sätzen, mit denen wir starten, einfach aufschreiben.

Jede entscheidbare Menge von Sätzen nennen wir Axiomensystem. Mit den Definitionen von oben wissen wir nun auch, was ein vollständiges Axiomensystem ist. (Frage an dich: Nämlich was?) Eine Theorie T nennen wir axiomatisierbar, falls es ein Axiomensystem Gamma gibt mit der Eigenschaft Gamma^(|-) = T.

OK, nun ein letzter Anlauf an das Problem von Russell und Whitehead mit diesem Begriff: "Gesucht wird ein Axiomensystem für Th(N*)".

Leider trat Mitte der 1930er-Jahre Kurt Gödel auf die Bühne der Mathematik und bewies, daß es kein Axiomensystem für Th(N*) gibt, also daß Th(N*) nicht axiomatisierbar ist. Das fanden Russell und Whitehead (und viele andere Mathematiker) natürlich nicht besonders toll, weil sie doch die letzten Jahre darin investiert haben, sich ein Axiomensystem auszudenken und mehrere Bücher darüber geschrieben haben, welche Sätze aus der Arithmetik sie mit Hilfe dieses Axiomensystems beweisen konnten.

Das bedeutet also: Für jedes Axiomensystem Gamma über L* gilt: Entweder ist Gamma unvollständig oder Gamma^(|-) ist eine echte Obermenge von Th(N*) und damit widersprüchlich. (Frage an dich: Warum ist Gamma^(|-) in diesem Fall widersprüchlich?)

Gödel hat sogar gezeigt, daß sogar eine vereinfachte Form von Th(N*) nicht axiomatisierbar ist. (Das ist die Menge Q, die Du als die Menge der rationalen Zahlen gelesen hat. Wirf mal einen Blick auf Seite 22 im Skript, dort wird Q definiert.)

Diese Resultate wurden zwar für die Zahlentheorie aufgestellt, sind aber auch auf allen anderen Disziplinen der Mathematik übertragbar. Das kuriose Resultat ist damit, daß es in der Mathematik Sätze gibt, die zwar wahr sind, aber nicht als wahr bewiesen werden können.

So, ich hoffe, daß ich auf die Schnelle nicht zuviele Fehler gemacht habe. Falls doch: korrigiere mich! :)

(Achso: Die Fragen an dich, die ich in den Text eingestreut habe, sollen Dir beim Verständnis helfen. Hier im Forum brauchst Du sie daher nicht zu beantworten.)
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »Joachim« (27. Juli 2007, 23:11)


Sinan

Senior Schreiberling

  • »Sinan« ist männlich
  • »Sinan« ist der Autor dieses Themas

Beiträge: 1 019

Registrierungsdatum: 5. Juli 2003

Wohnort: Hannover

Beruf: M.Sc. Informatik --> Deutsches Zentrum für Luft- und Raumfahrt

7

Samstag, 28. Juli 2007, 17:22

Joachim, Du hast dir echt Mühe gegeben!
:) :) :) EINEN GANZ HERZLICHEN DANK :) :) :)

Meine Güte, ich verstehe das 8o glaube ich zumindest ;)
daher möchte ich doch gern auf die Fragen antworten:

Zitat

Original von Joachim
Ist M eine Interpretation und F ein Satz, so ist F unter M entweder wahr oder falsch. (Frage an dich: Warum? Und wovon hängt es ab, ob F unter M wahr oder falsch ist?)

Oh mein Gott, wieder eine Frage die zunächst als primitiv erscheint, aber dahinter sich wohl viel verbirgt!
von der Definition der Interpretation. Sieht offensichtlich aus, muss mir aber bestimmt noch gedanken drüber machen.

Zitat


Es gibt dann also Sätze über L*, von denen mittels Gamma weder bewiesen werden kann, daß sie in N* wahr sind, noch daß sie in N* falsch sind. (Frage an dich: Warum ist das so?)

Da es ja keine Menge Gamma gibt, aus der sich alle wahren Sätze in N* herleiten lassen (Th(N*) ist nicht axiomatisiertbar == es gibt kein vollständiges Axiomensystem für Th(N*)),
gibt es also wahre Sätze, deren Wahrheit nicht bewiesen werden kann.
Da sie eben wahr sind, kann auch nicht bewiesen werden, dass sie falsch sind.

Zitat


Andererseits kann es aber auch sein, daß Gamma widersprüchlich ist, daß heißt, daß Gamma sowohl einen Satz F als auch seine Negation NOT F enthält. In diesem Fall wäre Gamma^(|-) identisch mit der Menge aller Sätze über L* (Frage an dich: Warum?).

Weil aus einem Widerspruch sich alles herleiten lässt (auch die Widerspruchsfreiheit).

Zitat


Man beachte: Vollständigkeit von Mengen von Sätzen ist etwas anderes als Vollständigkeit von Theorien. (Frage an dich: Was ist der Unterschied?)

Eine Menge Gamma von Sätzen ist vollständig, falls sich alle wahren Sätze unter einer bestimmten Interpretation anhand der Sätze von Gamma implizieren lassen.
Die Menge T aller Sätze die von Gamma impliziert werden ist eine Theorie. Die Theorie ist vollständig, fass jeder Satz oder die Negation dieses Satzes in T enthalten ist. (sind beide enthalten, ist sie auch vollständig, aber widersprüchlich)

Zitat


Man kann zeigen, daß für jede Interpretation M gilt, daß Th(M) vollständig ist. (Frage an dich: Warum ist das so?)

Eine Theorie Th(M) ist ja die Menge aller wahren Sätze unter der Interpretation M. Nach obiger Definition der Vollständigkeit von Theorien ist sie vollständig.

also die Arthmetik (Th(N*)) ist vollständig! Selber rausgefunden, ganz alleine.

Zitat


Mit den Definitionen von oben wissen wir nun auch, was ein vollständiges Axiomensystem ist. (Frage an dich: Nämlich was?)

Ein vollständiges Axiomensystem ist eine Menge von unter einer bestimmten Interpretation wahren Sätzen, aus den sich alle unter dieser Interpretation wahren Sätze herleiten lassen.

Zitat


Leider trat Mitte der 1930er-Jahre Kurt Gödel auf die Bühne der Mathematik und bewies, daß es kein Axiomensystem für Th(N*) gibt, also daß Th(N*) nicht axiomatisierbar ist.

geil :D
genauer gesagt "kein vollständiges Axiomensystem"!
hätte so gern den Gesichstausdruck von Russell und Whitehead zu jenem Zeitpunkt gesehen :D

Zitat


Das bedeutet also: Für jedes Axiomensystem Gamma über L* gilt: Entweder ist Gamma unvollständig oder Gamma^(|-) ist eine echte Obermenge von Th(N*) und damit widersprüchlich. (Frage an dich: Warum ist Gamma^(|-) in diesem Fall widersprüchlich?)

Wenn Gamma^(|-) eine echte Obermenge von Th(N*) ist, dann enthält sie alle wahren Sätze und noch weitere dazu (mindestens einen). Dieser „zusätzliche“ Satz ist falsch. Da nun Th(N*), und damit auch Gamma^(|-), die Negation dieses Satzes (der Satz in wahrer Form) enthält, ist Gamma^(|-) widersprüchlich.

Zitat


Gödel hat sogar gezeigt, daß sogar eine vereinfachte Form von Th(N*) nicht axiomatisierbar ist. (Das ist die Menge Q, die Du als die Menge der rationalen Zahlen gelesen hat. Wirf mal einen Blick auf Seite 22 im Skript, dort wird Q definiert.)

Jap, alles klar. Hatte direkt die Definition gelesen ohne den Kapiteln davor, daher Q falsch interpretiert.

Die Fragen haben mir echt viel geholfen! nochmal Danke.
Salsasüchtig!
Scharf wie die Soße, heiß wie der Rhythmus!


kann ich auch... in 10 Jahren
hier flipp ich aus

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »Sinan« (28. Juli 2007, 20:09)


Panschk[FP]

Junior Schreiberling

  • »Panschk[FP]« ist männlich

Beiträge: 148

Registrierungsdatum: 21. Oktober 2005

Wohnort: H-town

Beruf: Informatik Master

8

Sonntag, 29. Juli 2007, 21:57

Wirklich beeindruckend. Joachim, du solltest mal ein Buch darüber schreiben oder so ;)

absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

9

Donnerstag, 9. August 2007, 15:08

Wie leite ich denn her, daß Th(N*) vollständig ist?

Ist das so, weil N* eine Interpretation über eine Sprache L ist, mithin also eine Interpretation (M), und für jede solche gilt, daß Th(M) immer vollständig ist (S. 15 unten)?

[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]

Oder wie? Oder was?
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »absynth« (9. August 2007, 15:37)


  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

10

Freitag, 10. August 2007, 11:50

Zitat

Original von absynth
[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]
Exakt.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Joachim« (10. August 2007, 11:50)


absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

11

Freitag, 10. August 2007, 13:37

Zitat

Original von Joachim

Zitat

Original von absynth
[EDIT: Oder ist das so, weil ein jeder arithmetischer Satz entweder wahr oder falsch sein muß und nicht beides sein kann?]
Exakt.


Huch. Das ist ja direkt anschaulich. Ich bin bestürzt.
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

fatdolphin

Trainee

  • »fatdolphin« ist männlich

Beiträge: 71

Registrierungsdatum: 30. Mai 2005

12

Mittwoch, 15. August 2007, 17:35

hat sich schon erledigt.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »fatdolphin« (16. August 2007, 21:18)


absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

13

Mittwoch, 22. August 2007, 00:40

Eine syntaktische Frage hätte ich: Auf Seite 16, Kapitel 5 wird erstmals eine Notation eingeführt mit

Zitat

(n_1, ..., n_k) element aus M gdw. F(n_1, ..., n_k) gilt.

Diese Unterstreichung wird vorher als Kurzform für S_n(0,y) eingeführt, aber in L* existiert das ja nicht. Später wird sie als Kurzform für das Gödel-Numeral eingeführt, aber diese Definition ist ja an der Stelle noch nicht bekannt. Was ist es nun...?
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

Informatik Minister

Senior Schreiberling

  • »Informatik Minister« ist männlich

Beiträge: 1 234

Registrierungsdatum: 11. Dezember 2001

14

Mittwoch, 22. August 2007, 09:07

[EDIT]Hätte ich mal genauer gelesen. Hier stand einiges, aber wenig passendes. Das folgende lasse ich aber stehen:[/EDIT]

Durch das Unterstreichen wird (verkürzt) das Symbol einer Konstante von ihrer Interpretation unterschieden, Symbol 3, Interpretation 3.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Informatik Minister« (22. August 2007, 12:04)


absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

15

Mittwoch, 22. August 2007, 10:03

Zitat

Original von Informatik Minister
So meine Auffassung, bzw. kürzer: durch das Unterstreichen wird (verkürzt) das Symbol einer Konstante von ihrer Interpretation unterschieden, Symbol 3, Interpretation 3.


Und nun noch einmal zurück zu S.16 bzw. n_k vs. n_k: n_k ist das Symbol, n_k die vereinfachende Schreibweise für die Interpretation unter N*?
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

Informatik Minister

Senior Schreiberling

  • »Informatik Minister« ist männlich

Beiträge: 1 234

Registrierungsdatum: 11. Dezember 2001

16

Mittwoch, 22. August 2007, 11:16

Anmerkung: Seite 11 spricht natürlich von einer ganz anderen Symbolmenge als Seite 7 bzw. Seite 16, also lasse ich das jetzt mal außer Acht.

Zitat

Original von absynth
Und nun noch einmal zurück zu S.16 bzw. n_k vs. n_k: n_k ist das Symbol, n_k die vereinfachende Schreibweise für die Interpretation unter N*?

Nein, jetzt noch einmal ohne die (mich) verwirrende Seite 11.

n_k stellt eine Abkürzung für einen Term über L* dar.
Beispiel: 5 steht abkürzend für 0’’’’’, einen Term über L* (ohne Bedeutung), n_k also für den Term 0 gefolgt von n_k-mal ’.

n_k ist dann die Interpretation von n_k, bzw. dem dahinterstehenden Term über L*, also die n_k-male Ausführung der Nachfolgerfunktion, angefangen bei 0, im Beispiel also der fünfte Nachfolger von 0, also 5.

Das Ganze ist der Tribut, den man an die spärliche Ausstattung von L* zahlen muss, denn dort gibt es ja u.a. nur 0 als Konstantensymbol und ein Symbol für die Nachfolgerfunktion.

Erbärmlicher Nachtrag:
Da ich inzwischen selbst ein wenig verwirrt bin, da die Vereinfachung in ganz anderem Zusammenhang eingeführt wurde (wie von absynth schon anfangs bemerkt und von mir konsequent überlesen), lasse ich mich gerne verbessern.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von »Informatik Minister« (22. August 2007, 12:12)


absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

17

Mittwoch, 22. August 2007, 14:09

Gelten Korrektheits- und Gödelscher Vollständigkeitssatz

a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?

Baut die Definition von |- "durch passende Schlußregeln", die zum Satz von der Rekursiven Aufzählbarkeit von Gamma^(|-) führt, auf dieser Definition auf, d.h. gilt alles auf S.15 genannte gleichzeitig?

Warum kann ich mit fast 28 das griechische Alphabet immer noch nicht komplett? Werde ich es je lernen?

Fragen über Fragen...
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

18

Mittwoch, 22. August 2007, 14:20

Zitat

Original von absynth
Gelten Korrektheits- und Gödelscher Vollständigkeitssatz

a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?
Die Definition von |- beruht auf besagten Schlußregeln, damit auch die von Dir genannten Sätze. Diese Sätze sind jedoch nicht für beliebige Sammlungen von Schlußregeln wahr. Es gibt allerdings eine Sammlung einfacher Schlußregeln (dies wird in der Vorlesung nicht thematisiert), mit denen |- so definiert werden kann, daß die von Dir genannten Sätze wahr sind.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

absynth

Gründervater

  • »absynth« ist männlich

Beiträge: 666

Registrierungsdatum: 10. Dezember 2001

Wohnort: Hannover

Beruf: M. SC. Informatik

19

Mittwoch, 22. August 2007, 14:28

Zitat

Original von Joachim

Zitat

Original von absynth
Gelten Korrektheits- und Gödelscher Vollständigkeitssatz

a) aufeinander aufbauend, also mit beiden gelte Gamma |- F <-> Gamma |= F? Sind doch beide Richtungen durch Sätze definiert...
b) Nur bei spezieller Definition von |- S.15 ganz unten als Überleitung zu den Sätzen) mit Schlußregeln?
Die Definition von |- beruht auf besagten Schlußregeln, damit auch die von Dir genannten Sätze. Diese Sätze sind jedoch nicht für beliebige Sammlungen von Schlußregeln wahr. Es gibt allerdings eine Sammlung einfacher Schlußregeln (dies wird in der Vorlesung nicht thematisiert), mit denen |- so definiert werden kann, daß die von Dir genannten Sätze wahr sind.


Und Gamma |- F <=> Gamma |= F? Folgt das (unter den oben erwähnten Schlußregeln) aus den beiden Sätzen?
I refuse to submit
To the god you say is kind
I know what's right, and it is time
It's time to fight, and free our minds
http://www.christopher-kunz.de/

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11. Dezember 2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

20

Mittwoch, 22. August 2007, 14:53

Zitat

Original von absynth
Und Gamma |- F <=> Gamma |= F? Folgt das (unter den oben erwähnten Schlußregeln) aus den beiden Sätzen?
Ja, steht doch so im Skript.

Die Idee dahinter: Logische Implikation kann äquivalent sowohl auf semantischer Ebene (|=, über alle möglichen Interpretationen) als auch auf syntaktischer Ebene (|-, über die Schlußregeln) definiert werden.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Joachim« (22. August 2007, 14:56)