Induzione strutturale

Dovendo provare proprietà di oggetti definiti ricorsivamente può essere utile l’induzione strutturale

Sia $A =$ un insieme di elementi definiti ricorsivamente e $P =$ proprietà avente come oggetto gli elementi di $A$, si vuole provare che $\forall x \in A \space P(x)$

Con l’induzione strutturale basta provare che:

• base: mostrare che l’enunciato $P$ è vero per tutti gli elementi nell’insieme specificati dal passo base della definizione ricorsiva di $A$
• passo ricorsivo: mostrare che
  • se l’enunciato $P$ è vero per ciascuno degli elementi già in $A$, cioè gli elementi usati per costruire nuovi elementi nel passo ricorsivo della definizione di $A$
  • allora l’enunciato $P$ è vero per questi nuovi elementi

Esempio: Sia $A$ l’insieme costituito dagli elementi definiti ricorsivamente come segue

• passo base: $1 \in A$
• passo ricorsivo: se $x \in A$ allora $x+2 \in A$

Provare che $A$ è costituito dagli interi dispari positivi

dim: sia $D$ l’insieme di tutti gli interi dispari positivi cioè $D=\{ y \in \mathbb Z^+ | \exist k \space (k \geq 0 \land y = 2k+1)\}$

Dobbiamo provare che $D = A$, cioè che $D \subseteq A$ e $A \subseteq D$

• $D \subseteq A$: procediamo usando l’induzione matematica con $P(k): 2k+1 \in A \space \forall k \geq 0$

  • base: $P(0): 2 \cdot 0 +1 = 1 \in A$
  • passo di induzione: $2 \cdot (k+1) +1 = 2k +2+1 = (2k+1)+2 \in A$

• $A \subseteq D$: procediamo usando l’induzione strutturale con $P(x): x= 2k+1$ per qualche intero $k \geq 0 \space \forall x \in A$

  Usiamo la definizione ricorsiva di $A$:

  • base: da passo base della definizione ricorsiva sappiamo che $1 \in A$, poichè $1 = 2 \cdot 0 +1 \Rightarrow P(1)$ è vera $\Rightarrow 1 \in D$

  • passo di ricorsione: usiamo la seconda parte della definizione ricorsiva di $A$, e sia un $x+2 \in A$

    $x = 2k+1$ per qualche intero $k \geq 0$

    $x+2 = 2k+1 +2 = 2(k+1)+1 \in D$

Esempio: sia $A$ un insieme definito nel modo seguente:

• passo base: $3 \in A$
• passo ricorsivo: se $x \in A$ e $y \in A$ allora $x+y \in A$

Provare che $A$ è costituito dagli interi positivi multipli di $3$

dim: sia $M$ l’insieme di tutti i multipli di $3$, cioè $M=\{ y \in \mathbb Z^+|\exist k \space (k \in \mathbb Z^+ \land y = 3k) \}$