Induction structurelle

Exercice 6

Soit $F_0 = \{a\}$ et $F_1 = \{s\}$ . On considère l’ensemble $\mathcal{T}$ des termes construits sur $F_0 \cup F_1$.

  1. Démontrer que $\mathcal{T} =\{s^n(a) \mid n \in \mathbb{N}\}$, où $s^n(a)$ est défini inductivement par : $s^0(a)=a$ et pour tout $n \in \mathbb{N}$, $s^{n+1}(a) = s(s^n(a))$.

    Indication : L’ensemble $\mathcal{T}$ est défini inductivement par :

    (B) $a$ appartient à $\mathcal{T}$.

    (I) Pour tout $t \in \mathcal{T}$, $s(t)$ appartient à $\mathcal{T}$

    Montrez d’abord que $\{s^n(a) \mid n \in \mathbb{N}\}$ est inclus dans $\mathcal{T}$, par récurrence sur $n$. Pour l’inclusion réciproque, on montre par induction sur la structure de $\mathcal{T}$ que pour tout terme $t \in \mathcal{T}$, il existe $k$ tel que $t = s^k(t)$.

Sur le domaine $D = \mathbb{N}$, on associe à la constante $a$ la valeur $a_D \in \mathbb{N}$ et au symbole de fonction $s$ la fonction $s_D : D \longrightarrow D$ ; On rappelle que l’interprétation $h^*$ des termes $T$ (à valeur dans $D$) est telle que :

(B') Si $t = a \in F_0$, $h^*(t) = a_D$,

(I') Si $t = s(t_1)$, $h^*(t) = s_D(h^*(t_1))$.

Calculer $h^*$ dans les cas suivants :

  1. $a_D = 0$, $s_D(n) = n + 1$.

    Indication : Dans ces trois questions, il faut deviner la forme générale de la valeur d’un terme, en calculant $h^*(s(a))$, $h^*(s^2(a))$, etc. Le cas de base (à vérifier) est toujours obtenu par $h^*(a)=a_D$. Vérifiez par induction que $h^*(s^{n}(a))=n$ pour tout $n$.

  2. $a_D = 1$, $s_D(n) = 2n$.

    Indication : Vérifiez par induction que $h^*(s^{n}(a))=2^n$ pour tout $n$.

  3. $a_D = 1$, $s_D(n) = n + 2$.

    Indication : Vérifiez par induction que $h^*(s^{n}(a))=2n+1$ pour tout $n$.

Précédent
Suivant