Existe um homomorfismo fraco da coalgebra?

Dado um endofuncor , podemos definir funções de observação como funções polimórficas para qualquer álgebra- , ou seja, é definido para qualquer álgebra- emaranhado . Outra maneira de olhar para as funções de observação é como funções da álgebra final se existir . Obtemos o polimorfismo automaticamente compondo a função de observação com o homomorfismo único no álgebra- final . Mas isso só funciona se o último coalgebra existir. $F : Set \rightarrow Set$ $F$ $obs$ $F$ $\langle A, c : A \rightarrow FA\rangle$

o b s : \forall ⟨ A, c ⟩ . A \to B

$obs : \forall \langle A, c \rangle . A \to B$

F

$F$

F

$F$

F

$F$

Uma das características definidoras de uma função de observação é que ela cancela qualquer homomorfismo de coalgebra composto à direita, devido ao seu polimorfismo. Se é um homomorfismo coalgebra, então: Durante minha pesquisa, na tentativa de definir uma noção de consistência observacional entre um coalgebra e outro, tive a idéia de um fraco homomorfismo coalgebra. A idéia é que podemos "falsificar" um homomorfismo da coalgebra se conhecermos a função de observação antes do tempo. Assim, podemos satisfazer, mas apenas para um particular . $hom$ $F$

o b s = o b s \circ h o m

$obs = obs \circ hom$

o b s = o b s \circ h o m

$obs = obs \circ hom$

o b s

$obs$

Por exemplo, deixe e deixe ser definido como Ou seja, pega os dois primeiros elementos de um fluxo. $FX = \{0,1\} \times X$ $obs$

o b s : \forall ⟨ A, c ⟩ . A \to {0, 1}^{2}

$obs : \forall \langle A, c\rangle. A \to \{0,1\}^2$

o b s = ⟨ (π_{1} \circ c), (π_{1} \circ c \circ π_{2} \circ c) ⟩

$obs = \langle (\pi_1 \circ c), (\pi_1 \circ c \circ \pi_2 \circ c) \rangle$

o b s

$obs$

Então, um homomorfismo F-coalgebra precisaria garantir a preservação de todos os elementos do fluxo, enquanto um homomorfismo fraco para só precisa preservar os dois primeiros elementos do fluxo. $obs$

Em minha pesquisa, essa noção seria útil para mostrar que uma coalgebra é observacionalmente consistente com outra, mostrando que toda função de observação linear finita tem um homomorfismo fraco da primeira coalgebra à segunda coalgebra. Em outras palavras, toda observação linear finita na primeira coalgebra pode ser reproduzida na segunda coalgebra.

(O que quero dizer com função de observação linear parece quase irrelevante, mas por uma questão de compartilhar ... Uma função de observação linear é mais ou menos aquela que usa cada estado do conjunto de transportadoras apenas uma vez. Estou tentando modelar um oráculo, e o usuário não tem permissão para voltar e fingir que nunca fez uma pergunta.)

Minhas perguntas são assim:

Isso foi pesquisado? Já existem "homomorfismos fracos de coalgebra", talvez com algum outro nome?
Existe uma maneira mais "teórica das categorias" de apresentar isso?

Editar : foram removidas duas perguntas que não são tão importantes.

ct.category-theory Francisco Mota
fonte

Existe alguma razão para pensar que um site de perguntas e respostas sobre ciência da computação é o lugar certo para esta pergunta?

Sasho Nikolov

Sim. coalgebras têm aplicações em ciência da computação, e essa questão surgiu enquanto se pesquisava em ciência da computação. Além disso, há outras perguntas sobre coalgebras em cstheory.stackexchange.

F

$F$

F

$F$

Francisco Mota

Como exemplo de aplicações à ciência da computação, noções de indistinguibilidade (que são usadas às vezes em criptografia) podem ser definíveis em termos de homomorfismos fracos.

Francisco Mota

Eu ficaria curioso para ver uma referência onde isso foi feito e usado para provar alguma coisa.

Sasho Nikolov

O

$O$

O

$O$

⟨ A, α ⟩

$\langle A, \alpha \rangle$

⟨ B, β ⟩

$\langle B, \beta \rangle$

f : A \to B

$f: A \to B$

β^{O} \circ f = O (f) \circ α^{O}

$\beta^O \circ f = O(f) \circ \alpha^O$

O

$O$

Respostas:

Os "morfismos fracos" que você descreve têm um nome em um ambiente um pouco restrito. Eles também podem ser definidos de maneira geral, como explicarei.

$T : \mathsf{Set} \to \mathsf{Set}$ $\mathsf{Set}$ $\alpha$ $\alpha$ $\alpha \leq \omega$ . Antes da coalgebra, os lógicos modais haviam estudado bisimulações em n etapas para os quadros de Kripke, que equivalem a bienulações em n etapas para barras de carvão para o functor de conjunto de potência. Sua exigência de que sejam funções em oposição a relações os torna bissimulações funcionais em n etapas.

$\mathbb{C}$ $T : \mathbb{C} \to \mathbb{C}$ $T$ $\mathsf{Set}$ $\mathbb{C}$

$1 \quad \xleftarrow{!_{T1}} \quad T1 \quad \xleftarrow{T !_{T1}} \quad T^2 1 \quad \xleftarrow{T^2 !_{T1}} \quad \dots \quad T^\omega 1 \quad \xleftarrow{f_\omega^{\omega + 1}} \quad T(T^\omega 1) \quad \xleftarrow{Tf_\omega^{\omega + 1}} \quad \dots$

$1$ $\mathbb{C}$ $\mathsf{Set}$ $1 = \{*\}$ $!_{T1} : T1 \to 1$ $\mathsf{Set}$ $T1$ $*$ $T^n 1$ $T$ $T^\omega 1$ $\omega$ $T^\alpha 1$ $\alpha$

$T$ $(Z,\gamma)$ $\mathbb{C}$ $\mathsf{beh}_\gamma^\alpha : Z \to T^\alpha 1$ $\alpha$ $\alpha < \omega$

$\mathsf{beh}_\gamma^0 : Z \to 1$

$\mathsf{beh}_\gamma^{n+1} = T\mathsf{beh}_\gamma^n \circ \gamma : Z \to T^{n+1} 1$

$Z$ $\alpha$ $T$ $(A,\gamma)$ $(B,\delta)$ $\mathbb{C}$ $f : A \to B$ $\alpha$

$\mathsf{beh}_\delta^\alpha \circ f = \mathsf{beh}_\gamma^\alpha$

$\alpha$ $f(z)$ $\delta$ $\alpha$ $z$ $\gamma$

Enfim, espero que isso seja útil. Você pode encontrar várias referências pesquisando 'sequência terminal coalgebra' ou 'sequência final coalgebra'.

Roubar
fonte

α

$\alpha$

o b s : T^{α} 1 \to B

$\mathsf{obs}:T^\alpha 1 \to B$

o b s \circ {b e h}_{δ}^{α} \circ f = o b s \circ {b e h}_{γ}^{α}

$\mathsf{obs} \circ \mathsf{beh}_\delta^\alpha \circ f = \mathsf{obs} \circ \mathsf{beh}_\gamma^\alpha$

{b e h}_{γ}^{ω}

$\mathsf{beh}_\gamma^\omega$

{b e h}_{γ}^{ω + 1}

$\mathsf{beh}_\gamma^{\omega+1}$

z

$z$

f (z)

$f(z)$

z^{'}

$z'$

f (z^{'})

$f(z')$

α

$\alpha$

β

$\beta$

β \leq α

$\beta \leq \alpha$

{b e h}_{γ}^{ω}

$\mathsf{beh}_\gamma^\omega$

{b e h}_{γ}^{ω + 1}

$\mathsf{beh}_\gamma^{\omega+1}$

ω

$\omega$

2 \times I d : S e t \to S e t

$2 \times Id : \mathsf{Set} \to \mathsf{Set}$

{b e h}_{γ}^{ω + 1}

$\mathsf{beh}_\gamma^{\omega + 1}$

α

$\alpha$

X \mapsto (2 \times X)^{2}

$X \mapsto (2 \times X)^2$

α

$\alpha$

α

$\alpha$

Como regra, deve-se evitar uma terminologia fortemente sobrecarregada, como fraca, regular, normal etc., a menos que a noção tenha alguma universalidade. Em particular, parece que sua noção não corresponde à noção usual de homomorfismo fraco após o lançamento da seta.

Sempre existem termos mais descritivos sempre que você faz algo menos universal, como "homomorfismo observacionalmente enfraquecido" abreviado para "ow-homomorfismo", talvez.

Sua noção de função de observação já fornece uma apresentação teórica de categoria. Eu me preocuparia mais em esclarecer o que exatamente isso significa e por que é interessante, em vez de buscar a maior generalidade possível. Em particular, você deve dar um exemplo informativo e não um exemplo ao introduzir noções incomuns na impressão.

Jeff Burdges
fonte

Obrigado pela resposta. Concordo com sua recomendação de usar um nome mais específico. Ainda pretendo ler os artigos sobre Fraco Bisimulations de Jan Rothe ( citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7571 ) para determinar como eles estão relacionados à minha definição acima, mas eu sou ( prematuramente) convencidos de que são diferentes. Mais uma vez obrigado.

Francisco Mota