Fattorizzazione unica nei reticoli?
Sia qui e nel seguito [tex](S,\le)[/tex] un reticolo ordinato e siano [tex]\wedge, \lor : S \times S \to S[/tex] le operazioni definite da [tex]a \wedge b := \inf \{a,b\}[/tex], [tex]a \lor b := \sup \{a,b\}[/tex].
Definizione. Diciamo che [tex]p \in S[/tex] è un elemento primo se ogni volta che [tex]a \lor b = p[/tex] allora [tex]a = p[/tex] oppure [tex]b = p[/tex].
Definizione. Sia [tex]A \subseteq S[/tex] un sottoinsieme di [tex]S[/tex]. Diciamo segmento inferiore generato da [tex]A[/tex] l'insieme [tex]S_A := \{x \in S : \: x \le a \: \forall a \in A\}[/tex].
Definizione. Diciamo che un reticolo [tex](S,\le)[/tex] è inferiormente finito se per ogni [tex]A \subseteq S[/tex] finito, il segmento inferiore [tex]S_A[/tex] è ancora un insieme finito.
Prove it! Sia [tex](S,\le)[/tex] un reticolo inferiormente finito e distributivo. Allora ogni elemento ammette un'unica decomposizione in join di primi non confrontabili, ossia ogni elemento [tex]a \in S[/tex] può essere scritto come [tex]a = p_1 \lor p_2 \lor \ldots \lor p_k[/tex] dove i [tex]p_k[/tex] sono primi a due a due non confrontabili tra di loro e inoltre se [tex]p_1 \lor p_2 \lor \ldots \lor p_k = q_1 \lor q_2 \lor \ldots \lor q_h[/tex], con i [tex]q_h[/tex] primi, allora [tex]h = k[/tex] e, a meno di un riordinamento, [tex]p_i = q_i[/tex] per ogni [tex]1 \le i \le k[/tex].
Bonus question. Provare che questo risultato è una generalizzazione del [url=http://it.wikipedia.org/wiki/Teorema_fondamentale_dell'aritmetica]teorema fondamentale dell'aritmetica[/url].
Note. i) Il problema mi è stato sottoposto da un mio amico. La fonte è questa (pagina 16, esercizio 4). Quello che ho proposto qui non è l'esercizio proposto del testo, ma un lemma che ho usato per la dimostrazione. Tuttavia, ritengo di interesse maggiore il lemma che non l'esercizio.
ii) Ho liberamente tradotto con "primo" la parola inglese join irreducible, perché mi sembra che il calco italiano suoni male e sia meno opportuno in questo contesto.
Enjoy!
Definizione. Diciamo che [tex]p \in S[/tex] è un elemento primo se ogni volta che [tex]a \lor b = p[/tex] allora [tex]a = p[/tex] oppure [tex]b = p[/tex].
Definizione. Sia [tex]A \subseteq S[/tex] un sottoinsieme di [tex]S[/tex]. Diciamo segmento inferiore generato da [tex]A[/tex] l'insieme [tex]S_A := \{x \in S : \: x \le a \: \forall a \in A\}[/tex].
Definizione. Diciamo che un reticolo [tex](S,\le)[/tex] è inferiormente finito se per ogni [tex]A \subseteq S[/tex] finito, il segmento inferiore [tex]S_A[/tex] è ancora un insieme finito.
Prove it! Sia [tex](S,\le)[/tex] un reticolo inferiormente finito e distributivo. Allora ogni elemento ammette un'unica decomposizione in join di primi non confrontabili, ossia ogni elemento [tex]a \in S[/tex] può essere scritto come [tex]a = p_1 \lor p_2 \lor \ldots \lor p_k[/tex] dove i [tex]p_k[/tex] sono primi a due a due non confrontabili tra di loro e inoltre se [tex]p_1 \lor p_2 \lor \ldots \lor p_k = q_1 \lor q_2 \lor \ldots \lor q_h[/tex], con i [tex]q_h[/tex] primi, allora [tex]h = k[/tex] e, a meno di un riordinamento, [tex]p_i = q_i[/tex] per ogni [tex]1 \le i \le k[/tex].
Bonus question. Provare che questo risultato è una generalizzazione del [url=http://it.wikipedia.org/wiki/Teorema_fondamentale_dell'aritmetica]teorema fondamentale dell'aritmetica[/url].
Note. i) Il problema mi è stato sottoposto da un mio amico. La fonte è questa (pagina 16, esercizio 4). Quello che ho proposto qui non è l'esercizio proposto del testo, ma un lemma che ho usato per la dimostrazione. Tuttavia, ritengo di interesse maggiore il lemma che non l'esercizio.
ii) Ho liberamente tradotto con "primo" la parola inglese join irreducible, perché mi sembra che il calco italiano suoni male e sia meno opportuno in questo contesto.
Enjoy!
Risposte
umm cosa intendi con "unica"? perchè ad esempio se ho una catena,tutti gli elemnti sono primi; e io posso scrivere un'elemento $p$ come $p=$[tex]p \lor p_1 \lor p_2 \lor \ldots \lor p_k[/tex] ma anche come [tex]a = p \lor p_1 \lor p_2 \lor \ldots \lor p_q[/tex] con $q
so che la mia è un po una gabola,ma potresti comunque dare una definizione precisa di "fattorizzazione unica"?
so che la mia è un po una gabola,ma potresti comunque dare una definizione precisa di "fattorizzazione unica"?
ok,forse ho una dimostrazione dell'esistenza della scomposizione(mi manca ancora la parte difficile,cioè l'unicità)
dico forse perchè utilizzo una tecnica molto contestabile,anche se a me pare corretta,una specie di induzione strana.
infatti farò vedere che l'asserzione vale per il minimo di $S$,dopodichè farò vedere che se vale per ogni $x
allora innanzitutto dico che $S$ ammette minimo. infatti consideriamo un elemento $a$ e l'insieme $A={a}$
supponiamo che [tex]S_A[/tex] sia non vuoto(se è vuoto $a$ è un'elemento minimale e dopo farò vedere che in un reticolo questo coincide con l'essere minimo).
per ipotesi è finito,quindi posso calcolarne l'inf(in un reticolo esiste l'inf e il sup di ogni sottoinsieme finito). questo inf sarà un'elemento $c$ minore di $a$ per transitività($c$ è minore di ogni x che appartiene a [tex]S_A[/tex] che è a sua volta minore di $a$)
quindi $c$ appartiene ad [tex]S_A[/tex] e in particolare è il minimo dell'insieme.
ma $c$ è anche un elemento minimale di $S$; sia infatti $x<=c$ ottengo per transitività $x<=a$ e quindi $x$ appartiene a [tex]S_A[/tex] e quindi $c<=x$ e quindi $c=x$. ma in un reticolo un elemento minimale è un minimo; sia infatti $m$ elemento minimale e consideriamo inf$(x,m)=y$ per ogni $x$;abbiamo $y<=m$ e quindi $y=m$. quindi per ogni $x$ inf$(m,x)=m$ e quindi $m$ è un minimo di $S$.
sia ora $m$ il minimo di $S$. esso è banalmente primo(sup$(a,b)=m$ implica $a=b=m$),quindi puo essere banalmente rappresentato come join di primi.
sia ora $a$ un elemento di $S$,supponiamo che ogni $x<=a$ con $x!=a$ sia scomponibile in join di un numero finito di primi.
supponiamo che $a$ non sia primo(o l'asserzione vale banalmente come valeva per $m$); allora esistono $b,c$ diversi da $a$ tali che [tex]a=c \lor b[/tex]
ma quindi per $b$ e $c$ vale l'ipotesi induttiva,cioè posso scrivere [tex]b = p_1 \lor p_2 \lor \ldots \lor p_k[/tex] e [tex]c = q_1 \lor q_2 \lor \ldots \lor q_n[/tex].
ma essendo il sup associativo,[tex]a=c \lor b[/tex] implica [tex]a = p_1 \lor p_2 \lor \ldots \lor p_k \lor q_1 \lor q_2 \lor \ldots \lor q_n[/tex].
e quindi $a$ è scomponibile in join di primi.
spero che sia tutto corretto;per l'unicita mi servirebbe innanzitutto la definizione formale,e magari un suggerimento su come usare l'ipotesi di distributività..
dico forse perchè utilizzo una tecnica molto contestabile,anche se a me pare corretta,una specie di induzione strana.
infatti farò vedere che l'asserzione vale per il minimo di $S$,dopodichè farò vedere che se vale per ogni $x
allora innanzitutto dico che $S$ ammette minimo. infatti consideriamo un elemento $a$ e l'insieme $A={a}$
supponiamo che [tex]S_A[/tex] sia non vuoto(se è vuoto $a$ è un'elemento minimale e dopo farò vedere che in un reticolo questo coincide con l'essere minimo).
per ipotesi è finito,quindi posso calcolarne l'inf(in un reticolo esiste l'inf e il sup di ogni sottoinsieme finito). questo inf sarà un'elemento $c$ minore di $a$ per transitività($c$ è minore di ogni x che appartiene a [tex]S_A[/tex] che è a sua volta minore di $a$)
quindi $c$ appartiene ad [tex]S_A[/tex] e in particolare è il minimo dell'insieme.
ma $c$ è anche un elemento minimale di $S$; sia infatti $x<=c$ ottengo per transitività $x<=a$ e quindi $x$ appartiene a [tex]S_A[/tex] e quindi $c<=x$ e quindi $c=x$. ma in un reticolo un elemento minimale è un minimo; sia infatti $m$ elemento minimale e consideriamo inf$(x,m)=y$ per ogni $x$;abbiamo $y<=m$ e quindi $y=m$. quindi per ogni $x$ inf$(m,x)=m$ e quindi $m$ è un minimo di $S$.
sia ora $m$ il minimo di $S$. esso è banalmente primo(sup$(a,b)=m$ implica $a=b=m$),quindi puo essere banalmente rappresentato come join di primi.
sia ora $a$ un elemento di $S$,supponiamo che ogni $x<=a$ con $x!=a$ sia scomponibile in join di un numero finito di primi.
supponiamo che $a$ non sia primo(o l'asserzione vale banalmente come valeva per $m$); allora esistono $b,c$ diversi da $a$ tali che [tex]a=c \lor b[/tex]
ma quindi per $b$ e $c$ vale l'ipotesi induttiva,cioè posso scrivere [tex]b = p_1 \lor p_2 \lor \ldots \lor p_k[/tex] e [tex]c = q_1 \lor q_2 \lor \ldots \lor q_n[/tex].
ma essendo il sup associativo,[tex]a=c \lor b[/tex] implica [tex]a = p_1 \lor p_2 \lor \ldots \lor p_k \lor q_1 \lor q_2 \lor \ldots \lor q_n[/tex].
e quindi $a$ è scomponibile in join di primi.
spero che sia tutto corretto;per l'unicita mi servirebbe innanzitutto la definizione formale,e magari un suggerimento su come usare l'ipotesi di distributività..
Ho editato il testo dell'esercizio, così dovrebbe essere a prova di fraintendimento.
Beh, per come ho definito il segmento inferiore, [tex]S_{\{a\}} = \{b \in S \mid b \le a\}[/tex] e quindi [tex]a \in S_{\{a\}}[/tex]. Quindi [tex]S_A[/tex], in questo caso, è banalmente non vuoto.
Il ragionamento sembrerebbe filare. Temo, però, che perché la tua prova possa essere considerata valida in assoluta generalità, occorra ricorrere all'induzione transfinita (e quindi all'assioma della scelta). Forse in questo modo potremmo anche rimuovere l'ipotesi di inferiore finitezza; purtroppo non sono un esperto di teoria assiomatica degli insiemi...
L'ipotesi di inferiore finitezza serviva appunto a rimuovere questa difficoltà. La dimostrazione che ho dato io di questo risultato utilizza solo l'induzione classica, di Peano; ti invito a provare a fare un tentativo in quetsa direzione.
Poi, per essere pignoli
Dovresti provare per lo meno che i primi non sono confrontabili, in accordo al nuovo enunciato (questa è davvero una sciocchezza).
Per quanto riguarda l'hint, temo che direi tutto. Davvero, la distributività è la chiave, ma basta la definizione.
"paolo.papadia":
[...] infatti consideriamo un elemento $a$ e l'insieme $A={a}$
supponiamo che [tex]S_A[/tex] sia non vuoto(se è vuoto $a$ è un'elemento minimale e dopo farò vedere che in un reticolo questo coincide con l'essere minimo).
[...]
Beh, per come ho definito il segmento inferiore, [tex]S_{\{a\}} = \{b \in S \mid b \le a\}[/tex] e quindi [tex]a \in S_{\{a\}}[/tex]. Quindi [tex]S_A[/tex], in questo caso, è banalmente non vuoto.
Il ragionamento sembrerebbe filare. Temo, però, che perché la tua prova possa essere considerata valida in assoluta generalità, occorra ricorrere all'induzione transfinita (e quindi all'assioma della scelta). Forse in questo modo potremmo anche rimuovere l'ipotesi di inferiore finitezza; purtroppo non sono un esperto di teoria assiomatica degli insiemi...
L'ipotesi di inferiore finitezza serviva appunto a rimuovere questa difficoltà. La dimostrazione che ho dato io di questo risultato utilizza solo l'induzione classica, di Peano; ti invito a provare a fare un tentativo in quetsa direzione.
Poi, per essere pignoli
"paolo.papadia":
[...] ma essendo il sup associativo,[tex]a = c \lor b[/tex] implica [tex]a = p_1 \lor p_2 \lor \ldots \lor p_k \lor q_1 \lor q_2 \lor \ldots \lor q_n[/tex] e quindi [tex]a[/tex] è scomponibile in join di primi.
Dovresti provare per lo meno che i primi non sono confrontabili, in accordo al nuovo enunciato (questa è davvero una sciocchezza).
Per quanto riguarda l'hint, temo che direi tutto. Davvero, la distributività è la chiave, ma basta la definizione.
Ok, il ragionamento proposto da paolo.papadia effettivamente funziona, anche se andrebbe ancora leggermente riformulato. Si può effettivamente abbandonare l'ipotesi di inferiore finitezza e sostituirlo con la più debole condizione della catena discendente, a patto naturalmente di riporre la fede nell'assioma della scelta (ma direi che a questo punto non ci facciamo più problemi!)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo