Poset localmente finiti e catene
Un poset $(P,<=)$ si dice localmente finito se ognuno degli intervalli $[a,b]={x\inP|a<=x<=b}$ è finito. Quello che mi stavo chiedendo è se questa condizione fosse o no equivalente alla seguente condizione: "ogni catena è isomorfa ad un sottoposet di $ZZ$".
Io ho provato a pensarci, ma in entrambi i casi se assumo una delle due condizioni non so come usare l'ipotesi quindi sono bloccato.
Ringrazio in anticipo chiunque risponderà.
Io ho provato a pensarci, ma in entrambi i casi se assumo una delle due condizioni non so come usare l'ipotesi quindi sono bloccato.
Ringrazio in anticipo chiunque risponderà.
Risposte
Sparo (a sale): \(\displaystyle\mathbb{Z}\times\mathbb{Z}\) con l'ordine lessicografico?
Di sicuro non è localmente finito, ma non soddisfa nemmeno l'altra condizione, infatti è totalmente ordinato ma non è isomorfo a un sottoposet di $ZZ$.
Non lo so, ma comincerei chiedendomi se ogni catena localmente finita è numerabile (credo che sia questo il punto). Cioè:
totalmente ordinato + localmente finito
implica numerabile?
Per caso hai una risposta a questo?
totalmente ordinato + localmente finito
implica numerabile?
Per caso hai una risposta a questo?
Mi sfugge quale sia il problema: forse ignoro un fatto fondamentale di teoria degli ordini?
Chiama \(\cal A\) la proprietà che ogni catena di \(P\) è order-isomorfa a un sotto-poset di \(\mathbb Z\); per mostrare che \(\cal A\) implica che \(P\) sia localmente finito, prendi un intervallo \(K\) di \(P\) della forma \([p,q]\); vuoi mostrare che è finito.
Per ipotesi, però, esso è order-isomorfo, diciamo mediante una funzione monotona e biiettiva \(\varphi\) a un sottoposet di \(\mathbb Z\), precisamente a \([\varphi(p),\varphi(q)]\) (l'immagine di catene è catena), e quest'ultimo è finito perché \(\mathbb Z\) è localmente finito. Quindi \(K\) è finito.
Al viceversa pensiamo se questo è giusto.
Chiama \(\cal A\) la proprietà che ogni catena di \(P\) è order-isomorfa a un sotto-poset di \(\mathbb Z\); per mostrare che \(\cal A\) implica che \(P\) sia localmente finito, prendi un intervallo \(K\) di \(P\) della forma \([p,q]\); vuoi mostrare che è finito.
Per ipotesi, però, esso è order-isomorfo, diciamo mediante una funzione monotona e biiettiva \(\varphi\) a un sottoposet di \(\mathbb Z\), precisamente a \([\varphi(p),\varphi(q)]\) (l'immagine di catene è catena), e quest'ultimo è finito perché \(\mathbb Z\) è localmente finito. Quindi \(K\) è finito.
Al viceversa pensiamo se questo è giusto.
"Martino":
totalmente ordinato + localmente finito
implica numerabile?
Non lo so, ma penso sia vero, ma non so dimostrarlo e in realtà non saprei nemmeno che farmene.
@killing_buddha Non è detto che gli intervalli siano totalmente ordinati (se non ho capito male tu lo assumi).
Lemma. Un poset P totalmente ordinato localmente finito è isomorfo a un sottoposet di $ZZ$.
Dimostrazione. L'idea è definire il successore $s(x)$ di un elemento $x$ di P (che non sia il massimo di P) come un $y$ tale che $[x,y]={x,y}$, dopo aver dimostrato che questo ha senso, e analogamente il predecessore $p(x)$ quando $x$ non è il minimo di P. Poi bisogna giocare un po' con $s$ e $p$.
Usando il lemma è immediato che in un poset localmente finito ogni catena è isomorfa a un sottoposet di $ZZ$.
Dimostrazione. L'idea è definire il successore $s(x)$ di un elemento $x$ di P (che non sia il massimo di P) come un $y$ tale che $[x,y]={x,y}$, dopo aver dimostrato che questo ha senso, e analogamente il predecessore $p(x)$ quando $x$ non è il minimo di P. Poi bisogna giocare un po' con $s$ e $p$.
Usando il lemma è immediato che in un poset localmente finito ogni catena è isomorfa a un sottoposet di $ZZ$.
Poi se prendiamo l'intervallo usuale P=[0,1] e gli diamo l'ordine per cui ogni $x in (0,1)$ è comparabile solo con se stesso e $0 le x le 1$ per ogni $x in P$ allora questo P non è localmente finito (ha minimo e massimo) ma le catene di P sono tutte finite (hanno cardinalità al massimo 3) quindi sono tutte isomorfe a sottoposet di $ZZ$.
Poco dopo che avevo dato la mia risposta mi era venuta in mente un'idea ragionando sul primo post di Martino, ma era fuori e non potevo scriverla, lo faccio ora.
Sostanzialmente quello a cui ho pensato è una dimostrazione del lemma detto da Martino (un po' diversa dalla sua):
A questo punto basta notare che essere localmente finito è una proprietà che passa ai sottoposet per concludere un verso dell'equivalenza che avevo in mente.
Ma l'altro verso non vale per il controesempio fornito da Martino (che si può generalizzare un pochino prendendo un qualsiasi insieme infinito come anticatena e aggiungendoci un massimo e un minimo).
Sostanzialmente quello a cui ho pensato è una dimostrazione del lemma detto da Martino (un po' diversa dalla sua):
Dimostrazione: Sia $S$ una catena localmente finita, se $S=\emptyset$ la tesi è soddisfatta, se invece $S!=\emptyset$, sia $x\inS$, ora mi metto a definire $\phi:P->ZZ$. Sia $y\inS$, allora uno degli insiemi $[x,y]$ e $[y,x]$ è non vuoto, allora $\phi(y)={(|\text([)a,b\text(])|-1, if [x,y]!=\emptyset),(1-|\text([)a,b\text(])|, if [y,x]!=\emptyset):}$ dove con $|X|$ indico la cardinalità di $X$.
Bisogna innanzitutto verificare che sia ben definita, cioè verificare che se entrambi gli intervalli sono non vuoti il valore della funzione non dipende dalla scelta dell'intervallo che si usa per calcolare la funzione, ma se sono entrambi non vuoti vuol dire che $EEz_1,z_2$ t.c. $y<=z_1<=x<=z_2<=y=>x=y$, quindi $[x,y]=[y,x]={x}$ quindi $\phi(y)=0$ in entrambi i modi si voglia calcolare.
Inoltre $y<=z<=>\phi(y)<=\phi(z)$, che è abbastanza banale, solo che è un po' palloso perché bisogna distinguere i casi $x<=y<=z, y<=x<=z, y<=z<=x$, quindi conserva e riflette l'ordine, quindi è un isomorfismo con l'immagine, che è un sottoposet di $ZZ$.
A questo punto basta notare che essere localmente finito è una proprietà che passa ai sottoposet per concludere un verso dell'equivalenza che avevo in mente.
Ma l'altro verso non vale per il controesempio fornito da Martino (che si può generalizzare un pochino prendendo un qualsiasi insieme infinito come anticatena e aggiungendoci un massimo e un minimo).
A me è venuto in mente questo esempio:
\[
S=\mathbb{R}\times\{1,2\},\,(x,a)\leq(y,b)\iff a\leq b,x=y;
\]
allora \(\displaystyle S\) è un poset, tutte le sue catene hanno lunghezza al più \(\displaystyle2\), ovvero è localmente finito, ma non è un insieme numerabile.
Ho sbagliato?
\[
S=\mathbb{R}\times\{1,2\},\,(x,a)\leq(y,b)\iff a\leq b,x=y;
\]
allora \(\displaystyle S\) è un poset, tutte le sue catene hanno lunghezza al più \(\displaystyle2\), ovvero è localmente finito, ma non è un insieme numerabile.
Ho sbagliato?
Armando, localmente finito non significa che ogni catena è finita, significa che ogni intervallo è finito (catena e intervallo sono cose diverse). Comunque il tuo sarebbe un controesempio a cosa? Io chiedevo se totalmente ordinato e localmente finito implica numerabile, ma il tuo S non è totalmente ordinato.
@otta96 Non ho ancora letto il tuo intervento, ma più tardi lo leggo!
@otta96 Non ho ancora letto il tuo intervento, ma più tardi lo leggo!
Se fosse totalmente ordinato sarebbe un controesempio, ma non lo è.
"Martino":Questo non lo sapevo; e 'stanotte, causa caldo torrido (non scherzo), avevo pensato (tra le altre cose) a questa affermazione:
Armando, localmente finito non significa che ogni catena è finita, significa che ogni intervallo è finito (catena e intervallo sono cose diverse)...
parzialmente ordinato + localmente finito => numerabile.
@Armando: ok!
@otta96: sì, concordo. Forse è ancora più chiaro definire una distanza $d(x,y)$ come [tex]|[x,y]|-1[/tex] se $x le y$ e come [tex]|[y,x]|-1[/tex] se $x ge y$. Si mostra che è una distanza e poi si conclude come hai fatto tu.
@otta96: sì, concordo. Forse è ancora più chiaro definire una distanza $d(x,y)$ come [tex]|[x,y]|-1[/tex] se $x le y$ e come [tex]|[y,x]|-1[/tex] se $x ge y$. Si mostra che è una distanza e poi si conclude come hai fatto tu.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo