Come generalizzare il principio di induzione

[dissonance]

Leggendo il topic "maratona di problemi teoria dei gruppi", in cui tra le altre cose si è discusso sull'induzione applicata ai soli naturali dispari, mi sono chiesto quali fossero le ipotesi minime su un insieme $X$ perché si possa applicare il principio di induzione.
Ad esempio, si può parlare di induzione estesa ai numeri razionali? Direi di no: se anche dimostrassimo una proprietà $P$ essere vera per $0$, poi con che numero dovremmo continuare? Non si sa perché non c'è un "successivo" di 0.

Quindi pensavo che le ipotesi minime perché si possa parlare di induzione su un insieme $X$ siano le seguenti:
a) $(X,-<)$ sia diretto (nel senso che la relazione binaria $-<$ ammette sempre un successivo: $\forallx\existsy$ t.c. $x- b) $-<$ sia un ordine totale;
c) valga il principio del minimo: $\forallS\subX\existss\inS$ t.c. $s-
Che dite? sono troppe? forse si può risparmiare sull'ordine totale?
Infine: se valgono queste tre ipotesi, $X$ è 1:1 con $NN$?

[dissonance]

"Sergio":
[quote="dissonance"]Direi di no: se anche dimostrassimo una proprietà $P$ essere vera per $0$, poi con che numero dovremmo continuare? Non si sa perché non c'è un "successivo" di 0.

Sicuro? Dal momento che $QQ$ può essere posto in corrispondenza biunivoca con $NN$, il "successivo secondo quella corrispondenza" lo trovi sempre.
[/quote]
Hai ragione. Ed in effetti non è nemmeno troppo strano: se consideriamo $QQ$ con questa corrispondenza, è come se stessimo considerando $NN$, cambiano solo i nomi dei numeri. Quindi in linea teorica potremmo parlare di induzione su $QQ$. Naturalmente tutto questo non preserva per nulla l'ordinamento dei razionali.

"Sergio":
[quote="dissonance"]Quindi pensavo che le ipotesi minime perché si possa parlare di induzione su un insieme $X$ siano le seguenti:
a) $(X,-<)$ sia diretto (nel senso che la relazione binaria $-<$ ammette sempre un successivo: $\forallx\existsy$ t.c. $x-
A me $\forallx\existsy$ t.c. $x- [/quote]
Forse qui c'è un problema di nomenclatura, e comunque è vero che ho sbagliato. Infatti si parla di insieme diretto se, dati due elementi $x_1, x_2$, esiste sempre un $y$ che li segue entrambi: $x_1-
L'idea di usare questi insiemi mi è venuta perché ho letto che si possono usare per costruire delle generalizzazioni delle successioni che prescindano dai numeri naturali. Perciò mi è venuta la curiosità di vedere come si comporta il principio di induzione in questo contesto.

"Sergio":
[quote="dissonance"]Che dite? sono troppe? forse si può risparmiare sull'ordine totale?

Non mi pare. Se non fosse totale, non sarebbe lineare. Cioè vi sarebbe qualche elemento per il quale la relazione d'ordine non varrebbe e verrebbe meno, per quell'elemento, la proprietà transitiva. Immediata conseguenza: circolarità.
Non ha caso c'è l'assioma "numeri diversi hanno successori diversi".
[/quote]
Qui però devo rifletterci un poco. Infatti in un insieme diretto questa proprietà non vale in generale ... però forse col principio del minimo e l'ordine totale sì.

[Megan00b]

Caro dissonance... dopo una abbondante soffiata sui duecentimetriemezzo di polvere che sovrastano i miei ricordi di logica ecco cosa ne è venuto fuori.
C'è un assioma che si suol chiamare assioma dell'infinito che ti dice che esistono insiemi induttivi. Un insieme induttivo è un insieme che contiene il vuoto (come elemento) e per ogni elemento contiene il suo successore. A sua volta il successore di un elemento X (insieme) è definito come $X U {X}$. In questo modo si definiscono i numeri naturali nella ZFC, ossia come intersezione di tutti gli insiemi induttivi. Da questa definizione segue il principio di induzione sui naturali.
Come generalizzare? Consideri gli assiomi di Peano, essi definiscono quello che si chiama un "modello di numeri naturali". Ogni insieme che li verifica (fissata opportunamente una funzione successore) è un modello. Si dimostra che i modelli di Peano sono tutti isomorfi, dove un isomorfismo è una funzione biunivoca stabile per le operazioni di successore nell'insieme di partenza e in quello di arrivo. Scendendo dalla teoria alla pratica: Puoi fissare un isomorfismo (quello ovvio) tra i numeri naturali e i numeri dispari, mettendo sul primo insieme l'operazione di successore $n mapsto n+1$ e sul secondo $d mapsto d+2$. A questo punto l'induzione vale sul primo e poichè c'è l'isomorfismo vale anche sul secondo.
Altro modo: Se hai una funzione biunivoca tra $NN$ e $X$ puoi usare l'induzione su X perchè: Sia f l'isomorfismo, Sia P la porprietà che vuoi mostrare vera per ogni $x in X$. Allora consideri la proprietà $Q: Q(n) iff P(f(n))$ Allora è evidente che se provi Q per tutti gli elementi di $NN$ hai provato P per tutti gli elementi di X. Ora riscrivendo quello che ho detto in maniera civile e decorosa dovrebbe risultare la risposta alla tua domanda. Credo. Ciao.
A.

[dissonance]

Sì si hai risposto in pieno alla mia domanda. Adesso ho le idee più chiare: gli insiemi diretti non c'entrano nulla. Meglio così...
Ciao!

[neopeppe89]

Mi permetto di aggiungere un ringraziamento a megan perchè anche io sono al primo anno di matematica...e diciamo che il principio d'induzione mi ha molto affascinato...soprattutto vedendolo come conseguenza degli assiomi d peano...d'altra parte è utilissimo!!!ciao

[G.D.5]

"neopeppe89":..soprattutto vedendolo come conseguenza degli assiomi d peano...

Vorrei fare notare che il Prncipio di Induzione non è una conseguenza degli assiomi di Peano, ma è un assoma di Peano.

[Megan00b]

"WiZaRd":
Vorrei fare notare che il Prncipio di Induzione non è una conseguenza degli assiomi di Peano, ma è un assoma di Peano.

Quoto. Aggiungo che in quello che ho detto andrebbe anche notato che ho barato <> una teoria al prim'ordine ed una al secondo. Nella pratica non cambia molto ma a voler essere rigorosi andrebbe chiarito e sviluppato un raccordo.

[neopeppe89]

scusate l'imprecisione...a me è stato spiegato come conseguenza degli assiomi d Peano!ma penso di aver capito...Peano ha inserito nei suoi assiomi un enunciato che contenesse il principio d'induzione e a noi c è stata fatta rilevare la cosa a posteriori!!!
grazie cmq per il chiarimento!!!:)

[G.D.5]

"neopeppe89":scusate l'imprecisione...a me è stato spiegato come conseguenza degli assiomi d Peano!ma penso di aver capito...Peano ha inserito nei suoi assiomi un enunciato che contenesse il principio d'induzione e a noi c è stata fatta rilevare la cosa a posteriori!!!
grazie cmq per il chiarimento!!!:)

Volendo essere puntigliosi fino alla noia, il principio di induzione è un assioma che riguarda gli insiemi: sia $S subseteq NN$ tale che $0 in S, (x in S => x+1 in S)$, allora $S=NN$. Nei corsi univeristari odierni viene fatto rilevare come una conseguenza della struttura dei naturali perché viene detto che il principio di induzione è un assioma che riguarda le proposizioni con dominio di variabili l'insieme $NN$, in realtà questo è un metodo dimostrativo che ha, a sua volta, una dimostrazione di valdità, molto molto semplice, che consiste nell'usare il principio di induzione ponenso $S$ l'insieme delle varibili naturali che verificano la proprietà da verificare.