Fachrat Informatik - Forum

Quoted

Original von Dr. Jekyll
Ich verstehe gerade grundsätzlich den Unterschied zwischen "Definierbarkeit" und "Repräsentierbarkeit" (von Funktionen) nicht. Ich stehe da total auf dem Schlauch.
Wann genau ist eine Funktion in T definierbar, aber nicht repräsentierbar?

Repräsentierbarkeit bedeutet anschaulich, daß die Aussage f(n) = m (und damit auch f(n) != r für alle r != m) sich direkt in Form eines Satzes (ich nenne ihn im folgenden mal R(n)) in der Theorie wiederfindet. Daraus folgen unmittelbar auch alle Sätze, die bei der Definierbarkeit verlangt werden (ich nenne sie im folgenden mal D1(n), D2(n), ...).

Andersrum ist es jedoch nicht unbedingt so. Würde Definierbarkeit die Repräsentierbarkeit implizieren, so müßte in jeder Theorie aus {D1(n), D2(n), ...} der Satz R(n) gefolgert werden können. Beweise sind aber immer endlich, die Menge {D1(n), D2(n), ...} jedoch unendlich. Ohne Zuhilfenahme weiterer Sätze aus der jeweiligen Theorie läßt sich diese Folgerung also nicht anstellen.

Quoted

Warum ist beides äquivalent wenn T = T* ?

Sei f in T* definierbar (siehe oben). Da T* vollständig ist (wegen der Definition über Th(...)), ist entweder R(n) oder !R(n) in T*. Wäre !R(n) in T*, so gäbe es ein i, für das !Di(n) in T* wäre. Dies stellt einen Widerspruch zur Definierbarkeit dar. Ist T* aber widerspruchsfrei (wovon auszugehen ist), so muß f darin also repräsentierbar sein. Ist T* widerspruchsvoll, so ist sowieso jeder Satz in T* enthalten, also ist f darin erst recht repräsentierbar.

Somit können sich Definierbarkeit und Repräsentierbarkeit nur in unvollständigen Theorien unterscheiden. (Ein Beispiel dafür habe ich leider gerade keines.)