Induzione per n che varia in un insieme finito

[Daniele_98]

Se per esempio deve dimostrare per induzione una $P(N)$ per $nin{0,.....,m}$, allora non cambia nulla, da un punto di vista formale, e posso eseguire gli stessi passaggi che si svolgono usualmente, oppure nel passaggio induttivo $P(n)=>P(n+1)$ deve fare ulteriori considerazioni?

[megas_archon]

Quando \(n=m\) il passo induttivo non ha senso, e allora si danno due casi:

- o il risultato è vero anche per \(k\ge m+1\), e allora la proposizione $P$ ammette una estensione non banale \(P^* : \{0,\dots,m+1\}\to Set\), che ti fa ricadere nello stesso tipo di tranello;
- o il risultato è effettivamente vero per tutti gli elementi di \(\{0,\dots,m\}\) ma non per tutti gli elementi di \(\{m+1,m+2\dots\}\). E allora però devi controllare un numero finito di casi, e nell'insieme \(\{m+1,m+2\dots\}\) c'è un $k$ tale che \(\lnot Pk\). E allora, in che senso hai dimostrato "per induzione" che la proposizione $P$ è vera?

Parlando a spanne, l'induzione è un processo di dimostrazione che è fatto per proposizioni il cui insieme di valori di verità "non finisce"; più precisamente, se una funzione proposizionale ha un dominio di validità (cioè il sottoinsieme massimo \(D\) di \(\mathbb N\) dove \(P\) è sempre vera) tale che

1. $D$ contiene lo zero;
2. $D$ è chiuso per successore;

allora \(D=\mathbb N\). Un po' più in generale, se $D$ contiene il segmento iniziale di \(n_0\), allora $D$ coincide col segmento iniziale di \(n_0\), che è praticamente la stessa cosa perché esiste un isomorfismo d'ordine tra \(\mathbb N\) e ogni suo segmento iniziale.

Questo fatto (formulato nel primo modo, a partire da zero) si può vedere così, è una conseguenza simpatica della proprietà universale dei numeri naturali, e io lo do per esercizio a lezione:

The mathematical induction principle (MIP) says that
\[ \big(Q0\land \bigwedge_{i\le n} Qi\Rightarrow Q(i+1)\big)\Rightarrow \bigwedge_{n : \mathbb N} Qn\](in words, if \(Q : \mathbb N \to \{0,1\}\) is a proposition, \(Q0\) is true, and \(Qn \Rightarrow Q(n+1)\), then \(Qn\) is true for all \(n : \mathbb N\). Show that there is a way to state the MIP in terms of the universal property of \(\mathbb N\) [Hint: use the universal property of \(\mathbb N\) to show that if \(S\subseteq \mathbb N\) is a nonempty subset such that the inclusion \(i : S \hookrightarrow \mathbb N\) is a morphism in \(\sf Dyn\)[¹], then \(S=\mathbb N\). Deduce the induction principle using a suitable \(S_Q\) obtained from the property \(Q\).}]

[¹]

Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.

1. Esiste una categoria \(\sf Dyn\) i cui oggetti sono le terne \((X,t : X \to X, x\in X)\), ovvero i diagrammi della torma
\[
\begin{CD}
1 @>x>> X @>t>> X
\end{CD}
\] e i morfismi tra \((X,t,x)\) e \((Y,g,y)\) consistono delle funzioni $u : X \to Y$ tali che $u(x)=y$ e $u\circ t=g\circ u$.

2. \(\mathbf{N}=(\text{s} : \mathbb N \to \mathbb N, 0\in \mathbb N)\) è un oggetto di questa categoria.

3. Per ogni oggetto \(\mathbf{X} = (X,t,x)\) di \(\sf Dyn\) esiste un morfismo \(u : \mathbf N \to\mathbf X\) in \(\sf Dyn\) tale che[1]
\[
\begin{CD}
1 @>0>> \mathbb N @>\text{s}>> \mathbb N \\
@| @VuVV @VVuV\\
1 @>>x> X @>>t> X
\end{CD}
\] e tale $u$ è unico con questa proprietà[2]; ciò significa esattamente che \((\mathbb N, \text{s}, 0)\) è l'oggetto iniziale di \(\sf Dyn\).

[1] Questo significa che dato \(u_0=x\) e un endomorfismo di $X$, esiste un unico modo di definire per ricorsione una successione di \(u_n\) ponendo
\[
\begin{cases}
u_0 = x \\
u_{n+1} = t(u_n)
\end{cases}
\]
[2] Se esiste una $v : \mathbb N \to X$ con la stessa proprietà, deve essere definita dalla stessa ricorsione usando $t$, quindi $u=v$.

[Daniele_98]

Scusami, non mi sono spiegato bene. Nel mio caso $nin{0,.....,m}$, ma $m$ può essere un qualsiasi numero naturale.
Quindi deve dimostrare che dato un qualsiasi valore di $m$ la proposizione $P(n)$ per $nin{0,.....,m}$ è vera.

[megas_archon]

E in cosa allora questo è diverso dalla induzione solita, se è vero per ogni m? E poi, perché questo limite su m?

[ingres]

Ciao Daniele_98

megas_archon ha ragione. Non è ben chiaro il problema induttivo in oggetto.
Mi sembrava di aver capito, ma dopo l'ultimo post non ne sono più sicuro. Provo quindi a fare un esempio per capire se ho inteso bene.
Supponiamo che la proposizione sia banalmente di dimostrare che:
$(n/10000) - (n/10000)^2 ge 0$ per tutti gli $n le m=10000$

Ammettiamo che si voglia procedere per "induzione" (ci sono evidentemente metodi migliori, ma non è questo il punto). In questo caso l'applicazione del metodo "induttivo" è possibile, ma richiederà nella dimostrazione di introdurre esplicitamente il vincolo n<m.

E' di questo tipo di problemi di cui stiamo parlando?

[Daniele_98]

Faccio l'esempio su cui mi è sorto il dubbio:
Ho una ipotesi $I$ da cui devo dimostrare la validità di $P(n)=$"$EE w_1,...,w_(k-n) in Span(S)$ e $v_(k-n+1),...,v_k inS$ $t.c. {w_1,...,w_(k-n),v_(k-n+1),...,v_k}$ è un insieme di k vettori linearmente dipedenti" $AA n in {1,...,k}$.
La mia domanda è quando faccio il passasggio induttivo $P(n)=>P(n+1)$ devo imporre che $n+1<=k$?