Delucidazione sui quantificatori limitati

[astrifiammante]

Salve a tutti. Nei metodi finitari una frase col quantificatore esistenziale limitato della forma:

$$ \exists n
ha senso quando:

1) si può avere una dimostrazione diretta di un numero $1\le n < k $ tale percui si ha $A(n)$

2) si è in grado di esporre un processo (algoritmo) per ottenere tale numero compreso fra 1 ed n

giusto?

Invece, sempre nei metodi finitari, quando ho una frase col quantificatore universale limitato della forma:

$$ \forall n
ha senso quando è possibile provare, per ogni n compreso fra 1 e k, che abbiamo A(n). Ma in tal caso riusciremmo a farlo soltanto per una singola istanza di k. Altrimenti possiamo usare la dimostrazione per induzione? E' valida come metodo finitario? Ovviamente si estende a tutti i naturali, ma possiamo sempre restringerla in un certo intervallo 1,k

[Ancona1]

Non so cosa tu intenda per ragionamento finitario precisamente in ogni caso:

Ovviamente si estende a tutti i naturali, ma possiamo sempre restringerla in un certo intervallo 1,k

E' un controsenso usare l'induzione e poi restringerla a un intervallo finito. Se ti interessa un intervallo finito e dimostri che la proprietà vale per il primo elemento e che se vale per l'elemento n-1-esimo allora vale per l'n-esimo, allora hai già dimostrato che vale per ogni singolo elemento dell'intervallo finito senza usare da nessuna parte il principio di induzione. E la dimostrazione è semplicemente una successione finita di deduzioni partendo dal primo elemento e arrivando all'ultimo.

Il principio di induzione serve quando vuoi dimostrare una proprietà per un intervallo infinito di numeri naturali (o per tutti).

[astrifiammante]

Allora rimane la seconda alternativa: ovvero dimostrare che si ha: A(1) e A(2) e..........eA(k), ma in questo caso posso provare soltanto delle istanze: ad esempio k = 4 dovrò provare A(1) e A(2) e A(3) e A(4), ma non posso farlo per un k generico. In oltre se k è grande..........Mentre invece si legge che il quantificatore universale limitato ha senso finitario, ma in tal caso cosa significa (visto che l'ipotesi dell'induzione è da scartare e quella di ogni singola istanza non ci dà la prova per k generico)?

[Ancona1]

Quello che intendevo è solo che, se hai la possibilità di ragionare "per induzione" come volevi fare, cioè dimostrare che una proprietà vale per il primo elemento e poi che se vale per l'n-1-esimo allora vale per l'n-esimo, nel caso di un intervallo finito in realtà non stai veramente usando il principio di induzione. Ma quel tipo di ragionamento è corretto e, non usando veramente nessun assioma di induzione, non devo preoccuparti che il principio di induzione sia adeguato o meno per i tuoi scopi ( qualunque essi siano).

[astrifiammante]

Grazie Ancona.