Elemento massimale in un insieme parzialmente ordinato
Dimostrare in modo formale (rigoroso) che se X è un insieme finito parzialmente ordinato allora ha un elemento massimale.
Grazie.
Grazie.
Risposte
Ciao,
te come inizieresti?
te come inizieresti?
Prendo un elemento \(\displaystyle a \) dell'insieme e cerco se ce ne è uno maggiore ad esso se lo trovo, prendo in considerazione quest'ultimo e vado avanti vado, altrimenti \(\displaystyle a \) è massimale. Il processo ha termine perchè X è finito.
Vorrei che qualcuno mi formalizasse questo ragionamento in modo rigoroso o desse anche un'altra dimostrazione formale.
Grazie.
Vorrei che qualcuno mi formalizasse questo ragionamento in modo rigoroso o desse anche un'altra dimostrazione formale.
Grazie.
Il ragionamento si formalizza con l'induzione sul numero degli elementi di X.
Qualcuno ha qualche altra dimostrazione?
Qualcuno ha qualche altra dimostrazione?
Vale il Principio di Massimalità di Hausdorff:
Sia \(X\) una famiglia totalmente ordinata massimale del tuo insieme \(\Omega\); dato che \(\Omega\) è finito, \(X\) è finita, dunque è dotata di massimo e minimo; in particolare, il massimo di \(X\) è un elemento massimale in \(\Omega\).
In ogni insieme parzialmente ordinato esiste almeno una famiglia totalmente ordinata massimale.
Sia \(X\) una famiglia totalmente ordinata massimale del tuo insieme \(\Omega\); dato che \(\Omega\) è finito, \(X\) è finita, dunque è dotata di massimo e minimo; in particolare, il massimo di \(X\) è un elemento massimale in \(\Omega\).
Cosa intendi per "famiglia totalmente ordinata massimale " una famiglia di sottoinsiemi? In che senso un insieme è massimale?
Sia \((\Omega ,\leq )\) un insieme parzialmente ordinato.
Chiaramente anche \((\mathcal{P} (\Omega), \subseteq)\) è un insieme parzialmente ordinato, indipendentemente dal fatto che sia definita una struttura d'ordine su \(\Omega\).
Un insieme \(C\subseteq \Omega\)non vuoto è detto totalmente ordinato da \(\leq\) se e solo se la restrizione di \(\leq\) a \(C\) è una relazione d'ordine totale (in tal caso si dice pure che \(C\) è una catena).
Il Principio di Massimalità di Hausdorff si può enunciare come segue:
Ora, prendiamo un elemento \(\omega \in \Omega\) e consideriamo la parte non vuota \(C:=\{\omega\}\subseteq \Omega\); chiaramente \(C\) è totalmente ordinata da \(\leq\) (avendo un solo elemento!), dunque per il Principio di Massimalità esiste un insieme \(X\subseteq \Omega\) che soddisfi le 1-3, cioè \(X\) è un insieme totalmente ordinato contenente \(C\) massimale in \(\mathcal{P}(\Omega)\).
Ora, per andare avanti dobbiamo usare necessariamente il fatto che \(\Omega\) è finito.
Essendo \(\Omega\) finito, l'insieme \(X\) è necessariamente finito.
Essendo \(X\) totalmente ordinato e finito, esso è dotato di massimo: poniamo perciò \(x^*=\max X\).
Quello che vogliamo fare, adesso, è mostrare che \(x^*\) è un elemento massimale in \(\Omega\).
Chiaramente, se \(x\in X\), allora \(x\leq x^*\); quindi, per acquisire la massimalità di \(x^*\), basta dimostrare che se \(x\in \Omega \setminus X\) allora o si ha \(x\leq x^*\) oppure \(x\) ed \(x^*\) non sono confrontabili rispetto a \(\leq \).
Per fare ciò, basta mostrare che se \(x\in \Omega \setminus X\) non si può avere \(x\geq x^*\).
Dim.:
Conseguentemente \(x^*\) è massimale in \(\Omega\).
Chiaramente anche \((\mathcal{P} (\Omega), \subseteq)\) è un insieme parzialmente ordinato, indipendentemente dal fatto che sia definita una struttura d'ordine su \(\Omega\).
Un insieme \(C\subseteq \Omega\)non vuoto è detto totalmente ordinato da \(\leq\) se e solo se la restrizione di \(\leq\) a \(C\) è una relazione d'ordine totale (in tal caso si dice pure che \(C\) è una catena).
Il Principio di Massimalità di Hausdorff si può enunciare come segue:
Comunque si fissi un insieme \(C\subseteq \Omega\) totalmente ordinato da \(\leq\), esiste un insieme \(X\subseteq \Omega\) tale che:
[list=1] [*:3boqcw7j] \(X\) è totalmente ordinato da \(\leq\),
[/*:m:3boqcw7j]
[*:3boqcw7j] \(C\subseteq X\),
[/*:m:3boqcw7j]
[*:3boqcw7j] \(X\) è una parte massimale contenente \(C\) in \((\mathcal{P}(\Omega), \subseteq )\) (nel senso che, per ogni altro \(Y\subseteq \Omega \) contenente \(C\), allora o è \(Y\subseteq X\) oppure \(X\) ed \(Y\) non sono confrontabili rispetto a \(\subseteq\)).[/*:m:3boqcw7j][/list:o:3boqcw7j]
Ora, prendiamo un elemento \(\omega \in \Omega\) e consideriamo la parte non vuota \(C:=\{\omega\}\subseteq \Omega\); chiaramente \(C\) è totalmente ordinata da \(\leq\) (avendo un solo elemento!), dunque per il Principio di Massimalità esiste un insieme \(X\subseteq \Omega\) che soddisfi le 1-3, cioè \(X\) è un insieme totalmente ordinato contenente \(C\) massimale in \(\mathcal{P}(\Omega)\).
Ora, per andare avanti dobbiamo usare necessariamente il fatto che \(\Omega\) è finito.
Essendo \(\Omega\) finito, l'insieme \(X\) è necessariamente finito.
Essendo \(X\) totalmente ordinato e finito, esso è dotato di massimo: poniamo perciò \(x^*=\max X\).
Quello che vogliamo fare, adesso, è mostrare che \(x^*\) è un elemento massimale in \(\Omega\).
Chiaramente, se \(x\in X\), allora \(x\leq x^*\); quindi, per acquisire la massimalità di \(x^*\), basta dimostrare che se \(x\in \Omega \setminus X\) allora o si ha \(x\leq x^*\) oppure \(x\) ed \(x^*\) non sono confrontabili rispetto a \(\leq \).
Per fare ciò, basta mostrare che se \(x\in \Omega \setminus X\) non si può avere \(x\geq x^*\).
Dim.:
Conseguentemente \(x^*\) è massimale in \(\Omega\).
Ok, il principio di Hausdorff usa l'assioma di scelta per essere dimostrato? Sarebbe interessante trovare dimostrazioni, del problema posto, che non ne fanno uso.
Comunque non conoscevo questo interessante teorema.
Comunque non conoscevo questo interessante teorema.
"gianni80":
Ok, il principio di Hausdorff usa l'assioma di scelta per essere dimostrato?
Il PMH è equivalente ad AC, se non erro.
"gianni80":
Sarebbe interessante trovare dimostrazioni, del problema posto, che non ne fanno uso.
La dimostrazione algoritmica che hai pensato non usa AC.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo