Estendere ordine parziale a ordine totale
Un ordine parziale $(X,\le)$ è una coppia formata da un insieme $X$ e da una relazione binaria $\le$ su X riflessiva, antisimmetrica e transitiva.
Un ordine totale $(X,\le)$ è una coppia formata da un insieme $X$ e da una relazione binaria $\le$ su X riflessiva, antisimmetrica, transitiva e totale.
Un ordine parziale $(X,\le_\star)$ estende un ordine parziale $(X,\le)$ se per ogni $x,y\inX$ si ha che $x\ley$ implica $x\le_\stary$.
Vorrei dimostrare che se $(X,\le)$ è un ordine parziale e $X$ è un insieme finito allora esiste un ordine totale $(X,\le_\star)$ che estende $(X,\le)$.
Se provo a procedere per induzione sulla cardinalità di $X$ la base dell'induzione è semplice.
Se $X$ ha cardinalità $0$ allora $X=\emptyset$ e quindi l'unico ordine parziale è quello in cui $\le$ è la relazione vuota e $(X,\le)$ è già un ordine totale.
Se $X$ ha cardinalità $1$ allora $X=\{x\}$ e quindi l'unico ordine parziale è quello in cui $\le$ è la relazione "piena" definita ponendo $x\lex$ e $(X,\le)$ è già un ordine totale.
La difficoltà è nel dimostrare il passo induttivo.
Se suppongo di saper estendere ogni ordine parziale di cardinalità $n$ ad un ordine totale, come posso estendere un ordine parziale di cardinalità $n+1$ ad un ordine totale?
Un ordine totale $(X,\le)$ è una coppia formata da un insieme $X$ e da una relazione binaria $\le$ su X riflessiva, antisimmetrica, transitiva e totale.
Un ordine parziale $(X,\le_\star)$ estende un ordine parziale $(X,\le)$ se per ogni $x,y\inX$ si ha che $x\ley$ implica $x\le_\stary$.
Vorrei dimostrare che se $(X,\le)$ è un ordine parziale e $X$ è un insieme finito allora esiste un ordine totale $(X,\le_\star)$ che estende $(X,\le)$.
Se provo a procedere per induzione sulla cardinalità di $X$ la base dell'induzione è semplice.
Se $X$ ha cardinalità $0$ allora $X=\emptyset$ e quindi l'unico ordine parziale è quello in cui $\le$ è la relazione vuota e $(X,\le)$ è già un ordine totale.
Se $X$ ha cardinalità $1$ allora $X=\{x\}$ e quindi l'unico ordine parziale è quello in cui $\le$ è la relazione "piena" definita ponendo $x\lex$ e $(X,\le)$ è già un ordine totale.
La difficoltà è nel dimostrare il passo induttivo.
Se suppongo di saper estendere ogni ordine parziale di cardinalità $n$ ad un ordine totale, come posso estendere un ordine parziale di cardinalità $n+1$ ad un ordine totale?
Risposte
Si tratta di un caso particolare di un teorema famoso, il teorema di estensione di Szpilrajn, che vale per ogni cardinalità, non necessariamente finita. La dimostrazione del caso generale è una elegante applicazione del lemma di Zorn, vedi qui https://en.wikipedia.org/wiki/Szpilrajn ... on_theorem ma nel caso finito non c'è molto da dimostrare: un ordine totale su un insieme finito (diciamo avente $n$ elementi) è per forza isomorfo a un segmento iniziale di \(\omega\), cioè a \(\{1<2<\dots
Una maniera più formale di ragionare è adattare l'idea del teorema di Szpilrajn, dicendo che se hai una coppia di elementi \((a,b)\) non in relazione li aggiungi a \(\le\) (considerato come sottoinsieme di \(X\times X\)) e prendi la chiusura transitiva \(\le'\) di \(\le\cup \{(a,b)\}\). Hai un ordine totale? Se sì hai finito, altrimenti esiste \((a',b')\notin\le'\); allora aggiungilo e prendi la chiusura transitiva...
Questa dimostrazione non va bene quando \(X\) è infinito, ma per te a un certo punto questa catena di estensioni deve fermarsi, perché devi terminare gli elementi di \(X\times X\) eventualmente non in \(\le\).
Una maniera più formale di ragionare è adattare l'idea del teorema di Szpilrajn, dicendo che se hai una coppia di elementi \((a,b)\) non in relazione li aggiungi a \(\le\) (considerato come sottoinsieme di \(X\times X\)) e prendi la chiusura transitiva \(\le'\) di \(\le\cup \{(a,b)\}\). Hai un ordine totale? Se sì hai finito, altrimenti esiste \((a',b')\notin\le'\); allora aggiungilo e prendi la chiusura transitiva...
Questa dimostrazione non va bene quando \(X\) è infinito, ma per te a un certo punto questa catena di estensioni deve fermarsi, perché devi terminare gli elementi di \(X\times X\) eventualmente non in \(\le\).
Esatto, stavo proprio cercando di dimostrare il teorema di Szpilrajn nel caso di ordini finiti.
Seguo il secondo approccio che mi hai suggerito (quello che hai definito più formale).
Parto da un ordine parziale $(X,\le)$.
Se questo è un ordine totale ho finito.
Altrimenti esiste $(x,y)\in X \times X$ tale che $(x,y) \notin \le$ e $(y,x) \notin \le$, in tal caso aggiungo la coppia ordinata $(x,y)$ alla relazione $\le$ (perdendo così la transitività di $\le$) e poi ripristino la transitività di $\le \cup \{(x,y)\}$ prendendone la chiusura transitiva.
Per prendere la chiusura transitiva di $\le \cup \{(x,y)\}$ aggiungo a $\le$ tutti gli elementi $(p,q)$ tali che $p\lex$ e $\y\le q$.
A questo punto se ho ottenuto un ordine totale ho finito, altrimenti ripeto il procedimento appena descritto ed entro un numero finito di iterazioni otterrò un ordine totale in quanto $X$ è finito.
Ho però due dubbi riguardanti la chiusura transitiva di $\le \cup \{(x,y)\}$:
Come posso essere sicuro che aggiungendo gli elementi $(p,q)$ tali che $p\lex$ e $\y\le q$ io non vada e perdere l'antiriflessività della relazione?
E come posso essere sicuro che una volta aggiunti questi elementi la proprietà transitiva sia ripristinata?
Seguo il secondo approccio che mi hai suggerito (quello che hai definito più formale).
Parto da un ordine parziale $(X,\le)$.
Se questo è un ordine totale ho finito.
Altrimenti esiste $(x,y)\in X \times X$ tale che $(x,y) \notin \le$ e $(y,x) \notin \le$, in tal caso aggiungo la coppia ordinata $(x,y)$ alla relazione $\le$ (perdendo così la transitività di $\le$) e poi ripristino la transitività di $\le \cup \{(x,y)\}$ prendendone la chiusura transitiva.
Per prendere la chiusura transitiva di $\le \cup \{(x,y)\}$ aggiungo a $\le$ tutti gli elementi $(p,q)$ tali che $p\lex$ e $\y\le q$.
A questo punto se ho ottenuto un ordine totale ho finito, altrimenti ripeto il procedimento appena descritto ed entro un numero finito di iterazioni otterrò un ordine totale in quanto $X$ è finito.
Ho però due dubbi riguardanti la chiusura transitiva di $\le \cup \{(x,y)\}$:
Come posso essere sicuro che aggiungendo gli elementi $(p,q)$ tali che $p\lex$ e $\y\le q$ io non vada e perdere l'antiriflessività della relazione?
E come posso essere sicuro che una volta aggiunti questi elementi la proprietà transitiva sia ripristinata?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo