Hyperdoctrines et logique monadique du second ordre

Cette question est essentiellement la question que j'ai posée sur Mathoverflow.

La logique monadique du second ordre (MSO) est une logique du deuxième ordre avec quantification sur des prédicats unaires. Autrement dit, la quantification sur des ensembles. Il existe plusieurs logiques MSO qui sont fondamentales pour les structures étudiées en informatique.

Question 1. Existe-t-il une sémantique catégorique pour les logiques monadiques du second ordre?

Question 2. Les traitements de la logique catégorielle parlent souvent de «logique intuitionniste d'ordre supérieur». Ai-je raison de supposer qu'elles se réfèrent à des fonctions d'ordre supérieur, plutôt qu'à une quantification sur des prédicats de second ordre?

Question 3. (Ajouté, 8 novembre 2013, après la réponse de Neel) Ma compréhension de la quantification de premier ordre (en termes de présentation de Pitts mentionnée ci-dessous) est qu'elle est définie par rapport au retrait d'un morphisme de projection . Plus précisément, la quantification universelle est interprétée comme l'adjoint droit de et la quantification existentielle est interprétée comme l'adjoint gauche de . Ces adjonctions doivent satisfaire à certaines conditions, que j'ai parfois vues appelées conditions Beck-Chevalley et Frobenius-Reciprocity. $\pi^*$ $\pi$ $\pi^*$ $\pi^*$

Maintenant, si nous voulons quantifier sur des prédicats, je suppose que je suis dans une catégorie fermée cartésienne, l'image est presque la même, sauf que ci-dessous a une structure différente d'avant. $X$

\exists_{I, X}, \forall_{I, X} : P_{C} (I \times X) \to P_{C} (I)

$\exists_{I,X}, \forall_{I,X}: P_C(I\times X) \to P_C(I)$

Est-ce correct?

Je crois que mon blocage mental était dû au fait que je m'occupais auparavant d'hyperdoctrines de premier ordre et que je n'avais pas besoin que la catégorie soit fermée cartésienne et que je ne l'ai pas considérée plus tard.

Contexte et contexte. J'ai travaillé avec la présentation de la logique catégorique par Andy Pitts dans son article Handbook of Logic in Computer Science , mais je connais également le traitement de la théorie Tripos dans sa thèse de doctorat, ainsi que les notes d'Awodey et Bauer. J'ai commencé à étudier les catégories pour les types de Crole et le livre de Lambek et Scott, mais cela fait un moment que je n'ai pas consulté les deux derniers textes.

Pour la motivation, je m'intéresse au type de logiques MSO apparaissant dans les théorèmes ci-dessous. Je ne veux pas traiter d'une logique qui est expressivement équivalente à l'une d'entre elles. Cela signifie que je ne veux pas encoder des prédicats monadiques en termes de fonctions d'ordre supérieur et ensuite traiter avec une autre logique, mais je suis heureux d'étudier une sémantique qui inclut un tel encodage sous le capot.

(Théorème de Buechi et Elgot) Lorsque l'univers des structures est constitué de mots finis sur un alphabet fini, une langue est régulière exactement si elle est définissable dans MSO avec un prédicat interprété pour exprimer des positions consécutives.
(Théorème de Buechi) Lorsque l'univers des structures est mots sur un alphabet fini, une langue est régulière exactement si elle est définissable dans MSO avec un prédicat interprété approprié. $\omega$ $\omega$
(Théorème de Thatcher et Wright) Un ensemble d'arbres finis est reconnaissable par un automate d'arbre fini ascendant exactement s'il est définissable dans MSO avec un prédicat interprété.
WS1S est la théorie du second ordre monadique faible d'un successeur. Les formules définissent des ensembles de nombres naturels et les variables de second ordre ne peuvent être interprétées que comme des ensembles finis. WS1S peut être décidé par des automates finis en encodant des tuples de nombres naturels en mots finis.
(Théorème de Rabin) S2S est la théorie du second ordre des deux successeurs. S2S peut être décidé par les automates Rabin.

lo.logic ct.category-theory Vijay D
la source

Je ne sais pas!
Non, votre hypothèse n'est pas juste. Vous pouvez quantifier des fonctions et des prédicats d'ordre supérieur dans IHOL (en fait, les prédicats ne sont que des fonctions dans un type de propositions). La configuration ressemble un peu à ceci:

$\begin{array}{llcl} Sort & ω & ::= & ω \to ω | ω \times ω | 1 | p r o p | ι \\ Term & t & ::= & x | λ x . t | t t^{'} | (t, t) | π_{1} (t) | π_{2} (t) | () \\ | & p \Rightarrow q | ⊤ | p \land q | ⊥ | p \lor q \\ | & \forall x : ω . p | \exists x : ω . p | t =_{ω} t^{'} \\ | & f (\vec{t}) \end{array}$ $\begin{array}{llcl} \mbox{Sort} & \omega & ::= & \omega \to \omega \;\; | \;\; \omega \times \omega \;\; | \;\; 1 \;\;|\;\; \mathrm{prop} \;\;|\;\; \iota\\ \mbox{Term} & t & ::= & x \;\;|\;\; \lambda x.t \;\;|\;\; t\;t' \;\;|\;\; (t,t) \;\; | \;\; \pi_1(t) \;\;|\;\; \pi_2(t) \;\;|\;\; () \\ & & | & p \Rightarrow q \;\;|\;\; \top \;\;|\;\; p \wedge q \;\;|\;\; \bot \;\;|\;\; p \vee q \\ & & | & \forall x:\omega.p \;\;|\;\; \exists x:\omega.p \;\;|\;\; t =_\omega t' \\ & & | & f(\vec{t}) \end{array}$

Vous donnez les règles de frappe habituelles pour juger de la bonne forme d'un terme. La première ligne de termes est le calcul lambda simplement typé habituel, les deux deuxièmes lignes sont les propositions d'une logique d'ordre supérieur (typées en tant qu'éléments de ), et la troisième ligne sont les constantes que vous utilisez pour former des individus (éléments de ). $\mathrm{prop}$ $\iota$

Ensuite, l'idée est que vous souhaitez étendre la sémantique de Kripke pour la logique intuitionniste de premier ordre à la logique d'ordre supérieur, en étendant la sémantique hyperdoctrine avec une structure supplémentaire. Une hyperdoctrine de premier ordre est un foncteur entre une catégorie avec des produits (utilisée pour interpréter les termes en contexte) et une catégorie de posets (les réseaux de valeur de vérité ), remplissant certaines conditions pour que la substitution fonctionne correctement. $P : C^\mathrm{op} \to \mathrm{Poset}$ $C$

Pour vous rendre à l'IHOL, vous affirmez en outre que

$C$ est fermé cartésien (pour modéliser la capacité de quantifier sur les types de fonctions), et
$C$ a une algèbre de Heyting interne satisfaisant la propriété que pour chaque , . Vous utilisez pour modéliser , et l'isomorphisme vous indique que les termes de type correspondent vraiment aux valeurs de vérité. $H$ $\Gamma \in C$ $\mathit{Obj}(P(\Gamma)) \simeq C(\Gamma, H)$ $H$ $\mathrm{prop}$ $\mathrm{prop}$

Cette structure est presque un "topos élémentaire". Si vous avez également besoin que soit un poset de sous-projets de , alors vous y êtes. (Cela dit essentiellement que vous pouvez ajouter un principe de compréhension à votre logique.) $P(\Gamma)$ $\Gamma$

Neel Krishnaswami
la source

Hyperdoctrines et logique monadique du second ordre

Réponses: