Definition des Rangs von Begriffen in der Sprache erster Ordnung

Ich lese den Kurs in mathematischer Logik von SM Srivastava. Der Autor definiert Begriffe und ihren Rang einer Sprache erster Ordnung L folgendermaßen:

Die Menge aller Terme einer Sprache L ist die kleinste Menge T von Ausdrücken von L die alle Variablen und Konstantensymbole enthält und unter der folgenden Operation geschlossen wird: when T 1 , … , T N ∈ T , F J T 1 … T N ∈ T , Wo F J ist beliebig N -äres Funktionssymbol von L . Äquivalent können alle Terme einer Sprache wie folgt induktiv definiert werden: Variable und konstante Symbole sind Rangterme 0 ; Wenn T 1 , … , T N sind Rangbegriffe ≤ k , und wenn F J ist ein N -äres Funktionssymbol, dann F J T 1 … T N ist höchstens ein Rangbegriff k + 1 . Also der Rang eines Begriffs T ist die kleinste natürliche Zahl k so dass T ist von Rang ≤ k .

Hier sind meine Fragen:

  1. Im induktiven Schritt der Rangdefinition sagt der Autor if F J ist ein N -äres Funktionssymbol, dann F J T 1 … T N ist höchstens ein Rangbegriff k + 1 und weist nicht ausdrücklich eine Zahl als Rang zu. Ist das gültig? Zum Beispiel, wenn C ist ein konstantes Symbol und F ist ein unäres Funktionssymbol in einer Sprache erster Ordnung L dann Rang des Begriffs C Ist 0 per Definition. Wie erlaubt mir diese Definition, den Rang des Begriffs zu bestimmen? F C oder auch F F C ?
  2. Ich sehe nicht, wie die Begriffe durch den Begriff des Ranges äquivalent definiert werden können, wenn sich die Definition selbst auf den Begriff "Begriff" selbst bezieht. Übersehe ich hier etwas?

Antworten (1)

Srivastava definiert den Rang eines Begriffs nicht durch Induktion. Stattdessen definiert er den Satz von Rangbegriffen ≤ k durch Induktion an k . Dann ist (implizit) ein Begriff ein Rangbegriff ≤ k für eine natürliche Zahl k . Schließlich definiert er den Rang eines Begriffs T die am wenigsten natürliche Zahl sein, so dass T Rang hat ≤ k .

Hier ist eine etwas präzisere Art, Srivastavas Definition auszudrücken:

Wir definieren die Menge S k höchstens der Rangordnung k durch Induktion an k . S 0 ist die Menge aller Variablen und konstanten Symbole. Gegeben S k , wir definieren

S k + 1 = S k ∪ { F T 1 … T N ∣ F  ist ein  N -äres Funktionssymbol und  T 1 , … , T N ∈ S k } .
Die Menge aller Terme ist T = ⋃ k ∈ N S k . Gegeben ein Begriff T ∈ T , der Rang eines T ist die kleinste natürliche Zahl k so dass T ∈ S k .

Beachten Sie, dass ich ausdrücklich darauf hingewiesen habe S k + 1 enthält S k (das heißt, dass höchstens ein Rangbegriff k hat auch höchstens Rang k + 1 ). Srivastava lässt dies in seiner Definition implizit.

Betrachten Sie zum Beispiel den Begriff F C (Wo F ist ein 1 -äres Funktionssymbol und C ist ein konstantes Symbol). C ∈ S 0 , So F C ∈ S 1 . Andererseits, F C ∉ S 0 (da es sich nicht um ein variables oder konstantes Symbol handelt). Also der Rang F C Ist 1 . Ebenso der Rang eines F F C Ist 2 (Aber für dieses hier müssen Sie eine Sekunde darüber nachdenken, warum F F C ∉ S 1 ).

Ist das Rangkonzept, wie es hier definiert wird, in irgendeiner Weise mit vielsortierten Alphabeten verwandt?
@Jason Was ist ein vielsortiertes Alphabet?
Ich hätte viele sortierte Unterschriften entschuldigen sollen. Es ist eine Möglichkeit, zu "sortieren", welche Symbole auf welche Symbole angewendet werden können, indem eine Reihe von Sortierungen und eine Funktion jedes Symbol einer Sortierung zuordnet.
@Jason Nun, Sie müssen wissen, dass Sie bei einer vielsortierten Signatur den Satz von Begriffen in dieser Signatur erstellen können. Und die gleiche Definition von Rang kann auf diese Begriffe angewendet werden. Ich bin mir nicht sicher, was es sonst noch zu sagen gibt.
Das macht so viel Sinn! Ich füge diese Notiz am Rand hinzu.
Es ist offensichtlich, dass alle Ausdrücke in S 1 ist entweder eine Konstante oder eine Variable oder von der Form F z 1 z 2 … z N Wo F ein n-stelliges Funktionssymbol und ist z ich sind entweder Konstanten oder Variablen. Also wenn F F C war in S 1 das würde zwingen F C angesagt sein S 0 was natürlich auch nicht der Fall sein kann! Ist diese Argumentation richtig?
@ashK Ja, das ist richtig.
Definition des Rangs von Begriffen in der Sprache erster Ordnung
AntwortenHierDatenschutz-Bestimmungen1y, 0v