# Semipullbacks of labelled Markov processes

Jan Pachl Pedro Sánchez Terraf Supported by Conicet and Secyt-UNC project
30720150100529CB.

###### Abstract

A _labelled Markov process (LMP)_ consists of a measurable space $S$ together
with an indexed family of Markov kernels from $S$ to itself. This structure
has been used to model probabilistic computations in Computer Science, and one
of the main problems in the area is to define and decide whether two LMP $S$
and $S^{\prime}$ “behave the same”. There are two natural categorical
definitions of sameness of behavior: $S$ and $S^{\prime}$ are _bisimilar_ if
there exist an LMP $T$ and measure preserving maps forming a diagram of the
shape $S\leftarrow T\rightarrow{S^{\prime}}$; and they are _behaviorally
equivalent_ if there exist some $U$ and maps forming a dual diagram
$S\rightarrow U\leftarrow{S^{\prime}}$.

These two notions differ for general measurable spaces but Edalat proved that
they coincide for analytic Borel spaces, showing that from every diagram
$S\rightarrow U\leftarrow{S^{\prime}}$ one can obtain a bisimilarity diagram
as above. Moreover, the resulting square of measure preserving maps is
commutative (a _semipullback_).

In this paper, we extend Edalat’s result to measurable spaces $S$ isomorphic
to a universally measurable subset of a Polish space with the trace of the
Borel $\sigma$-algebra, using a version of Strassen’s theorem on common
extensions of finitely additive measures.

00footnotetext: _Keywords:_ semipullback, Radon measure, labelled Markov
process, bisimulation, universally measurable set. _MSC 2010:_ 28A35; 28A60,
68Q85. _ACM class:_ F.4.1; F.1.2.

##  1 Introduction

Markov decision processes have been considered in the Computer Science
literature as a model for probabilistic computation. In this context, a
_labelled Markov process (LMP)_ is a structure
$\mathbf{S}=(S,\Sigma,\\{\tau_{a}:a\in L\\})$ where $(S,\Sigma)$ is a
measurable space and for $a\in L$, $\tau_{a}:S\times\Sigma\rightarrow[0,1]$ is
a _Markov kernel_ , i.e., a function such that for each fixed $s\in S$,
$\tau(s,\cdot)$ is a finite positive measure bounded above by 1, and for each
fixed $Q\in\Sigma$, $\tau(\cdot,Q)$ is a
$\Sigma$-$\mathfrak{B}([0,1])$-measurable function. In one interpretation of
this computational model, the system $\mathbf{S}$ stands at any particular
time at a _current state_ $s_{0}\in S$, but this information is hidden from
the hypothetical _users_ of $\mathbf{S}$, whose only interaction with the
system is through $L$. Intuitively, the user is presented with a black box
with buttons labelled by $L$, and a button $l$ is available to be pressed
whenever $\tau_{l}(s_{0},S)>0$. A detailed discussion of LMP and many
motivating examples are to be found in Desaharnais thesis [2].

Of primary importance is to be able to determine when two such systems
$\mathbf{S}$ and $\mathbf{S^{\prime}}$ behave the same way from the user
viewpoint. That is, when a user doing repeated experiments with $\mathbf{S}$
and $\mathbf{S^{\prime}}$ would conclude that they are indistinguishable.
Actually, for such probabilistic systems there are at least two different ways
to formalize a notion of behavior, and they are intimately related to measure-
preserving maps.

######  Definition 1.

Let $\mathbf{S}=(S,\Sigma,\\{\tau_{a}:a\in L\\})$ and
$\mathbf{S}^{\prime}=(S^{\prime},\Sigma^{\prime},\\{\tau_{a}^{\prime}:a\in
L\\})$ be LMP. A _zigzag morphism_ $f:\mathbf{S}\to\mathbf{S^{\prime}}$ is a
surjective measurable map $f:(S,\Sigma)\to(S^{\prime},\Sigma^{\prime})$ such
that for all $a\in L$ we have:

$\forall s\in S\;\forall
Q\in\Sigma^{\prime}:\tau_{a}(s,f^{-1}(Q))=\tau_{a}^{\prime}(f(s),Q).$

We say that $\mathbf{S}$ and $\mathbf{S^{\prime}}$ are _bisimilar_ if there
exists an LMP $\mathbf{T}$ and zigzag morphisms forming a diagram of the shape
$\mathbf{S}\leftarrow\mathbf{T}\rightarrow\mathbf{S^{\prime}}$. This
definition, in this categorical form, can be traced to Joyal _et al._ [8] and
it provides one of the possible formalizations of the concept of equality of
behavior. The second one is given by the dual diagram: $\mathbf{S}$ and
$\mathbf{S^{\prime}}$ are _behaviorally equivalent_ if there exists an LMP
$\mathbf{U}$ and morphisms forming a diagram of the shape
$\mathbf{S}\rightarrow\mathbf{U}\leftarrow\mathbf{S^{\prime}}$. This notion,
in turn, was introduced by Danos _et al._ [1], and it can be shown by
functorial manipulations that behavioral equivalence is a transitive relation
in the category of LMP. It can be proved that bisimilar LMP are behaviorally
equivalent. Also, there is neat logical characterization of this last
relation, with further ramifications; the reader can consult Doberkat [3] and
the references therein.

Some of the main problems in this area are to find conditions for the relation
of bisimilarity to be transitive, and more strongly, for behavioral
equivalence to entail bisimilarity. This is not true in the general case [11],
but it was proved by Edalat that if the state spaces $(S,\Sigma)$,
$(S^{\prime},\Sigma^{\prime})$ are analytic, then it holds: every _cospan_
$\mathbf{S}\rightarrow\mathbf{U}\leftarrow\mathbf{S^{\prime}}$ can be
completed to commutative square by finding an appropriate $\mathbf{T}$ and
arrows to $\mathbf{S}$, $\mathbf{S^{\prime}}$. This $\mathbf{T}$ is called the
_semipullback_ of the cospan.

In his [5], Edalat specifically shows the existence of semipullbacks in the
category of Markov kernels (that is, LMP with a singleton label set $L$) over
analytic state spaces and Borel zigzag maps. From this the result for general
LMP follows.

In the present paper we will show that the existence of semipullbacks holds in
the larger category of Markov kernels over universally measurable spaces. Our
proof does not rely on the existence of disintegrations (regular conditional
probabilities) as in [5], but we use a result about common extensions of
finitely additive measures (Lemma 6, a version of Strassen’s theorem). In
Section 2 we present a related category, that of _probability kernels_. The
main technical result of this paper is to show that this category has
semipullbacks. In Section 3 we gather some results on extensions of finitely
additive measures. Section 4 presents the construction of the semipullback
$S_{3}$ of a given cospan of probability kernels $S_{1}\to S_{0}\leftarrow
S_{2}$; this is essentially built over the set-theoretic pullback of that
diagram. The reduction of the problem of Markov kernels and general LMP to our
result is done in Section 5; in particular we show that LMP over coanalytic
Borel spaces have semipullbacks. We conclude with some counterexamples in the
last section.

##  2 Probability kernels

We find it technically convenient to describe the main construction in terms
of probability kernels from a fixed measurable space. Let $(X,\Xi)$ and
$(S,\Sigma)$ be two measurable spaces. As in [9, Ch.1], a mapping $\mu\colon
X\times\Sigma\to[0,\infty)$ is a _kernel from $X$ to $S$_ if $\mu(x,\cdot)$ is
a measure on $\Sigma$ for each $x\in X$ and $\mu(\cdot,Q)$ is a
$\Xi$–$\mathfrak{B}([0,1])$-measurable function on $X$ for each $Q\in\Sigma$.
From now on we write $\mu^{x}(Q)$ instead of $\mu(x,Q)$ for $x\in X$,
$Q\in\Sigma$.

We say that $\mu$ is a _probability kernel_ if $\mu^{x}(S)=1$ for all $x\in
X$, and a _subprobability kernel_ if $\mu^{x}(S)\leq 1$ for all $x\in X$. We
say that $\mu$ is a _Radon (sub)probability kernel_ if moreover $S$ is a
topological space, $\Sigma$ is its Borel $\sigma$-algebra and every $\mu^{x}$
is a Radon (sub)probability measure on $\Sigma$.

Thus a Markov kernel in the definition of LMP above is a subprobability kernel
from $S$ to itself.

When $\mu$ is a kernel from $X$ to $S$, we write $(S,\Sigma,\mu)$ instead of
$\mu$ when $(X,\Xi)$ is understood and we wish to make $S$ and $\Sigma$
explicit.

For a fixed $(X,\Xi)$, kernels from $X$ form a category with surjective
measure-preserving maps as morphisms:

######  Definition 2.

Let $(X,\Xi)$ be a fixed measurable space. For $j=1,2$ and $x\in X$ let
$(S_{j},\Sigma_{j},\mu^{x}_{j})$ be a measure space such that $\mu_{j}$ is a
kernel from $X$ to $S_{j}$. A mapping $h\colon S_{1}\to S_{2}$ is a _kernel
morphism from $\mu_{1}$ to $\mu_{2}$_ if it is $\Sigma_{1}$–$\Sigma_{2}$
measurable, $h(S_{1})=S_{2}$, and $\mu^{x}_{1}(h^{-1}(A))=\mu^{x}_{2}(A)$ for
all $x\in X$, $A\in\Sigma_{2}$. A morphism $h$ from $\mu_{1}$ to $\mu_{2}$ is
sometimes written
$h\colon(S_{1},\Sigma_{1},\mu_{1})\to(S_{2},\Sigma_{2},\mu_{2})$, or simply
$h\colon S_{1}\to S_{2}$ when $\Sigma_{j}$ and $\mu_{j}$ are understood.

In the present paper we prove:

######  Theorem 3.

Let $(X,\Xi)$ be a fixed measurable space. Consider the category in which each
object is a Radon subprobability kernel from $X$ to a separable metric space,
and morphisms are kernel morphisms. Every cospan
$(S_{1},\Sigma_{1},\mu_{1})\rightarrow(S_{0},\Sigma_{0},\mu_{0})\leftarrow(S_{2},\Sigma_{2},\mu_{2})$
has a semipullback $(S_{3},\Sigma_{3},\mu_{3})$ such that $S_{3}$ is the set
pullback of $S_{1}\rightarrow S_{0}\leftarrow S_{2}$. Moreover $S_{3}$ is a
measurable subset of $S_{1}\times S_{2}$.

We will first prove the theorem for probability kernels. For this we fix, up
to Section 4, three Radon probability kernels $(S_{j},\Sigma_{j},\mu_{j})$
(for $j=0,1,2$) as in the statement of Theorem 3, and for $j=1,2$, kernel
morphisms $h_{j}\colon S_{j}\to S_{0}$. Our goal is to construct a
semipullback of $h_{1}$, $h_{2}$, i.e. $(S_{3},\Sigma_{3},\mu_{3})$ and for
$j=1,2$, morphisms $k_{j}\colon S_{3}\to S_{j}$ such that $h_{1}\circ
k_{1}=h_{2}\circ k_{2}$ (see Figure 1).

---
$\textstyle{{(S_{3},\Sigma_{3},\mu_{3})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{k_{1}}$$\scriptstyle{k_{2}}$$\textstyle{{(S_{1},\Sigma_{1},\mu_{1})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h_{1}}$$\textstyle{{(S_{2},\Sigma_{2},\mu_{2})}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{h_{2}}$$\textstyle{(S_{0},\Sigma_{0},\mu_{0})}$
Figure 1: A semipullback.

We first proceed to construct the pullback of the mappings $h_{1}$ and $h_{2}$
in the category of measurable spaces, whose upper vertex will be the
underlying space of the semipullback. Let $\pi_{j}\colon S_{1}\times S_{2}\to
S_{j}$, $j=1,2$, be the natural projections. Denote by
$\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2}$ the smallest
$\sigma$-algebra on $S_{1}\times S_{2}$ for which $\pi_{j}$ are
$\Sigma_{j}$-measurable.

Define

$\begin{split}S_{3}&:=\\{(x_{1},x_{2})\in S_{1}\times
S_{2}:h_{1}(x_{1})=h_{2}(x_{2})\\}\\\ \Sigma_{3}&:=\\{A\cap
S_{3}:A\in\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2}\\}\\\ k_{j}&:=\text{
restriction of }\pi_{j}\text{ to }S_{3},\text{ for }j=1,2.\end{split}$ (1)

Then $k_{j}(S_{3})=S_{j}$ for $j=1,2$ (because $h_{j}(S_{j})=S_{0}$).

All that remains now is to construct the probability kernel $\mu_{3}$; this
will be done in several steps. We define a countable algebra
$\mathfrak{A}\subseteq\Sigma_{3}$ that generates $\Sigma_{3}$ as a
$\sigma$-algebra, and finitely additive measures $\nu^{x}_{3}$ on
$\mathfrak{A}$. In defining $\nu^{x}_{3}$ we use a constructive variant of the
Hahn-Banach theorem, to ensure that $\nu^{x}_{3}$ is a measurable function of
$x$. Then we prove that $\nu^{x}_{3}$ is countably additive, so that it
extends to a countably additive measure $\mu^{x}_{3}$ on $\Sigma_{3}$.

##  3 Preliminaries

In this section we establish notation and several results that will be needed
in the main construction.

If $S$ is a set and $V$ is a linear subspace of $\ell_{\infty}(S)$, write
$V^{+}:=\\{f\in V:f\geq 0\\}$. Here $\geq$ is the pointwise partial order on
the real-valued functions on $S$.

When $\mathfrak{B}_{1}$ and $\mathfrak{B}_{2}$ are algebras of subsets of
$S_{1}$ and $S_{2}$, we denote by $\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}$
the algebra of subsets of $S_{1}\times S_{2}$ consisting of finite unions of
sets of the form $B_{1}\times B_{2}$, $B_{j}\in\mathfrak{B}_{j}$ for $j=1,2$.
Recall that we denote by
$\mathfrak{B}_{1}\mathbin{\widehat{\otimes}}\mathfrak{B}_{2}$ the
$\sigma$-algebra generated by $\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}$.

If $\mathfrak{A}$ is an algebra of sets, denote by $\mathsf{L}(\mathfrak{A})$
the space of simple $\mathfrak{A}$-measurable functions; that is, functions of
the form $\sum_{i\in F}r_{i}\chi_{A_{i}}$ where $F$ is a finite set,
$A_{i}\in\mathfrak{A}$ and $r_{i}\in\mathbb{R}$ for $i\in F$. If in addition
$\nu$ is a finitely additive measure on $\mathfrak{A}$, denote by
$\overline{\nu}$ its integral defined on $\mathsf{L}(\mathfrak{A})$:

$\overline{\nu}(f):=\int f\mathrm{d}\nu\quad\text{for
}f\in\mathsf{L}(\mathfrak{A}).$

In other words, $\overline{\nu}(f)=\sum_{i\in F}r_{i}\nu(A_{i})$ when
$f=\sum_{i\in F}r_{i}\chi_{A_{i}}$. This is well-defined— see e.g. [4, Ch.
III].

Note that if $\nu^{x}(A)$ is a measurable function of $x$ for every
$A\in\mathfrak{A}$ then so is $\overline{\nu^{x}}(f)$ for every
$f\in\mathsf{L}(\mathfrak{A})$.

######  Lemma 4.

Any Borel-measurable image of a compact metrizable space in a separable metric
space is analytic, and therefore universally measurable.

###### Proof.

Let $K$ be compact, $S$ a separable metric space, and $h:K\to S$ Borel. Then
the completion $\hat{S}$ of $S$ is analytic and $h:K\to\hat{S}$ is also Borel.
Hence by [7, 423G(b)] the image is analytic, hence by [7, 434D(c)] it is
universally measurable. ∎

######  Lemma 5.

Let $S$ and $S_{0}$ be metric spaces and $\Sigma$, $\Sigma_{0}$ their Borel
$\sigma$-algebras. Let $\mu$ and $\mu_{0}$ be Radon probability measures on
$\Sigma$ and $\Sigma_{0}$, respectively. Let $h\colon S\to S_{0}$ be a Borel-
measurable measure-preserving mapping. Then for every $A\in\Sigma$ there
exists $D\in\Sigma_{0}$ such that $D\subseteq h(A)$ and
$\mu_{0}(D)\geq\mu(A)$.

###### Proof.

Since $\mu$ is inner regular with respect to compact sets, we can find a
countable family $\mathcal{K}$ of compact subsets of $A$ such that

$\mu(A)=\sup\\{\mu(K):K\in\mathcal{K}\\}.$

For every such $K$ the image $h(K)$ is universally measurable by Lemma 4.
Therefore, there exist $B_{K},B^{\prime}_{K}\in\Sigma_{0}$ such that
$B_{K}\subseteq h(K)\subseteq B^{\prime}_{K}$ and
$\mu_{0}(B^{\prime}_{K}\setminus B_{K})=0$. Since $h$ is measure-preserving,
we have

$\mu_{0}(B_{K})=\mu_{0}(B^{\prime}_{K})=\mu(h^{-1}(B^{\prime}_{K})).$

Now $h^{-1}[B^{\prime}_{K}]\supseteq K$, and therefore
$\mu_{0}(B_{K})=\mu(h^{-1}(B^{\prime}_{K}))\geq\mu(K)$ for each
$K\in\mathcal{K}$. Hence we may take
$D\mathrel{\mathop{:}}=\mathop{\textstyle\bigcup}\\{B_{K}:K\in\mathcal{K}\\}$.
∎

######  Lemma 6 ([7, 457C]).

Let $\mathfrak{A}$ be an algebra of subsets of a set $S$, and
$\mathfrak{A}_{j}$, $j=1,2$, two of its subalgebras. Let
$\nu_{j}\colon\mathfrak{A}_{j}\to[0,1]$, $j=1,2$, be finitely additive
measures such that $\nu_{1}(S)=\nu_{2}(S)=1$. Assume that
$\nu_{1}(A_{1})+\nu_{2}(A_{2})\leq 1$ whenever $A_{j}\in\mathfrak{A}_{j}$,
$j=1,2,$ are such that $A_{1}\cap A_{2}=\emptyset$. Then there exists a
finitely additive measure $\nu\colon\mathfrak{A}\to[0,1]$ that extends both
$\nu_{1}$ and $\nu_{2}$. ∎

We need the following variant of the Hahn-Banach theorem, which preserves
measurability.

######  Lemma 7.

Let $S$ be a non-empty set. Let $V\subseteq\ell_{\infty}(S)$ be a subspace of
countable dimension and $W$ a subspace of $V$ that contains all constant
functions on $S$. Let $\Psi^{x}\colon W\to\mathbb{R}$, $x\in X$, be a
collection of linear functionals on $W$ such that $\Psi^{x}(f)$ is a
measurable function of $x$ for every $f\in W$, $\Psi^{x}(1)=1$ and
$\Psi^{x}(f)\geq 0$ for $f\in W^{+}$, $x\in X$. Then there is a collection of
linear functionals $\Phi^{x}\colon V\to\mathbb{R}$, $x\in X$, that extend
$\Psi^{x}$ and such that $\Phi^{x}(f)$ is a measurable function of $x$ for
every $f\in V$, and $\Phi^{x}(f)\geq 0$ for $f\in V^{+}$, $x\in X$.

###### Proof.

Extend $\Psi^{x}$ one dimension at a time. When $\Phi^{x}$ has been defined on
a linear subspace $U\supseteq W$ and $f_{0}\in V\setminus U$, define $p^{x}$
and $\Phi^{x}$ on $U+\mathbb{R}f_{0}$ by

$\displaystyle p^{x}(f)$ $\displaystyle:=\inf\\{\Phi^{x}(g):g\in U\text{ and
}g\geq f\\}\quad\text{for }f\in U+\mathbb{R}f_{0}$
$\displaystyle\Phi^{x}(f_{0})$
$\displaystyle:=\inf\\{p^{x}(g+f_{0})-\Phi^{x}(g):g\in U\\}.$

Thus $p^{x}$ is subadditive and positively homogeneous on $U+\mathbb{R}f_{0}$.
We claim that $\Phi^{x}(f)\leq p^{x}(f)$ for every $f\in U+\mathbb{R}f_{0}$.
To prove the claim, write $f=u+rf_{0}$ where $u\in U$ and $r\in\mathbb{R}$,
and distinguish two cases:
For $r>0$ use $g=u/r$ in the definition of $\Phi^{x}(f_{0})$ to get

$\displaystyle\Phi^{x}(f)$
$\displaystyle=\Phi^{x}(u)+r\Phi^{x}(f_{0})=\Phi^{x}(u)+\inf\\{rp^{x}(g+f_{0})-r\Phi^{x}(g):g\in
U\\}$
$\displaystyle\leq\Phi^{x}(u)+rp^{x}((u/r)+f_{0})-r\Phi^{x}(u/r)=p^{x}(f).$

For $r<0$ we have

$\displaystyle\Phi^{x}(g)-\Phi^{x}(u/r)$ $\displaystyle=p^{x}(g-(u/r))\leq
p^{x}(g+f_{0})+p^{x}(-(u/r)-f_{0})$ for $g\in U$,
$\displaystyle-p^{x}(-(u/r)-f_{0})-\Phi^{x}(u/r)$
$\displaystyle\leq\inf\\{p^{x}(g+f_{0})-\Phi^{x}(g):g\in U\\}=\Phi^{x}(f_{0})$
$\displaystyle\Phi^{x}(f)=r\Phi^{x}(u/r)+r\Phi^{x}(f_{0})$ $\displaystyle\leq-
rp^{x}(-(u/r)-f_{0})=p^{x}(u+rf_{0})=p^{x}(f).$

That proves the claim. It follows that if $f\in(U+\mathbb{R}f_{0})^{+}$ then

$\Phi^{x}(f)=-\Phi^{x}(-f)\geq-p^{x}(-f)\geq 0.$

To prove that $\Phi^{x}(f_{0})$ is a measurable function of $x$ for every
$f\in U$, fix a countable basis $C$ of $U$ such that $1\in C$ and define
$\widetilde{U}$ to be the set of finite linear combinations of elements of $C$
with rational coefficients. Then

$\displaystyle p^{x}(f)$
$\displaystyle=\inf\\{\Phi^{x}(g):g\in\widetilde{U}\text{ and }g\geq
f\\}\quad\text{for }f\in U+\mathbb{R}f_{0}$ $\displaystyle\Phi^{x}(f_{0})$
$\displaystyle=\inf\\{p^{x}(g+f_{0})-\Phi^{x}(g):g\in\widetilde{U}\\}$

so that $x\mapsto\Phi^{x}(f_{0})$ is the infimum of a countable set of
measurable functions. ∎

The next lemma is a variant of a theorem of Marczewski and Ryll-Nardzewski
[10]. When $\mathfrak{B}_{j}=\Sigma_{j}$, this is a special case of [7, 454C].

######  Lemma 8.

Let $S_{1}$ be a Hausdorff topological space, $\Sigma_{1}$ its Borel
$\sigma$-algebra and $\mu_{1}\colon\Sigma_{1}\to[0,1]$ a Radon probability
measure. Let $(S_{2},\Sigma_{2},\mu_{2})$ be any probability space. Denote by
$\pi_{j}\colon S_{1}\times S_{2}\to S_{j}$ the natural projections. For
$j=1,2$, let $\mathfrak{B}_{j}\subseteq\Sigma_{j}$ be an algebra of subsets of
$S_{j}$. Let $\mu\colon\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}\to[0,1]$ be a
finitely additive measure such that $\mu(\pi_{j}^{-1}(B_{j}))=\mu_{j}(B_{j})$
for $j=1,2$ and all $B_{j}\in\mathfrak{B}_{j}$. Then $\mu$ has an extension to
a countably additive measure on the $\sigma$-algebra
$\mathfrak{B}_{1}\mathbin{\widehat{\otimes}}\mathfrak{B}_{2}$.

###### Proof.

This is a minor modification of the proof of [7, 454C]. Let $\mathfrak{D}$ be
the set of finite unions of sets of the form $C\times B_{2}$ where $C$ is a
compact subset of $S_{1}$ and $B_{2}\in\mathfrak{B}_{2}$. As $\mu_{1}$ is a
Radon measure, it follows that for every $\varepsilon>0$ and
$B\in\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}$ there are $D\in\mathfrak{D}$ and
$E\in\Sigma_{1}$ such that $D\subseteq B$, $\mu_{1}(E)<\varepsilon$ and
$B\subseteq D\cup(E\times S_{2})$.

Now let $\\{B_{i}\\}_{i\in\mathbb{N}}$ be a non-increasing sequence of sets in
$\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}$ with empty intersection. To prove
that $\lim_{i}\mu(B_{i})=0$, take any $\varepsilon>0$. There are
$D_{i}^{\prime}\in\mathfrak{D}$ and $E_{i}^{\prime}\in\Sigma_{1}$ such that
$D_{i}^{\prime}\subseteq B_{i}$, $\mu_{1}(E_{i}^{\prime})<2^{-i}\varepsilon$
and $B_{i}\subseteq D_{i}^{\prime}\cup(E_{i}^{\prime}\times S_{2})$. Set
$D_{n}:=\bigcap_{i\leq n}D_{i}^{\prime}$ and $E_{n}:=\bigcup_{i\leq
n}E_{i}^{\prime}$ for each $n$. Then $\\{D_{n}\\}_{n}$ is a non-increasing
sequence of sets in $\mathfrak{D}$, $D_{n}\subseteq B_{n}$,
$\mu_{1}(E_{n})<2\varepsilon$ and $B_{n}\subseteq D_{n}\cup(E_{n}\times
S_{2})$.

For $n\in\mathbb{N}$ and $y\in S_{2}$ set
$D_{n}^{y}:=\pi_{1}(D_{n}\cap\pi_{2}^{-1}(y))$ and $H_{n}:=\pi_{2}(D_{n})$.
Then $\\{D_{n}^{y}\\}_{n}$ and $\\{H_{n}\\}_{n}$ are non-increasing sequences
of subsets of $S_{1}$ and $S_{2}$, respectively. The sets $D_{n}^{y}$ are
compact and $H_{n}\in\mathfrak{B}_{2}$. Next $\bigcap_{n}D_{n}^{y}=\emptyset$
because $\bigcap_{n}D_{n}\subseteq\bigcap_{n}B_{n}=\emptyset$. Hence for every
$y\in S_{2}$ there is $n$ such that $D_{n}^{y}=\emptyset$, which means that
$\bigcap_{n}H_{n}=\emptyset$. It follows that

$\lim_{i}\mu(B_{i})\leq\lim_{i}\mu(S_{1}\times
H_{i})+\lim_{i}\mu(B_{i}\setminus(S_{1}\times
H_{i}))\leq\lim_{i}\mu_{2}(H_{i})+\lim_{i}\mu_{1}(E_{i})\leq 2\varepsilon.$

We have proved that $\lim_{i}\mu(B_{i})=0$. By [7, 413K] $\mu$ has an
extension to a countably additive measure on the $\sigma$-algebra generated by
$\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}$. ∎

##  4 Proof of the main theorem

In this section we complete the proof of Theorem 3. Recall that $S_{j}$,
$j=0,1,2$, are separable metric spaces, $\Sigma_{j}$ are their Borel
$\sigma$-algebras, and $\mu_{j}$ are Radon probability kernels from $X$ to
$S_{j}$.

For $j=0,1,2$, fix countable algebras $\mathfrak{B}_{j}\subseteq\Sigma_{j}$
such that

  * •

$\mathfrak{B}_{j}$ generates $\Sigma_{j}$ as a $\sigma$-algebra for $j=0,1,2,$
and

  * •

$h_{j}^{-1}(B_{0})\in\mathfrak{B}_{j}$ whenever $B_{0}\in\mathfrak{B}_{0}$,
for $j=1,2$.

For $j=1,2$, define
$\mathfrak{A}_{j}:=\\{k_{j}^{-1}(B):B\in\mathfrak{B}_{j}\\}$. Let
$\mathfrak{A}$ be the algebra of subsets of $S_{3}$ generated by
$\mathfrak{A}_{1}\cup\mathfrak{A}_{2}$. Then $\mathfrak{A}$ is countable and
it generates $\Sigma_{3}$ as a $\sigma$-algebra.

For $j=1,2$, and $B\in\mathfrak{B}_{j}$, let
$\nu^{x}_{j}(k_{j}^{-1}(B)):=\mu^{x}_{j}(B)$. As $k_{j}(S_{3})=S_{j}$, this is
well defined and $\nu^{x}_{j}$ is a finitely additive measure on
$\mathfrak{A}_{j}$.

Take any $A_{j}\in\mathfrak{A}_{j}$, $j=1,2,$ such that $A_{1}\cap
A_{2}=\emptyset$. Then $A_{j}=k_{j}^{-1}(B_{j})$ for some
$B_{j}\in\mathfrak{B}_{j}$. By Lemma 5 there are $D_{j}\in\Sigma_{0}$ such
that $D_{j}\subseteq h_{j}(B_{j})$ and
$\mu^{x}_{0}(D_{j})\geq\mu^{x}_{j}(B_{j})$. From the definition of $S_{3}$ we
get $h_{1}(B_{1})\cap h_{2}(B_{2})=\emptyset$, hence $D_{1}\cap
D_{2}=\emptyset$. Therefore

$\nu^{x}_{1}(A_{1})+\nu^{x}_{2}(A_{2})=\mu^{x}_{1}(B_{1})+\mu^{x}_{2}(B_{2})\leq\mu^{x}_{0}(D_{1})+\mu^{x}_{0}(D_{2})\leq
1.$

By Lemma 6 there is a finitely additive measure $\nu^{x}$ on $\mathfrak{A}$
that extends both $\nu^{x}_{1}$ and $\nu^{x}_{2}$. As the proof of Lemma 6
relies on the axiom of choice, $\nu^{x}(A)$ is not necessarily a measurable
function of $x$ for every $A\in\mathfrak{A}$. However, observe that
$\overline{\nu^{x}}(f)$ is a measurable function of $x$ for every
$f\in\mathsf{L}(\mathfrak{A}_{1})+\mathsf{L}(\mathfrak{A}_{2})$. Indeed, if
$f=f_{1}+f_{2}$, $f_{j}\in\mathsf{L}(\mathfrak{A}_{j})$ for $j=1,2$, then

$\overline{\nu^{x}}(f)=\overline{\nu^{x}_{1}}(f_{1})+\overline{\nu^{x}_{2}}(f_{2})$

by the linearity of integral, so that $\overline{\nu^{x}}(f)$ is a sum of two
measurable functions of $x$.

By Lemma 7 with $W=\mathsf{L}(\mathfrak{A}_{1})+\mathsf{L}(\mathfrak{A}_{2})$
there is a linear functional
$\Phi^{x}\colon\mathsf{L}(\mathfrak{A})\to\mathbb{R}$ that agrees with
$\overline{\nu^{x}}$ on
$\mathsf{L}(\mathfrak{A}_{1})+\mathsf{L}(\mathfrak{A}_{2})$ and such that
$\Phi^{x}(f)$ is a measurable function of $x$ for every
$f\in\mathsf{L}(\mathfrak{A})$, and $\Phi^{x}(f)\geq 0$ for
$f\in\mathsf{L}(\mathfrak{A})^{+}$, $x\in X$. Now
$\nu^{x}_{3}(A):=\Phi^{x}(\chi_{A})$ for $A\in\mathfrak{A}$ defines a finitely
additive measure $\nu^{x}_{3}\geq 0$ on $\mathfrak{A}$ such that
$\nu^{x}_{3}(S_{3})=1$ and $x\mapsto\nu^{x}_{3}(A)$ is measurable for every
$A\in\mathfrak{A}$.

We have $\mathfrak{A}=\\{B\cap
S_{3}:B\in\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}\\}$. For
$B\in\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}$ define
$\mu^{x}(B):=\nu^{x}_{3}(B\cap S_{3})$. By Lemma 8 each $\mu^{x}$ extends to a
countably additive measure $\widehat{\mu}^{x}$ on the $\sigma$-algebra
$\mathfrak{B}_{1}\mathbin{\widehat{\otimes}}\mathfrak{B}_{2}=\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2}$,
which is the Borel $\sigma$-algebra of the product topology on $S_{1}\times
S_{2}$. By [7, 454A(a)], $\widehat{\mu}^{x}$ is a Radon measure.

######  Lemma 9.

$S_{3}\in\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2}$; moreover, we have

$S_{1}\times S_{2}\setminus S_{3}=\bigcup\\{h_{1}^{-1}(B_{0})\times
h_{2}^{-1}(S_{0}\setminus B_{0}):B_{0}\in\mathfrak{B}_{0}\\}$ (2)

and $\widehat{\mu}^{x}(S_{3})=1$.

###### Proof.

Take any $(x_{1},x_{2})\in S_{1}\times S_{2}\setminus S_{3}$. Then
$h_{1}(x_{1})\neq h_{2}(x_{2})$, hence there is $B_{0}\in\mathfrak{B}_{0}$
such that $h_{1}(x_{1})\in B_{0}$ and $h_{2}(x_{2})\not\in B_{0}$, which means
$(x_{1},x_{2})\in h_{1}^{-1}(B_{0})\times h_{2}^{-1}(S_{0}\setminus B_{0})$.

Each set $B:=h_{1}^{-1}(B_{0})\times h_{2}^{-1}(S_{0}\setminus B_{0})$, where
$B_{0}\in\mathfrak{B}_{0}$, is in the algebra
$\mathfrak{B}_{1}\otimes\mathfrak{B}_{2}$ and
$\widehat{\mu}^{x}(B)=\mu^{x}(B)=\nu^{x}_{3}(\emptyset)=0$. It follows that
$S_{3}\in\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2}$ and
$\widehat{\mu}^{x}(S_{3})=1$. ∎

By Lemma 9, $S_{3}$ is a measurable subset of $S_{1}\times S_{2}$. Define
$\mu_{3}^{x}$ to be the restriction of $\widehat{\mu}^{x}$ to the
$\sigma$-algebra $\Sigma_{3}$.

It remains to be proved that for every $E\in\Sigma_{3}$ the function
$x\mapsto\mu_{3}^{x}$ is measurable. To that end define

$\mathcal{D}\mathrel{\mathop{:}}=\\{E\in\Sigma_{3}:x\mapsto\mu_{3}^{x}(E)\text{
is measurable}\\}.$

Then $\mathfrak{A}\subseteq\mathcal{D}$, and $\mathcal{D}$ is closed under
complements and unions of disjoint sequences. By the Monotone Class Theorem
[6, 136B] we have $\mathcal{D}=\Sigma_{3}$.

That completes the proof of Theorem 3 for the case of probability kernels. To
extend the result to subprobability kernels we work as follows. Let
$(S_{1},\Sigma_{1},\mu_{1})\rightarrow(S_{0},\Sigma_{0},\mu_{0})\leftarrow(S_{2},\Sigma_{2},\mu_{2})$
be a cospan of Radon subprobability kernels, where $S_{j}$ are separable
metric spaces.

Define $\bar{S}_{j}\mathrel{\mathop{:}}=S_{j}\oplus\\{s_{j}\\}$ where
$s_{j}\notin S_{j}$ for each $j=0,1,2$ and for measurable
$E\subseteq\bar{S}_{j}$, let

$\bar{\mu}^{x}_{j}(E)\mathrel{\mathop{:}}=\mu_{j}^{x}(E\cap
S_{j})+(1-\mu_{j}^{x}(S_{j}))\cdot\chi_{E}(s_{j})$

Then $\bar{\mu}_{j}$ are Radon probability kernels. We also extend the maps
$h_{j}$ by stipulating

$\bar{h}_{j}(x)\mathrel{\mathop{:}}=\begin{cases}h_{j}(x)&x\neq s_{j}\\\
s_{0}&x=s_{j}\end{cases}$

for $j=1,2$. Then $\bar{h}_{j}$ are kernel morphisms.

By Theorem 3 for probability kernels, the cospan
$\bar{S}_{1}\rightarrow\bar{S}_{0}\leftarrow\bar{S}_{2}$ has a semipullback
$(\bar{S}_{3},\bar{\Sigma}_{3},\bar{\mu}_{3})$ with kernel morphisms
$k_{j}\colon\bar{S}_{3}\to\bar{S}_{j}$, and
$\bar{S}_{3}\subseteq\bar{S}_{1}\times\bar{S}_{2}$ is the set pullback. Hence
$\bar{S}_{3}=S_{3}\oplus\\{(s_{1},s_{2})\\}$ where $S_{3}$ is the set pullback
of $S_{1}\rightarrow S_{0}\leftarrow S_{2}$.

We can take $\mu^{x}_{3}$ to be the restriction of $\bar{\mu}^{x}_{3}$ to
$\Sigma_{3}\mathrel{\mathop{:}}=\\{E\cap S_{3}:E\in\bar{\Sigma}_{3}\\}$. It is
straightforward to check that the restrictions $k_{j}\restriction S_{3}$ are
kernel morphisms from $S_{3}$ onto $S_{j}$ for $j=1,2$, and we are done.

##  5 Application to the problem of bisimulation

###  5.1 Labelled Markov processes with Radon measures

By Theorem 3, semipullbacks exist in a certain category of subprobability
kernels from a fixed measurable space $(X,\Xi)$.

As a corollary we obtain the following theorem, which asserts the existence of
semipullbacks in the corresponding category of LMP and zigzag morphisms:

######  Theorem 10.

Consider the category in which objects are LMP $(S,\Sigma,\\{\tau_{a}:a\in
L\\})$ such that $S$ is a separable metric space and $\tau_{a}(s,\cdot)$ are
Radon measures, with zigzag morphisms. In this category every cospan has a
semipullback.

Moreover, every cospan

$(S_{1},\Sigma_{1},\\{\tau_{1a}:a\in
L\\})\rightarrow(S_{0},\Sigma_{0},\\{\tau_{0a}:a\in
L\\})\leftarrow(S_{2},\Sigma_{2},\\{\tau_{2a}:a\in L\\})$

has a semipullback $(S_{3},\Sigma_{3},\\{\tau_{3a}:a\in L\\})$ such that
$S_{3}$ is the set pullback of $S_{1}\rightarrow S_{0}\leftarrow S_{2}$ and
$S_{3}$ is a measurable subset of $S_{1}\times S_{2}$.

###### Proof.

First we deal with the LMP for which the label set $L$ has a single element
$a$, and write $\tau=\tau_{a}$.

Let
$(S_{1},\Sigma_{1},\tau_{1})\rightarrow(S_{0},\Sigma_{0},\tau_{0})\leftarrow(S_{2},\Sigma_{2},\tau_{2})$
be a cospan in the given category, with connecting zigzags $h_{j}\colon
S_{j}\to S_{0}$, $j=1,2$. As in Theorem 3, take the measurable pullback
$(S_{3},\Sigma_{3})$ with the measurable mappings $k_{j}\colon S_{3}\to
S_{j}$, $j=1,2$.

Now let $(X,\Xi)\mathrel{\mathop{:}}=(S_{3},\Sigma_{3})$ and for $x\in X$,
$j=1,2$, define

$\displaystyle\mu^{x}_{j}$
$\displaystyle\mathrel{\mathop{:}}=\tau^{k_{j}(x)}_{j}$ $\displaystyle j=1,2$
$\displaystyle\mu^{x}_{0}$
$\displaystyle\mathrel{\mathop{:}}=\tau^{h_{1}(k_{1}(x))}_{0}=\tau^{h_{2}(k_{2}(x))}_{0}.$

Since the maps $k_{j}$, $h_{j}$ and $x\mapsto\tau^{x}_{j}$ are measurable, it
follows that $\mu_{j}$ are subprobability kernels. By Theorem 3 there exists a
semipullback $\mu_{3}$ in the category of Radon subprobability kernels from
$X=S_{3}$. For $A\in\Sigma_{j}$, $j=1,2$, and $x\in S_{3}$ we have

$\mu^{x}_{3}(k^{-1}_{j}(A))=\mu^{x}_{j}(A)=\tau^{k_{j}(x)}_{j}(A),$

which means that $\mu_{3}$ is also a semipullback in the LMP category. That
concludes the proof for the case of a singleton label set $L$.

Now consider an arbitrary label set $L$. We have just proved that for each
$a\in L$ there exists a semipullback $(S_{3},\Sigma_{3},\tau_{a})$ in which
$S_{3}$ and $\Sigma_{3}$ do not depend on $a$. But that means that
$(S_{3},\Sigma_{3},\\{\tau_{a}:a\in L\\})$ is a semipullback in the category
of the LMP labelled by $L$. ∎

###  5.2 Universally measurable labelled Markov processes

Theorem 10 places a restriction on each measure $\tau_{a}(s,\cdot)$. It may be
more convenient to have instead a single restriction on the underlying space
$S$, as in the next theorem.

######  Definition 11.

A measurable space $(S,\Sigma)$ is a _separable universally measurable space_
if it is isomorphic to a universally measurable subset of a separable
completely metrizable (“Polish”) space with the trace of the Borel
$\sigma$-algebra.

######  Theorem 12.

Consider the category in which objects are LMP $(S,\Sigma,\\{\tau_{a}:a\in
L\\})$ such that $S$ is a separable universally measurable space, with zigzag
morphisms. In this category, every cospan has a semipullback.

###### Proof.

Let

$(S_{1},\Sigma_{1},\\{\tau_{1a}:a\in
L\\})\rightarrow(S_{0},\Sigma_{0},\\{\tau_{0a}:a\in
L\\})\leftarrow(S_{2},\Sigma_{2},\\{\tau_{2a}:a\in L\\})$

be a cospan of LMP with $S_{j}$ separable universally measurable spaces. Then
each $(S_{j},\Sigma_{j})$ is isomorphic to some
$(X_{j},\mathfrak{B}(Y_{j})\restriction X_{j})$ where $X_{j}$ is a universally
measurable subset of a Polish space $Y_{j}$ and $\mathfrak{B}(Y_{j})$ is its
Borel $\sigma$-algebra. Since $Y_{j}$ is a Radon space, by [7, 434F(c)] we
conclude that every Borel measure on $X_{j}$ is Radon.

Let $(S_{3},\Sigma_{3},\\{\tau_{3a}:a\in L\\})$ be a semipullback with the
properties from Theorem 10. In particular, $S_{3}$ is a measurable subset of
$S_{1}\times S_{2}$. It remains to prove that $S_{3}$ is a separable
universally measurable space. There exists a measurable isomorphism

$f:(S_{1}\times
S_{2},\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2})\to(X_{1}\times
X_{2},\mathfrak{B}(Y_{1}\times Y_{2})\restriction X_{1}\times X_{2}),$

$X_{1}\times X_{2}$ is universally measurable by [7, 434X(c)]. But then
$(S_{3},\Sigma_{3})=(S_{3},\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2}\restriction
S_{3})$ is isomorphic to $(f(S_{3}),\mathfrak{B}(Y_{1}\times
Y_{2})\restriction f(S_{3}))$, where $f(S_{3})\in\mathfrak{B}(Y_{1}\times
Y_{2})\restriction X_{1}\times X_{2}$ since
$S_{3}\in\Sigma_{1}\mathbin{\widehat{\otimes}}\Sigma_{2}$. ∎

In [11] it was asked whether behaviorally equivalent LMP over coanalytic
spaces were bisimilar. We can answer this question affirmatively. Recall that
a metric space is coanalytic if it is homeomorphic to the complement of an
analytic subset of a Polish space. We say that a measurable space is
_coanalytic_ if it is isomorphic to the Borel space of a coanalytic metric
space.

######  Corollary 13.

The category of LMP over coanalytic measurable spaces has semipullbacks.

###### Proof.

This follows by essentially the same argument for Theorem 12, showing that a
cospan of coanalytic measurable spaces has a coanalytic pullback, and that
coanalytic sets are universally measurable. ∎

In the same way, every analytic space with its Borel $\sigma$-algebra is a
separable universally measurable space; hence we obtain Edalat’s result [5] as
a corollary to Theorem 12 as well.

##  6 Counterexamples

The key assumption in previous sections is that each measure is defined on the
Borel $\sigma$-algebra. The results no longer hold without that assumption,
even for $\sigma$-algebras of subsets of $[0,1]$. The counterexample in [11]
uses a $\sigma$-algebra larger than the Borel $\sigma$-algebra on $[0,1]$; we
hint at this construction below. In the opposite direction, the following
counterexample uses $\sigma$-algebras that are smaller but still large enough
to separate the points of $[0,1]$.

######  Example 14.

Consider $(S,\Sigma)$ to be the interval $[0,1]$ with the countable-
cocountable $\sigma$-algebra, and let $\mu_{0}:\Sigma\to\\{0,1\\}$ be the
probability measure such that

$\mu_{0}(Q)=1\iff Q\text{ has countable complement.}$

Take $V\mathrel{\mathop{:}}=[0,\tfrac{1}{2}]$. It is straightforward to check
that for any different $r_{1},r_{2}\in(0,1)$, the following maps

$\mu_{i}(Q)\mathrel{\mathop{:}}=\begin{cases}\mu(Q)&Q\in\Sigma\\\
r_{i}&Q\in\Sigma_{V}\setminus\Sigma\text{ and }Q\setminus V\text{ is
countable}\\\ 1-r_{i}&\text{otherwise,}\end{cases}$

are probability measures that extend $\mu_{0}$ to
$\Sigma_{V}\mathrel{\mathop{:}}=\sigma(\Sigma\cup\\{V\\})$.

By using these probability spaces we can replicate the idea of [11, Thm. 12]
to obtain a cospan of LMP that can’t be completed to a commutative square. We
now sketch the construction. Fix $s_{0}\in S$ and define LMP
$\mathbf{S}_{i}\mathrel{\mathop{:}}=(S,\Sigma_{i},\tau_{i})$, with
$\Sigma_{1}=\Sigma_{2}\mathrel{\mathop{:}}=\Sigma_{V}$ and
$\Sigma_{0}\mathrel{\mathop{:}}=\Sigma$, and

$\tau_{i}(s,A):=\begin{cases}1&s\neq s_{0}\text{ and }s_{0}\in A\\\
\mu_{i}(A)&s=s_{0}\\\ 0&\text{otherwise}\end{cases}$

for $i=0,1,2$, every $s\in S$, and $A$ in the corresponding $\sigma$-algebra.

The identity maps $\mathit{Id}_{S}:\mathbf{S}_{i}\to\mathbf{S}_{0}$ form a
cospan of zigzags, and it can be seen that there are no $\mathbf{S}$ and
zigzag maps $h_{i}:\mathbf{S}\to\mathbf{S}_{i}$ ($i=1,2$) completing that
cospan to a semipullback.

######  Acknowledgments.

We would like to thank Zoltán Vidnyánsky for initial suggestions regarding
Example 14. The second author would also like to thank Prof. S.M. Srivastava
and Prof. S. Todorčević for enlightening discussions around this problem.

## References

  * Danos et al. [2006] V. Danos, J. Desharnais, F. Laviolette, P. Panangaden, Bisimulation and cocongruence for probabilistic systems, Inf. Comput. 204: 503–523 (2006).
  * Desharnais [1999] J. Desharnais, “Labeled Markov Process”, Ph.D. thesis, McGill University (1999).
  * Doberkat [2009] E.E. Doberkat, “Stochastic Coalgebraic Logic”, Monographs in theoretical computer science, Springer (2009).
  * Dunford and Schwartz [1957] N. Dunford, J.T. Schwartz, “Linear Operators, 1: General Theory”, Pure and applied mathematics, Academic press, London, New York, Sydney (1957).
  * Edalat [1999] A. Edalat, Semi-pullbacks and bisimulation in categories of Markov processes, Mathematical Structures in Comp. Sci. 9: 523–543 (1999).
  * Fremlin [2011] D.H. Fremlin, “Measure Theory vol. 1”, Torres Fremlin (2011), second edition.
  * Fremlin [2013] D.H. Fremlin, “Measure Theory vol. 4”, Torres Fremlin (2013), second edition.
  * Joyal et al. [1996] A. Joyal, M. Nielsen, G. Winskel, Bisimulation from open maps, Information and Computation 127: 164 – 185 (1996).
  * Kallenberg [2002] O. Kallenberg, “Foundations of modern probability”, Probability and its Applications (New York), Springer-Verlag, New York: xx+638 (2002), second edition.
  * Marczewski and Ryll-Nardzewski [1953] E. Marczewski, C. Ryll-Nardzewski, Remarks on the compactness and non direct products of measures, Fundamenta Mathematicae 40: 165–170 (1953).
  * Sánchez Terraf [2011] P. Sánchez Terraf, Unprovability of the logical characterization of bisimulation, Information and Computation 209: 1048–1056 (2011).

J. Pachl

> The Fields Institute
>
> 222 College Street,
>
> Toronto, Ontario M5T 3J1 Canada

P. Sánchez Terraf

> CIEM — Facultad de Matemática, Astronomía y Física (Fa.M.A.F.)
>
> Universidad Nacional de Córdoba — Ciudad Universitaria
>
> Córdoba 5000. Argentina.

and

> Department of Mathematics. University of Toronto.
>
> Bahen Centre, 40 St. George St.
>
> Toronto, ON M5S 2E4 Canada


Homotopy and Homology at Infinity and at the Boundary

Mohammed Barhoush

Abstract

In this paper we study the relationship between the homology and homotopy of a
space at infinity and at its boundary. Firstly, we prove that if a locally
connected, connected, $\delta$-hyperbolic space that is acted upon
geometrically by a group has trivial homotopy at infinity then the first Čech
homotopy group is trivial. Secondly, we prove that if a hyperbolic group on a
finite field has trivial $i^{th}$ homology at infinity then the boundary of
the group has trivial $i^{th}$ Steenrod homology. This result turns out to be
important in addressing an open problem related to Cannon’s conjecture.

##  1 Introduction

Homology and homotopy theories have proven very useful in helping
mathematicians classify and understand different spaces. It is why basic
homology and homotopy theory has expanded to include new variations such as
Čech homology and Steenrod homotopy. In some cases these variations prove
easier and more useful to calculate than the original groups. One of the
important applications of these groups is to Cannon’s conjecture which states:

######  Conjecture 1.

(Cannon’s conjecture) Let $G$ be a hyperbolic group. If $\partial G\cong
S^{2}$ then $G$ acts geometrically on the hyperbolic space $\mathbb{H}^{3}$.

Cannon first proposed this conjecture in an attempt to prove the Thurston
Hyperbolization Theorem. Even though the Thurston hyperbolization theorem has
already been proven, Connan’s conjecture remains a highly important open
problem in geometric group theory. This is mainly because it would imply that
a closed, irreducible, 3-manifold whose fundamental group is hyperbolic is
hyperbolic. This result would be a great leap in our understanding of
hyperbolic spaces.

Special cases of Cannon’s conjecture have been proven. For instance, Connan’s
conjecture holds true for Coxeter groups. The most relevant cases of Connan’s
conjecture have been proven B. Beeker and N. Lazarovich in [29] and by V.
Markovic in [2]. Combining these two recent papers we have the following
result:

######  Theorem 1.

Let $G$ be a hyperbolic group then the following are equivalent

  1. 1.

$G$ acts geometrically on $\mathbb{H}^{3}$.

  2. 2.

$\partial G\cong\mathbb{S}^{2}$ and $G$ contains ’enough’ quasi-convex surface
subgroups.

  3. 3.

$G$ is one ended, has vanishing first cohomology over $\mathbb{Z}/2$ at
infinity and contains ’enough’ quasi-convex co-dimension 1 surface subgroups.

In B. Beeker and N. Lazarovich’s paper the following open question was posed
at the end.

######  Conjecture 2.

If $G$ is one ended, has vanishing first cohomology over $\mathbb{Z}/2$ at
infinity and any two points on the boundary of $G$ are separated by a Jordan
curve then $\partial G\approx\mathbb{S}^{2}$.

One of the results proved in this paper (Corollary 4) tells us that the
vanishing first cohomology over $\mathbb{Z}/2$ at infinity can be implies
vanishing first Steenrod homology of the boundary. This is useful because to
translate all the conditions of the conjecture to boundary conditions which
should be easier to deal with. In other words with the results of this paper
we have shown that Conjecture 2 is implied by the following conjecture.

######  Conjecture 3.

If $X=\partial G$ is a connected space such that any two points are separated
by a Jordan curve, and $H^{st}_{1}(X)=0$ then $X\approx\mathbb{S}^{2}$.

In fact this is a similar result to the following theorem by P. Papazoglou
[36].

######  Theorem 2.

Let $X$ be a locally compact, geodesic metric space. If $X$ is 1-ended,
simply-connected, and any two points are separated by a f-line then $X$ is
homeomorphic to the plane.

Every condition is satisfied by $G$ but the critical difference is that in
Papazoglou’s theorem we have that $\pi_{1}(X)=0$ while in the conjecture we
have $H^{st}_{1}(X)=0$. There is a strong connection between homotopy and
homology. This can be seen in Hurewicz theorem (page 338 in [15]) which states
that the first homology group is the abelianization of the first homotopy
group. Therefore it is possible that we can modify Papazoglou’s proof and
obtain a proof for Conjecture 3 and thus a proof for the open problem proposed
by B. Beeker and N. Lazarovich.

This paper is structured as follows. An overview of the different variants of
homotopy and homology groups is given in Section 2. Afterwards in Section 3,
it is shown that the natural map from the first Čech homotopy to the first
homotopy at infinity is injective. Finally in Section 4, it is shown that if
the homology at infinity is trivial then the Steenrod homology of the boundary
is trivial.

##  2 Preliminaries: Homology and Homotopy at Infinity

In this section we will give a brief over view of Čech, Steenrod and locally
finite homology theories (based on [20]) as well as Čech homotopy theory
(based on [21]). This will prepare the reader for the theorems in the next
sections.

###  2.0.1 Simplical homology

Let $X$ be a $\Delta$-complex. We define $C_{n}(X)$ to be the abelian group
with basis consisting of the $n$-simplices in $X$. Any element in $C_{n}(X)$
is called an $n$-chain and can be written as a finite sum of $n$-simplices.

For any $n$-simplex $s^{n}=[v_{0},...,v_{n}]$, we denote the $(n-1)$-simplex
boundary of $s^{n}$ that is made up of every vertex excluding $v_{i}$ by
$s^{n}|_{[v_{0},..,\hat{v}_{i},..,v_{n}]}$.

We can define the $n$-boundary homomorphism $\partial_{n}:C_{n}\rightarrow
C_{n-1}$ that sends an $n$-simplex $s^{n}$ to its boundary through the
following formula.

$\partial_{n}s^{n}=\sum_{i=1}^{n}(-1)^{i}s^{i}|_{[v_{1},..,\hat{v}_{i},..,v_{n}]}$

This defines the homomorphism since the $n$-simplices form a basis of
$C_{n}(X)$. It is easy to show that $\partial_{n}\circ\partial_{n+1}=0$, i.e.
$Im(\partial_{n+1})<Ker(\partial_{n})$.

We now define the $n^{th}$ homology group as

$H_{n}(X)=Ker(\partial_{n})/Im(\partial_{n+1})$

We call elements of $Ker(\partial_{n})$ $n$-cycles and elements of
$Im(\partial_{n+1})$ $n$-boundaries.

We can generalize homology groups for any space $X$ by simply replacing
$n$-simplices with continuous maps from a $n$-simplex to $X$. The resulting
groups are called singular homology groups.

###  2.0.2 Locally Finite Homology

Note that the $n$-chains defined above must be finite sums. However this means
that the homology group are not giving us information about the infinite sums
of simplices. This turns out to be a problem as many results only hold true
when we take into account the infinite chains (for instance Theorem 7). This
motivated the development of locally finite homology.

######  Definition 1.

Let $X$ be a locally compact space with the restriction that every compact set
$K\subset X$ meets the image of only finitely many simplices from any chain.
We define the locally finite singular homology of $X$, $H^{LF}_{*}(X)$, to be
the homology theory that includes infinite chains. In other words, an
$n$-chain in $C_{n}^{LF}(X)$ can be an infinite sum of $n$-simplices.

###  2.0.3 Čech Homology

We will now briefly introduce the notion of Čech homology. Let
$\mathcal{U}=\\{U_{\alpha}\\}$ be an open cover of a space $X$ where $\alpha$
is some indexing set. We define the nerve $\mathcal{N(U)}$ to be the simplical
complex made up of a vertex for each $U_{i}\in\mathcal{U}$ and an
$(n-1)$-simplex spanned by $n$ vertices $u_{i_{1}},...,u_{i_{n}}$ whenever
$\cap_{1\leq k\leq n}U_{i_{k}}$ is non-empty.

A cover $\\{U_{\alpha\in A}\\}$ is said to be a refinement of another cover
$\\{V_{\beta\in B}\\}$ if for every $\beta\in B$ there exists $\alpha\in A$
such that $U_{\beta}\subset V_{\alpha}$. We get an ordering on the set of open
covers of $X$ where $\mathcal{U}_{1}<\mathcal{U}_{2}$ if and only if
$\mathcal{U}_{2}$ is a refinement of $\mathcal{U}_{1}$. It is easy to show
that this set is a directed quasi-ordered set which means that

  1. 1.

$\mathcal{U}<\mathcal{U}$

  2. 2.

$\mathcal{U}_{1}<\mathcal{U}_{2}<\mathcal{U}_{3}$ entails that
$\mathcal{U}_{1}<\mathcal{U}$

  3. 3.

For any two covers $\mathcal{U}_{1},\mathcal{U}_{2}$ there exists a cover
$\mathcal{U}_{3}$ such that $\mathcal{U}_{1}<\mathcal{U}_{3}$ and
$\mathcal{U}_{2}<\mathcal{U}_{3}$.

Furthermore, it can show that the inverse limit in terms of larger and larger
refinements is well defined and independent of the sequence of covers.

Now let $\mathcal{V}>\mathcal{U}$ then there is a natural simplical map
$\mathcal{N(V)}\rightarrow\mathcal{N(U)}$ which is well defined up to
homotopy. This map is not unique however the induced map on the homology
groups is unique.

######  Definition 2.

We define the $i^{th}$ Čech cohomology of $X$ to be $lim_{\mathcal{U}}\
H(\mathcal{N(U)},G)$ where the limit is for larger and larger refinements
$\mathcal{U}$ of $X$.

###  2.0.4 Steenrod Homology

The dual of Čech cohomology is called Steenrod homology which we will now
define.

######  Definition 3.

A regular map $f$ from a complex $A$ to a space $X$ is a map that sends
vertices in $A$ to $X$ such that for any $\epsilon>0$, all but finitely many
simplices in $A$ have their vertices sent onto sets of diameter $<\epsilon$.

######  Definition 4.

A regular $n$-chain is a tuple $(A,f,s^{n})$ where $A$ is a complex, $f$ is a
regular function from $A$ to $X$, and $s^{n}$ is a locally finite $n$-chain in
$A$. If $s^{n}$ is a cycle then we call the tuple a regular $n$-cycle.

Two regular $n$-cycles $(A_{1},f_{1},s^{n}_{1})$ and $(A_{2},f_{2},s^{n}_{2})$
are called homologous if there exists a regular $(n+1)$-cycle $(A,f,s^{n+1})$
such that $A_{1}$ and $A_{2}$ are closed subcomplexes of $A$, $f$ agrees with
$f_{1}$ on $A_{1}$ and with $f_{2}$ on $A_{2}$, and $\partial s^{n+1}=\partial
s^{n}_{1}-\partial s^{n}_{2}$. It is clear now how the regular cycles can be
used to create homology groups.

######  Definition 5.

We define the $n^{th}$ Steenrod homology of $X$, denoted by $H^{st}_{n}(X)$,
as the homology group of regular $n$-cycles in $X$.

###  2.0.5 Cech Homotopy

One of the interesting things about homotopy is its strong relation to
homology. This relation can evidently be seen in the following theorem by
Hurewicz (page 338 in [15]).

######  Theorem 3.

Let $X$ be a simply connected space. Then

$H_{n}(X)\cong\pi_{n}(X)$

when $\pi_{i}(X)=0$ for all $i<n$.

This theorem only holds for Čech homology groups under certain restrictions
like local compactness. We want to find a group that is more closely related
to the Čech homology group than singular homotopy groups. There is more than
one way to define Čech homotopy but we use the following definition.

######  Definition 6.

We define the $n^{th}$ Čech homotopy group of $X$ by

$\hat{\pi}_{n}(X)=lim_{\mathcal{U}}\ \pi_{n}(\mathcal{N(U)})$

where the limit is taken larger and larger refinements (similar to Čech
cohomology).

##  3 Homotopy at Infinity and Čech Homotopy

In this section we will prove the following theorem. This part of the paper is
not relevant to Cannon’s conjecture or Conjecture 2.

######  Theorem 4.

Let $X$ be a locally connected, connected, $\delta$-hyperbolic space that is
acted upon geometrically by a group $G$. If the first homotopy group at
infinity of $X$ is trivial then the first Čech homotopy group of the boundary
$\partial X$ is trivial.

######  Definition 7.

The first homotopy at infinity of $X$ based on the geodesic ray $w$ is defined
as

$\pi_{1}^{\infty}(X,w)=\lim_{i\rightarrow\infty}\pi_{1}(X\setminus\overline{B}(i),w(i+1))$

where $\overline{B}(i)$ is the closed ball of radius $i$ around $w(0)$.

It can be equivalently defined by replacing the balls with any sequence of
compact sets ordered by inclusion but we use the above definition for
simplicity.

More explicitly, we have a sequence

$\pi_{1}(X\setminus\overline{B}(1),w(2))\xrightarrow{i_{1}}\pi_{1}(X\setminus\overline{B}(2),w(3))\xrightarrow{i_{2}}....$

where $i_{j}$ is the composition of the inclusion map
$\pi_{1}(X\setminus\overline{B}(k),w(k+1))\rightarrow\pi_{1}(X\setminus\overline{B}(k-1),w(k+1))$
and the isomorphism
$\pi_{1}(X\setminus\overline{B}(k-1),w(k+1))\rightarrow\pi_{1}(X\setminus\overline{B}(k-1),w(k))$
which simply slides the base-point of the loops from $w(k+1)$ to $w(k)$ along
$w$.

G. Conner and H. Fisher proved a similar result [35] to Theorem 4.

######  Theorem 5.

Let $X$ be a geodesic negatively curved space. Then there is a natural
homomorphism between the fundamental group of the boundary of $X$ to its
fundamental group at infinity. This homomorphism is an isomorphism when $X$
admits a universal cover and is an injection when $X$ is one-dimensional.

Let $\gamma\in\pi_{1}(\partial G)$ with base point $x_{0}$. The natural
homomorphism referred to in the theorem is the following

$\gamma\rightarrow\\{\gamma_{1},\gamma_{2},...\\}$

where $\gamma_{i}$ is the intersection of $\gamma$ with $S_{i}(x_{0})$. The
limit of such a sequence is an element of the fundamental group at infinity
(more details in [35])

Ofcourse a loop in $\hat{\pi}_{1}(\partial X)$ is made up of a discrete points
so it will map to descrete points on $X$ but we can connect these points with
geodesic and get loops as well. This gives us a similar map from
$\hat{\pi}_{1}(\partial X)$ to $\pi_{1}^{\infty}(X)$. Theorem 4 will allow us
to show that for any hyperbolic space $X$, this map is injective.

We define $\mathcal{U}_{\epsilon}=\\{U_{\alpha}\\}$ to be the open cover where
$U_{\alpha}=B_{\epsilon}(u_{\alpha})$ for some $u_{\alpha}\in X$. Note that a
loop in $\mathcal{N(U_{\epsilon})}$ is made up of a set of points
$\\{u_{1},...,u_{n}\\}$ such that $U_{i}\cap U_{i+1}\neq\emptyset$.

######  Definition 8.

If $L=\\{u_{1},..,u_{n}\\}$ is a loop in $\mathcal{N(U_{\epsilon})}$. We say
that a set of points $S$, where $\\{u_{1},..,u_{n}\\}\subset S\subset X$, is
an $\epsilon$-subdivision of $L$ if there exists $\delta>0$ and a subset
$D\subset(\mathbb{D}^{2})^{(0)}$ such that

  1. 1.

Every ball of radius $\delta$ in $\mathbb{D}^{2}$ contains a point $d\in D$.

  2. 2.

There exists a bijective map $\phi:D\rightarrow S$ such that for any
$d_{1},d_{2}\in D$

$d(d_{1},d_{2})\leq 10\delta\implies d(\phi(d_{1}),d(\phi(d_{2}))<\epsilon$

  3. 3.

$\phi^{-1}(L)\subset\partial\mathbb{D}^{2}$

######  Lemma 1.

Let $\mathcal{N(U_{\epsilon})}$ be the nerve of a space $X$ and let
$L=\\{u_{1},...,u_{n}\\}$ be a loop in the nerve. If there exists a
$\epsilon$-subdivision of $L$ then $L$ is contractible.

###### Proof.

Connect any two points in $D$ that are a distance at most $10\delta$ apart
with a line. This would partition $D$ into triangles. This is because any ball
$B_{10\delta}$ in $\mathbb{D}^{2}$ must contain at least 3 points and every
point is adjacent to every other point which creates a triangle subdivision in
$B_{10\delta}$. Thus we get a triangle subdivision of $D$. Now if
$d_{1},d_{2}\in D$ are adjacent then $d(\phi(d_{1}),d(\phi(d_{2}))<\epsilon$
so $\phi(d_{1})$ and $\phi(d_{2})$ form a 1-simplex. In other words triangles
are sent to triangles. Note that $L$ is in the image of $\phi$ so $\phi(D)$
gives us a subdivision of $L$ into triangles. But every triangle will span a
2-simplex in $\mathcal{N(U_{\epsilon})}$ since each of the vertices are within
a distance of $\epsilon$. Therefore $L$ is contractible. ∎

Note that the proof still works if we replace a disk with a shape homeomorphic
to a disk.

For any ray $r\in\partial X$ define $r(t)$ to be the point on the ray that is
a distance $t$ from its base point. The following lemma will be useful in the
proof of Theorem 4.

######  Lemma 2.

Let $r,r^{\prime}$ be two geodesic rays in $X$ with base point $x_{0}\in X$.
If for $t^{\prime}>\delta log_{2}(10C)+1+log(\epsilon)$ we have
$d(r(t^{\prime}),r^{\prime}(t^{\prime}))<10C$ then
$d_{a}(r,r^{\prime})<\epsilon$.

Here $C>\delta$ is a constant we shall explain later.

###### Proof.

Clearly there exists $t_{0}>0$ such that
$d(r(t_{0}),r^{\prime}(t_{0}))=\delta$. By Proposition 1.25 in [34] we know
that for any $t>t_{0}$, $d(r(t),r^{\prime}(t))>2^{\frac{t-t_{0}-1}{\delta}}$.
This means that for $t=t_{0}+\delta log_{2}{10C}+1$ we get that
$d(r(t),r^{\prime}(t))>10C$.

We know that $d(r^{\prime}(t^{\prime}),r(t^{\prime}))<10C$ so $t_{0}\geq
t^{\prime}-\delta log_{2}{2C}+1\geq log(\epsilon)$. Therefore
$d_{a}(r_{1},r_{1}^{\prime})=e^{t_{0}}<\epsilon$. ∎

We are now ready to prove Theorem 4.

###### Proof.

Let $\epsilon>0$ and $\mathcal{U}_{\epsilon}=\cup_{i\in I}U_{i}$ be an open
cover of $\partial X$. We can then construct a nerve
$\mathcal{N(U_{\epsilon})}$ made up of the open sets $\\{U_{i}\\}_{i\in I}$
and their corresponding points $\\{u_{i}\\}_{i\in I}$.

We need to show that any loop in $\mathcal{N(U_{\epsilon})}$ can become
contractible by making $\mathcal{U_{\epsilon}}$ finer.

Let $L$ be a loop in $\mathcal{N(U)}$ spanned by the rays
$\\{r_{1},...,r_{n}\\}$ where for $1\leq j\leq n$, ${r_{j}}$ and ${r_{j+1}}$
($r_{n+1}=r_{1}$) bound a 1-simplex, i.e are within a distance of $\epsilon$
from each other.

For any $t>0$, the points $\\{r_{1}(t),...,r_{n}(t)\\}$ are part of a loop,
call it $L(t)$, in $X$. This is because $X$ is a geodesic space so we can
connect any two consecutive points in this set with a geodesic segment to form
a loop.

######  Lemma 3.

There exists $r_{0}\in\mathbb{N}$ such that for every integer $r>r_{0}$, every
loop $L(t)$, $t\in\mathbb{N}$ and $t>r$, is contractible in
$X\setminus\overline{B_{r}}(x_{0})$.

###### Proof.

We have a sequence of loops $\\{L(1),L(2),...\\}$ getting further and further
from $x_{0}$. These loops are not collapsing to a point since rays eventually
diverge. If this lemma is false then for every $r_{0}\in\mathbb{N}$ there
exists $r>r_{0}$ such that $X\setminus\overline{B_{r}}(x_{0})$ is not simply
connected. So clearly the limit of the fundamental group of
$\\{X\setminus\overline{B_{1}}(x_{0}),X\setminus\overline{B_{2}}(x_{0}),...\\}$
is not trivial which is a contradiction. ∎

Therefore we can find $r-1>\delta log_{2}(10C)+1+log(\epsilon)$ such that
$L(t)$ is contractible in $X\setminus\overline{B_{r-1}}(x_{0})$ for any
$t>r-1$.

By Lemma 3.1 in [33] we know that any ball of radius $C$ intersects a geodesic
ray from $x_{0}$. This is where the constant $C$ comes from. Let $R$ be the
set of rays that pass within a distance of $C$ from one of the points in the
filling of $L(r)$.

Now let $\delta=C$ and $\phi$ be the map that sends the a point of
intersection of a geodesic ray in $R$ with the filling of $L(r)$ to the
geodesic ray itself. We need to check that this map satisfies all the
conditions of Definition 8. The first condition is satisfied by Lemma 3.1 in
[33]. The second condition is satisfied by Lemma 2. It is clear that the third
condition is satisfied. Therefore by Lemma 1 we know that $L$ is fillable and
so the first Cech homology of $\partial X$ is trivial. ∎

##  4 Homology at Infinity and Steenrod Homology

In this section we will prove the following theorem.

######  Theorem 6.

Let $G$ be a hyperbolic group and let $k$ be a finite field. If $G$ has
trivial $i^{th}$ homology over k at infinity then $\partial G$ has trivial
$i^{th}$ Steenrod homology over $k$.

######  Definition 9.

We define the Rips complex $P_{t}(G)$ of $G$ to be the simplical complex whose
vertices are elements of $G$ and any set of vertices $v_{1},...,v_{n}\in G$
span an $n$-simplex if $d(v_{i},v_{j})<t$ for all $1\leq i,j\leq n$.

The useful thing about the Rips complex is that for large enough $t$ ,
$P_{t}(G)$ becomes contractible. Set $P(G)=P_{t}(G)$ for $t$ large enough.

The action of $G$ on itself by left translation can be extended to an action
on $P(G)$. Moreover, its is easy to show that $G$ acts geometrically on the
Rips complex since it acts geometrically on itself. Therefore the assumption
in the theorem tells us that $H^{\infty}(P(G))=0$. (More details about the
Rips complex can be found in Section 9.2 in [24]).

Now define $B(n)$ to be the subset of $P(G)$ that contains every vertex $v\in
G$ that satisfies $d(v,e)<n$, where $e$ is the identity of $G$, and every
simplex whose vertices are in $B(n)$. Similarly define $S(n)$ to be the subset
of $P(G)$ that contains every vertex $v\in G$ that satisfies $d(v,e)=n$ and
every simplex whose vertices are in $S(n)$. Finally, define $\overline{B}(n)$
to be the subset that contains every vertex $v\in G$ that satisfies
$d(v,e)\leq n$ and every simplex whose vertices are in $\overline{B}(n)$. We
are now ready to prove Theorem 6.

###### Proof.

We will begin the proof with the following theorem by M. Bestvina (Proposition
1.5 in [33]).

######  Theorem 7.

Let $G$ be a hyperbolic group and let $R$ be a ring. Then there is an
isomorphism of $RG$-modules

$H^{st}_{i}(\partial G)\cong H_{i+1}^{LF}(P(G))$

Therefore it is sufficient to prove that $H_{i+1}^{LF}(P(G))=0$.

Let $c\in C_{i+1}^{LF}(P(G))$ be an $(i+1)$-cycle. This means $c$ is a sum of
simplices so we can write $c=\sum_{s\in S^{i+1}}\alpha(s)s$ where $S^{i+1}$ is
the set of all $(i+1)$-simplices in $P(G)$ and $\alpha$ is a function that
sends a simplex to its coefficient in $c$. We need to show that $c$ is an
$(i+1)$-boundary i.e. it bounds an $(i+2)$-chain. It is well known that a
contractible space has trivial simplical homology, therefore if $c$ is a
finite sum of simplices then $c$ is a boundary.

So assume $c$ is an infinite sum of simplices. We define $c\ \cap
B(j)=\sum_{s\in S^{i+1}}\mathfrak{i}(s)\alpha(s)s$ where $\mathfrak{i}$ is the
function that sends a simplex $s$ to 1 if every vertex of $s$ is in $B(j)$ and
0 otherwise. Similarly for $\overline{B}(j)$ and $S(j)$. Let $n\in\mathbb{N}$
be large enough so that the intersection $c\cap B(n)$ is non-empty.

Claim: The boundary of $c\cap\overline{B}(n)$ is an $i$-cycle.

By definition, $c\cap\overline{B}(n)$ is a sum of $(i+1)$-simplices in $c$
whose vertices are within a distance of $n$ from the identity. The boundary of
$(i+1)$-simplices are $i$-boundaries and thus $i$-cycles.

It is important to note that these cycles may not lie on $S(n)$. However they
have to be a distance of at most $t$ from $S(n)$, where $t$ is the constant we
defined when discussing the Rips complex.

Since the $i^{th}$ homology at infinity is trivial we get that for any $n>0$
there exists $m>n+t$ such that every $i$-cycle in
$P(G)\setminus\overline{B}(m)$ is will bound an $(i+1)$-chain in
$P(G)\setminus\overline{B}(n+t)$. Denote the sum of the $(i+1)$-chains that
bound $c\cap\overline{B}(m)$ by $c(m)$. It is important to note that $c(m)$ is
outside the ball $B(n+t)$ so it cannot intersect to
$(c\cap\overline{B}(n-1))$. The constant $m$ depends on $n$ so write $m=m(n)$.

Consider the finite sum of $(i+1)$-simplices,
$c_{n}=c(m(n))-(c\cap\overline{B}(m(n)))$. It is clear that this is an
$(i+1)$-cycle since the boundary of $c(m)$ is equal to the boundary of
$c\cap\overline{B}(m)$ so they cancel out. As it is a finite cycle it must be
a boundary. Let $b_{n}$ be an $(i+2)$-cycle such that
$\partial_{i+2}b_{n}=c_{n}$ where $\partial_{i+2}$ is the $(i+2)$ boundary map
of the homology groups. In a similar fashion as $c$, we write
$b_{j}=\sum_{s\in S^{i+2}}\beta_{j}(s)s$.

So we now have a sequence of ’fillings’ that fill larger and larger ’sections’
of $c$. We want to show that the limit of these filling will fill $c$.
However, $lim_{j\rightarrow\infty}b_{j}$ is not necessarily well defined. This
is because the coefficient of any $(i+2)$-simplex may continuously fluctuate
in the sequence $\\{b_{j}\\}$ and never converge. However there is a way
around this problem.

Assume $s^{\prime}$ is an $(i+2)$-simplex in $B(1)$. Since $k$ is finite, any
sequence of coefficients $\\{\beta_{j}(s^{\prime})\\}$ must contain a
subsequence that is constant. Correspondingly, let $\\{b_{j^{\prime}}\\}$ be a
subsequence of $\\{b_{j}\\}$ where the coefficient of $s^{\prime}$ are
constant. Now take another simplex $s^{\prime\prime}$ in $B(1)$. We can repeat
this process and find a subsequence of $\\{b_{j^{\prime}}\\}$ such that the
coefficient of $s^{\prime\prime}$ is constant. Since $P(G)$ is locally finite
there are finitely many $(i+2)$-simplices in $B(1)$. Therefore after repeating
this process finitely many times we get a subsequence of $\\{b_{j}\\}$ such
that the coefficients of any $(i+2)$-simplex in $B(1)$ is constant. Call this
subsequence $\\{b_{j_{1}}\\}$.

Now replace $\\{b_{j}\\}$ with $\\{b_{j_{1}}\\}$ and repeat this process on
$B(2)$. We will get a subsequence of $\\{b_{j_{1}}\\}$ such that the
coefficients of any $(i+1)$-simplex in $B(2)$ are constant. Denote this
subsequence by $\\{b_{j_{2}}\\}$. Now consider the following sequence

$\\{b_{j_{j}}\\}=\\{b_{1,1},b_{2,2},...\\}$

Claim: The limit of this sequence is well defined.

Let $s$ be an arbitrary $(i+2)$-simplex. Then there exists $n\in\mathbb{N}$
such that $s\in B(n)$. Note that the sequence $\\{b_{j_{j}}\\}_{j\geq n}$ is a
subsequence of $\\{b_{j_{n}}\\}$ which means that the coefficient of $s$ is
constant in $\\{b_{j_{j}}\\}_{j\geq n}$. This means that the limit of the
coefficients of $s$ is well defined. In other words, the limit of the
coefficient of any $(i+2)$-simplex is well defined. Hence the limit of
$\\{b_{j_{j}}\\}$ is well defined and we denote this limit as $b$.

Claim: $\partial_{i+2}b=c$.

Assume this is not true. Then for some $(i+1)$-simplex $s^{i+1}$, the
coefficient of $s^{i+1}$ in $c$ is not equal to the coefficient of $s^{i+1}$
in $\partial_{i+2}b$. Let $n\in\mathbb{N}$ be such that $s^{i+1}\in B(n-2)$
and let $m$ be an arbitrary integer larger than $n+t$. Recall that
$\partial_{i+2}b_{m_{m}}=c(m_{m})-(c\ \cap\overline{B}(m_{m}))$. Also recall
that the simplices in $c(m_{m})$ are outside the ball $B(m_{m})$ so they do
not contribute to the coefficient of $s^{i+1}$ in $\partial_{i+2}b_{m_{m}}$.
In other words the coefficient of $s^{i+1}$ in $\partial_{i+2}b_{m_{m}}$ is
equal to $\alpha(s^{i+1})$. As this is true for any $m>n+t$ it must also be
true for the limit as well.

Therefore every $(i+1)$-cycle is a boundary and thus $H^{LF}_{i+1}(P(G))=0$.
By Theorem 7 we get that $H^{st}_{i}(\partial G)=0$ and we are done. ∎

The following is a direct Corollary of this theorem and Lemma LABEL:relator.

######  Corollary 1.

If a hyperbolic group $G$ has vanishing first cohomology at infinity over
$\mathbb{Z}/2$ then $H^{st}_{1}(\partial G)=0$.

This implies that the open problem Conjecture 2 is implied by Conjecture 3.

## References

  * [1] Berger, M. and Gostiaux, B., 2012. Differential Geometry: Manifolds, Curves, and Surfaces: Manifolds, Curves, and Surfaces (Vol. 115). Springer Science Business Media.
  * [2] V. Markovic, Criterion for Cannon’s Conjecture, ArXiv e-prints (2012).
  * [3] I. Agol, D. Groves, and J. Manning, The virtual Haken conjecture, ArXiv e-prints (2012).
  * [4] Sageev, M., 1995. Ends of group pairs and non-positively curved cube complexes. Proceedings of the London Mathematical Society, 3(3), pp.585-617.
  * [5] Gitik, R., Mitra, M., Rips, E. and Sageev, M., 1998. Widths of subgroups. Transactions of the American Mathematical Society, 350(1), pp.321-329.
  * [6] Milnor, J., 1962. A unique decomposition theorem for 3-manifolds. American Journal of Mathematics, 84(1), pp.1-7.
  * [7] Michael Kapovich, Hyperbolic manifolds and discrete groups, Progress in Mathematics, vol. 183, Birkhäuser Boston Inc., Boston, MA, 2001.
  * [8] Bowditch, B.H., 1999. Convergence groups and configuration spaces. Geometric group theory down under (Canberra, 1996), pp.23-54.
  * [9] Kapovich, I. and Benakli, N., 2002. Boundaries of hyperbolic groups. arXiv preprint math/0202286.
  * [10] Bergeron, N. and Wise, D.T., 2012. A boundary criterion for cubulation. American Journal of Mathematics, 134(3), pp.843-859.
  * [11] Scott, G.P., 1973. Compact Submanifolds of 3-Manifolds. Journal of the London mathematical society, 2(2), pp.246-250.
  * [12] Stillwell, J., 2012. Classical topology and combinatorial group theory (Vol. 72). Springer Science Business Media.
  * [13] MR Bridson, A Haefliger, Metric spaces of non-positive curvature, Grundl. Math. Wissen. 319, Springer (1999)
  * [14] BH Bowditch, Cut points and canonical splittings of hyperbolic groups, Acta Math. 180 (1998) 145–186
  * [15] Hatcher (2005). Algebraic Topology.
  * [16] Tukia, P., 1988. Homeomorphic conjugates of Fuchsian groups. J. reine angew. Math, 391(1), p.54.
  * [17] Hamann, M., 2018. Tree amalgamations and quasi-isometries. arXiv preprint arXiv:1812.04987.
  * [18] Bergeron, N., 2014. TOUTE VARIÉTÉ DE DIMENSION 3 COMPACTE ET ASPHÉRIQUE EST VIRTUELLEMENT DE HAKEN. Séminaire BOURBAKI, p.66ème.
  * [19] Lee, J., 2010. Introduction to topological manifolds (Vol. 202). Springer Science Business Media.
  * [20] Ferry, S.C., 1991. Remarks on Steenrod homology. In Proceedings of the 1993 Oberwolfach Conference on the Novikov Conjecture (Vol. 227, pp. 148-166).
  * [21] Porter, T., 1973. Čech homotopy I. Journal of the London Mathematical Society, 2(3), pp.429-436.
  * [22] Buyalo, S. and Schroeder, V., 2007. Elements of asymptotic geometry, EMS Monogr. Math., Eur. Math. Soc., Zürich.
  * [23] Cannon, J.W. and Cooper, D., 1992. A characterization of cocompact hyperbolic and finite-volume hyperbolic groups in dimension three. Transactions of the American Mathematical Society, 330(1), pp.419-431.
  * [24] Drutu, C. and Kapovich, M., 2017. Geometric group theory. In American Mathematical Society Colloquium Publications (Vol. 63).
  * [25] Tuftsedu. 2019. Tuftsedu. [Online]. [2 September 2019]. Available from: https://mduchin.math.tufts.edu/notes/hyp-groups-course.pdf
  * [26] Schwartz, R.E., 2011. Mostly surfaces (Vol. 60). American Mathematical Soc..
  * [27] N Brady, Finite subgroups of hyperbolic groups, Internat. J. Algebra Comput. 10 (2000) 399–405
  * [28] Caprace, P.E. and Sageev, M., 2011. Rank rigidity for CAT (0) cube complexes. Geometric and functional analysis, 21(4), p.851.
  * [29] Beeker, B. and Lazarovich, N., 2017. Detecting sphere boundaries of hyperbolic groups. Geometry and Topology, 22(1), pp.439-470.
  * [30] Bing, R.H., 1946. The Kline sphere characterization problem. Bulletin of the American Mathematical Society, 52(8), pp.644-653.
  * [31] Miesch. 2013. On Cannon’s Conjecture.
  * [32] Ayres, W.L., 1929. Concerning continuous curves in metric space. American Journal of Mathematics, 51(4), pp.577-594.
  * [33] Bestvina, M. and Mess, G., 1991. The boundary of negatively curved groups. Journal of the American Mathematical Society, 4(3), pp.469-481.
  * [34] Luminy and Duchin (2014). Hyperbolic Groups Minicourse. [online] Mduchin.math.tufts.edu. Available at: https://mduchin.math.tufts.edu/notes/hyp-groups-course.pdf [Accessed 19 Jul. 2019].
  * [35] Conner, G.R. and Fischer, H., 2003. The fundamental group of a visual boundary versus the fundamental group at infinity. Topology and its Applications, 129(1), pp.73-78.
  * [36] Papasoglu, P., 2005. Quasi-isometry invariance of group splittings. Annals of mathematics, pp.759-830.