Struktur (Modelltheorie)

In der Modelltheorie sind Strukturen mathematische Objekte. Sie geben einer logischen Sprache eine semantische Bedeutung. Mit diesem Begriff kann die Semantik von Logiken wie der Prädikatenlogik definiert werden.

Definition

Eine Signatur $\sigma=\{R_1,\ldots,R_k,c_1,\ldots,c_l\}$ ist eine endliche Menge von Relationssymbolen $R_1,\ldots,R_k$ , jedes mit einer gegebenen Stelligkeit $ar(R_i)\in\mathbb{N}$ , $1\leq i\leq k$ und Konstantensymbolen $c_1,\ldots,c_l$ .

Ein Tupel $\mathcal{A}=(A,R_1^{\mathcal{A}},\ldots,R_k^{\mathcal{A}},c_1^{\mathcal{A}},\ldots,c_l^{\mathcal{A}})$ ist eine $σ$ -Struktur, falls gilt:

A ist eine Menge,
$R^{\mathcal{A}}\subseteq A^{ar(R)}$ für jedes Relationssymbol $R\in\sigma$
und $c^{\mathcal{A}}\in A$ für jedes Konstantensymbol $c\in\sigma$

$A$ heißt auch Universum oder Trägermenge von $\mathcal{A}$ . Ist $A$ endlich, so heißt $\mathcal{A}$ endliche Struktur.

Häufig werden neben Relationen und Konstanten auch Funktionen in die Definition von Strukturen aufgenommen.

Beispiel

Die Signatur ${E}$ , wobei $E$ ein zweistelliges Relationssymbol ist, wird häufig die Signatur der Graphen genannt. Die ${E}$ -Struktur $\mathcal{G}=(V,E^{\mathcal{G}})$ mit Trägermenge $V = {A, B, C, D}$ und $E^{\mathcal{G}}=\{(A,B),(B,C),(C,D),(D,A)\}$ bezeichnet folgenden gerichteten Graphen: