Esercizio Induzione forte

[axel123]

Buonasera,sto provando a risolvere il seguente esercizio:

Si provi utilizzando l'induzione forte,che ogni insieme finito e non vuoto di numeri interi è dotato di minimo
e di massimo. (Si utilizzi l'induzione sul numero di n elementi dell'insieme dato).

Procedo in questo modo:

PASSO BASE
Dato che la traccia richiede esplicitamente l'induzione forte considero due casi:
Sia S un generico insieme

|S| = 1 -> L'insieme s contiene un solo elemento.Esso sarà contemporaneamente sia minimo che massimo
|S| = 2 -> L'insieme S contiene due elementi che chiamiamo per semplicità {a} e {b}
se a>b, allora max(S) = a e min(S) = b altrimenti il contrario
IPOTESI INDUTTIVA
P(k) = "L'insieme S che contiene k elementi ammette minimo e massimo"

PASSO INDUTTIVO

Vogliamo dimostrare che P(k-1) and P(k) -> P(k+1)
Il problema è qui... come posso procedere?

[axel123]

Ho provato a considerare un insieme che chiamo S1 che contiente k+1 elementi dicendo che
S1 = S U {x}, dove x è un generico elemento

Per ipotesi induttiva S ammette sia min che max
Ora dico: se x>max(S) allora max(S1) = x
se x <min(S) allora min(S1) = x
altrimenti min(S1) = min(S) e max(S1) = max(S)

Il problema è che la mia dimostrazione non è proprio "forte"..

[Martino]

La tua dimostrazione è giusta, in che senso non è "forte"?

[axel123]

Nel senso che io sto affermando vero P(k-1) and P(k) ,ma non utilizzo affatto P(k-1),quindi nella mia dimostrazione
utilizzo l'induzione semplice,giusto?

[Martino]

Giusto.

[axel123]

Come posso quindi usare l'induzione forte?

[Martino]

Questo problema in particolare si presta particolarmente ad essere risolto con l'induzione semplice, non saprei scriverne una dimostrazione che usi l'induzione forte senza essere molto artificiale.