Longueur d'une formule — Les-mathematiques.net The most powerful custom community solution in the world

Longueur d'une formule

Bonjour,
je suis en train de lire le premier chapitre du Cori Lascar (calcul propositionnel). Comment prouve-t-on que pour une formule de hauteur $n$, les longueurs $n+2$ , $n+3$, $2^{n+2}-8$, $2^{n+2}-5$ et $2^{n+2}-4$ ne sont pas possibles ?

Merci pour votre aide

Réponses

  • @Raskolnikov : bonsoir. Par définition, quelle est la hauteur d'une formule $\phi\in\mathscr{F}$ ?
  • Il s'agit en fait d'une question posée dans le corrigé de l'exercice 2 (page 282).114388
    114390
  • Il s'agit de remarquer que si $\phi$ est de hauteur $n$, alors elle est soit de la forme $\neg F$ avec $F$ de hauteur $n-1$, soit de la forme $F \alpha G$ avec $F$ ou $G$ de hauteur $n-1$, l'autre étant de hauteur $\leq n-1$. Dans le premier cas, on a $l(\phi) = 1 + l(F)$, dans le second, $l(\phi) = l(F) + l(G) + 1$.

    À partir de ces observations, on doit pouvoir faire un raisonnement par récurrence.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!