Definierbarer Satz - Definable set

In der mathematischen Logik ist eine definierbare Menge eine n- fache Beziehung im Bereich einer Struktur, deren Elemente genau diejenigen Elemente sind, die eine Formel in der Sprache erster Ordnung dieser Struktur erfüllen . Eine Menge kann mit oder ohne Parameter definiert werden. Dies sind Elemente der Domäne, auf die in der Formel verwiesen werden kann, die die Beziehung definiert.

Definition

Sei eine Sprache erster Ordnung, eine Struktur mit Domäne , eine feste Teilmenge von und eine natürliche Zahl . Dann:

  • Eine Menge ist mit Parametern genau dann definierbar, wenn es eine Formel und Elemente gibt, so dass für alle ,
dann und nur dann, wenn
Die Klammernotation hier gibt die semantische Auswertung der freien Variablen in der Formel an.
  • Eine Menge kann ohne Parameter definiert werden, wenn sie mit Parametern aus der leeren Menge definiert werden kann (dh ohne Parameter in der Definitionsformel).
  • Eine Funktion ist in (mit Parametern) definierbar, wenn ihr Graph (mit diesen Parametern) in definierbar ist .
  • Ein Element ist in (mit Parametern) definierbar, wenn die Singleton-Menge in (mit diesen Parametern) definierbar ist.

Beispiele

Die natürlichen Zahlen mit nur der Ordnungsrelation

Sei die Struktur, die aus den natürlichen Zahlen mit der üblichen Reihenfolge besteht. Dann ist jede natürliche Zahl ohne Parameter definierbar . Die Zahl wird durch die Formel definiert, die besagt, dass es keine Elemente kleiner als x gibt : und eine natürliche Zahl wird durch die Formel definiert, die besagt, dass es genau Elemente gibt, die kleiner als x sind :

Im Gegensatz dazu kann man keine bestimmte Ganzzahl ohne Parameter in der Struktur definieren, die aus den Ganzzahlen mit der üblichen Reihenfolge besteht (siehe den Abschnitt über Automorphismen unten).

Die natürlichen Zahlen mit ihren arithmetischen Operationen

Sei die Struktur erster Ordnung, die aus den natürlichen Zahlen und ihren üblichen arithmetischen Operationen und Ordnungsrelationen besteht. Die in dieser Struktur definierbaren Mengen werden als arithmetische Mengen bezeichnet und in die arithmetische Hierarchie eingeteilt . Wenn die Struktur in der Logik zweiter Ordnung anstelle der Logik erster Ordnung betrachtet wird, werden die definierbaren Mengen natürlicher Zahlen in der resultierenden Struktur in der analytischen Hierarchie klassifiziert . Diese Hierarchien zeigen viele Beziehungen zwischen der Definierbarkeit in dieser Struktur und der Berechenbarkeitstheorie und sind auch für die deskriptive Mengenlehre von Interesse .

Das Feld der reellen Zahlen

Sei die Struktur, die aus dem Feld der reellen Zahlen besteht . Obwohl die übliche Ordnungsbeziehung nicht direkt in der Struktur enthalten ist, gibt es eine Formel, die die Menge der nichtnegativen Reals definiert, da dies die einzigen Reals sind, die Quadratwurzeln besitzen:

Somit ist jede genau dann nicht negativ, wenn . In Verbindung mit einer Formel, die die additive Umkehrung einer reellen Zahl in definiert , kann man die übliche Reihenfolge in definieren : für , genau dann festlegen, wenn dies nicht negativ ist. Die vergrößerte Struktur s wird als definitive Erweiterung der ursprünglichen Struktur bezeichnet. Es hat die gleiche Ausdruckskraft wie die ursprüngliche Struktur, in dem Sinne, dass eine Menge über die vergrößerte Struktur aus einer Reihe von Parametern genau dann definierbar ist, wenn sie über die ursprüngliche Struktur aus derselben Menge von Parametern definierbar ist.

Die Theorie von hat Quantifizierereliminierung . Somit sind die definierbaren Mengen boolesche Kombinationen von Lösungen für Polynomgleichungen und -ungleichungen; Diese werden als semi-algebraische Mengen bezeichnet . Die Verallgemeinerung dieser Eigenschaft der reellen Linie führt zur Untersuchung der o-Minimalität .

Invarianz unter Automorphismen

Ein wichtiges Ergebnis bei definierbaren Mengen ist, dass sie unter Automorphismen erhalten bleiben .

Lassen Sie sein , eine -Struktur mit Domain , und definierbar aus mit Parametern . Sei ein Automorphismus, auf dem die Identität liegt . Dann für alle ,
dann und nur dann, wenn

Dieses Ergebnis kann manchmal verwendet werden, um die definierbaren Teilmengen einer bestimmten Struktur zu klassifizieren. Im obigen Fall ist beispielsweise jede Übersetzung von ein Automorphismus, der den leeren Parametersatz beibehält, und daher ist es unmöglich, eine bestimmte Ganzzahl in dieser Struktur ohne Parameter in zu definieren . Da zwei beliebige Ganzzahlen durch eine Übersetzung und ihre Umkehrung zueinander übertragen werden, sind die einzigen Mengen von Ganzzahlen, die ohne Parameter definiert werden können, die leere Menge und sich selbst. Im Gegensatz dazu gibt es unendlich viele definierbare Mengen von Paaren (oder tatsächlich n- Tupeln für jedes feste n > 1) von Elementen , da jeder Automorphismus (Übersetzung) den "Abstand" zwischen zwei Elementen beibehält .

Zusätzliche Ergebnisse

Der Tarski-Vaught-Test wird verwendet, um die elementaren Unterstrukturen einer bestimmten Struktur zu charakterisieren .

Verweise

  • Hinman, Peter. Grundlagen der mathematischen Logik , AK Peters, 2005.
  • Marker, David. Modelltheorie: Eine Einführung , Springer, 2002.
  • Rudin, Walter. Prinzipien der mathematischen Analyse , 3 .. ed. McGraw-Hill, 1976.
  • Slaman, Theodore A. und W. Hugh Woodin. Mathematische Logik: Der Berkeley Undergraduate Course . Frühling 2006.