Zum Inhalt springen

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

Aus Wikiversity


  1. Die folgenden rekursiv definierten Wörter heißen die Ausdrücke dieser Sprache.
    1. Wenn und Terme sind, so ist
      ein Ausdruck.
    2. Wenn ein -stelliges Relationssymbol ist und Terme sind, so ist

      ein Ausdruck.

    3. Wenn und Ausdrücke sind, so sind auch

      Ausdrücke.

    4. Wenn ein Ausdruck ist und eine Variable, so sind auch

      Ausdrücke.

  2. Ein Ideal ist eine nichtleere Teilmenge , für die die beiden folgenden Bedingungen erfüllt sind:
    1. Für alle ist auch .
    2. Für alle und ist auch .
  3. Die Variablensubstitution definiert man rekursiv über den Aufbau der -Ausdrücke.
    1. Für Terme setzt man
    2. Für ein -stelliges Relationssymbol und Terme setzt man
    3. Für einen Ausdruck setzt man
    4. Für Ausdrücke und setzt man

      und ebenso für die anderen zweistelligen Junktoren.

    5. Für einen Ausdruck seien diejenigen Variablen (unter den ), die in frei vorkommen. Es sei , falls nicht in vorkommt. Andernfalls sei die erste Variable (in einer fixierten Variablenaufzählung, falls es abzählbar viele Variablen gibt, bzw. in einer fixierten Wohlordnung der Variablenmenge), die weder in noch in vorkommt. Dann setzt man

      und ebenso für den Existenzquantor.

  4. Der Ausdruck heißt ableitbar, wenn er sich aus den Grundtautologien, also
      • den aussagenlogischen syntaktischen Tautologien,
      • den Gleichheitsaxiomen,
      • der Existenzeinführung im Sukzedens,

    durch sukzessive Anwendung der Ableitungsregeln Modus ponens und der Existenzeinführung im Antezedens erhalten lässt.

  5. Die Abbildung heißt arithmetisch repräsentierbar, wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die Äquivalenz genau dann, wenn gilt.
  6. Eine unter aussagenlogischen Ableitungen abgeschlossene Teilmenge der modallogischen Sprache heißt (formale) Modallogik.