Mathematische Logik/Gemischte Definitionsabfrage/19/Aufgabe/Lösung


  1. Ein Element heißt maximal, wenn es kein Element , , mit gibt.
  2. Die Termsubstitution wird rekursiv folgendermaßen definiert.
    1. Für eine Variable ist
    2. Für eine Konstante ist
    3. Für ein -stelliges Funktionssymbol und Terme ist
  3. Der Rang von wird rekursiv durch
    1. , falls atomar ist.
    2. , falls ist.
    3. , falls mit ist.
    4. , falls oder ist.

    definiert.

  4. Die beiden -Strukturen und heißen elementar äquivalent, wenn jeder -Satz, der in gilt, auch in gilt.
  5. Die Funktion

    heißt -berechenbar, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe (in den ersten Registern) anhält und als (einzige) Ausgabe besitzt.

  6. Unter der -Funktion versteht man die Abbildung

    die folgendermaßen festgelegt ist. ist die kleinste Zahl , die die Bedingung erfüllt, dass es natürliche Zahlen gibt, die die folgenden Eigenschaften erfüllen:

    1. .
    2. .
    3. .
    4. ist eine Quadratzahl.
    5. Alle Teiler von sind ein Vielfaches von .

    Wenn kein solches existiert, so ist .