Correttezza di una dimostrazione

[mario9555]

Sia $(S,<=)$ un insieme totalmente ordinato. Allora ogni parte non vuota e finita di S è dotata di minimo e massimo.

Io ho fatto così.

Si ponga $S^**=NN$ se S è infinito oppure $S^**=I_|S|$ se S è finito. Per ogni $ninS^**$ si ponga $S_n={X inP(S):$X è finito e $|X|=n}$. Dimostrare l'asserto sopra equivale quindi a dimostrare che per ogni $ninS^**$ ogni elemento di $S_n$ è dotato di minimo e di massimo. Per n=1, qualunque sia $X inS_1$ si può porre $X={x}$, e risulta $minX=maxX=x$. Sia $ninS^**$ con n>1, e si supponga che per ogni $iinNN$ tale che $1<=i<n$, ogni elemento di $S_i$ sia dotato di massimo e minimo. Se X è un elemento di $S_n$ e $x inX$ allora $X\\{x}inS_(n-1)$ è dotato di minimo $bar(x)$ e di massimo $bar(x)'$. Dunque

$minX=min{x,bar(x)}$
$maxX=max{x,bar(x)'}$

Quindi ogni elemento di $S_n$ è dotato di minimo e massimo.

Secondo voi va bene? Ci sarebbe qualche alternativa migliore?
Grazie in anticipo per le eventuali risposte.

[gugo82]

Si ponga…

E perché?

Conviene, casomai, distinguere due casi e fare la dimostrazione in modo differente.

[mario9555]

Perchè altrimenti distinguere il caso in cui S è finito e quello in cui è infinito;però in entrambi i casi si procede nello stesso modo. E' una questione di forma più che altro.

[caulacau]

Cioè non esistono insiemi infiniti diversi da $NN$? Mi sembra un'affermazione forte.

La dimostrazione che fai, tutto sommato, è giusta; è un po' scritta male. Quel che stai facendo è dimostrare la cosa che ti interessa per induzione, partendo dal fatto che se $A\subseteq S$ è un singoletto, la tesi è ovviamente vera, e se ha $n+1$ elementi, puoi confrontare $a_1$ con \(\min A\setminus\{a_1\}\) e \(\max A\setminus\{a_1\}\) che esistono per ipotesi induttiva.

[mario9555]

Scusatemi, forse non mi sono spiegato bene. Nello sviluppare la dimostrazione, non ho di certo ritenuto che $NN$ fosse l'unico insieme infinito. Il punto è questo: nel caso in cui $S$ è infinito, ho utilizzato il principio di induzione nella seconda forma che afferma che: Se $m$ è un numero naturale e $X$ è una parte non vuota di $NN_m$ avente come minimo m, e che contiene ogni numero naturale $n>m$ per il quale è vera l'implicazione
$m<=h<n=>h inX$, allora $X=NN_m$.
Quindi la dimostrazione in tal caso sarebbe


Per ogni $n in NN$ si ponga $S_n={X inP(S):X$ è finito e $|X|=n}$. Dimostrare l'asserto sopra equivale quindi a dimostrare che per ogni $n inNN$ ogni elemento di $S_n$ è dotato di minimo e di massimo. Per n=1, qualunque sia $X inS_1$ si può porre X={x}, e risulta $minX=maxX=x$. Sia $n inNN$ con n>1, e si supponga che per ogni $i inNN$ tale che $1<=i<n$, ogni elemento di S sia dotato di massimo e minimo. Se X è un elemento di $S_n$ e $x inX$ allora $X\\{x} inS_(n-1)$ è dotato di minimo $bar(x)$ di massimo $bar(x)'$. Dunque

$minX=min{x,bar(x)}$
$maxX=max{x,bar(x)'}$

Quindi ogni elemento di $S_n$ è dotato di minimo e massimo.

Le considerazioni implicite dietro la dimostrazione sono le seguenti

Indichiamo con T l'insieme dei sottoinsiemi finiti e non vuoti di S, e si consideri in $T$ la relazione binaria $R$ definita ponendo $XRY$ se e soltanto se $X,Y inT $e $|X|=|Y|$. Ovviamente $R$ è una relazione di equivalenza in T. Altro fatto ovvio è che $[X]_R=S_(|X|)$ per ogni $X inT$ (si rammenti che $S_n$ è l'insieme degli elementi di T di ordine n). Si consideri ora l'applicazione

$f:[X]_R inT/R->|X| inNN$

L'iniettività è banale. Allo scopo di provare la suriettività di f, sia $n inN$ e si proceda per induzione su n. Se n=1, allora qualunque sia l'elemento $x inS$ risulta $f([{x}]_R)=1$. Sia $n>1$ e si supponga che per $n-1$ esista un elemento $Y$ di T tale che $f([Y]_R)=n-1$. Essendo Y finito, $S\\Y$ è infinito (infatti in caso contrario, l'unione $(S\\Y) uu Y=S$ è finita, assurdo); in particolare $S\\Y!=O/$, per cui esiste un elemento $x$ di S che non appartiene a Y, e $X=Y uu{x}}$ ha ordine n. Quindi $f([X]_R)=n$. Dunque f è suriettiva, e quindi biettiva.

Si ha quindi

$ \bigcup_(ninNN)S_n $ = $ \bigcup_([X]_Rin T//R)[X]_R=T$


Nel caso in cui $S$ è finito, ho utilizzato il seguente risultato (che il mio testo di riferimento utilizza tacitamente nella dimostrazione sull'algoritmo delle divisioni successive)

Sia $n inNN$, e sia X una parte non vuota di $NN$. Se $1 inNN$ e se X contiene ogni elemento $1<i<=n$ tale per cui vale l'implicazione $1<=j<i=>j inX$ , allora $X=I_n$.

La forma del suddetto asserto è simile al principio di induzione nella seconda forma, e si dimostra analogamente.

E' ovvio che $XsubeI_n$. Se per assurdo $X sub I_n$, sia m il minimo $I_n\\X$. Allora $1<m<=n$, e vale l'implicazione
$1<=j<m=>j inX$ (essendo m il minimo di $I_n\\X$)
quindi per ipotesi $m inX$, assurdo. Dunque $X=I_n$

Quindi se S è finito la dimostrazione si svolge così

Per ogni $n in I_|S|$ si ponga $S_n={X inP(S):X$ è finito e $|X|=n}$. Dimostrare l'asserto sopra equivale quindi a dimostrare che per ogni $n inI_|S|$ ogni elemento di $S_n$ è dotato di minimo e di massimo. Per n=1, qualunque sia $X inS_1$ si può porre X={x}, e risulta $minX=maxX=x$. Sia $n in I_|S|$ con n>1, e si supponga che per ogni $i inNN$ tale che $1<=i<n$, ogni elemento di S sia dotato di massimo e minimo. Se X è un elemento di $S_n$ e $x inX$ allora $X\\{x} inS_(n-1)$ è dotato di minimo $bar(x)$ di massimo $bar(x)'$. Dunque

$minX=min{x,bar(x)}$
$maxX=max{x,bar(x)'}$

Quindi ogni elemento di $S_n$ è dotato di minimo e massimo.

Confrontando questa dimostrazione con quella sopra, si deduce inoltre l'utilità di $S^**$.