Modelltheorie

Endliche Modelltheorie

Die Endliche Modelltheorie ist ein Teilbereich der Modelltheorie, der auf die Eigenschaften logischer Sprachen (wie etwa der Prädikatenlogik) sowie auf endliche Strukturen wie etwa endliche Gruppen, Graphen und die meisten Maschinenmodelle fokussiert ist. Ein Schwerpunkt liegt dabei insbesondere in den Beziehungen zwischen logischen Sprachen und der Berechenbarkeitstheorie. Weiterhin bestehen enge Bezüge zur diskreten Mathematik, zur Komplexitätstheorie und zur Theorie der Datenbanken.

Typische Fragen in der endlichen Modelltheorie sind, zu welchen Kardinalitäten sich für ein gegebenes Axiomensystem Modelle schaffen lassen. So ist diese Frage für die Körperaxiome vollständig geklärt: Primzahlen und Primzahlpotenzen sind die alleinigen Kardinalitäten endlicher Modelle. Diese Menge natürlicher Zahlen heißt dann Spektrum der Körperaxiome.

Es ist bisher ungeklärt, ob das Komplement eines Spektrums stets wieder ein Spektrum ist: Gesucht ist also eine Axiomenmenge dergestalt, dass alle endlichen Modelle eine Kardinalität im Komplement des Spektrums besitzen. Diese Frage hängt auch mit dem P-NP-Problem aus der Komplexitätstheorie zusammen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Modelltheorie aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung