Sur les preuves de la complexité descriptive

Question

Dans la complexité descriptive, nous avons des théorèmes qui ressemblent à $ mathrm {eso} = mathrm {np} $ ou "sur des structures ordonnées linéairement, $ fo (lfp) = p $", mais je ne comprends pas vraiment les preuves de ceux.

Pour ce dernier, l'égalité intuitive signifie vraiment que l'instruction "$ mathcal a modèles varphi $" peut être vérifiée pour être vraie sur une structure ordonnée linéairement $ mathcal a $ in Time $ n ^ k $ iff $ varphi $ est exprimant dans une logique de fix. L'inclusion de droite à gauche lit alors $ forall m ; mathrm {polytime ; tm}, existant varphi in mathrm {fo (lfp)} quad Left [ mathcal a modèles varphi leftrightarrow m ( mathcal a) = 1 droite] $.

La preuve qui m'a été enseignée en classe pour l'inclusion du droite à gauche comme suit: D'après une machine Turing m (avec un ensemble d'états $ s $), nous construisons une formule sur la langue $ {t_0, t_1 } Cup {h_i: i in s } $, où toutes les relations sont d'Arity $ 2k $. Cette formule indique que la structure sur laquelle il est évalué est un calcul correct de $ M $ qui se termine par un état acceptant. Comment cela prouve-t-il le théorème? Bien sûr, il existe une bijection entre l'acceptation de calculs de $ m $ et les structures $ mathcal a $ st $ m ( mathcal a) = 1 $, mais l'énoncé du théorème ne mentionne pas cette bijection. À mon avis, la formule $ varphi $ que nous créons devrait vraiment vérifier les propriétés de $ mathcal a $, et non les propriétés du calcul de $ m $ sur $ mathcal a $ ... Où est mon erreur? Suis-je en train de réfléchir à cela?