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$.
-
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 :
-
$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$.
-
$a_D = 1$, $s_D(n) = 2n$.
Indication : Vérifiez par induction que $h^*(s^{n}(a))=2^n$ pour tout $n$.
-
$a_D = 1$, $s_D(n) = n + 2$.
Indication : Vérifiez par induction que $h^*(s^{n}(a))=2n+1$ pour tout $n$.