Correttezza di una dimostrazione
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
$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.
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
$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.
Risposte
Si ponga…
E perché?
Conviene, casomai, distinguere due casi e fare la dimostrazione in modo differente.
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.
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.
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.
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<=hh 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
$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 $1j 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 $1j 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
$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^**$.
$m<=h
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
$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
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
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
$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^**$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo