Complexité des formules
Bonjour à tous,
Je m'embrouille dans la complexité des formules.
Je parle ici des formules ensemblistes, mais je suppose que c'est la même chose pour l'arithmétique.
J'ai compris ce qu'étaient les formules $\Sigma^{0}_{n}$, souvent abrégées en $\Sigma_{n}$.
Mais que sont exactement les formules $\Sigma^{1}_{n}$ ?
Et, plus généralement, les formules $\Sigma^{m}_{n}$ ?
Merci d'avance
Martial
Je m'embrouille dans la complexité des formules.
Je parle ici des formules ensemblistes, mais je suppose que c'est la même chose pour l'arithmétique.
J'ai compris ce qu'étaient les formules $\Sigma^{0}_{n}$, souvent abrégées en $\Sigma_{n}$.
Mais que sont exactement les formules $\Sigma^{1}_{n}$ ?
Et, plus généralement, les formules $\Sigma^{m}_{n}$ ?
Merci d'avance
Martial
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Dans le cas qui t'intéresse (les formules), c'est assez proche de l'arithmétique et donc de la complexité computationnelle, mais ce que tu obtiens ne peut pas forcément être décrit par des formules (en tout cas du premier ordre : tu vois bien que ces dernières apparaissent forcément à un étage des $\Sigma^0$, donc introduire un $\Sigma^k$ pour un truc qui peut être décrit par $\Sigma^0$ ce serait triste)
0 --> quantification sur des entiers
1 --> quantification sur des réels
Au delà, il me semble que les auteurs ont intérêt à rappeler le sens qu'ils donnent, car ça me parait peu médiatisé et fixé (P(IR), P(P(IR)), etc)
@Maxtimax : Ce qui m'a mis la puce à l'oreille c'est le truc qu'on appelle le lemme d'absoluité de Shoenfield.
De mémoire : si $M$ est modèle de ZFC et si une certaine formule $\Sigma^{1}_{2}$ (à moins que ça soit $\Pi^{1}_{2}$) est vraie dans $M[G]$, alors elle était déjà vraie dans $M$.
J'en déduis que soit je suis devenu plus intelligent, soit j'ai été un mauvais élève : j'ai dormi pendant les cours, j'ai omis de faire mes exercices, ou/et mon cerveau est trop petit, lol.
@Tous deux : Plus sérieusement, et pour info, dans son livre, Page 485, Patrick définit une formule $\Sigma^{m}_{n}$ par récurrence, comme étant une formule de la logique ensembliste du (m+1)ième ordre qui est formée de n blocs alternants de quantifications d'ordre m+1 commençant par il existe, puis d'une formule du mième ordre (formule du langage usuel sans quantificateur dans le cas m=0) où les variables d'ordre m+1 peuvent apparaître comme paramètres.
Je ne suis pas sûr de comprendre parfaitement cette définition. Un peu d'aide de votre part serait la bienvenue...
Sache que de toute facon la fin est écrasée par le début. Par exemple une formule sigma haut 2 bas 5 peut s'écrire de manière équivalente par une alternance de 5 quantification sur les parties de IR et ensuite plus que des forall pour les "petites" variables.
Mais je te précise en latex tout ça demain.