$rho$ buon ordinamento $=>$ $rho$ totale
Devo dimostrare che se una relazione $rho$, definita su un insieme $X$, è un buon ordinamento, allora tale relazione è anche di ordine totale.
Ordine totale vuol dire che $AA x,y in X, x rho y$ oppure $y rho x$
Distinguo se $X$ sia finito o infinito
1) Per ipotesi, ogni sottoinsieme di $X$ non vuoto ammette minimo. Considero tutto $X$, che per ipotesi è finito: $X = {a_1,a_2,...,a_k}$. Questo ha minimo. Sia $b$ il minimo di $X$, allora $b<=a_i, i=1,...,k$. Questo in realtà non vuol dire ancora che $X$ sia totalmente ordinato[nota]Magari $b<= a_i$ e $b<= a_j$, ma $a_i$ e $a_j$ non sono confrontabili[/nota], però ora io posso togliere da $X$ l'elemento $b$, riuscendo comunque a trovare il minimo (sia ad esempio $b_2$ il minimo di $X - {b}$, e così via fino a rimanere con un singoletto che ha un unico elemento che è sia massimo che minimo.). Per fare questo io ho confrontato tutti gli elementi di $X$ ($AA x,y in X$, sono riuscito a determinare se $a_i rho a_j$ o se $a_j rho a_i$ e quindi deduco che, per gli insiemi finiti, l'ordine è totale.
2) Se $X$ è infinito, posso prendere di nuovo $X$ e per ipotesi so che ha minimo, ad esempio $x_1$. Come prima, posso considerare $X - {x_1}$ e anche questo insieme avrà minimo, ad esempio $x_2$. E' chiaro che posso andare avanti cosi, e per fare questo sono sempre in grado di confrontare tutti gli elementi di $X$, quindi anche qui deduco che l'ordine è totale.
E' giusta questa dimostrazione?
Ordine totale vuol dire che $AA x,y in X, x rho y$ oppure $y rho x$
Distinguo se $X$ sia finito o infinito
1) Per ipotesi, ogni sottoinsieme di $X$ non vuoto ammette minimo. Considero tutto $X$, che per ipotesi è finito: $X = {a_1,a_2,...,a_k}$. Questo ha minimo. Sia $b$ il minimo di $X$, allora $b<=a_i, i=1,...,k$. Questo in realtà non vuol dire ancora che $X$ sia totalmente ordinato[nota]Magari $b<= a_i$ e $b<= a_j$, ma $a_i$ e $a_j$ non sono confrontabili[/nota], però ora io posso togliere da $X$ l'elemento $b$, riuscendo comunque a trovare il minimo (sia ad esempio $b_2$ il minimo di $X - {b}$, e così via fino a rimanere con un singoletto che ha un unico elemento che è sia massimo che minimo.). Per fare questo io ho confrontato tutti gli elementi di $X$ ($AA x,y in X$, sono riuscito a determinare se $a_i rho a_j$ o se $a_j rho a_i$ e quindi deduco che, per gli insiemi finiti, l'ordine è totale.
2) Se $X$ è infinito, posso prendere di nuovo $X$ e per ipotesi so che ha minimo, ad esempio $x_1$. Come prima, posso considerare $X - {x_1}$ e anche questo insieme avrà minimo, ad esempio $x_2$. E' chiaro che posso andare avanti cosi, e per fare questo sono sempre in grado di confrontare tutti gli elementi di $X$, quindi anche qui deduco che l'ordine è totale.
E' giusta questa dimostrazione?
Risposte
In realtà, se $X$ è infinito, un concetto che riesce a formalizzare la dimostrazione mi sembra l'induzione.
Passo base: prendo un singoletto di $X$, ad esempio ${a_1}$. Questo ha minimo.
Passo induttivo sia $X_(n-1) sube X$ un sottoinsieme di $X$ tale per cui $rho$ induce un ordine totale. Devo dimostrare che $X_n$ è un ordine totale. $n$ e $n-1$ a pedice rappresentano le rispettive cardinalità
Sia $x_k$ s il minimo di $X_n$. Quindi $x_k <= x_i, AA x_i in X_n$. Tolgo $x_k$, ottenendo un insieme di cardinalità $n-1$, che per ipotesi induttiva so essere totalmente ordinato.
Da qui ho la tesi.
Fatemi sapere se il ragionamento è corretto, grazie.
Passo base: prendo un singoletto di $X$, ad esempio ${a_1}$. Questo ha minimo.
Passo induttivo sia $X_(n-1) sube X$ un sottoinsieme di $X$ tale per cui $rho$ induce un ordine totale. Devo dimostrare che $X_n$ è un ordine totale. $n$ e $n-1$ a pedice rappresentano le rispettive cardinalità
Sia $x_k$ s il minimo di $X_n$. Quindi $x_k <= x_i, AA x_i in X_n$. Tolgo $x_k$, ottenendo un insieme di cardinalità $n-1$, che per ipotesi induttiva so essere totalmente ordinato.
Da qui ho la tesi.
Fatemi sapere se il ragionamento è corretto, grazie.
No, il punto 2 non va bene. E neanche usare l'induzione va bene, perché $X$ può essere infinito e non numerabile.
È molto più semplice. Considera l'insieme ${x,y}$. È un sottoinsieme non vuoto di $X$, quindi ammette minimo. Quindi?
È molto più semplice. Considera l'insieme ${x,y}$. È un sottoinsieme non vuoto di $X$, quindi ammette minimo. Quindi?
Quindi $x rho y$ oppure $y rho x$, però ricado nella dimostrazione per insiemi finiti. Se ho un insieme infinito e non numerabile, come riesco a dimostrare la proposizione?
Non c'entra molto con la proposizione che devo dimostrare, ma se un insieme ha minimo allora la relazione d'ordine è necessariamente totale? A me non sembra, però forse mi sbaglio. Mi potreste fare un controesempio?
Quello che voglio dire è: ho un insieme $X = {1,3,4,5}$ con questo grafico della relazione $rho: {(1,1), (1,3), (1,4), (1,5), (3,3), (4,4), (5,5)}$ Questa è un relazione d'ordine (è riflessiva, antisimmetrica e transitiva) ma l'ordine non è totale: ad esempio 3 non è in relazione con 4 e 4 non è in relazione con 3. Il minimo però c'è, ed è $1$
Quello che voglio dire è: ho un insieme $X = {1,3,4,5}$ con questo grafico della relazione $rho: {(1,1), (1,3), (1,4), (1,5), (3,3), (4,4), (5,5)}$ Questa è un relazione d'ordine (è riflessiva, antisimmetrica e transitiva) ma l'ordine non è totale: ad esempio 3 non è in relazione con 4 e 4 non è in relazione con 3. Il minimo però c'è, ed è $1$
La finitezza di $X$ non c'entra niente. L'argomento che ti ho detto dimostra che dati due qualsiasi $x,y in X$ si ha $x rho y$ oppure $y rho x$. Che $X$ sia finito o infinito non ha nessuna importanza.
Se un insieme ha minimo la relazione non è necessariamente totale. Prendi per esempio un insieme $X$ e definisci $P$ come l'insieme di tutti i sottoinsiemi di $X$ ordinato dall'inclusione. L'insieme vuoto è il minimo di $P$. Tuttavia l'ordine di $P$ non è totale se $|X| ge 2$ perché è facile costruire due sottoinsiemi di $X$ nessuno dei quali è contenuto nell'altro (prova).
Se un insieme ha minimo la relazione non è necessariamente totale. Prendi per esempio un insieme $X$ e definisci $P$ come l'insieme di tutti i sottoinsiemi di $X$ ordinato dall'inclusione. L'insieme vuoto è il minimo di $P$. Tuttavia l'ordine di $P$ non è totale se $|X| ge 2$ perché è facile costruire due sottoinsiemi di $X$ nessuno dei quali è contenuto nell'altro (prova).
$P$ sarebbe l'insieme delle parti?
Se sì è facilissimo. Considero $P(X)$ insieme delle parti di $X={a,b,c}$. In tale insieme non è vero che ( ${a,b} sube {b,c}$ o ${b,c}sube{a,b}$), quindi la relazione d'ordine dell'inclusione $sube$ non è totale. Tuttavia il minimo c'è, ed l'insieme vuoto.
Se sì è facilissimo. Considero $P(X)$ insieme delle parti di $X={a,b,c}$. In tale insieme non è vero che ( ${a,b} sube {b,c}$ o ${b,c}sube{a,b}$), quindi la relazione d'ordine dell'inclusione $sube$ non è totale. Tuttavia il minimo c'è, ed l'insieme vuoto.
"Martino":
La finitezza di $X$ non c'entra niente. L'argomento che ti ho detto dimostra che dati due qualsiasi $x,y in X$ si ha $x rho y$ oppure $y rho x$. Che $X$ sia finito o infinito non ha nessuna importanza.
Perché, all'aumentare del numero di elementi che considero, non dovrebbe succedere qualcosa di brutto facendo sì che l'ordine non è più totale? Con due elementi mi sembra banale.
Forse perché se aggiungo un altro elemento l'insieme ottenuto avrebbe sempre minimo, e questo lo posso fare fino a ricoprire tutto l'insieme (o reiterando il procedimento se l'insieme è infinito). Facendo ciò avrei sempre messo in relazione tutti gli elementi dell'insieme, e quindi la dimostrazione per gli insiemi finiti mi convince. Per quanto riguarda gli insiemi infiniti, l'unico strumento che conosco per formalizzare una dimostrazione in tali insiemi è l'induzione, però come hai detto tu ci possono essere anche insiemi infiniti e non numerabili per i quali non la posso utilizzare.
Ma scusa, di cosa stai parlando?
Prendi due elementi qualsiasi $x,y$, che d'ora in poi sono fissati. Devi mostrare che $x rho y$ oppure $y rho x$. Se ci riesci hai dimostrato che l'ordine è totale. Come fai? Con l'argomento che ti ho detto. Questo dimostra che ogni buon ordinamento è totale. Fine.
Prendi due elementi qualsiasi $x,y$, che d'ora in poi sono fissati. Devi mostrare che $x rho y$ oppure $y rho x$. Se ci riesci hai dimostrato che l'ordine è totale. Come fai? Con l'argomento che ti ho detto. Questo dimostra che ogni buon ordinamento è totale. Fine.
Ok credo di aver capito il tuo ragionamento. Io stavo cercando di costruire l'insieme più grande possibile nel quale dimostravo che tutti gli elementi erano confrontabili, però in effetti è più semplice ragionare per coppie ${x,y}$, $x,y in X$, per dimostrare che l'ordine è totale.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo