You are not logged in.

Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

1

Thursday, July 26th 2007, 5:40pm

Fragen zu Berechenbarkeit und Logik

Hallo,

Habe (erstmal) zwei Fragen:

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

Quoted


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

Nach dem Beweis kommt

Quoted


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:

Quoted


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
With great power comes great responsibility

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Thursday, July 26th 2007, 7:13pm

RE: Fragen zu Berechenbarkeit und Logik

Quoted

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

Quoted

2. Seite 7:

Quoted


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

This post has been edited 1 times, last edit by "Joachim" (Jul 26th 2007, 7:17pm)


Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

3

Friday, July 27th 2007, 9:58am

RE: Fragen zu Berechenbarkeit und Logik

Quoted

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

8 Zeilen tiefer.

Quoted


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".
With great power comes great responsibility

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

Friday, July 27th 2007, 10:27am

RE: Fragen zu Berechenbarkeit und Logik

Quoted

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

This post has been edited 1 times, last edit by "Joachim" (Jul 27th 2007, 10:32am)


Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

5

Friday, July 27th 2007, 6:19pm

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...
With great power comes great responsibility

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

6

Friday, July 27th 2007, 10:59pm

RE: Fragen zu Berechenbarkeit und Logik

Quoted

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

This post has been edited 3 times, last edit by "Joachim" (Jul 27th 2007, 11:11pm)


Sinan

Senior Schreiberling

  • "Sinan" is male
  • "Sinan" started this thread

Posts: 1,021

Date of registration: Jul 5th 2003

Location: Malaga

Occupation: Senior Cloud Solution Engineer bei Oracle

7

Saturday, July 28th 2007, 5:22pm

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:

Quoted

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.

Quoted


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.

Quoted


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).

Quoted


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)

Quoted


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.

Quoted


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.

Quoted


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

Quoted


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.

Quoted


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.
With great power comes great responsibility

This post has been edited 4 times, last edit by "Sinan" (Jul 28th 2007, 8:09pm)


Panschk[FP]

Junior Schreiberling

  • "Panschk[FP]" is male

Posts: 148

Date of registration: Oct 21st 2005

Location: H-town

Occupation: Informatik Master

8

Sunday, July 29th 2007, 9:57pm

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

absynth

Gründervater

  • "absynth" is male

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

9

Thursday, August 9th 2007, 3:08pm

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/

This post has been edited 3 times, last edit by "absynth" (Aug 9th 2007, 3:37pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

10

Friday, August 10th 2007, 11:50am

Quoted

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

This post has been edited 1 times, last edit by "Joachim" (Aug 10th 2007, 11:50am)


absynth

Gründervater

  • "absynth" is male

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

11

Friday, August 10th 2007, 1:37pm

Quoted

Original von Joachim

Quoted

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" is male

Posts: 71

Date of registration: May 30th 2005

12

Wednesday, August 15th 2007, 5:35pm

hat sich schon erledigt.

This post has been edited 1 times, last edit by "fatdolphin" (Aug 16th 2007, 9:18pm)


absynth

Gründervater

  • "absynth" is male

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

13

Wednesday, August 22nd 2007, 12:40am

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

Quoted

(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" is male

Posts: 1,234

Date of registration: Dec 11th 2001

14

Wednesday, August 22nd 2007, 9:07am

[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

This post has been edited 7 times, last edit by "Informatik Minister" (Aug 22nd 2007, 12:04pm)


absynth

Gründervater

  • "absynth" is male

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

15

Wednesday, August 22nd 2007, 10:03am

Quoted

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" is male

Posts: 1,234

Date of registration: Dec 11th 2001

16

Wednesday, August 22nd 2007, 11:16am

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.

Quoted

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

This post has been edited 5 times, last edit by "Informatik Minister" (Aug 22nd 2007, 12:12pm)


absynth

Gründervater

  • "absynth" is male

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

17

Wednesday, August 22nd 2007, 2:09pm

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

18

Wednesday, August 22nd 2007, 2:20pm

Quoted

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" is male

Posts: 666

Date of registration: Dec 10th 2001

Location: Hannover

Occupation: M. SC. Informatik

19

Wednesday, August 22nd 2007, 2:28pm

Quoted

Original von Joachim

Quoted

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" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

20

Wednesday, August 22nd 2007, 2:53pm

Quoted

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

This post has been edited 1 times, last edit by "Joachim" (Aug 22nd 2007, 2:56pm)