Ordinamento parziale di funzioni totali.
Ciao a tutti,
ho il seguente Ordine Parziale $(N \to N_\bot, <=_\to)$ i cui elementi sono funzioni totali da $N$ a $N_\bot$
con l'ordinamento $f <=_\to g$ $=> AA x in dom(f) : f(x) <=g(x) $
dove
$N$ rappresenta l'insieme dei naturali senza alcuna relazione d'ordine
$N_\bot$ è l'insieme $Nuu{\bot}$ con l'ordinamento $\bot<=n$, per ogni n $in N$
L'ordinamento parziale $(N \to N_\bot, <=_\to)$ è un $CPO$ (complete partial order) ma non un reticolo.
Per ognuna delle definizioni seguenti, devo definire la più piccola funzione in $(N \to N_\bot , <=_\to)$ che le soddisfa:
(a) $f(x)={(2,if x=1),(f (x-2 ),if x>1):}$
(b) $g(x)={(2,if x>=2 text{ e x pari} ),(g (1),if text{x dispari}):}$
(c) $h(x)={(2,if x=0),(h(x+1 ),if x>0):}$
specificando in che relazione sono le minime soluzioni di $f$, $g$, $h$ rispetto ad $<=_\to$.
SOLUZIONE
Io ho definito queste tre funzioni per ognuna,
(a) $\bot^1={(0 \to \bot),(1 \to 2),(2 \to \bot), (...),(n \to \bot):} $ (b) $\bot^2={(0 \to \bot),(1 \to \bot),(...),(n \to 2 text{ n pari} ),(n \to \bot text{ n dispari} ):}$ (c) $\bot^3={(0 \to 2),(1 \to \bot),(2 \to \bot), (...),(n \to \bot):} $
Sono corrette?
Come faccio a definire in che relazione sono le minime soluzioni di $f$, $g$, $h$ rispetto ad $<=_\to$?
Grazie
ho il seguente Ordine Parziale $(N \to N_\bot, <=_\to)$ i cui elementi sono funzioni totali da $N$ a $N_\bot$
con l'ordinamento $f <=_\to g$ $=> AA x in dom(f) : f(x) <=g(x) $
dove
$N$ rappresenta l'insieme dei naturali senza alcuna relazione d'ordine
$N_\bot$ è l'insieme $Nuu{\bot}$ con l'ordinamento $\bot<=n$, per ogni n $in N$
L'ordinamento parziale $(N \to N_\bot, <=_\to)$ è un $CPO$ (complete partial order) ma non un reticolo.
Per ognuna delle definizioni seguenti, devo definire la più piccola funzione in $(N \to N_\bot , <=_\to)$ che le soddisfa:
(a) $f(x)={(2,if x=1),(f (x-2 ),if x>1):}$
(b) $g(x)={(2,if x>=2 text{ e x pari} ),(g (1),if text{x dispari}):}$
(c) $h(x)={(2,if x=0),(h(x+1 ),if x>0):}$
specificando in che relazione sono le minime soluzioni di $f$, $g$, $h$ rispetto ad $<=_\to$.
SOLUZIONE
Io ho definito queste tre funzioni per ognuna,
(a) $\bot^1={(0 \to \bot),(1 \to 2),(2 \to \bot), (...),(n \to \bot):} $ (b) $\bot^2={(0 \to \bot),(1 \to \bot),(...),(n \to 2 text{ n pari} ),(n \to \bot text{ n dispari} ):}$ (c) $\bot^3={(0 \to 2),(1 \to \bot),(2 \to \bot), (...),(n \to \bot):} $
Sono corrette?
Come faccio a definire in che relazione sono le minime soluzioni di $f$, $g$, $h$ rispetto ad $<=_\to$?
Grazie
Risposte
Ciao,
ovviamente $[\mathbb{N}->\mathbb{N}_{\bot}]$ è uno spazio di funzioni continue, se no non si può parlare di CPO o di trovare la funzione minima.
Non mi è chiara la relazione d'ordine, cosa starebbe la freccia a pedice $<=_\to$? di solito l'ordinamento classico sugli spazi di funzione è l'ordine puntuale, e la sua definizione mostra proprio quella che hai scritto, ma quella notazione dice forse altro?
il dominio $\mathbb{N}$ deve essere un CPO. La sua relazione d'ordine è la semplice funzione di idenità ($a<=b | a=b$).
il resto un altro momento, ora ho un po' di fretta.
"lordnergal":
Ciao a tutti,
ho il seguente Ordine Parziale $(N \to N_\bot, <=_\to)$ i cui elementi sono funzioni totali da $N$ a $N_\bot$
con l'ordinamento $f <=_\to g$ $=> AA x in dom(f) : f(x) <=g(x) $
dove
$N$ rappresenta l'insieme dei naturali senza alcuna relazione d'ordine
$N_\bot$ è l'insieme $Nuu{\bot}$ con l'ordinamento $\bot<=n$, per ogni n $in N$
L'ordinamento parziale $(N \to N_\bot, <=_\to)$ è un $CPO$ (complete partial order) ma non un reticolo.
ovviamente $[\mathbb{N}->\mathbb{N}_{\bot}]$ è uno spazio di funzioni continue, se no non si può parlare di CPO o di trovare la funzione minima.
Non mi è chiara la relazione d'ordine, cosa starebbe la freccia a pedice $<=_\to$? di solito l'ordinamento classico sugli spazi di funzione è l'ordine puntuale, e la sua definizione mostra proprio quella che hai scritto, ma quella notazione dice forse altro?
il dominio $\mathbb{N}$ deve essere un CPO. La sua relazione d'ordine è la semplice funzione di idenità ($a<=b | a=b$).
il resto un altro momento, ora ho un po' di fretta.
Dall'immagine si può visualizzare il domino e il codominio delle funzioni presenti in $N -> N_\bot$
L'ordinamento su spazi funzionali di funzioni aventi poset come dominio e codominio è difinito nel seguente modo:
$f <=_->g .... sse ... AA x in N...... f(x)<=g(x) $
dove $<=_->$ indica l'ordinamento di funzioni, mentre $<=$ indica l'ordinamento del poset del codominio.
Uso il simblo $_->$ per differenziare le due relazioni d'ordine.
Il dominio $N$ non ha nessuna relazione d'ordine, mentre il condominio $N_\bot$ ha una relazione d'ordine con $\bot <= n$ con $n in N$
$(N -> N_\bot)$ è un CPO se
a) Esiste un elemento minimo
b) Per ogni catena esite $LUB$ (least upper bound)
a) $f_\bot : n -> \bot$ sarà sicuramente la più piccola.
b) Tutte le catene di funzioni per essere un CPO devono aver il LUB. ( $ f <=_->f^1<=_->f^2<=_->f^3<=_->...<=_->f^n$ )
$f LUB={(0 -> LUB_{i in Y} f^i(0)),(1 -> LUB_{i in Y} f^i(1)),(...),(n -> LUB_{i in Y} f^i(n)):}$
dove $i$ sono gli indici della catana $Y$
In questo modo posso trovare il $LUB$ di tutte le catene infinite
L'ordinamento su spazi funzionali di funzioni aventi poset come dominio e codominio è difinito nel seguente modo:
$f <=_->g .... sse ... AA x in N...... f(x)<=g(x) $
dove $<=_->$ indica l'ordinamento di funzioni, mentre $<=$ indica l'ordinamento del poset del codominio.
Uso il simblo $_->$ per differenziare le due relazioni d'ordine.
Il dominio $N$ non ha nessuna relazione d'ordine, mentre il condominio $N_\bot$ ha una relazione d'ordine con $\bot <= n$ con $n in N$
$(N -> N_\bot)$ è un CPO se
a) Esiste un elemento minimo
b) Per ogni catena esite $LUB$ (least upper bound)
a) $f_\bot : n -> \bot$ sarà sicuramente la più piccola.
b) Tutte le catene di funzioni per essere un CPO devono aver il LUB. ( $ f <=_->f^1<=_->f^2<=_->f^3<=_->...<=_->f^n$ )
$f LUB={(0 -> LUB_{i in Y} f^i(0)),(1 -> LUB_{i in Y} f^i(1)),(...),(n -> LUB_{i in Y} f^i(n)):}$
dove $i$ sono gli indici della catana $Y$
In questo modo posso trovare il $LUB$ di tutte le catene infinite
Ok classiche definizioni sui CPO.
Forse chiami $N->N_\bot$ in un altro modo, ma di solito è chiamato spazio di funzioni se è un CPOs delle funzioni continue.
ok è l'ordine puntuale
questa è un'utile notazione, me la rivendo
ripeto che anche $N$ è un CPO flat generale (con minimo si chiama pointed CPO o CPOs) per definizione di spazio di funzioni. La sua relazione d'ordine è l'uguaglianza (la funzione identità). Infatti la rappresentazione grafica che hai fatto è proprio quella. Se utilizzi i diagrammi di Hasse risulteranno tutti inconfrontabili:
$1\ 4\ 2 ...$
Allora il tuo svolgimento/rappresentazione può funzionare solo per $g$ e $h$, infatti in $f$ la ricorsione non è espressa.
Lo ho rifatto utilizzando uno schema dei passi di ricorsione (simile ad un grafico cartesiano). Ho tenuto conto che si utilizza uno spazio semantico ricorsivo sui naturali:
Zoom
Guardalo e dimmi che ne pensi, se non comprendi qualcosa srivi pure.
L'ordine delle funzioni è: \( h \sqsubseteq f \sqsubseteq g\) dovrebbe essere ordine stretto /l'attributo delle successioni lascialo perdere, non è propriamente $n$ ma da l'idea che il LUB di ogni $\omega$-catena è funzione di un naturale).
"lordnergal":
Dall'immagine si può visualizzare il domino e il codominio delle funzioni presenti in $N -> N_\bot$
Forse chiami $N->N_\bot$ in un altro modo, ma di solito è chiamato spazio di funzioni se è un CPOs delle funzioni continue.
L'ordinamento su spazi funzionali di funzioni aventi poset come dominio e codominio è definito nel seguente modo:
$f <=_->g .... sse ... AA x in N...... f(x)<=g(x) $
ok è l'ordine puntuale
dove $<=_->$ indica l'ordinamento di funzioni, mentre $<=$ indica l'ordinamento del poset del codominio.
Uso il simobolo $_->$ per differenziare le due relazioni d'ordine.
questa è un'utile notazione, me la rivendo
Il dominio $N$ non ha nessuna relazione d'ordine
ripeto che anche $N$ è un CPO flat generale (con minimo si chiama pointed CPO o CPOs) per definizione di spazio di funzioni. La sua relazione d'ordine è l'uguaglianza (la funzione identità). Infatti la rappresentazione grafica che hai fatto è proprio quella. Se utilizzi i diagrammi di Hasse risulteranno tutti inconfrontabili:
$1\ 4\ 2 ...$
Allora il tuo svolgimento/rappresentazione può funzionare solo per $g$ e $h$, infatti in $f$ la ricorsione non è espressa.
Lo ho rifatto utilizzando uno schema dei passi di ricorsione (simile ad un grafico cartesiano). Ho tenuto conto che si utilizza uno spazio semantico ricorsivo sui naturali:
Zoom
Guardalo e dimmi che ne pensi, se non comprendi qualcosa srivi pure.
L'ordine delle funzioni è: \( h \sqsubseteq f \sqsubseteq g\) dovrebbe essere ordine stretto /l'attributo delle successioni lascialo perdere, non è propriamente $n$ ma da l'idea che il LUB di ogni $\omega$-catena è funzione di un naturale).
Mi sono accorto vedendo il tuo schema che ho scritto male la funzione a) 
Quella giusta è questa
a) $f(x)={(2,if x=1),(f(x-2),if x>1):}$
(corretta anche nel primo post)
con funzione minima in $(N->N_\bot)$ definita nel primo post $\bot^1$.
Se $\bot^1$ è corretta l'ordine delle funzioni dovrebbe essere $g<=_->f<=_->h$, giusto?
Aggiungo un altro quesito.
Esiste una soluzione che soddisfa tutte e tre le definizioni $f,g,h$?
Provando con questa
$\bot^a={(0 -> 2),(1 ->2),(n -> 2 {n...pari} ),(n -> \bot{n...dispari != 1}):}$
e rifacendo lo stesso schema che hai fatto prima, mi ritrovo che $f(\bot^a)$ è uguale a $g(\bot^a)$, quindi non più confrontabili.
Quella giusta è questa
a) $f(x)={(2,if x=1),(f(x-2),if x>1):}$
(corretta anche nel primo post)
con funzione minima in $(N->N_\bot)$ definita nel primo post $\bot^1$.
Se $\bot^1$ è corretta l'ordine delle funzioni dovrebbe essere $g<=_->f<=_->h$, giusto?
Aggiungo un altro quesito.
Esiste una soluzione che soddisfa tutte e tre le definizioni $f,g,h$?
Provando con questa
$\bot^a={(0 -> 2),(1 ->2),(n -> 2 {n...pari} ),(n -> \bot{n...dispari != 1}):}$
e rifacendo lo stesso schema che hai fatto prima, mi ritrovo che $f(\bot^a)$ è uguale a $g(\bot^a)$, quindi non più confrontabili.
"lordnergal":
Mi sono accorto vedendo il tuo schema che ho scritto male la funzione a)
Quella giusta è questa
a) $f(x)={(2,if x=1),(f(x-2),if x>1):}$
(corretta anche nel primo post)
con funzione minima in $(N->N_\bot)$ definita nel primo post $\bot^1$.
ah ecco mi sembrava mal condizionata la funzione.
Ma poco cambia, basta traslare di uno.
Mi pare che ora la funzione è definita per tutti i dispari. Il limite comunque è sempre la fun costante $\lfloor 2 \rfloor$.
Se $\bot^1$ è corretta l'ordine delle funzioni dovrebbe essere $g<=_->f<=_->h$, giusto?
perchè ritieni che $h$ sia la funzione più definita?
"hamming_burst":
perchè ritieni che $h$ sia la funzione più definita?
ritengo che $h$ sia più definita in base alla definizione dell'ordinamento
$f<_->g...sse...AA x in dom(f): f(x)<=g(x) $
Per come ho definito le funzioni $\bot^1$, $\bot^2$ e $\bot^3$ ad esempio ho
$g(0)<=h(0) rArr \bot<=2$........$f(0)<=h(0) rArr \bot<=2$ quindi ho che $g<_->f<_->h $
sbaglio a ragionare??
Per completezza questa è la rappresentazione di $f$:
Zoom
ritengo che $h$ sia più definita in base alla definizione dell'ordinamento
$f<_->g...sse...AA x in dom(f): f(x)<=g(x) $
Per come ho definito le funzioni $\bot^1$, $\bot^2$ e $\bot^3$ ad esempio ho
$g(0)<=h(0) rArr \bot<=2$........$f(0)<=h(0) rArr \bot<=2$ quindi ho che $g<_->f<_->h $
sbaglio a ragionare??[/quote]
se prendi un singolo caso ovvio che $h$ sia la più definita. Hai preso l'unico valore di $h$ che abbia convergenza
se noti nella definizione dell'ordinamento c'è un bel $\forall x in NN$ per ogni. Te valuti un singolo punto di definizione, non ha significato nel totale ma solo nel locale.
- $h$ è definito per un singolo valore $0$
- $g$ è definito per tutti i pari tranne $0$
- $f$ è definito per tutti i dispari (ha un punto in più di definizione rispetto a $g$)
perciò ora l'ordinamento diviene: \( h \sqsubseteq g \sqsubseteq f\)
per l'altro punto:
perchè dici che diverge per tutti i dispari tranne $1$ ?
NOTA sull'ordinamento:
se ci fosse stato questa situazione:
- $g$ è definito per tutti i pari
- $f$ è definito per tutti i dispari
la più definita sarebbe stata $g$ perché converge già al primo step di ricorsione nei pari, rispetto ad $f$ che ci mette più step.
Zoom
"lordnergal":
[quote="hamming_burst"] perchè ritieni che $h$ sia la funzione più definita?
ritengo che $h$ sia più definita in base alla definizione dell'ordinamento
$f<_->g...sse...AA x in dom(f): f(x)<=g(x) $
Per come ho definito le funzioni $\bot^1$, $\bot^2$ e $\bot^3$ ad esempio ho
$g(0)<=h(0) rArr \bot<=2$........$f(0)<=h(0) rArr \bot<=2$ quindi ho che $g<_->f<_->h $
sbaglio a ragionare??
[/quote]se prendi un singolo caso ovvio che $h$ sia la più definita. Hai preso l'unico valore di $h$ che abbia convergenza
se noti nella definizione dell'ordinamento c'è un bel $\forall x in NN$ per ogni. Te valuti un singolo punto di definizione, non ha significato nel totale ma solo nel locale.
- $h$ è definito per un singolo valore $0$
- $g$ è definito per tutti i pari tranne $0$
- $f$ è definito per tutti i dispari (ha un punto in più di definizione rispetto a $g$)
perciò ora l'ordinamento diviene: \( h \sqsubseteq g \sqsubseteq f\)
per l'altro punto:
Esiste una soluzione che soddisfa tutte e tre le definizioni f,g,h?
perchè dici che diverge per tutti i dispari tranne $1$ ?
NOTA sull'ordinamento:
se ci fosse stato questa situazione:
- $g$ è definito per tutti i pari
- $f$ è definito per tutti i dispari
la più definita sarebbe stata $g$ perché converge già al primo step di ricorsione nei pari, rispetto ad $f$ che ci mette più step.
"hamming_burst":
se noti nella definizone dell'ordinamento c'è un bel ∀x∈N per ogni. Te valuti un singolo punto di definizione, non ha significato nel totale ma solo nel locale.
bhè si, io ragionavo solo nel locale non nel totale come è definito nell'ordinamento
"hamming_burst":
perchè dici che diverge per tutti i dispari tranne $1$ ?
Ho definito la funzione $\bot^a$ in modo random, per vedere se poteva essere una soluzione minima per tutte e tre le funzioni.
"lordnergal":
bhè si, io ragionavo solo nel locale non nel totale come è definito nell'ordinamento
mi viene il dubbio che non hai compreso cosa ho scritto.Intendo dire che, per rendere vera la relazione d'ordine, deve essere vera per tutti i confronti non per un singolo caso del domino.
Ho definito la funzione $\bot^a$ in modo random, per vedere se poteva essere una soluzione minima per tutte e tre le funzioni.
la classica tecnica backtrack
La domanda comunque può avere più interpretazioni. Se soluzione si intende la funzione semantica limite, è ovviamente la funzione costante $\lfloor 2 \rfloor$ valida per tutti e tre.
Sistemo una mia affermazione fatta nel post, per evitare furviature a chi potrebbe leggere in futuro (per i posteri...).
Ho sottolineato più volte:
Smentisco in parte quanto detto.
Controllando su più libri sembra che in generale nello spazio di funzioni (dominio funzionale oppure dominio di funzioni) delle funzioni continue non è necessario che il dominio sia un CPO (con minimo o senza dipende dalla semantica).
Vedasi qualunque libro di introduzione alla teoria dei domini (es. i capitodi introdutti di Schmidt o Winskel, quest'ultimo utilizza la lettera $D$ per i domini di partenza che siano generici che CPO, si capisce dal contesto quando è uno o l'altro)
Al contrario, se immergiamo i domini funzionali es. in una semantica denotazionale con combinatore di punto fisso (perciò con ricorsione) che utilizza i CPO (con minimo ovviamente), si afferma per adeguatezza dei termini, che il dominio sia un CPO (generico, come sopra dipende dalla semantica lazy, ecc..). La relazione d'ordine può essere neutra come quella proposta sopra, cioè con la relazione d'identita o al contraio essere un CPO flat od altro. Questo perchè se si dicesse che non è un CPO si perderebbe il significato stesso di dominio semantico diciamo che è per standardizzare la terminologia (basti pensare ad un linguaggio funzionale con domini di ordine superiore, follia non specificare essere un CPOs, tranne per i domini primitivi).
Ho sottolineato più volte:
"hamming_burst":
il dominio $\mathbb{N}$ deve essere un CPO. La sua relazione d'ordine è la semplice funzione di idenità ($a<=b | a=b$).
"hamming_burst":
Forse chiami $N->N_\bot$ in un altro modo, ma di solito è chiamato spazio di funzioni se è un CPOs delle funzioni continue.
"hamming_burst":
ripeto che anche $N$ è un CPO flat generale (con minimo si chiama pointed CPO o CPOs) per definizione di spazio di funzioni. La sua relazione d'ordine è l'uguaglianza (la funzione identità). Infatti la rappresentazione grafica che hai fatto è proprio quella. Se utilizzi i diagrammi di Hasse risulteranno tutti inconfrontabili:
$1\ 4\ 2 ...$
Smentisco in parte quanto detto.
Controllando su più libri sembra che in generale nello spazio di funzioni (dominio funzionale oppure dominio di funzioni) delle funzioni continue non è necessario che il dominio sia un CPO (con minimo o senza dipende dalla semantica).
Vedasi qualunque libro di introduzione alla teoria dei domini (es. i capitodi introdutti di Schmidt o Winskel, quest'ultimo utilizza la lettera $D$ per i domini di partenza che siano generici che CPO, si capisce dal contesto quando è uno o l'altro)
Al contrario, se immergiamo i domini funzionali es. in una semantica denotazionale con combinatore di punto fisso (perciò con ricorsione) che utilizza i CPO (con minimo ovviamente), si afferma per adeguatezza dei termini, che il dominio sia un CPO (generico, come sopra dipende dalla semantica lazy, ecc..). La relazione d'ordine può essere neutra come quella proposta sopra, cioè con la relazione d'identita o al contraio essere un CPO flat od altro. Questo perchè se si dicesse che non è un CPO si perderebbe il significato stesso di dominio semantico diciamo che è per standardizzare la terminologia (basti pensare ad un linguaggio funzionale con domini di ordine superiore, follia non specificare essere un CPOs, tranne per i domini primitivi).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo