Presburger-Arithmetik (PA)

Wir definieren eine Folge F₀, F₁,… mathend000# von Formeln durch

F₀(x, z) = (x + 1 = z), F_k+1(x, z) = ∃y : F_k(x, y)∧F_k(y, z) mathend000#.

• Für welche z mathend000# gilt F₃(0, z) mathend000# ?
• Beschreiben Sie die Bedeutung von F_k(x, z) mathend000# durch eine nicht rekursive Formel, bei der Sie zusätzlich die Funktionssymbole für Multiplikation und Potenzierung verwenden dürfen.
• Reduzieren Sie die Formelgröße von F_k mathend000# (innerhalb PA), indem Sie eine äquivalente Definition von F_k+1 mathend000# angeben, in der F_k mathend000# nur einmal vorkommt.