Chiarimento su: relazioni e principio di induzione
Ciao a tutti, sto studiando "Introduzione alla logica matematica" di Elliot Mendelson. Come alcuni sanno l'introduzione del testo tratta alcuni argomenti che verranno poi utilizzati in seguito, tra i quali, appunto, il principio di induzione. In realtà vengono citati due "tipi" di principi di induzione: il principio di induzione matematica e il principio di induzione completa. Tuttavia il mio dubbio non riguarda tanto le due versioni del principio, quanto piuttosto una specifica frase, di cui non riesco a capire completamente il senso. Sicuramente sarà un dubbio stupido, ma comunque chiedo a voi di illuminarmi. Allora, riporto virgolettato una parte di testo e poi evidenzio la frase in questione.
" Sia $P(x,y_1,\cdots,y_k)$ una relazione sull'insieme degli interi non negativi. In particolare $P$ può contenere solo la variabile $x$ ed essere così una proprietà. Se vale $P(0,y_1,\cdots,y_k)$ e, se per ogni $n$, $P(n,y_1,\cdots,y_k)$ implica $P(n+1,y_1,\cdots,y_k)$, allora $P(x,y_1,\cdots,y_k)$ è vera per tutti gli interi non negativi $x$ (Principio di induzione matematica). Nell'applicare questo principio si dimostra di solito che, per ogni $n$, $P(n,y_1,\cdots,y_k)$ implica $P(n+1,y_1,\cdots,y_k)$, assumendo $P(n,y_1,\cdots,y_k)$ e deducendo poi $P(n+1,y_1,\cdots,y_k)$; in questa deduzione $P(n,y_1,\cdots,y_k)$ si chiama ipotesi deduttiva. Se la relazione contiene effettivamentele variabili $y_1,\cdots,y_k$, diverse da $x$, la dimostrazione di "per tutti gli $x$, $P(x)$" si dice procedere per induzione su $x$."
Bene, quello che non capisco è proprio la frase in grassetto, in particolare quel "se la relazione contiene effettivamente le variabili....
Cioè cosa significa, per una relazione, contenere EFFETTIVAMENTE determinate variabili, diverse da x? Potete farmi gentilmente qualche esempio?
Grazie in anticipo ragazzi.
" Sia $P(x,y_1,\cdots,y_k)$ una relazione sull'insieme degli interi non negativi. In particolare $P$ può contenere solo la variabile $x$ ed essere così una proprietà. Se vale $P(0,y_1,\cdots,y_k)$ e, se per ogni $n$, $P(n,y_1,\cdots,y_k)$ implica $P(n+1,y_1,\cdots,y_k)$, allora $P(x,y_1,\cdots,y_k)$ è vera per tutti gli interi non negativi $x$ (Principio di induzione matematica). Nell'applicare questo principio si dimostra di solito che, per ogni $n$, $P(n,y_1,\cdots,y_k)$ implica $P(n+1,y_1,\cdots,y_k)$, assumendo $P(n,y_1,\cdots,y_k)$ e deducendo poi $P(n+1,y_1,\cdots,y_k)$; in questa deduzione $P(n,y_1,\cdots,y_k)$ si chiama ipotesi deduttiva. Se la relazione contiene effettivamentele variabili $y_1,\cdots,y_k$, diverse da $x$, la dimostrazione di "per tutti gli $x$, $P(x)$" si dice procedere per induzione su $x$."
Bene, quello che non capisco è proprio la frase in grassetto, in particolare quel "se la relazione contiene effettivamente le variabili....
Cioè cosa significa, per una relazione, contenere EFFETTIVAMENTE determinate variabili, diverse da x? Potete farmi gentilmente qualche esempio?
Grazie in anticipo ragazzi.
Risposte
Se hai una relazione che dipende da diverse variabili $P(x_0,...,x_k)$ e procedi per induzione su $x_0$ , nel caso in cui riesci a dimostrare che sia vera la stai dimostrando per tutti gli $x_0inNN$. Dunque se vorrai dimostrare la stessa cosa per $x_1$ dovrai procedere con l'induzione su di essa.
Tipo se hai $P(a,b,c): (a+b)c=ac+bc$ se la dimostri per induzione su $c$ non è detto che valga anche per $a,b$
Tipo se hai $P(a,b,c): (a+b)c=ac+bc$ se la dimostri per induzione su $c$ non è detto che valga anche per $a,b$
Innanzitutto ti ringrazio per la risposta. Dunque è come dire che si considera una relazione generica a, diciamo, $k$ argomenti, dunque una relazione che dipende effettivamente da più variabili ma di cui io voglio dimostrarla (per induzione) solo per una delle $k$ variabili, ad esempio la prima. è corretto?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo