Darstellung einer σσ\sigma - Struktur durch eine Signatur-σσ\sigma in der Mathematischen Logik.

In der mathematischen Logik habe ich eine Frage dazu, wie eine Signatur- σ bezieht sich auf ein entsprechendes σ Struktur, die die Signatur interpretiert- σ

Im Buch „Mathematical Logic“ von Chiswell und Hodges führen sie auf Seite 11 des Kapitels „Quantifer Free Logic“ eine Sprache LR (Sprache der Beziehungen) ein, die eine wie folgt definierte Signatur hat:

[Unterschrift (Erstbestellung)- σ ]: Eine Signatur erster Ordnung ist ein 4-Tupel ( C Ö , F u , R e , R ) Wo:

(1) C Ö ist eine Menge (möglicherweise leer) von Symbolen, die als konstante Symbole bezeichnet werden ;

(2) F u ist eine Menge (möglicherweise leer) von Symbolen, die Funktionssymbole genannt werden ;

(3) R e ist eine Menge (möglicherweise leer) von Symbolen, die als Beziehungssymbole bezeichnet werden ;

(4) C Ö , F u , R e sind paarweise disjunkt;

(5) Die Funktion R nimmt jedes Symbol S In F u ∪ R e zu einer positiven ganzen Zahl R ( S ) genannt den Rang (oder *arity) von S . Wir sagen, ein Symbol ist N − A R j wenn es Arität hat N .

Jetzt natürlich in Verbindung mit dieser Signatur- σ , wenn wir eine Struktur bereitstellen- σ , können wir dann die Symbole der Signatur interpretieren σ .

Aus Definition 5.5.2 (a) auf Seite 129 von Kapitel fünf wird festgelegt, dass jeder σ -Struktur A besteht aus einer Domäne, die eine nicht leere Menge ist. Die Elemente einer solchen Domäne sind die Elemente von A .

Sollte das nicht bedeuten, welche Symbole wir auch immer in unserem verwenden σ Signatur, die Elemente im Bereich von A sollte mit den Symbolen der dargestellt werden σ Unterschrift? Im folgenden Beispiel bin ich jedoch verwirrt, wie diese Regel eingehalten wird.

Der σ D ich A G R A P H Struktur Bild

Im Beispiel im Bild heißt es, dass die Signatur σ D ich G R A P H hat nur ein Symbol: die binäre Relation E ( X , j ) .

Wenn dies der Fall ist, wie können Sie die Elemente im Bereich der Struktur darstellen? σ (Der Satz { 1 , 2 , 3 , 4 , 5 } ) mit der Signatur σ D ich G R A P H ? Da die Elemente der Menge keine entsprechenden Ausdrücke in der Signatur haben σ D ich G R A P H Da es keine konstanten Symbole für die Elemente in A gibt , wie funktioniert das?

Zuerst dachte ich vielleicht, dass die binäre Beziehung E ( X , j ) stellte alle Kanten des Digraphen dar, da es keine Sorge um die notwendige Darstellung der Scheitelpunkte für dieses Beispiel gibt. Aber selbst wenn dies der Fall ist, wie kann die Signatur σ D ich G R A P H stellen die geordneten Paarelemente von dar E ( X , j ) wenn die x- und y-Variablen Elemente in der Domäne ersetzen { 1 , 2 , 3 , 4 , 5 } und wir haben keine entsprechenden Symbole in unserer Signatur σ D ich G R A P H ?

Ich würde mich sehr über Hilfe freuen danke!

Antworten (1)

Jeden σ -Struktur A besteht aus einer Domäne, die eine nicht leere Menge ist. Die Elemente einer solchen Domäne sind die Elemente von A .

Sollte das nicht bedeuten, welche Symbole wir auch immer in unserem verwenden σ Signatur, die Elemente im Bereich von A sollte mit den Symbolen der dargestellt werden σ Unterschrift?

Nicht genau; die symbole der signatur sind über die elemente von zu interpretieren A :

ein konstantes Zeichen C ∈ C Ö wird interpretiert, indem man ihm ein Element zuweist C A ∈ A als seine Bezeichnung (ein konstantes Symbol ist wie ein "Name")

ein Beziehungssymbol _ R ∈ R e mit arität N = R ( R ) wird als Menge interpretiert R A ⊆ A N , dh eine Teilmenge des kartesischen Produkts A × … × A ( N mal)

usw.

Bezüglich der σ D ich A G R A P H Beispiel :

Vermuten G ist ein gerichteter Graph . Die Elemente des Definitionsbereichs von G heißen seine Ecken . Die binäre Beziehung E G heißt Kantenrelation von G , und die geordneten Paare in dieser Beziehung heißen Kanten von G .

Somit sind die Elemente der Domäne von G sind die Eckpunkte und das (binäre) Beziehungssymbol E (das einzige Symbol der Signatur) wird durchinterpretiert E G ⊆ G × G , dh als Satz von Paaren .

Zwei Eckpunkte A , B ∈ G wird "bezogen" durch E iff ( A , B ) ∈ E G , dh genau dann, wenn sie durch eine Kante verbunden sind.

Das Beziehungssymbol sein E Das einzige Symbol der Signatur haben wir:

C Ö = F u = ∅

R e = { E }

Und :

R ( E ) = 2

Weil E ist ein binäres Beziehungssymbol.

Danke schön! Allerdings habe ich noch ein Negging-Problem. Wie Sie sagten, ein konstantes Symbol C ist wie ein „Name“, der sich auf ein Objekt bezieht, das ein Element im Bereich der Menge ist A in diesem Fall. Wie ist es dann möglich, eine Kantenbeziehung von auszudrücken? G unter Verwendung der Signatur σ D ich G R A P H , wenn die binäre Beziehung E ( X , j ) hat Unterbegriffe T 1 Und T 2 welche die Elemente der Domäne sind A aber haben keine konstanten Symbole oder "Namen", um sie in der Signatur darzustellen σ D ich G R A P H ?
Müssen wir nicht eine Menge konstanter Symbole einführen, wie z 1 ¯ für das Element ' 1 ' im Satz A , 2 ¯ für das Element ' 2 ' usw., damit wir dann die Kantenbeziehungen über die Signatur darstellen können σ D ich G R A P H richtig als E ( 1 ¯ , 2 ¯ ) Wie können wir sagen, dass Kantenbeziehungen effektiv in der Signatur dargestellt werden können, indem nur diese eine binäre Relation verwendet wird, wenn diese binäre Relation Unterbegriffe enthält, die keinen entsprechenden „Namen“ in der Signatur haben?
@GavanC - 1 , 2 , 3 , 4 sind keine Terme , dh Konstanten der Sprache; sie sind die „Namen“ der Eckpunkte, die in der Metasprache verwendet werden. Wenn Sie sie in der Sprache benennen wollen, wie Sie sagen, müssen Sie konstante Symbole hinzufügen (siehe Ex.5.5.2 Seite 132).
@GavanC - ein Beispiel für eine "Eigenschaft" eines Graphen, die Sie auch ohne Konstanten ausdrücken können : E ( X , j ) → E ( j , X ) .
Darstellung einer σσ\sigma - Struktur durch eine Signatur-σσ\sigma in der Mathematischen Logik.
AntwortenHierDatenschutz-Bestimmungen1y, 0v