Comprendre la logique des points les moins fixes

Pour mieux comprendre un article, j'essaie d'obtenir une brève compréhension de la logique des points les moins fixes. Il y a quelques points où je suis coincé.

Si est un graphique et$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)) \}$$

est un opérateur sur la relation binaire . Je ne comprends pas pourquoi le point fixe moins de est la fermeture transitive de . L'exemple est tiré de la théorie des modèles finis et de ses applications (p. 60).P ∗ P $P$$P^*$$P$$E$

Lors de l'extension de la logique du premier ordre avec l'opérateur de pointeur le moins fixe, je ne comprends pas pourquoi le symbole de relation doit être positif dans la formule. Positif signifie que chaque occurrence de dans la formule se trouve dans un nombre pair de symboles de négation.$S_i$$S_i$

Quelqu'un a-t-il une idée de ce qui est bon à lire pour une compréhension intuitive de la logique du pointeur le moins fixe, de sa syntaxe et de sa sémantique?

Si vous rencontrez des problèmes avec le concept de point le moins fixe, je recommanderais de passer un peu de temps à acquérir une formation en théorie de l'ordre plus général.

Davey et Priestley, Introduction to Lattices and Order est une bonne introduction.

Pour voir pourquoi la fermeture transitive est le point le moins fixe, imaginez construire la fermeture à partir d'un ensemble vide, en appliquant la formule logique étape par étape. Le point le moins fixe arrive lorsque vous ne pouvez pas ajouter de nouvelles arêtes à l'aide de la formule.

L'exigence que la formule soit positive garantit que le processus est monotone, c'est-à-dire qu'il se développe à chaque étape. Si vous aviez une sous-formule négative, vous pourriez avoir le cas où, sur certaines étapes, l'ensemble des bords diminuerait, ce qui pourrait conduire à une oscillation sans fin de haut en bas, plutôt qu'une convergence vers la LFP.

Considérons l'algèbre booléenne formée à partir du jeu de puissance d'un ensemble fini , ordonné par inclusion d'ensemble. Maintenant, considérons l'opérateur P défini par$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$

Je trouve qu'il n'y a pas de substitut à faire ces preuves par vous-même pour vraiment intérioriser l'intuition.

il s'agit d'un très ancien message, vous avez peut-être déjà rencontré la réponse souhaitée. Depuis que j'étudie FO (LFP) depuis quelques mois. J'ai une certaine compréhension des réponses dont vous avez besoin.

$[\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\ \}$. Si cet opérateur est monotone, nous pouvons facilement capturer le point fixe à la fois dans la structure finie et infinie en suivant le théorème du point fixe du knaster tarski mentionné dans les réponses ci-dessus. Mais, le problème consiste à tester si la formule écrite hors du formulaire comme ci-dessus code pour un opérateur monotone ou non est indécidable, nous devons donc obtenir la meilleure chose suivante. La positivité dans la variable libre du second ordre garantit que l'exigence de monotonie est satisfaite, c'est une induction structurelle standard pour prouver ce phénomène. La question est, est-ce suffisant?

À cela, je n'ai pas encore de réponse solide, car je lis encore. Je peux signaler des articles sur ce front. Au moins, celle qui explique les idées que j'ai mentionnées ici est tirée du document Monotone vs Positive - Ajtai, Gurevich. Il mentionne également un autre document Extensions de points fixes de la logique du premier ordre de Gurevich et Shelah qui déclare que l'opérateur de point fixe lorsqu'il est appliqué à la formule positive ne perd pas sa puissance expressive par rapport à l'application effectuée sur des formules monotones arbitraires.