Grundlegendes zur Logik der kleinsten Fixpunkte

Um ein Papier besser zu verstehen, versuche ich, ein kurzes Verständnis der Logik der am wenigsten festen Punkte zu erlangen. Es gibt einige Punkte, an denen ich festsitze.

Wenn ist ein Graph und$G = (V,E)$

$$\Phi(P) = \{(a,b) \mid G \models E(a,b) \lor P(a,b) \lor \exists z (E(a,z) \land P(z,b)) \}$$

ist ein Bediener auf der binären Relation . Ich verstehe nicht, warum der kleinste Fixpunkt P ∗ von P der transitive Abschluss von E ist . Das Beispiel stammt aus der endlichen Modelltheorie und ihren Anwendungen (S. 60).$P$$P^*$$P$$E$

Wenn die Logik erste Ordnung erstreckt , um mit dem am wenigsten festen Zeiger Operator verstehe ich nicht , warum die Beziehung Symbol sein muss positiv in der Formel. Positiv bedeutet, dass jedes Auftreten von S i in der Formel innerhalb einer geraden Anzahl von Negationssymbolen liegt.$S_i$$S_i$

Hat jemand eine Idee, was gut zu lesen ist, um die am wenigsten feste Zeigerlogik und ihre Syntax und Semantik intuitiv zu verstehen?

Wenn Sie Probleme mit dem Konzept des kleinsten Fixpunkts haben, würde ich empfehlen, einige Zeit damit zu verbringen, sich mit der allgemeineren Ordnungstheorie vertraut zu machen.

Davey und Priestley, Einführung in Gitter und Ordnung ist ein gutes Intro.

Um zu sehen, warum der transitive Abschluss der am wenigsten festgelegte Punkt ist, stellen Sie sich vor, Sie bauen den Abschluss aus einer leeren Menge auf und wenden die logische Formel Schritt für Schritt an. Der am wenigsten festgelegte Punkt kommt an, wenn Sie mit der Formel keine neuen Kanten hinzufügen können.

Die Anforderung, dass die Formel positiv ist, stellt sicher, dass der Prozess monoton ist, dh dass er bei jedem Schritt wächst. Wenn Sie eine negative Subformel hätten, könnten Sie den Fall haben, dass bei einigen Schritten der Satz von Kanten abnimmt, und dies könnte zu einer nicht terminierenden Schwingung nach oben und unten führen, anstatt zu einer Konvergenz zum LFP.

$S$$P$

$$P(X) = \lnot X$$

$P$

1. $\mu P$$P(\mu P) = \mu P$$\mu X.\;P(X)$

2. $L$$f : L \to L$$f$$f$$f$

3. $X$

Ich finde, dass es keinen Ersatz dafür gibt, diese Beweise für sich selbst zu machen, um die Intuition wirklich zu verinnerlichen.

Dies ist ein sehr alter Beitrag, daher haben Sie die Antwort möglicherweise bereits wie gewünscht gefunden. Seit ich in den letzten Monaten FO (LFP) studiere. Ich habe ein gewisses Verständnis für die Antworten, die Sie benötigen.

$[\sigma$$\phi(\vec{x},X)$$|\vec{x}|=ar(X)$$f_\phi$$\mathcal{P}(A^{ar(X)}) \mapsto \mathcal{P}(A^{ar(x)})$$\sigma$$\mathbb{A}$$\mathcal{P}(Z)$$f_\phi(Z) = \{\ \vec{a} \in A^{ar(X)}\ |\ \mathbb{A},\vec{a},Z \models \phi\ \}$. Wenn dieser Operator monoton ist, können wir den Fixpunkt sowohl in endlicher als auch in unendlicher Struktur leicht nach dem in den obigen Antworten erwähnten Fixpunktsatz des Knaster Tarski erfassen. Das Problem besteht jedoch darin, zu testen, ob die Formel, die wie oben aus dem Formular geschrieben wurde, einen monotonen Operator codiert oder nicht, unentscheidbar ist, sodass wir das nächstbeste erhalten müssen. Die Positivität in der freien Variablen zweiter Ordnung stellt sicher, dass die Monotonie-Anforderung erfüllt ist. Dies ist eine standardmäßige strukturelle Induktion, um dieses Phänomen zu beweisen. Die Frage ist, ist es genug?

Darauf habe ich noch keine feste Antwort, da ich noch lese. Ich kann auf Papiere an dieser Front verweisen. Zumindest die eine, die die Ideen erklärt, die ich hier erwähnt habe, stammt aus der Zeitung Monotone vs Positive - Ajtai, Gurevich. Es wird auch ein anderes Papier erwähnt. Festpunkterweiterungen der Logik erster Ordnung von Gurevich und Shelah, das besagt, dass der Festpunktoperator bei Anwendung auf die positive Formel im Vergleich zur Anwendung über beliebige monotone Formeln nicht an Ausdruckskraft verliert.