<p>As a rule, one should avoid heavily overloaded terminology like weak, regular, normal, etc. unless the notion has some universality.  In particular, it appears your notion doesn't correspond with the usual notion of <a href="http://www.mini.pw.edu.pl/aaa80/abstractsaaa80/47.pdf">weak homomorphism</a> after arrow flipping.</p>

<p>There are always more descriptive terms whenever your doing something less universal, like "observationally weakened homomorphism" shortened to "ow-homomorphism" perhaps.</p>

<p>Your notion of observation function already provides a category theoretic presentation.  I'd worry more about clarifying what exactly it means, and why it's interesting, rather than seeking the most generality possible.  In particular, you should usually give an informative example and non-example when introducing unusual notions in print.</p>

CC BY-SA 3.0
2011-12-12T18:38:11.610Z
Thank you for the answer. I agree with your recommendation to use a more specific name. I still intend to go read the papers on Weak Bisimulations by Jan Rothe (http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7571) to determine how they are related to my definition above, but I am (prematurely) convinced that they are different. Once again, thank you.
Francisco Mota
CC BY-SA 3.0
2011-12-11T23:59:43.980Z
2011-12-11T23:59:43.980Z
Jeff Burdges
<p>The `weak morphisms' you describe do have a name in a slightly restricted setting. They can also be defined quite generally, as I'll explain.</p>

<p>In the case where $T : \mathsf{Set} \to \mathsf{Set}$ preserves weak pullbacks (many natural functors on $\mathsf{Set}$ do) it is known that behavioural equivalence coincides with coalgebraic bisimilarity. Then your morphisms are known as <strong>functional $\alpha$-step bisimulations</strong> where  $\alpha$ is an ordinal. Admittedly I've only ever seen them defined for ordinals $\alpha \leq \omega$. Prior to coalgebra, modal logicians had studied n-step bisimulations for Kripke frames, which amount to n-step bisimulations for coalgebras for the powerset functor. Your requirement that they be functions as opposed to relations makes them <em>functional</em> n-step bisimulations.</p>

<p>On the other hand, you can define the concept you are talking about in a far more general setting without referring to coalgebraic bisimulations. For any category $\mathbb{C}$ which has limits of ordinal-indexed cochains and any functor $T : \mathbb{C} \to \mathbb{C}$ one can define $T$ 's <strong>terminal sequence</strong>. The condition regarding limits is actually rather weak e.g. many categories (including $\mathsf{Set}$) are actually complete i.e. have all small limits. The terminal sequence is a diagram in $\mathbb{C}$ and looks like:</p>

<p>$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$</p>

<p>Here $1$ is the terminal object in $\mathbb{C}$ (limit of empty cochain). For example in $\mathsf{Set}$ this can be taken to be the one element set $1 = \{*\}$. The map $!_{T1} : T1 \to 1$ is the unique morphism into the terminal object e.g. in $\mathsf{Set}$ is simply maps every element of $T1$ to $*$. Each $T^n 1$ is computed by iterating $T$ and $T^\omega 1$ is the limit of the cochain preceding it. One can then continue beyond $\omega$, if necessary. Intuitively $T^\alpha 1$ is the collection of  $\alpha$-step behaviours.</p>

<p>Now any $T$-coalgebra $(Z,\gamma)$ induces a cone over this sequence i.e.  a collection of $\mathbb{C}$-morphisms $\mathsf{beh}_\gamma^\alpha : Z \to T^\alpha 1$ for each ordinal $\alpha$. I'll just define them for $\alpha &lt; \omega$:</p>

<p>$\mathsf{beh}_\gamma^0 : Z \to 1$ is the unique map into the terminal object.</p>

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

<p>Intuitively these maps send a state in $Z$ to its $\alpha$-step behaviour. Now we can describe what you are talking about. Suppose we have two $T$-coalgebras $(A,\gamma)$ and $(B,\delta)$. Then a $\mathbb{C}$-morphism $f : A \to B$ preserves $\alpha$-step behaviour iff:</p>

<p>$\mathsf{beh}_\delta^\alpha \circ f = \mathsf{beh}_\gamma^\alpha$</p>

<p>That is, the $\alpha$-step behaviour of $f(z)$ in $\delta$ is precisely the $\alpha$-step behaviour of $z$ in $\gamma$.</p>

<p>Anyway, I hope this is helpful. You can find various references by googling 'terminal sequence coalgebra' or 'final sequence coalgebra'.</p>

CC BY-SA 3.0
2011-12-16T01:18:09.583Z
Thank you for this informative and accessible answer! I have one remark and one question. Remark: The idea of an "observation function" and "weak morphism" as in my post is a bit more general -- the weak morphism need not preserve all behavior up to the $\alpha$ level (and this is crucial for my application). This can easily be 'fixed' by having $\mathsf{obs}:T^\alpha 1 \to B$ and $\mathsf{obs} \circ \mathsf{beh}_\delta^\alpha \circ f = \mathsf{obs} \circ \mathsf{beh}_\gamma^\alpha$. Question: What is the difference between $\mathsf{beh}_\gamma^\omega$ and $\mathsf{beh}_\gamma^{\omega+1}$?
Francisco Mota
CC BY-SA 3.0
2011-12-16T01:56:10.037Z
I'm not sure that I understand your remark. Do you mean that the depth of behaviour preserved varies e.g. $z$ and $f(z)$ are 2-step equivalent but $z'$ and $f(z')$ are 4-step equivalent? Note that $\alpha$-step equivalence implies $\beta$-step equivalence for all $\beta \leq \alpha$.
Rob
CC BY-SA 3.0
2011-12-16T02:07:04.947Z
It is not so easy for me to explain the difference between $\mathsf{beh}_\gamma^\omega$ and $\mathsf{beh}_\gamma^{\omega+1}$ in so little space. Briefly, the behaviour of many functors is determined by its $\omega$-step behaviour e.g. for $2 \times Id : \mathsf{Set} \to \mathsf{Set}$ each infinite binary stream is determined by its depth n approximants. However there exist functors whose behaviours are not determined in this way e.g. countable powerset or full powerset functor. In these cases $\mathsf{beh}_\gamma^{\omega + 1}$ provides additional information.
Rob
CC BY-SA 3.0
2011-12-16T09:43:44.267Z
No, you can keep $\alpha$ constant. The idea is that we don't want to show full bisimilarity, just part of it. For example, if my functor gave rise to a tree structure, such as $X \mapsto (2 \times X)^2$, I could choose only to look at one branch up to depth $\alpha$, rather than look at all nodes up to depth $\alpha$. Thank you for the answer.
Francisco Mota
CC BY-SA 3.0
2011-12-16T00:38:31.940Z
2011-12-16T10:22:15.580Z
2011-12-16T10:22:15.580Z
Rob
<p>Given an endofunctor $F : Set \rightarrow Set$, we can define observation functions as functions that are polymorphic for any $F$-coalgebra, that is $obs$ is defined for any $F$-coalgebra $\langle A, c : A \rightarrow FA\rangle$.
$$
obs : \forall \langle A, c \rangle . A \to B
$$
Another way of looking at observation functions is as functions of the final $F$-coalgebra <em>if it exists</em>. We get the polymorphism automatically by composing the observation function with the unique homomorphism to the final $F$-coalgebra. But this only works if the final $F$-coalgebra exists.</p>

<p>One of the defining characteristics of an observation function is that it cancels any coalgebra homomorphism composed to the right, due to its polymorphism. If $hom$ is an $F$-coalgebra homomorphism, then:
$$
obs = obs \circ hom
$$
During my research, in an attempt to define a notion of observational consistency between one coalgebra and another, I had the idea of a weak coalgebra homomorphism. The idea is that we can "fake" a coalgebra homomorphism if we know the observation function ahead of time. Thus, we might satisfy,
$$
obs = obs \circ hom
$$
but only for one particular $obs$.</p>

<p>For example, let $FX = \{0,1\} \times X$, and let $obs$ be defined as
$$
obs : \forall \langle A, c\rangle. A \to \{0,1\}^2
$$ $$
obs = \langle (\pi_1 \circ c), (\pi_1 \circ c \circ \pi_2 \circ c) \rangle
$$
That is, $obs$ takes the first two elements of a stream.</p>

<p>Then, an F-coalgebra homomorphism would need to ensure that it preserves all the elements of the stream, whereas a weak homomorphism for $obs$ only needs to preserve the first two elements of the stream.</p>

<p>In my research, this notion would be useful in order to show that one coalgebra is observationally consistent with another by showing that every finite linear observation function has a weak homomorphism from the first coalgebra to the second coalgebra. In other words, every finite linear observation on the first coalgebra can be reproduced on the second coalgebra.</p>

<p>(What I mean by <em>linear observation function</em> feels mostly irrelevant, but for the sake of sharing... A linear observation function is more or less one that uses each state of the carrier set only once. I'm trying to model an oracle, and the user is not allowed to go back and pretend it never asked a question.)</p>

<p>My questions are thus:</p>

<ol>
<li><p>Has this been researched? Do "weak coalgebra homomorphisms" exist already, under some other name perhaps?</p></li>
<li><p>Is there a more "category theory" way to present this?</p></li>
</ol>

<p><strong>Edit</strong>: Removed two questions which aren't that important.</p>

CC BY-SA 3.0
2011-12-10T20:02:59.173Z
Is there some reason to think that a computer science Q&A site is the right place for this question?
Sasho Nikolov
CC BY-SA 3.0
2011-12-10T20:10:05.907Z
Yes. $F$-coalgebras have applications in computer science, and this question came up while doing research in computer science. Also, there are other questions about $F$-coalgebras on cstheory.stackexchange.
Francisco Mota
CC BY-SA 3.0
2011-12-10T20:22:29.493Z
fair enough. just asking
Sasho Nikolov
CC BY-SA 3.0
2011-12-10T20:31:22.997Z
As an example of applications to computer science, notions of indistinguishibility (which are used in cryptography sometimes) might be definable in terms of weak homomorphisms.
Francisco Mota
CC BY-SA 3.0
2011-12-10T20:46:33.550Z
I'd be curious to see a reference where this has been done and used to prove something.
Sasho Nikolov
CC BY-SA 3.0
2011-12-10T23:04:28.967Z
Is this you? http://scholar.google.com/scholar?hl=en&lr=&q=related:Y36pLXW7tMwJ:scholar.google.com/&um=1&ie=UTF-8&ei=3-TjTqnXCdGltwel0OihBA&sa=X&oi=science_links&ct=sl-related&resnum=1&ved=0CCAQzwIwAA
Jeff Burdges
CC BY-SA 3.0
2011-12-10T23:26:00.090Z
Jeff Burdges: no. This is someone else also using the phrase "weak homomorphism" to mean "not quite a homomorphism". I am looking into this, but I think these notions are quite different. (Which suggests I should find a different name for "weak homomorphism", but it seems appropriate.)
Francisco Mota
CC BY-SA 3.0
2011-12-10T23:54:31.713Z
This article: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7571

Seems to have a very similar idea of "weak homomorphism" to mine above. But the definition is slightly different and I don't know if it actually coincides.

It defines an observer $O$, which I don't understand yet, and it defines a weak homomorphism for $O$ between $\langle A, \alpha \rangle$ and $\langle B, \beta \rangle$ as a function $f: A \to B$ such that
$$
\beta^O \circ f = O(f) \circ \alpha^O
$$
But I don't yet know what the $O$ means.
Francisco Mota
CC BY-SA 3.0
2011-12-11T00:35:06.030Z
Sasho Nikolov: I don't have any references for you, but if you are genuinely curious, I recommend looking into the proceedings of CMCS (Coalgebraic Methods in Computer Science) and CALCO (Algebra and Coalgebra in Computer Science).
Francisco Mota
CC BY-SA 3.0
2011-12-11T20:32:27.520Z
I know that your application is CS, but have you tried mathoverflow? Your question doesn't seem ultimately CS-specific. You might be able to get a good answer there. I want to be sure to say that I'm not suggesting that you "go away" or anything like that; I'm curious myself whether you're able to find an answer to this question.
Josephine Moeller
CC BY-SA 3.0
2011-12-13T17:23:07.360Z
@SashoNikolov: Coalgebras and observations have been used to give a uniform treatment of automata, infinite data-types, and other computational structures, paralleling the use of algebra (groups, rings, etc.) for classical mathematical objects.
Vijay D
<ct.category-theory>
Is there such a thing as a weak coalgebra homomorphism?
Francisco Mota
# Is there such a thing as a weak coalgebra homomorphism?

(Asked by: username_0 on 2011-12-10)

Given an endofunctor $F : Set \rightarrow Set$, we can define observation functions as functions that are polymorphic for any $F$-coalgebra, that is $obs$ is defined for any $F$-coalgebra $\langle A, c : A \rightarrow FA\rangle$.
$$
obs : \forall \langle A, c \rangle . A \to B
$$
Another way of looking at observation functions is as functions of the final $F$-coalgebra *if it exists*. We get the polymorphism automatically by composing the observation function with the unique homomorphism to the final $F$-coalgebra. But this only works if the final $F$-coalgebra exists.

One of the defining characteristics of an observation function is that it cancels any coalgebra homomorphism composed to the right, due to its polymorphism. If $hom$ is an $F$-coalgebra homomorphism, then:
$$
obs = obs \circ hom
$$
During my research, in an attempt to define a notion of observational consistency between one coalgebra and another, I had the idea of a weak coalgebra homomorphism. The idea is that we can "fake" a coalgebra homomorphism if we know the observation function ahead of time. Thus, we might satisfy,
$$
obs = obs \circ hom
$$
but only for one particular $obs$.

For example, let $FX = \{0,1\} \times X$, and let $obs$ be defined as
$$
obs : \forall \langle A, c\rangle. A \to \{0,1\}^2
$$ $$
obs = \langle (\pi\_1 \circ c), (\pi\_1 \circ c \circ \pi\_2 \circ c) \rangle
$$
That is, $obs$ takes the first two elements of a stream.

Then, an F-coalgebra homomorphism would need to ensure that it preserves all the elements of the stream, whereas a weak homomorphism for $obs$ only needs to preserve the first two elements of the stream.

In my research, this notion would be useful in order to show that one coalgebra is observationally consistent with another by showing that every finite linear observation function has a weak homomorphism from the first coalgebra to the second coalgebra. In other words, every finite linear observation on the first coalgebra can be reproduced on the second coalgebra.

(What I mean by *linear observation function* feels mostly irrelevant, but for the sake of sharing... A linear observation function is more or less one that uses each state of the carrier set only once. I'm trying to model an oracle, and the user is not allowed to go back and pretend it never asked a question.)

My questions are thus:

1. Has this been researched? Do "weak coalgebra homomorphisms" exist already, under some other name perhaps?
2. Is there a more "category theory" way to present this?

**Edit**: Removed two questions which aren't that important.

**Tags:** ct.category-theory
> **Comments:**
> **username_1**: Is there some reason to think that a computer science Q&A site is the right place for this question?  
> **username_0**: Yes. $F$-coalgebras have applications in computer science, and this question came up while doing research in computer science. Also, there are other questions about $F$-coalgebras on cstheory.stackexchange.  
> **username_1**: fair enough. just asking  
> **username_0**: As an example of applications to computer science, notions of indistinguishibility (which are used in cryptography sometimes) might be definable in terms of weak homomorphisms.  
> **username_1**: I'd be curious to see a reference where this has been done and used to prove something.  
> **username_2**: Is this you? http://scholar.google.com/scholar?hl=en&lr=&q=related:Y36pLXW7tMwJ:scholar.google.com/&um=1&ie=UTF-8&ei=3-TjTqnXCdGltwel0OihBA&sa=X&oi=science_links&ct=sl-related&resnum=1&ved=0CCAQzwIwAA  
> **username_0**: Jeff Burdges: no. This is someone else also using the phrase "weak homomorphism" to mean "not quite a homomorphism". I am looking into this, but I think these notions are quite different. (Which suggests I should find a different name for "weak homomorphism", but it seems appropriate.)  
> **username_0**: This article: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7571  Seems to have a very similar idea of "weak homomorphism" to mine above. But the definition is slightly different and I don't know if it actually coincides.  It defines an observer $O$, which I don't understand yet, and it defines a weak homomorphism for $O$ between $\langle A, \alpha \rangle$ and $\langle B, \beta \rangle$ as a function $f: A \to B$ such that $$ \beta^O \circ f = O(f) \circ \alpha^O $$ But I don't yet know what the $O$ means.  
> **username_0**: Sasho Nikolov: I don't have any references for you, but if you are genuinely curious, I recommend looking into the proceedings of CMCS (Coalgebraic Methods in Computer Science) and CALCO (Algebra and Coalgebra in Computer Science).  
> **username_3**: I know that your application is CS, but have you tried mathoverflow? Your question doesn't seem ultimately CS-specific. You might be able to get a good answer there. I want to be sure to say that I'm not suggesting that you "go away" or anything like that; I'm curious myself whether you're able to find an answer to this question.  
> **username_4**: @SashoNikolov: Coalgebras and observations have been used to give a uniform treatment of automata, infinite data-types, and other computational structures, paralleling the use of algebra (groups, rings, etc.) for classical mathematical objects.  

---

## 2 answers

### Answer by username_5 on 2011-12-16. Score: 6 | Accepted answer

The `weak morphisms' you describe do have a name in a slightly restricted setting. They can also be defined quite generally, as I'll explain.

In the case where $T : \mathsf{Set} \to \mathsf{Set}$ preserves weak pullbacks (many natural functors on $\mathsf{Set}$ do) it is known that behavioural equivalence coincides with coalgebraic bisimilarity. Then your morphisms are known as **functional $\alpha$-step bisimulations** where $\alpha$ is an ordinal. Admittedly I've only ever seen them defined for ordinals $\alpha \leq \omega$. Prior to coalgebra, modal logicians had studied n-step bisimulations for Kripke frames, which amount to n-step bisimulations for coalgebras for the powerset functor. Your requirement that they be functions as opposed to relations makes them *functional* n-step bisimulations.

On the other hand, you can define the concept you are talking about in a far more general setting without referring to coalgebraic bisimulations. For any category $\mathbb{C}$ which has limits of ordinal-indexed cochains and any functor $T : \mathbb{C} \to \mathbb{C}$ one can define $T$ 's **terminal sequence**. The condition regarding limits is actually rather weak e.g. many categories (including $\mathsf{Set}$) are actually complete i.e. have all small limits. The terminal sequence is a diagram in $\mathbb{C}$ and looks like:

$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$

Here $1$ is the terminal object in $\mathbb{C}$ (limit of empty cochain). For example in $\mathsf{Set}$ this can be taken to be the one element set $1 = \{\*\}$. The map $!\_{T1} : T1 \to 1$ is the unique morphism into the terminal object e.g. in $\mathsf{Set}$ is simply maps every element of $T1$ to $\*$. Each $T^n 1$ is computed by iterating $T$ and $T^\omega 1$ is the limit of the cochain preceding it. One can then continue beyond $\omega$, if necessary. Intuitively $T^\alpha 1$ is the collection of $\alpha$-step behaviours.

Now any $T$-coalgebra $(Z,\gamma)$ induces a cone over this sequence i.e. a collection of $\mathbb{C}$-morphisms $\mathsf{beh}\_\gamma^\alpha : Z \to T^\alpha 1$ for each ordinal $\alpha$. I'll just define them for $\alpha < \omega$:

$\mathsf{beh}\_\gamma^0 : Z \to 1$ is the unique map into the terminal object.

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

Intuitively these maps send a state in $Z$ to its $\alpha$-step behaviour. Now we can describe what you are talking about. Suppose we have two $T$-coalgebras $(A,\gamma)$ and $(B,\delta)$. Then a $\mathbb{C}$-morphism $f : A \to B$ preserves $\alpha$-step behaviour iff:

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

That is, the $\alpha$-step behaviour of $f(z)$ in $\delta$ is precisely the $\alpha$-step behaviour of $z$ in $\gamma$.

Anyway, I hope this is helpful. You can find various references by googling 'terminal sequence coalgebra' or 'final sequence coalgebra'.

> **Comments:**
> **username_0**: Thank you for this informative and accessible answer! I have one remark and one question. Remark: The idea of an "observation function" and "weak morphism" as in my post is a bit more general -- the weak morphism need not preserve all behavior up to the $\alpha$ level (and this is crucial for my application). This can easily be 'fixed' by having $\mathsf{obs}:T^\alpha 1 \to B$ and $\mathsf{obs} \circ \mathsf{beh}_\delta^\alpha \circ f = \mathsf{obs} \circ \mathsf{beh}_\gamma^\alpha$. Question: What is the difference between $\mathsf{beh}_\gamma^\omega$ and $\mathsf{beh}_\gamma^{\omega+1}$?  
> **username_5**: I'm not sure that I understand your remark. Do you mean that the depth of behaviour preserved varies e.g. $z$ and $f(z)$ are 2-step equivalent but $z'$ and $f(z')$ are 4-step equivalent? Note that $\alpha$-step equivalence implies $\beta$-step equivalence for all $\beta \leq \alpha$.  
> **username_5**: It is not so easy for me to explain the difference between $\mathsf{beh}_\gamma^\omega$ and $\mathsf{beh}_\gamma^{\omega+1}$ in so little space. Briefly, the behaviour of many functors is determined by its $\omega$-step behaviour e.g. for $2 \times Id : \mathsf{Set} \to \mathsf{Set}$ each infinite binary stream is determined by its depth n approximants. However there exist functors whose behaviours are not determined in this way e.g. countable powerset or full powerset functor. In these cases $\mathsf{beh}_\gamma^{\omega + 1}$ provides additional information.  
> **username_0**: No, you can keep $\alpha$ constant. The idea is that we don't want to show full bisimilarity, just part of it. For example, if my functor gave rise to a tree structure, such as $X \mapsto (2 \times X)^2$, I could choose only to look at one branch up to depth $\alpha$, rather than look at all nodes up to depth $\alpha$. Thank you for the answer.  

---

### Answer by username_2 on 2011-12-11. Score: 5

As a rule, one should avoid heavily overloaded terminology like weak, regular, normal, etc. unless the notion has some universality. In particular, it appears your notion doesn't correspond with the usual notion of [weak homomorphism](http://www.mini.pw.edu.pl/aaa80/abstractsaaa80/47.pdf) after arrow flipping.

There are always more descriptive terms whenever your doing something less universal, like "observationally weakened homomorphism" shortened to "ow-homomorphism" perhaps.

Your notion of observation function already provides a category theoretic presentation. I'd worry more about clarifying what exactly it means, and why it's interesting, rather than seeking the most generality possible. In particular, you should usually give an informative example and non-example when introducing unusual notions in print.

> **Comments:**
> **username_0**: Thank you for the answer. I agree with your recommendation to use a more specific name. I still intend to go read the papers on Weak Bisimulations by Jan Rothe (http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7571) to determine how they are related to my definition above, but I am (prematurely) convinced that they are different. Once again, thank you.  

---

