Discuter:Hiérarchie arithmétique

Un article de Wikipédia, l'encyclopédie libre.

J'ai un problème avec la définition de Π_n (et de Σ_n, et avec la démonstration subséquente que toute formule peut se mettre sous forme prénexe: la démonstration n'est pas fausse, mais comme elle remplace par , elle ne donne pas le bon indice pour le Π_n correspondant (2 degrés de trop par quantificateurs identiques successifs), ce qui peut être gênant. Du coup, je remplace par .

Galbolle 27 septembre 2006 à 18:59 (CEST)

Il serait plus simple d'autoriser plusieurs quantificateurs successifs de même nature dans chaque alternance (plutôt que de définir des quantificateurs sur des k-uples que l'on ne définit pas a priori). Donc là l'énoncé n'est plus le même. Sinon il faut du codage. Par ailleurs cet article devrait parler d' ensemble Sigma_n ou Pi_n. Enfin en général dans les delta_0 on autorise les quantifications bornées. Je l emets en ébauche. Proz 9 novembre 2006 à 21:34 (CET)