Reticoli e relazione d'ordine

[Overflow94]

1) If $≤$ is a partial order on a set $A$, show that there is a total order $ <=^(**) $ on $A$ such that $a ≤ b => a <=^(**) b$. (Hint: Use Zorn’s lemma.)

2) If $L$ is a lattice we say that an element $a in L$ is join irreducible if $ a=b vv c $ implies $a = b$ or $a = c$. If $L$ is a finite lattice show that every element is of the form $a_1 vv ··· vv a_n$, where each $a_i$ is join irreducible.

Se conoscete la soluzione o come impostarla grazie in anticipo.

[solaàl]

Beh, come pensi di usare il lemma di Zorn? Solitamente esso dimostra cose del tipo: sia $P$ una proprietà parametrica nell'insieme $A$; nell'insieme dei sottoinsiemi di $A$ tali che $P$, ogni catena ammette un massimale; allora quell'insieme ammette un massimale. Ma ora il massimale deve essere $A$, altrimenti (per assurdo) ci sarebbe qualcosa tra il massimale ed $A$.

Qui l'insieme è quello dei \(B \subseteq A\) tali che $B$ è totalmente ordinato, diciamo da \(\preceq\), e se $x \le y$ allora \(x \preceq y\). Ma qual è l'ordine da mettere sull'insieme di questi $B$?

[Overflow94]

Per l'(1) non riesco a formulare un ordine \( \preceq \) che mi permetta di applicare in modo così immediato il lemma di Zorn.

Un po' di pensieri sparsi...

Allora consideriamo l'insieme delle catene di $A$, ovvero $ \mathcal(C)={C in \mathcal(P)(A) | C \ \ è \ \ una \ \ catena \ \ rispe\t\t\o \ \ a <=} $. Se definiamo una relazione d'ordine su questo insieme secondo $ sube $ per il lemma di Zorn ammette un massimale, che chiameremo una catena massimale di $A$.

Definiamo con $\mathcal(M)$ l'insieme delle catene massimali di $A$ che abbiamo dimostrato non vuoto. Adesso vogliamo dimostrare che $\bigcup_(M in \mathcal(M)) M = A$. Ogni elemento $x in A$ appartiene ad una catena di $A$, per esempio $C={a in A| a<=x}$. L'insieme delle catene che contengono $x$ è parzialmente ordinato con l'inclusione e ammette un massimale, questo massimale è anche una catena massimale di $A$ e quindi appartiene ad $\mathcal(M)$, viceversa si otterrebbe un assurdo.

Definiamo una relazione di equivalenza su $\mathcal(M)$, ovvero $ M~C $ se $M \cap C != \emptyset$. La relazione è banalmente riflessiva e simmetrica, dobbiamo dimostrare che è transitiva. Se $x in M \cap C$ e $y in C \cap D$ allora $z=min{x, y} in M \cap D$. EDIT: dopo aver finito di scrivere tutto mi son reso conto che questo è falso e non è una relazione d'equivalenza, avevo in mente il caso particolare in cui $A$ sia un lattice...

Alla partizione di catene massimali corrisponde anche una partizione di $A$, elementi appartenenti a due classi differenti non sono paragonabili secondo $<=$ e possiamo estendere la relazione d'ordine in modo arbitrario. Scegliamo una classe $C_1$ e definiamo tutte i suoi elementi maggiori secondo $>=^(*)$ di tutti gli elementi in $A-C_1$, poi scegliamo una classe rimanente e definiamo tutti i suoi elementi maggiori di quelli in $A-C_1-C_2$ e così via. L'assioma della scelta dovrebbe rendere formalmente corretto questo procedimento.

A questo punto rimangono da trattare gli elementi che appartengono alla stessa partizione. Se tutte le partizioni avessero un minimo e l'ordine fosse discreto (intendo che tra $a$ e $b$ comparabili ci deve essere un numero finito di elementi). Si potrebbe rappresentare ogni partizione come un grafo diretto con il minimo come radice e si potrebbe risolvere ordinando arbitrariamente i nodi che appaiono allo stesso livello. Devo ancora gestire il continuum e la possibilità che non esista il minimo.

[solaàl]

Prova a definire un ordine parziale sull'insieme \(\mathcal B\) di quei \(B\subseteq A\) tali che

1. \(B\) è totalmente ordinato da una relazione \(\preceq_B\) (tecnicamente quindi l'insieme è quello delle coppie \((B,\preceq_B)\))
2. Se \(x \le y\) per due elementi di \(B\), allora \(x \preceq_B y\).

L'ordine parziale è quello che dice che \((B, \preceq_B) \lhd (C, \preceq_C)\) se \(B \subseteq C\) e \(\preceq_B\) è un sottoinsieme di \(\preceq_C\) (questa cosa significa una cosa sola). Ora, usa il lemma di Zorn su \((\mathcal B,\lhd)\). Ogni catena qui ha un massimale; allora c'è un massimale; supponi che non sia $A$... assurdo!

[Overflow94]

Ok adesso ho capito, grazie mille

Come hai detto te l'ordine parziale è \( (B, \preceq_B) \lhd (C, \preceq_C) \) se $B sube C$ e $\preceq_B$ è una restrizione di $\preceq_C$ su $B$. Presa una catena vediamo che l'unione di tutti i suoi elementi ne costituisce un'upper bound e quindi per il lemma di Zorn l'insieme \( \mathcal B \) ammette un massimale $(M, \preceq_M)$.

Ora supponiamo che esista $ x !in M $ e consideriamo $ U=Muu{x} $. Definiamo su $U$ l'ordine $\preceq_U$ come $a \preceq_U b$ se $a \preceq_M b$ per $a,b!=x$. Per $x$ invece consideriamo $O={a in M| a \preceq_M s vv s <= x}$ e definiamo $ a \preceq_U x \ \ AAainO $ e $ x \preceq_U b \ \ AAbinU-O $.

L'insieme $U$ è ben ordinato, $M sube U$ e $\preceq_M$ è una restrizione di $\preceq_U$, quindi è un assurdo. Allora deve necessariamente essere $M = A$ e quindi $A$ è ben ordinato da $\preceq_M$.

[Overflow94]

Mi è venuta una soluzione per il (2).

Sia $L$ un reticolo con un numero finito di elementi. Dimostriamo che ogni suo elemento $r$ può essere scritto come join di elementi irriducibili.

Se $r$ è irriducibile $r=r$ e abbiamo finito. Se $r$ non è join irriducibile possiamo scrivere $r=r_1 vv r_2$, e proseguire in modo ricorsivo su $r_1$ e $r_2$ . Dobbiamo dimostrare che questo processo termina dopo un numero finito di passi.

Ad ogni sequenza di split possiamo associare una successione di elementi di $L$, per esempio $r, r_1, r_(1,1) ...$, dimostreremo che ad ogni successione è associata una successione decrescente di interi positivi.

A partire dalla mappa $r->{kinL|k<=r}$, associamo ad ogni $r$ la cardinalità della sua immagine: $N(r)=|{kinL|k<=r}|$. Poiché $L$ è finito $N(r) in NN$.

Siano $r_1$ un elemento di una successione di split e $r_2$ il suo successore:

$r_1 = r_2 vv d$ con $r_1!=r_2 => r_1 > r_2 => {kinL|k<=r_2} sub {kinL|k<=r_1}$

Ne segue che $N(r_1)>N(r_2)$ completando la dimostrazione.

[Overflow94]

Un altro esercizio sui reticoli.

If $L$ is a finite lattice let $J(L)$ be the poset of join irreducible elements of $L$, where $a ≤ b$ in $J(L)$ means $a ≤ b$ in $L$. Show that if $L$ is a finite distributive lattice then $L$ is isomorphic to $L(J(L))$, the lattice of nonempty lower segments of $J(L)$. Hence a finite lattice is distributive if and only if it is isomorphic to some $L(P)$, for $P$ a finite poset with least element. (This will be used to show the theory of distributive lattices is undecidable.)