Archimedeità di $NN$ per induzione

Indrjo Dedej
Ciao a tutti! Ho fatto una dimostrazione per induzione per provare che $NN$ è archimedeo:
$forall x,y in NN_0 exists n in NN_0 :nx>y$,
dove $NN_0$ è l'insieme dei numeri naturali senza lo zero.
Per iniziare so che esiste almeno un $n in NN_0$ tale che $nx>1$: infatti ad esempio $2x>x≥1$. Suppongo a questo punto che sia vero $forall x in NN_0 exists n in NN_0 :nx>y$. Sia a questo punto $tilde{n} in NN_0$ tale che $tilde{n}x>y$. Ho così:
$y+1 ed ho concluso.
Può andare bene?

Risposte
kobeilprofeta
Secondo me devi fare induzione sia su x che su y

Indrjo Dedej
Io pensavo di agire per induzione su $y$ in questo predicato:
$forall x in NN_0 exists n in NN_0: nx>y$.

garnak.olegovitc1
provate per assurdo che fate prima...

Indrjo Dedej
Vabbé, per assurdo è semplice. A me interessa farlo per induzione. :-D

axpgn
Anche per induzione non è difficile ... :D

Come detto "induci" su $y$ ...

Passo base: dato $y=1$ per ogni $x in NN_0$ è vero che $2x>1$

Passo induttivo: visto che per ogni $x in NN_0$ il passo base è vero, possiamo ipotizzare che, dato un generico $y in NN_0$, per ogni $x in NN_0$ esista un $n_x in NN_0$ tale per cui sia $n_x*x>y$. Dobbiamo dimostrare che per ogni $x in NN_0$ esista un $m_x in NN_0$ per cui sia $m_x*x>y+1$.
Dato che è $2x>1$ allora dall'ipotesi $n_x*x>y$ ne cosnegue che $n_x*x+2x>y+1$ ovvero $(n_x+2)x>y+1$ cioè $m_x*x>y+1$

Va bene così? :D

Cordialmente, Alex

Indrjo Dedej
@axpgn,
abbiamo fatto quasi la stessa identica cosa.

axpgn
Quasi ... :-D

Indrjo Dedej
Infatti ho detto "quasi". Quindi può andare bene? A me il metodo che ho seguito, vedendo quello che hai fatti mi sembra crretto.

axpgn
Mi sembra poco "ordinato" ...

Indrjo Dedej
Ma può andare bene? Per "ordinato" intendi una cosa del tipo:
Passo base:...
Passo induttivo:...
O no?

axpgn
Anche ... ma non solo ... non ha molto senso (o comunque non é chiaro) per esempio dove dici " per ogni $x$ e $y$ ..." : a mio parere deve essere chiaro quale sia la variabile su cui "fai" l'induzione ...

Indrjo Dedej
Mi sono accorto di aver fatto un refuso nell'ipotesi di induzione.

Non ti piace il "$forall x,y$" che uso? Poi pensavo fosse chiaro il mio ragionamento e che procedessi per induzione su $y$. Però se è più chiaro posso riformulare così:

Fissato un $x in NN_0$ si ha
$forall y in NN_0 exists n in NN_0: nx>y$

A questo punto credo di aver messo in evidenza su chi agisco per induzione.

axpgn
Scusami ma se il passo base è $2x>1$ allora la variabile su cui fa induzione è $y$ e quindi quello che hai scritto ora è il contrario ... :D

Indrjo Dedej
Non capisco cosa intendi. Io procedo per induzione su $y$. Ti puoi spiegare meglio? :?
Può darsi che non mi sia espresso bene e che na abbia fatto intendere ciò che volevo.

axpgn
Non stai lavorando su $y$ tant'è che scrivi "per ogni $y$" invece il passo induttivo "lavora" su una $y$ sola (generica ma unica) e sulla successiva ...

Prova a rileggere cosa ho scritto e vedere cosa varia e come varia ...

Indrjo Dedej
"Per ogni $y$" l'ho messo nel teorema. Sul passo induttivo non mi pare di aver usato un "per ogni $y$".

axpgn
Lo hai scritto qui sopra ...

Indrjo Dedej
Scusami cerca di spiegarti meglio. Stiamo parlando della riformulazione che ho fatto qualche post fa?

axpgn
Il fatto è che io mi sono spiegato bene nel mio primo post e spiegarmi meglio mi è difficile ... :-D
Se, come ti ho suggerito, rilegessi quello, poi magari lo confronti con la tua formulazione e vedi dove stanno le differenze ...

Indrjo Dedej
Io ho confrontato la tua dimostrazione con la mia è non ci sono differenze che minano la correttezza della mia - mi sembra per ora. Non ho problemi di tempo, quindi faccio passare un po' di tempo e rivedo il tutto e rileggo e cerco di capire quello che mi hai detto.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.