MATHEMATISCHES INSTITUT Bonn, den 03.05.2002 DER UNIVERSITÄT BONN Prof. Dr. Philip Welch

Berechenbarkeitstheorie Aufgabenblatt 3

Aufgabe 1 Man kann k-näre Funktionen durch unäre Funktionen wie folgt ersetzen:

Sei F (x_{1}, ⋯, x_{k}) k-när. Definiere die Kontraktion < F > von F durch

< F > (x) ≃ F ((x)_{1}, ⋯, (x)_{k}).

(a) Zeigen Sie, wie F aus < F > rekonstruiert werden kann.

(b) Zeigen Sie, daß F ∈ C_{RM} genau dann gilt, wenn < F >∈ C_{RM} gilt.

(c) Beachten Sie: analog kann man auch k-näre Relationen in unäre Relationen umwandeln.

Aufgabe 2 (Enumerations-Satz für n Variablen) Zeigen Sie:

Für jedes n ≥ 1 existiert eine C_{RM}-Funktion ϕ_{z_{n}}(e, x_{1}, ⋯, x_{n}), so daß gilt:

ϕ_{z_{n}}(e, x_{1}, ⋯, x_{n}) ≃ ϕ_{e}^{(n)}(x_{1}, ⋯, x_{n}).

Homepage der Vorlesung:

http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Welch.html
Newsgroup: uni-bonn.math.logik