CPO e omega-catene

[_tenebra]

Ciao a tutti! Sto seguendo un corso di Metodi Formali all'università e ci sono alcuni concetti base che non riesco a capire... Speravo che qualcuno potesse aiutarmi!

Per ora penso (e spero) di aver capito il concetto di ordinamento parziale e di minimo maggiorante (least upper bound) di [tex]X \subseteq P[/tex], con [tex](P, \sqsubseteq)[/tex] ordine parziale. Comincio però a perdermi nella definizione di [tex]\omega[/tex]-catene:

Sia [tex](D, \sqsubseteq)[/tex] un ordinamento parziale. Una [tex]\omega[/tex]-catena dell'ordinamento parziale è una catena crescente [tex]d_0 \sqsubseteq d_1 \sqsubseteq ... \sqsubseteq d_n \sqsubseteq ...[/tex] di elementi dell'ordinamento parziale.

Sul fatto che la catena sia infinita ci sono, ma gli elementi contenuti nella catena (senza ripetizioni) possono essere infiniti?

Poi da la definizione di ordine parziale completo (cpo):
L'ordinamento parziale [tex](D, \sqsubseteq)[/tex] è un ordinamento parziale completo se tutte le sue [tex]\omega[/tex]-catene [tex]d_0 \sqsubseteq d_1 \sqsubseteq ... \sqsubseteq d_n \sqsubseteq ...[/tex] hanno il least upper bound, cioè ogni catena crescente [tex]\{d_n | n \in \omega\}[/tex] di elementi in [tex]D[/tex] ha un minimo maggiorante[tex]\bigsqcup \{d_n | n \in \omega\}[/tex] in [tex]D[/tex], spesso indicato con [tex]\bigsqcup d_n , n \in \omega[/tex].

Cosa si intende per least upper bound di una [tex]\omega[/tex]-catena? Il least upper bound è l'elemento [tex]d_n[/tex] della [tex]\omega[/tex]-catena?

spero di essermi spiegato bene, ringrazio in anticipo per le risposte

[apatriarca]

Sul fatto che la catena sia infinita ci sono, ma gli elementi contenuti nella catena (senza ripetizioni) possono essere infiniti?

Intendi dire infiniti come numero? Se è così allora certamente ne puoi avere infiniti. In effetti è necessario che siano infiniti affinché la catena sia infinita (se no ci sarebbe un elemento \(d_n\) massimale nell'insieme che stabilizza la catena).

Cosa si intende per least upper bound di una \(ω\) -catena? Il least upper bound è l'elemento
\(d_n\) della \(ω\) -catena?

Io credo che si tratti di un qualche elemento \(d \in D,\) non necessariamente contenuto nella catena, per cui valgano le relazioni \( d_i \sqsubseteq d \) per ogni \( i \) e \( d \sqsubseteq d' \) per ogni altro \( d' \in D \) che soddisfi le stesse relazioni sui \( d_i. \) Ci sono comunque persone più esperte di me nel settore che ti sapranno dare una risposta più sicura.

[hamming_burst]

concordo con c'è che ha scritto apatriarca. Non c'è molto altro da aggiungere in merito a queste due domande.

"tenebra":Cosa si intende per least upper bound di una \(ω\) -catena? Il least upper bound è l'elemento
\(d_n\) della \(ω\) -catena?

l'elemento $d_n$ è il LUB della catena: è il suo limite (quando esiste ovviamente). Ricordandoti la definizione di LUB (che ti ha riproposto apatriarca). E' in pratica l'elemento su cui si stabilizza all'infinito la catena.

PS: utilizzi il Winskel scommetto.

[_tenebra]

Innanzitutto grazie a tutti per le risposte!
Ma quindi, quando esiste un LUB che permette alla catena di stabilizzarsi quest'ultima si stabilizza sempre?
Questo dubbio lo ho perché il professore a lezione ci ha detto che [tex](\mathbb{N},\leq)[/tex] non è un cpo (ovviamente, ci saranno le [tex]\omega[/tex]-catene contenenti elementi sempre crescenti senza fermarsi mai, quindi senza un LUB), mentre [tex](\mathbb{N} \cup \{\infty\},\leq)[/tex] lo è, dove [tex]\infty[/tex] è un elemento top che è stato aggiunto nell'ordinamento parziale [tex](\mathbb{N},\leq)[/tex].
Quello che non capisco è perché nell'ordinamento parziale [tex](\mathbb{N} \cup \{\infty\},\leq)[/tex] non possiamo avere le stesse [tex]\omega[/tex]-catene che ci sono in [tex](\mathbb{N},\leq)[/tex], semplicemente non considerando l'elemento [tex]\infty[/tex] (anche se è presente nell'ordine parziale)..
spero di nuovo di essermi spiegato bene

comunque si, ho il winskel

[hamming_burst]

"tenebra":
Ma quindi, quando esiste un LUB che permette alla catena di stabilizzarsi quest'ultima si stabilizza sempre?

riproponi questa domanda, cosa itendi con quello che ho sottolineato?

"tenebra":
Questo dubbio lo ho perché il professore a lezione ci ha detto che [tex](\mathbb{N},\leq)[/tex] non è un cpo (ovviamente, ci saranno le [tex]\omega[/tex]-catene contenenti elementi sempre crescenti senza fermarsi mai, quindi senza un LUB), mentre [tex](\mathbb{N} \cup \{\infty\},\leq)[/tex] lo è, dove [tex]\infty[/tex] è un elemento top che è stato aggiunto nell'ordinamento parziale [tex](\mathbb{N},\leq)[/tex].
Quello che non capisco è perché nell'ordinamento parziale [tex](\mathbb{N} \cup \{\infty\},\leq)[/tex] non possiamo avere le stesse [tex]\omega[/tex]-catene che ci sono in [tex](\mathbb{N},\leq)[/tex], semplicemente non considerando l'elemento [tex]\infty[/tex] (anche se è presente nell'ordine parziale)..

Certo il tuo docente ha ragione. La questione è il tipo di relazione d'ordine utilizzata.
- in questo caso è $<=$ quella classica per i numeri interi \(\{a \sqsubseteq b\ | \ a - se cambi relazione su $NN$ es. con la relazione d'identita oppure se aggiungi bottom $NN_\bot$ \(\{a \sqsubseteq b\ | \ a=b \vee a=\bot\}\) avrai un CPO chiamato flat (con minimo) dove tutti gli elementi sono inconfrontabili tranne che con bottom. Perciò avrai un'altra "definizione" di CPO su $NN$.

Prova a disegnarti il diagramma di Hasse di entrambi.

[apatriarca]

Credo che tu abbia frainteso il significato di LUB (che ti ho comunque riproposto nel mio precedente post). Un LUB può anche NON APPARTENERE alla catena. Il LUB è una specie di limite per le catene di questo tipo, un limite non molto diverso da quello che studi in analisi. Se hai una successione che ha un certo limite (pensa ad esempio a 1/x per x che tende a 0 con x che tende all'infinito..). Lo 0 non appartiene alla successione.