Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Definitionsliste/kontrolle

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Aussagenlogische Grundtautologien

Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiom


Für eine Aussagenvariablenmenge und beliebige Ausdrücke legt man folgende (syntaktische) Tautologien axiomatisch fest.

  4. und


Frage:

Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiom/Begriff

Antwort:

Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiom/Begriff/Inhalt





Ableitbar (Aussagenlogik)

Aussagenlogik/Ausdrucksmenge/Ableitungsbeziehung/Definition


Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge und sei . Man sagt, dass aus ableitbar ist, geschrieben

wenn es endlich viele Ausdrücke derart gibt, dass

gilt.


Frage:

Die Ableitbarkeit eines Aussage aus einer Aussagenmenge in der Sprache der Aussagenlogik zu einer Aussagevariablenmenge .


Antwort:

Man sagt, dass aus ableitbar ist, wenn es endlich viele Ausdrücke derart gibt, dass

gilt.





Maximal widerspruchsfrei (Aussagenlogik)

Aussagenlogik/Ausdrucksmenge/Maximal widerspruchsfrei/Definition


Eine Teilmenge zu einer Menge an Aussagenvariablen heißt maximal widerspruchsfrei, wenn widerspruchsfrei ist und jede echt größere Menge widersprüchlich ist.


Frage:

Eine maximal widerspruchsfreie Teilmenge zu einer Menge an Aussagenvariablen.


Antwort:

Die Teilmenge heißt maximal widerspruchsfrei, wenn widerspruchsfrei ist und jede echt größere Menge widersprüchlich ist.





Grundtermmenge

Term/Variablenmenge/Funktionssymbole/Grundmenge/Definition


Eine Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.

  1. eine Variablenmenge ,
  2. eine Konstantenmenge ,
  3. zu jedem eine Menge von Funktionssymbolen.


Frage:

Die Bestandteile einer Grundtermmenge.


Antwort:

Die Bestandteile einer Grundtermmenge besteht aus den folgenden (untereinander disjunkten) Mengen.

  1. eine Variablenmenge ,
  2. eine Konstantenmenge ,
  3. zu jedem eine Menge von Funktionssymbolen.





Termmenge

Term/Variablenmenge/Funktionssymbole/Grundmenge/Rekursiv definierte Termmenge/Definition


Zu einer Grundtermmenge ist die zugehörige Termmenge (oder die Menge der -Terme) diejenige Teilmenge der Wörter über dem Termalphabet , die durch die folgenden rekursiven Vorschriften festgelegt wird.

  1. Jede Variable ist ein Term.
  2. Jede Konstante ist ein Term.
  3. Für jedes und Terme ist auch ein Term.


Frage:

Die Termmenge zu einer Grundtermmenge .


Antwort:

Die Termmenge ist diejenige Teilmenge der Wörter über dem Termalphabet , die durch die folgenden rekursiven Vorschriften festgelegt wird.

  1. Jede Variable ist ein Term.
  2. Jede Konstante ist ein Term.
  3. Für jedes und Terme ist auch ein Term.





Alphabet einer Sprache erster Stufe

Alphabet erster Stufe/Symbole für Relationen und Funktionen/Grunddaten/Definition


Ein Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.

  1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
  2. Zu jeder natürlichen Zahl eine Menge von -stelligen Relationssymbolen.
  3. Die aussagenlogischen Junktoren
  4. Das Gleichheitszeichen .
  5. Die Quantoren und .
  6. Klammern, also und .


Frage:

Das Alphabet einer Sprache erster Stufe.


Antwort:

Das Alphabet einer Sprache erster Stufe umfasst die folgenden Daten.

  1. Eine Grundtermmenge, also eine Menge aus Variablen, Konstanten und Funktionssymbolen.
  2. Zu jeder natürlichen Zahl eine Menge von -stelligen Relationssymbolen.
  3. Die aussagenlogischen Junktoren
  4. Das Gleichheitszeichen .
  5. Die Quantoren und .
  6. Klammern, also und .





Ausdruck in einer Sprache erster Stufe

Ausdrücke erster Stufe/Über Alphabet/Rekursiv/Definition


Es sei ein Alphabet einer Sprache erster Stufe gegeben. Dann nennt man die folgenden rekursiv definierten Wörter über diesem Alphabet 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.


Frage:

Die rekursive Definition für die Ausdrücke in einer Sprache erster Stufe.


Antwort:

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.





Produktmenge

Produktmenge/Zwei Mengen/Definition


Es seien zwei Mengen und gegeben. Dann nennt man die Menge

die Produktmenge der beiden Mengen.


Frage:

Die Produktmenge aus zwei Mengen und .


Antwort:

Man nennt die Menge

die Produktmenge der Mengen und .





Relation auf einer Menge

Mengentheorie/Relation auf einer Menge/n-stellig/Definition


Unter einer stelligen Relation auf einer Menge versteht man eine Teilmenge der -fachen Produktmenge .


Frage:

Eine -stellige Relation auf einer Menge .


Antwort:

Unter einer - stelligen Relation auf versteht man eine Teilmenge der -fachen Produktmenge .





Abbildung

Theorie der Abbildungen/Abbildung/Definition


Seien und Mengen. Eine Abbildung von nach ist dadurch gegeben, dass jedem Element der Menge genau ein Element der Menge zugeordnet wird. Das zu eindeutig bestimmte Element wird mit bezeichnet. Die Abbildung drückt man als Ganzes häufig durch

aus.


Frage:

Eine Abbildung von einer Menge in eine Menge .


Antwort:

Eine Abbildung von nach ist dadurch gegeben, dass jedem Element der Menge genau ein Element der Menge zugeordnet wird.





n-stellige Abbildung

Theorie der Abbildungen/n-stellige Funktion/Definition


Es sei eine Menge. Unter einer stelligen Abbildung auf versteht man eine Abbildung

vom -fachen Produkt von mit sich selbst nach .


Frage:

Theorie der Abbildungen/n-stellige Funktion/Definition/Begriff

Antwort:

Theorie der Abbildungen/n-stellige Funktion/Definition/Begriff/Inhalt





Interpretation

Alphabet erster Stufe/A/Struktur/Belegung/Interpretation/Definition


Es sei das Symbolalphabet einer Sprache erster Stufe. Unter einer Struktur versteht man eine nichtleere Menge mit den folgenden Festlegungen.

  1. Für jede Konstante ist ein Element festgelegt.
  2. Zu jedem -stelligen Funktionssymbol (aus ) ist eine -stellige Funktion

    festgelegt.

  3. Zu jedem -stelligen Relationssymbol (aus ) ist eine -stellige Relation

    festgelegt.

Unter einer (Variablen)belegung in versteht man eine Festlegung für jede Variable .

Unter einer Interpretation versteht man eine -Struktur zusammen mit einer -Belegung.


Frage:

Eine -Struktur zu einem Symbolalphabet einer Sprache erster Stufe.


Antwort:

Unter einer -Struktur versteht man eine nichtleere Menge mit den folgenden Festlegungen.

  1. Für jede Konstante ist ein Element festgelegt.
  2. Zu jedem -stelligen Funktionssymbol (aus ) ist eine -stellige Funktion

    festgelegt.

  3. Zu jedem -stelligen Relationssymbol (aus ) ist eine -stellige Relation

    festgelegt.





Terminterpretation

Alphabet erster Stufe/A/Interpretation für Terme/Definition


Zu einem Symbolalphabet erster Stufe und einer -Interpretation in einer Menge wird induktiv über den Aufbau der Terme für jeden -Term eine Interpretation in definiert.

  1. Für jede Konstante und jede Variable ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also und .
  2. Wenn Terme mit den Interpretationen sind und wenn ein -stelliges Funktionssymbol ist, so wird der Term als interpretiert.


Frage:

Die Interpretation der Terme zu einem Symbolalphabet in einer gegebenen -Interpretation auf einer Grundmenge .


Antwort:

Die Terminterpretation wird induktiv über den Aufbau der Terme für jeden -Term definiert.

  1. Für jede Konstante und jede Variable ist die Terminterpretation durch die Interpretation bzw. die Belegung direkt gegeben, also und .
  2. Wenn Terme mit Interpretationen sind und wenn ein -stelliges Funktionssymbol ist, so wird der Term als interpretiert.





Uminterpretation

Alphabet erster Stufe/A/Umbelegung und Uminterpretation/Definition


Es sei ein Symbolalphabet erster Stufe und eine -Interpretation in einer Menge gegeben. Es sei eine Variable und ein Element der Grundmenge. Dann versteht man unter der Uminterpretation diejenige Interpretation von in , die strukturgleich zu ist und für deren Variablenbelegung

gilt.


Frage:

Die Uminterpretation zu einer -Interpretation in einer Menge , wobei eine Variable und ein Element der Grundmenge ist.


Antwort:

Unter der Uminterpretation versteht man diejenige Interpretation von in , die strukturgleich zu ist und für deren Variablenbelegung

gilt.





Gültigkeit unter einer Interpretation

Mathematische Logik/Modellbeziehung/Definition


Zu einem Symbolalphabet erster Stufe und einer -Interpretation in einer Menge werden die -Ausdrücke folgendermaßen (induktiv über den Aufbau der Ausdrücke) interpretiert und als gültig (oder ungültig) charakterisiert (die Gültigkeit einer Aussage unter der Interpretation wird dabei als geschrieben). Es seien Terme und Ausdrücke.

  1. , wenn .
  2. , wenn .
  3. , wenn nicht gilt.
  4. , wenn und gilt.
  5. , wenn die Gültigkeit die Gültigkeit impliziert.
  6. , wenn es ein mit gibt.
  7. , wenn für alle die Beziehung gilt.


Frage:

Die (rekursiv definierte) Gültigkeit eines prädikatenlogischen -Ausdruckes bei einer -Interpretation auf einer Menge .


Antwort:

Die -Ausdrücke werden folgendermaßen als gültig charakterisiert (dabei seien Terme und Ausdrücke).

  1. , wenn .
  2. , wenn .
  3. , wenn nicht gilt.
  4. , wenn und gilt.
  5. , wenn die Gültigkeit die Gültigkeit impliziert.
  6. , wenn es ein gibt mit .
  7. , wenn für alle die Beziehung gilt.





Allgemeingültiger Ausdruck

Prädikatenlogik/Allgemeingültig/Jedes Modell/Definition


Es sei ein Symbolalphabet und ein -Ausdruck in der Prädikatenlogik erster Stufe. Man nennt allgemeingültig (oder eine semantische Tautologie), wenn er in jeder -Interpretation gilt, also wahr ist.


Frage:

Ein allgemeingültiger prädikatenlogischer Ausdruck .


Antwort:

Man nennt allgemeingültig, wenn er in jeder -Interpretation gilt.





Gruppe

Gruppentheorie/Gruppe/Direkt/Definition


Eine Menge mit einem ausgezeichneten Element und mit einer Verknüpfung

heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

  1. Die Verknüpfung ist assoziativ, d.h. für alle gilt
  2. Das Element ist ein neutrales Element, d.h. für alle gilt
  3. Zu jedem gibt es ein inverses Element, d.h. es gibt ein mit


Frage:

Eine Gruppe.


Antwort:

Eine Menge mit einem ausgezeichneten Element und mit einer Verknüpfung

heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

  1. Die Verknüpfung ist assoziativ, d.h. für alle gilt
  2. Das Element ist ein neutrales Element, d.h. für alle gilt
  3. Zu jedem gibt es ein inverses Element, d.h. es gibt ein mit





Ordnungsrelation

Ordnungstheorie/Ordnungsrelation/Definition


Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

  1. Es ist für alle .
  2. Aus und folgt stets .
  3. Aus und folgt .


Frage:

Eine Ordnungsrelation auf einer Menge .


Antwort:

Die Relation heißt Ordnungsrelation, wenn folgende drei Bedingungen erfüllt sind.

  1. Es ist für alle .
  2. Aus und folgt stets .
  3. Aus und folgt .





Folgerung

Prädikatenlogik/Folgerung/Über Modelle/Definition


Es sei ein Symbolalphabet erster Stufe, eine Menge von -Ausdrücken und ein -Ausdruck. Man sagt, dass aus folgt, geschrieben , wenn für jede -Interpretation mit auch gilt.


Frage:

Die Folgerungsbeziehung , wobei eine Menge von -Ausdrücken und ein -Ausdruck ist (und ein Symbolalphabet.)


Antwort:

Man sagt, dass aus folgt, wenn für jede -Interpretation mit auch gilt.





Erfüllbarer Ausdruck

Prädikatenlogik/Erfüllbar/Durch Modell/Definition


Es sei ein Symbolalphabet und es sei ein -Ausdruck in der Prädikatenlogik erster Stufe. Man nennt erfüllbar, wenn es eine -Interpretation mit gibt.


Frage:

Die Erfüllbarkeit eines -Ausdruckes , wobei ein Symbolalphabet bezeichnet.


Antwort:

Man nennt erfüllbar, wenn es eine -Interpretation mit gibt.





Variablensubstitution für Terme

Prädikatenlogik/Variablensubstitution/Terme/Definition


Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Dann definiert man rekursiv über den Aufbau der Terme die Substitution für jeden -Term .

  1. Für eine Variable ist
  2. Für eine Konstante ist
  3. Für ein -stelliges Funktionssymbol und Terme ist


Frage:

Die Termsubstitution für -Terme (dabei sei ein Symbolalphabet einer Sprache erster Stufe, paarweise verschiedene Variablen und fixierte -Terme).


Antwort:

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





Variablensubstitution für Ausdrücke

Prädikatenlogik/Variablensubstitution/Ausdrücke/Definition


Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Dann definiert man rekursiv über den Aufbau der -Ausdrücke die Substitution für jeden -Ausdruck .

  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.


Frage:

Die Variablensubstitution für einen -Ausdruck , wobei Variablen und fixierte -Terme seien.


Antwort:

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.





Ableitbar (Prädikatenlogik)

Prädikatenlogik/Ableitbar/Definition


Ein Ausdruck heißt ableitbar im Prädikatenkalkül (oder eine syntaktische Tautologie), wenn er sich aus den Grundtautologien, also

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

ausgedrückt.


Frage:

Die Ableitbarkeit eines Ausdrucks im prädikatenlogischen Kalkül.


Antwort:

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.





Ableitbar aus Ausdrucksmenge (Prädikatenlogik)

Prädikatenlogik/Ausdrucksmenge/Ableitbar/Definition


Es sei ein Symbolalphabet, eine Menge an -Ausdrücken

und ein weiterer -Ausdruck. Man sagt, dass aus ableitbar ist, geschrieben
wenn es endlich viele Ausdrücke derart gibt, dass

gilt.


Frage:

Die Ableitbarkeit eines -Ausdrucks aus einer Menge an -Ausdrücken.


Antwort:

Man sagt, dass aus ableitbar ist, wenn es endlich viele Ausdrücke derart gibt, dass

gilt.





Addition mit n

Natürliche Zahlen/Addition mit n/Als Verschiebung/Definition


Es sei ein Dedekind-Peano-Modell der natürlichen Zahlen und . Dann definieren wir die Addition mit als diejenige aufgrund von Satz 12.2 eindeutig bestimmte Abbildung

für die

gilt.


Frage:

Die Addition in einem Dedekind-Peano-Modell .


Antwort:

Die Addition wird über die Addition mit festem definiert, wobei die eindeutig bestimmte Abbildung

ist, für die

gilt.





Multiplikation mit n

Natürliche Zahlen/Multiplikation mit n/Definition


Es sei ein Dedekind-Peano-Modell der natürlichen Zahlen und . Dann definieren wir die Multiplikation mit als diejenige aufgrund von Satz 12.2 eindeutig bestimmte Abbildung

für die

gilt.


Frage:

Die Multiplikation mit in einem Dedekind-Peano-Modell .


Antwort:

Die Multiplikation mit ist diejenige aufgrund von Satz 12.2 eindeutig bestimmte Abbildung

für die

gilt.





Maximal widerspruchsfrei

Ausdrucksmenge/Maximal widerspruchsfrei/Definition


Eine Menge an -Ausdrücken (über einem Symbolalphabet ) heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks die Menge widersprüchlich macht.


Frage:

Eine maximal widerspruchsfreie prädikatenlogische Ausdrucksmenge .


Antwort:

Die Menge heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks die Menge widersprüchlich macht.





Ausdrucksmenge enthält Beispiele

Ausdrucksmenge/Enthält Beispiele/Definition


Man sagt, dass eine Menge an -Ausdrücken (über einem Symbolalphabet ) Beispiele enthält, wenn es für jeden Ausdruck der Form einen -Term derart gibt, dass

zu gehört.


Frage:

Die Eigenschaft einer Ausdrucksmenge , Beispiele zu enthalten.


Antwort:

Man sagt, dass Beispiele enthält, wenn es für jeden Ausdruck der Form aus einen -Term derart gibt, dass

zu gehört.





Atomarer Ausdruck

Prädikatenlogik/Atomarer Ausdruck/Definition


Unter einem atomaren Ausdruck versteht man Ausdrücke der Form , wobei und Terme sind, und der Form , wobei ein -stelliges Relationssymbol ist und Terme sind.


Frage:

Ein atomarer Ausdruck in der Prädikatenlogik.


Antwort:

Unter einem atomaren Ausdruck versteht man Ausdrücke der Form , wobei und Terme sind, und der Form , wobei ein -stelliges Relationssymbol ist und Terme sind.





Rang (Ausdruck)

Prädikatenlogik/Rang eines Ausdrucks/Definition


Es sei ein Alphabet einer Sprache erster Stufe gegeben. Dann definiert man für Ausdrücke den Rang von durch

  1. , falls atomar ist.
  2. , falls ist.
  3. , falls mit ist.
  4. , falls oder ist.


Frage:

Der Rang eines prädikatenlogischen Ausdrucks .

Antwort:

Der Rang von wird rekursiv durch

  1. , falls atomar ist.
  2. , falls ist.
  3. , falls mit ist.
  4. , falls oder ist.

definiert.





Elementar äquivalent

Prädikatenlogik/Strukturen/Elementar äquivalent/Definition


Zwei -Strukturen und über einem erststufigen Symbolalphabet heißen elementar äquivalent, wenn jeder -Satz, der in gilt, auch in gilt.


Frage:

Die elementare Äquivalenz von zwei -Strukturen und über einem erststufigen Symbolalphabet .


Antwort:

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





Homomorphismus

Strukturen/Homomorphismus/Definition


Es sei ein erststufiges Symbolalphabet und und seien -Strukturen. Eine Abbildung

heißt Homomorphismus, wenn folgende Eigenschaften gelten.

  1. Für jede Konstante ist
  2. Für jedes -stellige Funktionssymbol ist

    für alle .

  3. Für jedes -stellige Relationsymbol impliziert die Gültigkeit von

    die Gültigkeit von


Frage:

Ein -Homomorphismus

zwischen zwei -Strukturen und .


Antwort:

Die Abbildung

heißt -Homomorphismus, wenn folgende Eigenschaften gelten.

  1. Für jede Konstante ist
  2. Für jedes -stellige Funktionssymbol ist

    für alle .

  3. Für jedes -stellige Relationsymbol impliziert die Gültigkeit von

    die Gültigkeit von





Isomorphismus

Strukturen/Isomorphismus/Isomorph/Definition


Es sei ein erststufiges Symbolalphabet und und seien -Strukturen. Eine bijektive Abbildung

heißt Isomorphismus, wenn sowohl als auch die Umkehrabbildung ein -Homomorphismus ist.


Frage:

Ein Isomorphismus

zwischen zwei -Strukturen und .


Antwort:

heißt -Isomorphismus, wenn bijektiv ist und sowohl als auch die Umkehrabbildung ein -Homomorphismus ist.





Elementare Äquivalenz für Elemente

Prädikatenlogik/Modell/Elementare Äquivalenz für Elemente/Definition


Es sei ein erststufiges Symbolalphabet und eine -Struktur. Wir nennen zwei Elemente elementar äquivalent, wenn für jeden Ausdruck in der einen freien Variablen und jede Variablenbelegung auf die Beziehung

gilt.


Frage:

Die elementare Äquivalenz für Elemente für eine -Struktur .


Antwort:

Zwei Elemente heißen elementar äquivalent, wenn für jeden Ausdruck in der einen freien Variablen und jede Variablenbelegung auf die Beziehung

gilt.





Funktional-abgeschlossene Teilmenge

Modell/Teilmenge/Funktional abgeschlossen/Definition


Es sei ein erststufiges Symbolalphabet umd eine -Struktur. Eine Teilmenge heißt funktional abgeschlossen (oder eine Unterstruktur), wenn für jede Konstante das Element zu gehört und für jedes -stellige Funktionssymbol und beliebige Elemente auch zu gehört.


Frage:

Eine funktional abgeschlossene Teilmenge einer -Struktur , wobei ein erststufiges Symbolalphabet bezeichnet.


Antwort:

Die Teilmenge heißt funktional abgeschlossen, wenn für jede Konstante das Element zu gehört und für jedes -stellige Funktionssymbol und beliebige Elemente auch zu gehört.





Nichtstandardmodell

Modell/Nichtstandardmodell/Definition


Es sei eine fixierte -Struktur (das Standardmodell) über einem Symbolalphabet . Dann nennt man eine weitere -Struktur , die zu elementar äquivalent, aber nicht zu -isomorph ist, ein Nichtstandardmodell von .


Frage:

Ein Nichtstandardmodell zu einem fixierten -Modell .


Antwort:

Man nennt eine weitere -Struktur , die zu elementar äquivalent, aber nicht zu -isomorph ist, ein Nichtstandardmodell von .





Reell-abgeschlossener Körper

Reell abgeschlossener Körper/Definition


Ein angeordneter Körper heißt reell-abgeschlossen, wenn folgende Eigenschaften gelten.

  1. Jedes nichtnegative Element aus besitzt eine Quadratwurzel in .
  2. Jedes Polynom mit ungeradem Grad besitzt in eine Nullstelle.


Frage:

Ein reell-abgeschlossener Körper.


Antwort:

Ein angeordneter Körper heißt reell-abgeschlossen, wenn folgende Eigenschaften gelten.

  1. Jedes nichtnegative Element aus besitzt eine Quadratwurzel in .
  2. Jedes Polynom mit ungeradem Grad besitzt in eine Nullstelle.





Registermaschine

Registermaschine/Zahlen/Befehle/Programm/Definition


Unter einer Registermaschine versteht man eine endliche Folge von Registern (oder Speichern), deren Inhalt jeweils eine natürliche Zahl ist, die durch eine endliche (eventuell leere) Folge von Strichen repräsentiert wird.

Ein Programm für eine Registermaschine ist eine endliche durchnummerierte Folge von Befehlen , wobei es für die einzelnen Befehle die folgenden Möglichkeiten gibt.

  1. (erhöhe den Inhalt des Registers um , d.h. um einen Strich).
  2. (reduziere den Inhalt des Registers um , d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
  3. (wenn das -te Register leer ist, so gehe zum Befehl , andernfalls zum nächsten Befehl).
  4. Drucke (drucke den Inhalt des ersten Registers).
  5. Halte an.

Dabei muss für alle in einer Programmzeile adressierten Register und für alle adressierten Befehlszeilen gelten. Die letzte Befehlszeile ist ein Haltebefehl und sonst gibt es keinen Haltebefehl.


Frage:

Die Befehle für eine Registermaschine.


Antwort:

Die Befehle für eine Registermaschine sind (dabei bezeichnen Register und Befehlszeilen).

  1. (erhöhe den Inhalt des Registers um , d.h. um einen Strich).
  2. (reduziere den Inhalt des Registers um , d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
  3. (wenn das -te Register leer ist, so gehe zum Befehl , andernfalls zum nächsten Befehl).
  4. Drucke (drucke den Inhalt des ersten Registers).
  5. Halte an.





Register-berechenbar

Registermaschine/Berechenbare Funktion/Mehrstellig/Definition


Eine -stellige Funktion

heißt berechenbar (oder Register-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.


Frage:

Eine -berechenbare Funktion


Antwort:

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.





Register-entscheidbar

Registermaschine/Teilmenge der natürlichen Zahlen/Entscheidbarkeit/Definition


Es sei eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge entscheidbar (oder Register-entscheidbar) ist, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

gilt.


Frage:

Die Register-Entscheidbarkeit einer Teilmenge .


Antwort:

Die Teilmenge heißt Register-entscheidbar, wenn es ein Programm für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz

gilt.





Register-aufzählbar

Registermaschine/Teilmenge der natürlichen Zahlen/Aufzählbarkeit/Definition


Es sei eine Teilmenge der natürlichen Zahlen. Man sagt, dass diese Menge aufzählbar (oder Register-aufzählbar) ist, wenn es ein Programm für eine Registermaschine gibt, die bei Eingabe von nach und nach genau die Zahlen aus ausdruckt (dabei dürfen Zahlen aus auch mehrfach ausgedruckt werden).


Frage:

Die -Aufzählbarkeit einer Teilmenge .


Antwort:

Man sagt, dass -aufzählbar ist, wenn es ein Programm für eine Registermaschine gibt, die bei Eingabe von nach und nach genau die Zahlen aus ausdruckt.





Arithmetisch repräsentierbare Abbildung

Arithmetisch repräsentierbar/N/Abbildung/Definition


Eine 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.


Frage:

Die Arithmetische Repräsentierbarkeit einer Abbildung


Antwort:

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.





Arithmetisch repräsentierbare Relation

Arithmetisch repräsentierbar/N/Relation/Definition


Eine Relation 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.


Frage:

Eine arithmetisch repräsentierbare Relation .


Antwort:

Die Relation 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.





Arithmetische Ausdrücke für Befehle

Registermaschine/Einzelbefehle/Arithmetische Repräsentierung/Definition


Den Programmzeilen eines Registerprogramms mit Registern werden die folgenden arithmetischen Ausdrücke in den freien Variablen zugeordnet.

  1. Bei setzt man
  2. Bei setzt man
  3. Bei setzt man
  4. Bei setzt man


Frage:

Registermaschine/Einzelbefehle/Arithmetische Repräsentierung/Definition/Begriff

Antwort:

Registermaschine/Einzelbefehle/Arithmetische Repräsentierung/Definition/Begriff/Inhalt





-Funktion

Berechenbarkeit/Beta-Funktion/Definition


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 .


Frage:

Die -Funktion .


Antwort:

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 .





Theorie (Sprache erster Stufe)

Theorie/Erster Stufe/Ableitbar/Definition


Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Teilmenge heißt Theorie, wenn abgeschlossen unter der Ableitungsbeziehung ist, d.h. wenn aus für bereits folgt.


Frage:

Theorie/Erster Stufe/Ableitbar/Definition/Begriff

Antwort:

Theorie/Erster Stufe/Ableitbar/Definition/Begriff/Inhalt





Widersprüchliche Theorie

Theorie/Erster Stufe/Ableitbar/Widersprüchlich/Definition


Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt widersprüchlich, wenn es einen Satz mit und gibt.


Frage:

Theorie/Erster Stufe/Ableitbar/Widersprüchlich/Definition/Begriff

Antwort:

Theorie/Erster Stufe/Ableitbar/Widersprüchlich/Definition/Begriff/Inhalt





Vollständige Theorie

Theorie/Erster Stufe/Ableitbar/Vollständig/Definition


Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt vollständig, wenn für jeden Satz gilt oder .


Frage:

Eine vollständige Theorie .


Antwort:

Die Theorie heißt vollständig, wenn für jeden Satz gilt oder .





Endlich axiomatisierbar

Theorie/Erster Stufe/Ableitbar/Endlich axiomatisierbar/Definition


Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt endlich axiomatisierbar, wenn es endlich viele Sätze mit gibt.


Frage:

Die endliche Axiomatisierbarkeit einer Theorie .


Antwort:

Die endliche Axiomatisierbarkeit von liegt vor, wenn es endlich viele Sätze mit gibt.





Aufzählbar axiomatisierbar

Theorie/Erster Stufe/Ableitbar/Aufzählbar axiomatisierbar/Definition


Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt aufzählbar axiomatisierbar, wenn es eine -aufzählbare Satzmenge mit gibt.


Frage:

Die aufzählbare Axiomatisierbarkeit einer Theorie zu einem Symbolalphabet .


Antwort:

Eine Theorie heißt aufzählbar axiomatisierbar, wenn es eine -aufzählbare Satzmenge mit gibt.





Repräsentierbare Relation (in Ausdrucksmenge)

Arithmetik/Satzmenge/Relation/Repräsentierung (stark)/Definition


Es sei eine Menge von arithmetischen Ausdrücken. Eine Relation heißt repräsentierbar in , wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die beiden Eigenschaften

  1. Wenn , so ist ,
  2. Wenn , so ist ,

gelten.


Frage:

Arithmetik/Satzmenge/Relation/Repräsentierung (stark)/Definition/Begriff

Antwort:

Arithmetik/Satzmenge/Relation/Repräsentierung (stark)/Definition/Begriff/Inhalt





Repräsentierbare Funktion (in Ausdrucksmenge)

Arithmetik/Satzmenge/Funktion/Repräsentierung (stark)/Definition


Es sei eine Menge von arithmetischen Ausdrücken. Eine Funktion

heißt repräsentierbar in , wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die folgenden Eigenschaften

  1. Wenn , so ist ,
  2. Wenn , so ist ,
  3. ,

gelten.


Frage:

Die Repräsentierbarkeit einer Funktion