# Supplement to “Graphical Models with Attention for Context-Specific
Independence and an Application to Perceptual Grouping”

###### Table of contents

  1. 1 Applying MAMs to perceptual grouping
    1. 1.1 Formal description
    2. 1.2 An illustrative toy example
  2. 2 Symbol grounding with the sparsifier
    1. 2.1 Formal definition for the sparsifier
    2. 2.2 Illustrative example of sparsifying a line with the sparsifier
    3. 2.3 Learning object parts from binary images
  3. 3 MPBP updates for involved factors
    1. 3.1 MPBP updates for the HOFs in MAMs:
    2. 3.2 MPBP updates for the OR factors in the sparsifier:
  4. 4 Hardware used for experiments
  5. 5 Details for the pathfinder challenge
    1. 5.1 Dataset details
    2. 5.2 Model
    3. 5.3 Pathfinder sparsification example
    4. 5.4 Learning
    5. 5.5 Pathfinder ultimate
  6. 6 Details for the cABC challenge
    1. 6.1 Dataset details
    2. 6.2 Model
    3. 6.3 Formal definitions of the object-specific MAM
    4. 6.4 cABC sparsification example
    5. 6.5 Learning elastic graphs for cABC
    6. 6.6 Efficient inference with the object-specific MAM
  7. 7 Details for experiments on realistic images
    1. 7.1 Dataset
    2. 7.2 Edge detection and heuristic sparsification
    3. 7.3 Visualization of results

##  1 Applying MAMs to perceptual grouping

###  1.1 Formal description

Our MAMs for perceptual grouping are binary higher-order MRFs containing two
different types of variables: (1) binary part variables representing the
presence/absence of object parts, and (2) binary attention variables
representing the presence/absence of object parts interactions. Each part
variable is associated with one HOF, connecting the part variable and its
associated attention variables.

Use $\left|\cdot\right|$ to denote the cardinality of a set,
$\mathcal{P}(\cdot)$ to denote all subsets of a set, and
$\mathcal{P}_{2}(\cdot)$ to denote all cardinality 2 subsets of a set. We can
specify our MAM’s variables via the interaction graph, which is an undirected
graph $\mathcal{G}_{I}=\left(\mathcal{V}_{I},\mathcal{E}_{I}\right)$ where
$\mathcal{V}_{I}$ represents the set of vertices, and
$\mathcal{E}_{I}=\left\\{\left\\{u,v\right\\}:~{}u,v\in\mathcal{V}_{I},~{}\exists\text{
an edge in }\mathcal{G}_{I}\text{ connecting }u,v\right\\}$ represents the set
of edges. To build a MAM from $\mathcal{G}_{I}$, we associate a binary part
variable $x_{v}$ with each vertex $v\in\mathcal{V}_{I}$, and a binary
attention variable with each edge in $\mathcal{E}_{I}$. For ease of
presentation, in what follows we represent the attention variable associated
with $\left\\{u,v\right\\}\in\mathcal{E}_{I}$ interchangeably as either
$a_{\left\\{u,v\right\\}}$ or $a_{\left\\{x_{u},x_{v}\right\\}}$.

Let $a_{\sim
x_{v}}=\left\\{a_{\left\\{u,v\right\\}}:\left\\{u,v\right\\}\in\mathcal{E}_{I}\right\\}$
be the set of attention variables associated with the part variable
$x_{v},v\in\mathcal{V}_{I}$. The corresponding MAM is specified by
$\left|\mathcal{V}_{I}\right|$ factors $f_{x_{v}}$, one for each part variable
$x_{v}$ operating on $|a_{\sim x_{v}}|+1$ variables (namely
$\left\\{x_{v}\right\\}\cup a_{\sim x_{v}}$). Since all variables are binary,
we represent a configuration for $f_{x_{v}}$ by its entries that are ON, which
is an element of $\mathcal{P}\left(\left\\{x_{v}\right\\}\cup a_{\sim
x_{v}}\right)$.

The HOF $f_{x_{v}}$ is specified by a partition of $a_{\sim x_{v}}$ into
$M_{x_{v}}$ disjoint subsets of attention variables $a^{(k)}_{\sim
x_{v}},~{}k=1,\ldots,M_{x_{v}}$. Intuitively, we can think of each $a_{\sim
x_{v}}^{(k)}$ as an interaction group, consisting of a set of interchangeable
interactions. The HOF $f_{x_{v}}$ uses a set of prototypical interaction
patterns to control $x_{v}$’s interaction with other part variables. Each
prototypical interaction pattern turns on a set of interaction groups, and the
HOF $f_{x_{v}}$ makes context-specific decisions on which concrete interaction
to use within each interaction group. In particular, this implies that for any
valid configuration of the HOF $f_{x_{v}}$, at most one of the binary
variables in each subset $a^{(k)}_{\sim x_{v}}$ can be ON. See Sec. 1.2 and
Fig. 1 for a toy example and its HOFs to illustrate the formal descriptions
here.

Formally, we specify the HOF $f_{x_{v}}$ with a set of $M_{x_{v}}$-dimensional
binary vectors $\mathcal{B}_{x_{v}}\subset\left\\{0,1\right\\}^{M_{x_{v}}}$
where
$\boldsymbol{0}=\begin{pmatrix}0,\ldots,0\end{pmatrix}\in\mathcal{B}_{x_{v}}$,
and a potential in log domain
$\mathcal{U}_{x_{v}}:\mathcal{B}_{x_{v}}\mapsto\mathbb{R}$. Here
$\mathcal{B}_{x_{v}}$ encodes the set of prototypical interaction patterns for
$f_{x_{v}}$. Using $\mathbbm{1}$ to denote the indicator function, each
$\boldsymbol{b}=\left(b_{1},\ldots,b_{M_{x_{v}}}\right)\in\mathcal{B}_{x_{v}}$
induces a subset of valid configurations $\mathcal{C}_{x_{v}}(\boldsymbol{b})$
for the HOF $f_{x_{v}}$ as

$\mathcal{C}_{x_{v}}(\boldsymbol{b})=\left\\{\boldsymbol{c}\in\mathcal{P}\left(\left\\{x_{v}\right\\}\cup
a_{\sim x_{v}}\right):\left|\boldsymbol{c}\cap a_{\sim
x_{v}}^{(k)}\right|=b_{k},~{}~{}k=1,\ldots,M_{x_{v}}~{}~{}\text{and}~{}~{}\mathbbm{1}_{x_{v}\in\boldsymbol{c}}=\mathbbm{1}_{\|\boldsymbol{b}\|_{1}>0}\right\\},$

Each $\boldsymbol{c}\in\mathcal{C}_{x_{v}}(\boldsymbol{b})$ fully specifies a
joint configuration of the part variable $x_{v}$ and of all the attention
variables $a_{\sim x_{v}}$. In particular, note that if the part variable
$x_{v}$ is ON, then at least one attention variable in $a_{\sim x_{v}}$ is ON.
Reciprocally, if all the attention variables in $a_{\sim x_{v}}$ are OFF, then
$\boldsymbol{b}=\boldsymbol{0}$ and the part variable $x_{v}$ is OFF, meaning
$x_{v}$ does not interact with and has no effects on other part variables.

With a slight abuse of notation, for a configuration
$\boldsymbol{c}\in\mathcal{P}\left(\left\\{x_{v}\right\\}\cup a_{\sim
x_{v}}\right)$, we use $f_{x_{v}}\left(\boldsymbol{c}\right)$ to denote the
potential in log domain of $\boldsymbol{c}$ for $f_{x_{v}}$. The HOF
$f_{x_{v}}$ adopts a simple structure, and is defined as

$f_{x_{v}}\left(\boldsymbol{c}\right)=\begin{cases}\mathcal{U}_{x_{v}}\left(\begin{pmatrix}\left|\boldsymbol{c}\cap
a_{\sim x_{v}}^{(1)}\right|,\ldots,\left|\boldsymbol{c}\cap a_{\sim
x_{v}}^{(M_{x_{v}})}\right|\end{pmatrix}\right),&\forall\boldsymbol{c}\in\bigcup_{\boldsymbol{b}\in\mathcal{B}_{x_{v}}}\mathcal{C}_{x_{v}}\left(\boldsymbol{b}\right)\\\
-\infty,&\forall\boldsymbol{c}\not\in\bigcup_{\boldsymbol{b}\in\mathcal{B}_{x_{v}}}\mathcal{C}_{x_{v}}\left(\boldsymbol{b}\right)\end{cases}$

Figure 1: [Upper left] Toy example setup: line segments (solid black
rectangles) and their potential continuations (dotted lines). [Lower left] The
interaction graph for the corresponding MAM. [Upper right] The HOF
$f_{x_{v_{1}^{P}}}$ modeling top-down interactions. [Lower right] The HOF
$f_{x_{v_{22}}}$ coordinating top-down and lateral interactions. Figure 2:
Factor graph for the MAM used in the toy example in Sec. 3.1 in the main text.
Circles represent part variables. Hexagons represent attention variables.
Shaded squares represent HOFs.

###  1.2 An illustrative toy example

Our MAMs for perceptual grouping provide a unified framework for symbolic
recurrent computations. They coordinately model top-down parent/children
interactions and lateral contextual object parts interactions. They are
formulated as binary higher-order MRFs, but differ from typical MRFs: MRFs
commonly model graph vertices as variables and use graph edges to encode
conditional independence, while MAMs model both graph vertices and edges as
variables. The attention variables provide a convenient attention mechanism.
They allow part variables to selectively pay attention to a small subset of
other part variables while ignoring the rest, and enable efficient recurrent
computations. In what follows, we work through a toy example to illustrate
MAMs’ coordinated modeling of both top-down and lateral interactions for
perceptual grouping, as well as the efficiency gains from the attention
mechanism through attention variables when compared with typical MRFs.

Consider a $4\times 2$ grid of variables $v_{ij},~{}i=1,\ldots,4,~{}j=1,2$.
Each variable represents a horizontal line segment that can continue, either
in the horizontal direction or right above/below the horizontal direction, to
form a line consisting of two segments. See Fig. 1[upper left] for an
illustration. We further impose the global constraint that there can be at
most two such lines.

We can easily specify a MAM to model the above. In addition to the $8$ binary
part variables $x_{v_{ij}},i=1,\ldots,4,j=1,2~{}$, we introduce $2$ additional
variables $v^{P}_{1},v^{P}_{2}$ and their associated part variables
$x_{v^{P}_{1}},x_{v^{P}_{2}}$, representing possible presence of at most $2$
lines. We specify the interaction graph in Fig. 1[lower left], and the
complete factor graph in Fig. 2. This MAM contains $16$ top-down attention
variables
$a_{\left\\{v_{\ell}^{P},v_{ij}\right\\}},\ell=1,2,i=1,\ldots,4,j=1,2$, and
$10$ lateral attention variables
$a_{\left\\{v_{i_{1}1},v_{i_{2}2}\right\\}},1\leq i_{1},i_{2}\leq
4,\left|i_{1}-i_{2}\right|\leq 1$. We use the HOF
$f_{x_{v^{P}_{\ell}}},\ell=1,2$ (Fig. 1[upper right]) to capture the possible
presence of line $x_{v^{P}_{\ell}}$ and its top-down interaction with exactly
$2$ line segments by

$a_{\sim
x_{v^{P}_{\ell}}}^{(k)}=\left\\{a_{\left\\{v^{P}_{\ell},v_{ik}\right\\}},i=1,\ldots,4\right\\}~{}\forall
k=1,2;~{}~{}\mathcal{B}_{x^{P}_{\ell}}=\left\\{\begin{pmatrix}0,0\end{pmatrix},\begin{pmatrix}1,1\end{pmatrix}\right\\}\text{;
}\mathcal{U}_{x^{P}_{\ell}}(\boldsymbol{b})=0,~{}\forall\boldsymbol{b}\in\mathcal{B}_{x^{P}_{\ell}}$

This guarantees that a line, if present, has to interact with exactly one line
segment in each column. $\forall i=1,\ldots,4,~{}j=1,2$, we use the HOF
$f_{x_{v_{ij}}}$ (Fig. 1[lower right]) to capture the possible presence of
line segment $v_{ij}$, its top-down interaction with one line and its lateral
interaction with one of its continuation candidates by specifying
$\mathcal{B}_{x_{v_{ij}}}=\left\\{\begin{pmatrix}0,0\end{pmatrix},\begin{pmatrix}1,1\end{pmatrix}\right\\},~{}~{}\mathcal{U}_{x_{v_{ij}}}(\boldsymbol{b})=0,\forall\boldsymbol{b}\in\mathcal{B}_{x_{v_{ij}}}$
and

$a_{\sim
x_{v_{ij}}}^{(1)}=\left\\{a_{\left\\{v^{P}_{\ell},v_{ij}\right\\}},~{}\ell=1,2\right\\};~{}~{}~{}a_{\sim
x_{v_{ij}}}^{(2)}=\left\\{a_{\left\\{v_{ij},v_{\tilde{i}\tilde{j}}\right\\}},~{}~{}\left|\tilde{i}-i\right|\leq
1,~{}~{}\tilde{j}=3-j\right\\}$

The above MAM specifies a uniform distribution on all configurations with at
most 2 lines, and coordinately models top-down and lateral interactions
between part variables. Top-down interactions model the composition of a line
with 2 line segments, and inform lateral interactions to enforce the global
constraint of having at most 2 lines. However, they cannot prevent broken
lines. Lateral interactions resolve ambiguities in top-down interactions, and
ensure proper line segments continuations, which can be read off by looking at
the attention variables, even if the line segments themselves are ambiguous
about what the continuations are.

In contrast, an MRF operating only on binary part variables cannot do better
than explicitly encoding all valid joint configurations in a single HOF. This
is because of a complete lack of conditional independence relationships in the
absence of attention variables. As an example, consider the pair of variables
$v_{12}$ and $v_{41}$: if $v_{11},v_{22},v_{31},v_{42}$ are OFF, and
$v_{21},v_{32}$ are ON, then $v_{12}$ and $v_{41}$ have to be both ON or both
OFF. This implies $v_{12}$ and $v_{41}$ are not conditionally independent
given all other variables. In fact, we can use the same argument to establish
that, if we do not introduce attention variables, we do not have any pair of
part variables that are conditionally independent given the rest.

##  2 Symbol grounding with the sparsifier

###  2.1 Formal definition for the sparsifier

A sparsifier is a binary higher-order MRF containing two different types of
variables: (1) binary part variables, which are the same as the part variables
in MAMs and represent the presence/absence of object parts, and (2) binary
pixel variables, which represent pixels in a binary image. In this context, we
describe the object part associated with a part variable by a set of pixels on
the image, and consider the object part as a parent of its covered pixels.
There is one OR factor per pixel variable, which is a HOF that connects the
pixel variable and all its parent part variables.

Formally, for a given $M\times N$ binary image, we have $MN$ pixel variables
$I_{ij},~{}1\leq i\leq M,~{}1\leq j\leq N$ and a set of part variables
$\mathcal{V}_{S}$ in the sparsifier. For a given part variable
$x\in\mathcal{V}_{S}$, we use $I(x)\subset\left\\{(i,j):1\leq i\leq M,1\leq
j\leq N\right\\}$ to represent its associated object part. Let $x_{\sim
I_{ij}}=\left\\{x\in\mathcal{V}_{S}:\left(i,j\right)\in I(x)\right\\}$ be the
set of parent part variables for $I_{ij}$. The OR factor $f_{I_{ij}}$
associated with $I_{ij}$ operates on $\left|x_{\sim I_{ij}}\right|+1$
variables $\left\\{I_{ij}\right\\}\cup x_{\sim I_{ij}}$. We represent a
configuration for $f_{I_{ij}}$ by its set of entries that are ON, which is an
element of $\mathcal{P}\left(\left\\{I_{ij}\right\\}\cup x_{\sim
I_{ij}}\right)$. Using $f_{I_{ij}}\left(\boldsymbol{c}\right)$ to denote the
potential in log domain of configuration
$\boldsymbol{c}\in\mathcal{P}\left(\left\\{I_{ij}\right\\}\cup x_{\sim
I_{ij}}\right)$, the OR factor $f_{I_{ij}}$ is defined as

$f_{I_{ij}}(\boldsymbol{c})=\left\\{\begin{array}[]{lll}0,&\text{if
}\left|x_{\sim I_{ij}}\cap\boldsymbol{c}\right|>0\text{ and
}I_{ij}\in\boldsymbol{c}&\text{(at least one parent {ON}, pixel {ON})}\\\
0,&\text{if }\left|\boldsymbol{c}\right|=0&\text{(all parents {OFF}, pixel
{OFF})}\\\ \log\pi_{01},&\text{if }\left|x_{\sim
I_{ij}}\cap\boldsymbol{c}\right|>0\text{ and
}I_{ij}\not\in\boldsymbol{c}&\text{(at least one parent {ON}, pixel {OFF})}\\\
\log\pi_{10},&\text{if }\left|x_{\sim I_{ij}}\cap\boldsymbol{c}\right|=0\text{
and }I_{ij}\in\boldsymbol{c}&\text{(all parents {OFF}, pixel {ON})}\\\
\end{array}\right.$

where $0\leq\pi_{01},\pi_{10}<0.5$ and $\log 0$ is assumed to represent
$-\infty$.

###  2.2 Illustrative example of sparsifying a line with the sparsifier

We present herein a simple example to illustrate the explaining away type of
reasoning implemented by the sparsifier, and discuss how it can be used to
sparsify a binary image. Consider a $1\times(3K-1)$ binary image where all
pixels are ON, i.e. a line of length $3K-1$. We introduce a set of part
variables $x_{1},\ldots,x_{3K-1}$, and define their corresponding object parts
to be $I(x_{j})=\left\\{(1,k):1\leq k\leq 3K-1\text{ and }\left|j-k\right|\leq
1\right\\}$, i.e. short line segments consisting of two or three pixels. This
implies that $x_{\sim I_{1j}}=\\{x_{k}:~{}1\leq k\leq 3K-1\text{ and
}|j-k|\leq 1\\},~{}1\leq j\leq 3K-1$, which are sets of size two or three. The
OR factor $f_{I_{1j}}$ associated with $I_{1j}$ operates on the $\left|x_{\sim
I_{1j}}\right|+1$ variables $\left\\{I_{1j}\right\\}\cup x_{\sim I_{j}}$. See
Fig. 3 for the complete factor graph in the case $K=2$.

$I_{1,1}$$I_{1,2}$$I_{1,3}$$I_{1,4}$$I_{1,5}$$f_{I_{1,1}}$$f_{I_{1,2}}$$f_{I_{1,3}}$$f_{I_{1,4}}$$f_{I_{1,5}}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$
Figure 3: Factor graph for the toy example of sparsifying a line with the
sparsifier in Sec. 2.2, with $K=2$. The OR factor $f_{I_{1j}}$ operates on the
variables $\left\\{I_{1j}\right\\}\cup\\{x_{k}:~{}1\leq k\leq 3K-1\text{ and
}|j-k|\leq 1\\}$. Each part variable $x_{j}$ is associated with a unary
potential that encourages it to be OFF.

We associate a unary potential in the log domain of $0$ for being OFF and
$\log\pi$ for being ON with each part variable, and set $0<\pi_{10}<\pi<1$.
Under this setup, all the optimal joint configurations have exactly $K$ part
variables being ON, and each such joint configuration corresponds to a sparse
representation of the line. In the case $K=2$ shown in Fig. 3, these optimal
joint configurations are $\\{x_{1},x_{4}\\}$, $\\{x_{2},x_{4}\\}$ and
$\\{x_{2},x_{5}\\}$:

  1. 1.

If all the part variables are OFF, the potential of the joint configuration is
$5\log\pi_{10}$.

  2. 2.

If one part variable is ON, the potential of the joint configuration is
$\log\pi+2\log\pi_{10}$ (when $x_{2}$, $x_{3}$, or $x_{4}$ is ON) or
$\log\pi+3\log\pi_{10}$ (when $x_{1}$ or $x_{5}$ is ON),

  3. 3.

The three joint configurations $\\{x_{1},x_{4}\\}$, $\\{x_{2},x_{4}\\}$ and
$\\{x_{2},x_{5}\\}$ all have potential $2\log\pi$.

  4. 4.

If more than three part variables are ON the joint potential is at most
$3\log\pi$.

Since $0<\pi_{10}<\pi<1$, we establish the optimality of $\\{x_{1},x_{4}\\}$,
$\\{x_{2},x_{4}\\}$ and $\\{x_{2},x_{5}\\}$.

###  2.3 Learning object parts from binary images

We use a special case of hierarchical compositional network (HCN) [1], where
we have a single layer of latent variables and no POOL factors, to learn
object parts directly from binary images. Intuitively, this is equivalent to
replacing the predefined object parts by a set of binary weight variables
covering a regular region (e.g. a rectangular region) in the sparsifier, and
do MPBP inference jointly on the part, pixel and weight variables. Using the
inference results from MPBP, we decode a set of ON weight variables which we
use to define our learned object parts. The weight variables are shared
convolutionally and across multiple images, allowing us to aggregate
information from all images in the learning process and learn a small number
of meaningful, generic and reusable object parts.

##  3 MPBP updates for involved factors

Due to the simple structures in the HOFs in MAMs and the OR factors in the
sparsifier, MPBP updates for these factors can be done efficiently.

Use $\mathbb{M}^{u\to v}\in\mathbb{R}^{2}$ to denote the message (in log
domain) from $u$ to $v$, where $u,v$ correspond to a pair of factor and
variable. Since we can arbitrarily normalize the messages, for convenience and
efficiency, in our implementations we use $m_{u\to v}=\mathbb{M}^{u\to
v}_{2}-\mathbb{M}^{u\to v}_{1}$ as our messages (i.e. we normalize the
messages by substracting $\mathbb{M}^{u\to v}_{1}$ so that $\mathbb{M}^{u\to
v}_{1}$ is always assumed to be 0).

###  3.1 MPBP updates for the HOFs in MAMs:

Due to the simple structure of the HOFs in MAMs, MPBP updates can be done
efficiently. For the HOF $f_{x_{v}}$ in a MAM, given the messages $m_{x_{v}\to
f_{x_{v}}},~{}m_{a\to f_{x_{v}}},~{}a\in a_{\sim x_{v}}$ from variables to
$f_{x_{v}}$, $\forall k=1,\ldots,M_{x_{v}}$, define

$\displaystyle m^{(k)}_{1}$ $\displaystyle=\max_{a\in a_{\sim
x_{v}}^{(k)}}m_{a\to f_{x_{v}}},~{}~{}~{}a^{(k)}=\operatorname*{argmax}_{a\in
a_{\sim x_{v}}^{(k)}}m_{a\to f_{x_{v}}}$ $\displaystyle m^{(k)}_{2}$
$\displaystyle=\begin{cases}\max\limits_{a\in a_{\sim x_{v}}^{(k)}:~{}a\neq
a^{(k)}}m_{a\to f_{x_{v}}}&\text{if }|a^{(k)}_{\sim x_{v}}|>1\\\ 0&\text{if
}|a^{(k)}_{\sim x_{v}}|=1,\end{cases}$

so that $m^{(k)}_{1}$ denotes the largest message coming from all the elements
in the set $a^{(k)}$ and $m^{(k)}_{2}$ denote the second largest message.

For a pair of factor $f$ and variable $v$, the MPBP updates $m_{f\to v}$ are
given by $\mathbb{M}^{f\to v}_{2}-\mathbb{M}^{f\to v}_{1}$, where

$\displaystyle\mathbb{M}^{f_{x_{v}}\to x_{v}}_{2}$
$\displaystyle=\max_{b\in\mathcal{B}_{x_{v}},\|\boldsymbol{b}\|_{1}>0}\left[\mathcal{U}_{x_{v}}(\boldsymbol{b})+m_{x_{v}\to
f_{x_{v}}}+\sum_{k=1}^{M_{x_{v}}}b_{k}m^{(k)}_{1}\right]$
$\displaystyle\mathbb{M}^{f_{x_{v}}\to x_{v}}_{1}$
$\displaystyle=\mathcal{U}_{x_{v}}(\begin{pmatrix}0,\ldots,0\end{pmatrix})$
$\displaystyle\mathbb{M}^{f_{x_{v}}\to a}_{2}$
$\displaystyle=\max_{\boldsymbol{b}\in\mathcal{B}_{x_{v}}:~{}b_{k}=1}\left[\mathcal{U}_{x_{v}}(\boldsymbol{b})+m_{x_{v}\to
f_{x_{v}}}+\sum_{\ell\neq k}b_{\ell}m^{(\ell)}_{1}\right],~{}a\in a_{\sim
x_{v}}^{(k)},~{}a\neq a^{(k)}$ $\displaystyle\mathbb{M}^{f_{x_{v}}\to a}_{1}$
$\displaystyle=\max_{\boldsymbol{b}\in\mathcal{B}_{x_{v}}}\left[\mathcal{U}_{x_{v}}(b)+\mathbbm{1}_{\|\boldsymbol{b}\|_{1}>0}m_{x_{v}\to
f_{x_{v}}}+\sum_{\ell=1}^{M_{x_{v}}}b_{\ell}m^{(\ell)}_{1}\right],~{}a\in
a_{\sim x_{v}}^{(k)},~{}a\neq a^{(k)}$ $\displaystyle\mathbb{M}^{f_{x_{v}}\to
a^{(k)}}_{2}$
$\displaystyle=\max_{\boldsymbol{b}\in\mathcal{B}_{x_{v}}:~{}b_{k}=1}\left[\mathcal{U}_{x_{v}}(\boldsymbol{b})+m_{x_{v}\to
f_{x_{v}}}+\sum_{\ell\neq k}b_{\ell}m^{(\ell)}_{1}\right]$
$\displaystyle\mathbb{M}^{f_{x_{v}}\to a^{(k)}}_{1}$
$\displaystyle=\max_{\boldsymbol{b}\in\mathcal{B}_{x_{v}}}\left[\mathcal{U}_{x_{v}}(\boldsymbol{b})+\mathbbm{1}_{\|\boldsymbol{b}\|_{1}>0}m_{x_{v}\to
f_{x_{v}}}+\sum_{\ell\neq k}b_{\ell}m^{(\ell)}_{1}+b_{k}m^{(k)}_{2}\right]$

###  3.2 MPBP updates for the OR factors in the sparsifier:

For a OR factor $f_{I_{ij}}$ in the sparsifier, if $\left|x_{\sim
I_{ij}}\right|=1$, the updates are trivial. If $\left|x_{\sim
I_{ij}}\right|>1$, given the messages $m_{I_{ij}\to f_{I_{ij}}},m_{x\to
f_{I_{ij}}},x\in x_{\sim I_{ij}}$, define
$x^{(ij)}_{1}=\operatorname*{argmax}_{x\in x_{\sim I_{ij}}}m_{x\to
f_{I_{ij}}},x^{(ij)}_{2}=\operatorname*{argmax}_{x\in x_{\sim I_{ij}},x\neq
x^{(ij)}_{1}}m_{x\to f_{I_{ij}}}$.

Use $m^{+}$ to denote $\max\left\\{0,m\right\\}$, and $m\vee n$ to denote
$\max\left\\{m,n\right\\}$. For a pair of factor $f$ and variable $v$, the
MPBP updates $m_{f\to v}$ are given by $\mathbb{M}^{f\to
v}_{2}-\mathbb{M}^{f\to v}_{1}$, where

$\displaystyle\mathbb{M}^{f_{I_{ij}}\to I_{ij}}_{2}$
$\displaystyle=\left[m_{x^{(ij)}\to f_{I_{ij}}}+\sum_{x\neq x^{(ij)}}m_{x\to
f_{I_{ij}}}^{+}\right]\vee\log\pi_{10}$
$\displaystyle\mathbb{M}^{f_{I_{ij}}\to I_{ij}}_{1}$
$\displaystyle=\left(\log\pi_{01}+m_{x^{(ij)}\to f_{I_{ij}}}+\sum_{x\neq
x^{(ij)}}m_{x\to f_{I_{ij}}}^{+}\right)^{+}$
$\displaystyle\mathbb{M}^{f_{I_{ij}}\to x^{(ij)}_{1}}_{2}$
$\displaystyle=m_{I_{ij}\to f_{I_{ij}}}\vee\log\pi_{01}+\sum_{q\in x_{\sim
I_{ij}},~{}q\neq x^{(ij)}_{1}}m_{q\to f_{I_{ij}}}^{+}$
$\displaystyle\mathbb{M}^{f_{I_{ij}}\to x^{(ij)}_{1}}_{1}$
$\displaystyle=\left(m_{I_{ij}\to
f_{I_{ij}}}+\log\pi_{10}\right)^{+}\vee\left(m_{I_{ij}\to
f_{I_{ij}}}\vee\log\pi_{01}+m_{x^{(ij)}_{2}\to f_{I_{ij}}}+\sum_{q\neq
x,x^{(ij)}_{2}}m_{q\to f_{I_{ij}}}^{+}\right)$

and $\forall x\neq x^{(ij)}_{1}$,

$\displaystyle\mathbb{M}^{f_{I_{ij}}\to x}_{2}$ $\displaystyle=m_{I_{ij}\to
f_{I_{ij}}}\vee\log\pi_{01}+\sum_{q\in x_{\sim I_{ij}},~{}q\neq x}m_{q\to
f_{I_{ij}}}^{+},~{}\forall x\neq x^{(ij)}_{1}$
$\displaystyle\mathbb{M}^{f_{I_{ij}}\to x}_{1}$
$\displaystyle=\left(m_{I_{ij}\to
f_{I_{ij}}}+\log\pi_{10}\right)^{+}\vee\left(m_{I_{ij}\to
f_{I_{ij}}}\vee\log\pi_{01}+m_{x^{(ij)}_{1}\to f_{I_{ij}}}+\sum_{q\in x_{\sim
I_{ij}},~{}q\neq x,x^{(ij)}_{1}}m_{q\to f_{I_{ij}}}^{+}\right)$

##  4 Hardware used for experiments

We use machines with 32 Intel Xeon E5-2620 CPUs and 2 GeForce RTX 2080 Ti GPUs
for experiments.

##  5 Details for the pathfinder challenge

###  5.1 Dataset details

Figure 4: Pathfinder example images from the 3 difficulty levels (easy, medium
and hard).

The easy, medium and hard pathfinder datasets used in our experiments were
generated using code provided by the authors, available at
https://github.com/drewlinsley/pathfinder. See Fig. 4 for example images from
the 3 difficulty levels.

The code was released under the MIT license.

###  5.2 Model

The MAM for the pathfinder challenges uses $T\times M\times N$ part variables
$x_{trc},1\leq t\leq T,1\leq r\leq M,1\leq c\leq N$ to represent the possible
presence of $T$ types of object parts in an $M\times N$ grid of locations. Let
$\left\\{(t_{1},t_{2},\Delta r,\Delta c),~{}(t_{2},t_{1},-\Delta r,-\Delta
c)\right\\},~{}1\leq t_{1},t_{2}\leq T,~{}\Delta r,~{}\Delta c\in\mathbb{Z}$
denote the co-occurrence of $2$ object parts of types $t_{1},t_{2}$, where the
relative displacement of the type $t_{2}$ object part with respect to the type
$t_{1}$ object part is $(\Delta r,\Delta c)$. Each co-occurrence
$\left\\{(t_{1},t_{2},\Delta r,\Delta c),~{}(t_{2},t_{1},-\Delta r,-\Delta
c)\right\\}$ is applied convolutionally and defines a set of attention
variables
$\left\\{a_{\left\\{x_{t_{1}r_{1}c_{1}},x_{t_{2}r_{2}c_{2}}\right\\}}:r_{2}-r_{1}=\Delta
r,c_{2}-c_{1}=\Delta c,1\leq r_{1},r_{2}\leq M,1\leq c_{1},c_{2}\leq
N\right\\}$. The attention variables in the MAM are given by the union of the
above sets of attention variables. We learn $T=16$ types of object parts (Fig.
5[left]) from 10 training images, and extract co-occurences of object parts
from data. For $x_{trc}$, we partition its associated attention variables
$a_{\sim x_{trc}}$ into $2$ sets to capture possible contour continuations on
both sides. The HOF $f_{x_{trc}}$ is specified by (1) the set of prototypical
interaction patterns
$\mathcal{B}_{x_{trc}}=\left\\{\begin{pmatrix}0,0\end{pmatrix},\begin{pmatrix}0,1\end{pmatrix},\begin{pmatrix}1,0\end{pmatrix},\begin{pmatrix}1,1\end{pmatrix}\right\\}$,
which indicates that a contour should continue on one or both sides, and (2)
the potential in log domain
$\mathcal{U}_{x_{trc}}\left(\begin{pmatrix}0,0\end{pmatrix}\right)=\mathcal{U}_{x_{trc}}\left(\begin{pmatrix}1,1\end{pmatrix}\right)=0,\mathcal{U}_{x_{trc}}\left(\begin{pmatrix}0,1\end{pmatrix}\right)=\mathcal{U}_{x_{trc}}\left(\begin{pmatrix}1,0\end{pmatrix}\right)=-1.6$,
which penalizes contour termination and encourages the contour to be OFF or
continue on both sides. We connect the MAM to the image with the sparsifier to
model the presence of a variable number of broken contours.

###  5.3 Pathfinder sparsification example

See Fig. 5 for an example of sparsifying pathfinder images.

Figure 5: Sparsifying pathfinder images.

###  5.4 Learning

Learning:  Learning of object parts and sparsifications are done with
$\pi_{01}=0.07,\pi_{10}=0.0019$, and a unary potential in log domain of $0$
for OFF and $-20$ for ON for all part variables to promote sparse object part
activations. For sparsifications, we repeat MPBP 10 times for each individual
contour to account for randomness. We define the MAM by aggregrating co-
occurences from all individual contours while filtering out any co-occurence
whose relative frequency is less than $1.7\times 10^{-7}$.

###  5.5 Pathfinder ultimate

In the original pathfinder datasets, for easy, there are two long contours of
length 6, and 15 distractor contours of length 2 (Fig. 4[left]). For medium,
there are two long contours of length 9, and 9 distractor contours of length 3
(Fig. 4[center]). For hard, there are two long contours of length 14, and 7
distractor contours of length 4 (Fig. 4[right]).

Since only the hard difficulty level proves to be challenging, we generate a
new ultimate difficulty level by modifying the original data generation code
to further probe the generalization capacities of MAM and H-CNN. For each
ultimate image: (1) we first draw two long contours, each one with a length
selected uniformly in $\left[20,30\right]$; (2) we then draw two long
distractors, each one with a length selected uniformly in $\left[15,30\right]$
(3) we finally draw at most $8$ short distractors with length selected
uniformly in $\left[6,14\right]$. See Fig. 4[center right] in the main text
for an example.

##  6 Details for the cABC challenge

###  6.1 Dataset details

We use datasets provided by the authors at
https://openreview.net/forum?id=HJxrVA4FDS, available for download at
https://bit.ly/2wdQYGd. See Fig. 4 for example images from the 3 difficulty
levels.

Figure 6: cABC example images from the 3 difficulty levels (easy, medium and
hard).

###  6.2 Model

We model elastic graphs with object-specific MAMs, and match elastic graphs to
noisy, distorted letters to solve the cABC challenge. An elastic graph
$\mathcal{G}_{E}(\eta)=\left(\mathcal{V}_{E},\mathcal{E}_{E},\eta\right)$ is
an undirected graph where $\mathcal{V}_{E}$ represents its set of vertices and
$\mathcal{E}_{E}=\left\\{\left\\{u,v\right\\}:~{}u,v\in\mathcal{V}_{E},~{}\exists\text{
an edge in }\mathcal{G}_{E}\text{ connecting }u,v\right\\}$. Each
$v\in\mathcal{V}_{E}$ represents an object part, and each
$\left\\{u,v\right\\}\in\mathcal{E}_{E}$ represents an elastic constraint on
$u,v$. An elastic graph models the letter as a composition of all the object
parts represented by the vertices. We associate a reference location
$(r_{v},c_{v})$ with $v\in\mathcal{V}_{E}$, which indicates the expected
location of the corresponding object part. We allow the vertex
$v\in\mathcal{V}_{E}$ to move around, and use
$\left(\tilde{r}_{v},\tilde{c}_{v}\right)$ to denote its actual location. We
use $\eta\geq 1$ to restrict the actual locations of the vertices to be
$0\leq\tilde{r}_{v}-r_{v},\tilde{c}_{v}-c_{v}<\eta,\forall
v\in\mathcal{V}_{E}$. We associate a perturb radius
$\gamma_{\left\\{u,v\right\\}}$ with each edge
$\left\\{u,v\right\\}\in\mathcal{E}_{E}$, which constrains the actual relative
displacements
$\left(\tilde{r}_{v}-\tilde{r}_{u},\tilde{c}_{v}-\tilde{c}_{u}\right)$ to
differ (in $L_{\infty}$ norm) by no more than $\gamma_{\left\\{u,v\right\\}}$
from the reference relative displacements
$\left(r_{v}-r_{u},c_{v}-c_{u}\right)$, i.e.
$\left|(\tilde{r}_{v}-\tilde{r}_{u})-(r_{v}-r_{u})\right|\leq\gamma_{\left\\{u,v\right\\}},\left|(\tilde{c}_{v}-\tilde{c}_{u})-(c_{v}-c_{u})\right|\leq\gamma_{\left\\{u,v\right\\}}$.

###  6.3 Formal definitions of the object-specific MAM

Elastic graphs are inherently shift invariant, and are completely specified by
the relative displacements of its vertices. For ease of presentation, we
define
$\left(r^{\mathcal{G}_{E}(\eta)},c^{\mathcal{G}_{E}(\eta)}\right)=\left(\min_{v\in\mathcal{V}_{E}}r_{v},\min_{v\in\mathcal{V}_{E}}c_{v}\right)$
as the anchor point of $\mathcal{G}_{E}(\eta)$ with reference locations
$\left\\{\left(r_{v},c_{v}\right),v\in\mathcal{V}_{E}\right\\}$. We can
transform an elastic graph $\mathcal{G}_{E}(\eta)$ with anchor point
$\left(r^{\mathcal{G}_{E}(\eta)},c^{\mathcal{G}_{E}(\eta)}\right)$ into an
elastic graph $\overline{\mathcal{G}}_{E}(\eta)$ with anchor point
$\left(r^{\overline{\mathcal{G}}_{E}(\eta)},c^{\overline{\mathcal{G}}_{E}(\eta)}\right)$
by updating the reference location of vertex $v\in\mathcal{V}_{E}$ from
$\left(r_{v},c_{v}\right)$ to
$\left(r_{v}-r^{\mathcal{G}_{E}(\eta)}+r^{\overline{\mathcal{G}}_{E}(\eta)},c_{v}-c^{\mathcal{G}_{E}(\eta)}+c^{\overline{\mathcal{G}}_{E}(\eta)}\right)$.

We can specify an object-specific MAM for a given elastic graph
$\mathcal{G}_{E}(\eta)$. We associate a part variable
$x_{v\tilde{r}_{v}\tilde{c}_{v}}^{\mathcal{G}_{E}(\eta)}$ with each allowed
location
$\left(\tilde{r}_{v},\tilde{c}_{v}\right),v\in\mathcal{V}_{E},0\leq\tilde{r}_{v}-r_{v},\tilde{c}_{v}-c_{v}<\eta$.
For each edge $\left\\{u,v\right\\}\in\mathcal{E}_{E}$, we associate a lateral
attention variable
$a_{\left\\{x^{\mathcal{G}_{E}(\eta)}_{u\tilde{r}_{u}\tilde{c}_{u}},x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}\right\\}}$
with each pair of locations
$\left(\tilde{r}_{u},\tilde{c}_{u}\right),\left(\tilde{r}_{v},\tilde{c}_{v}\right)$
in an allowed relative displacement (i.e.
$\left|(\tilde{r}_{v}-\tilde{r}_{u})-(r_{v}-r_{u})\right|\leq\gamma_{\left\\{u,v\right\\}},\left|(\tilde{c}_{v}-\tilde{c}_{u})-(c_{v}-c_{u})\right|\leq\gamma_{\left\\{u,v\right\\}}$).
We additionally introduce the part variable $x^{\mathcal{G}_{E}(\eta)}$ to
represent the possible presence of the letter, and the top-down attention
variables

$a_{\left\\{x^{\mathcal{G}_{E}(\eta)},x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}\right\\}},v\in\mathcal{V}_{E},0\leq\tilde{r}_{v}-r_{v},\tilde{c}-c_{v}<\eta$

For the HOF $f_{x^{\mathcal{G}_{E}(\eta)}}$, we partition $a_{\sim
x^{\mathcal{G}_{E}(\eta)}}$ into
$M_{x^{\mathcal{G}_{E}(\eta)}}=\left|\mathcal{V}_{E}\right|$ disjoint sets of
attention variables

$a_{\sim
x^{\mathcal{G}_{E}(\eta)}}^{(k)}=\left\\{a_{\left\\{x^{\mathcal{G}_{E}(\eta)},x^{\mathcal{G}_{E}(\eta)}_{v_{k}\tilde{r}_{v_{k}},\tilde{c}_{v_{k}}}\right\\}}:0\leq\tilde{r}_{v_{k}}-r_{v_{k}},\tilde{c}_{v_{k}}-c_{v_{k}}<\eta\right\\},k=1,\ldots,\left|\mathcal{V}_{E}\right|$

where
$\mathcal{V}_{E}=\left\\{v_{1},\ldots,v_{\left|\mathcal{V}_{E}\right|}\right\\}$
is some ordering of all the vertices in $\mathcal{V}_{E}$. Define
$\mathcal{B}_{x^{\mathcal{G}_{E}(\eta)}}=\left\\{\begin{pmatrix}0,\ldots,0\end{pmatrix},\begin{pmatrix}1,\ldots,1\end{pmatrix}\right\\}$
and $\mathcal{U}_{x^{\mathcal{G}_{E}(\eta)}}(b)=0,\forall
b\in\mathcal{B}_{x^{\mathcal{G}_{E}(\eta)}}$. Intuitively, this enforces that,
if the letter is present, then each $v\in\mathcal{V}_{E}$ much be present, at
exactly one of the allowed location.

For the HOFs
$f_{x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}},v\in\mathcal{V}_{E},0\leq\tilde{r}_{v}-r_{v},\tilde{c}_{v}-c_{v}<\eta$,
we partition $a_{\sim
x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}$ into
$M^{\mathcal{G}_{E}(\eta)}_{v}=\left|\left\\{u\in\mathcal{V}_{E}:\left\\{u,v\right\\}\in\mathcal{E}_{E}\right\\}\right|+1$
disjoint sets of attention variables

$a_{\sim
x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}^{(k)}=a_{\sim
x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}\cap a_{\sim
x^{\mathcal{G}_{E}(\eta)}_{u_{k}\tilde{r}_{u_{k}}\tilde{c}_{u_{k}}}},k=1,\ldots,M^{\mathcal{G}_{E}(\eta)}_{v}-1,a_{\sim
x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}^{\left(M^{\mathcal{G}_{E}(\eta)}_{v}\right)}=\left\\{a_{x^{\mathcal{G}_{E}(\eta)},x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}\right\\}$

where we impose some ordering
$\left\\{u\in\mathcal{V}_{E}:\left\\{u,v\right\\}\in\mathcal{E}_{E}\right\\}=\left\\{u_{1},\ldots,u_{M_{x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}-1}\right\\}$.
We define
$\mathcal{B}_{x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}=\left\\{\begin{pmatrix}0,\ldots,0\end{pmatrix},\begin{pmatrix}1,\ldots,1\end{pmatrix}\right\\}$
and
$\mathcal{U}_{x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}\left(\begin{pmatrix}0,\ldots,0\end{pmatrix}\right)=-1000,\mathcal{U}_{x^{\mathcal{G}_{E}(\eta)}_{v\tilde{r}_{v}\tilde{c}_{v}}}(\begin{pmatrix}1,\ldots,1\end{pmatrix})=0$.

For the cABC challenge, assume the sizes of the images imply that object parts
can be instantiated on an $M\times M$ grid. We extract elastic graphs from $N$
letters in the training images using the procedure outlined in Sec. 6.5, and
transform them into a set of elastic graphs
$\mathcal{G}_{E}^{(n)}(M)=\left(\mathcal{V}_{E}^{(n)},\mathcal{E}_{E}^{(n)},M\right),n=1,\ldots,N$
whose anchor points are all $(1,1)$. We construct $N$ MAMs
$\mathcal{M}^{\mathcal{G}_{E}^{(n)}(M)},n=1,\ldots,N$ as described above, and
merge them into a single MAM $\mathcal{M}$ with part variables that live
within the $M\times M$ grid
$x^{\mathcal{G}_{E}^{(n)}(M)}_{v\tilde{r}_{v}\tilde{c}_{v}},v\in\mathcal{V}_{E}^{(n)},r_{v}\leq\tilde{r}_{v}\leq
M,c_{v}\leq\tilde{c}_{v}\leq M,n=1,\ldots,N$, the lateral attention variables
$a_{\left\\{x^{\mathcal{G}_{E}^{(n)}(M)}_{u\tilde{r}_{u}\tilde{c}_{u}},x^{\mathcal{G}_{E}^{(n)}(M)}_{v\tilde{r}_{v}\tilde{c}_{v}}\right\\}}$
where
$\left\\{u,v\right\\}\in\mathcal{E}_{E}^{(n)},\left|(\tilde{r}_{v}-\tilde{r}_{u})-(r_{v}-r_{u})\right|\leq\gamma_{\left\\{u,v\right\\}},\left|(\tilde{c}_{v}-\tilde{c}_{u})-(c_{v}-c_{u})\right|\leq\gamma_{\left\\{u,v\right\\}},r_{v}\leq\tilde{r}_{v}\leq
M,c_{v}\leq\tilde{c}_{v}\leq M,n=1,\ldots,N$ and collapsing the part variables
$x^{\mathcal{G}_{E}^{(n)}(M)}$ into a single part variable $x^{\mathcal{M}}$,
with top-down attention variables

$a_{\left\\{x^{\mathcal{M}},x^{\mathcal{G}_{E}^{(n)}(M)}_{v\tilde{r}_{v}\tilde{c}_{v}}\right\\}},r_{v}\leq\tilde{r}_{v}\leq
M,c_{v}\leq\tilde{c}_{v}\leq M,n=1,\ldots,N$

The HOFs
$f_{x^{\mathcal{G}_{E}^{(n)}(M)}_{v\tilde{r}_{v}\tilde{c}_{v}}},r_{v}\leq\tilde{r}_{v}\leq
M,c_{v}\leq\tilde{c}_{v}\leq M,n=1,\ldots,N$ remain the same (with
$x^{\mathcal{G}_{E}^{(n)}(M)}$ replaced by $x^{\mathcal{M}}$), while for the
HOF $f_{x^{\mathcal{M}}}$, we now partition $a_{\sim x^{\mathcal{M}}}$ into
$M_{x^{\mathcal{M}}}=\sum_{n=1}^{N}\left|\mathcal{V}_{E}^{(n)}\right|$
disjoint sets of attention variables: $\forall
n=1,\ldots,N,k=1,\ldots,\left|\mathcal{V}_{E}^{(n)}\right|$,

$a_{\sim
x^{\mathcal{M}}}^{(\sum_{i=1}^{n-1}\left|\mathcal{V}_{E}^{(n)}\right|+k)}=\left\\{a_{\left\\{x^{\mathcal{M}},x^{\mathcal{G}_{E}^{(n)}(M)}_{v_{k}\tilde{r}_{v_{k}},\tilde{c}_{v_{k}}}\right\\}}:r_{v}\leq\tilde{r}_{v}\leq
M,c_{v}\leq\tilde{c}_{v}\leq M\right\\}$

and
$\mathcal{B}_{x^{\mathcal{M}}}=\left\\{\begin{pmatrix}0,\ldots,0\end{pmatrix}\right\\}\cup\left\\{b^{(n)},n=1,\ldots,N\right\\}$,
where $\forall n\in\left\\{1,\ldots,N\right\\}$,

$b^{(n)}_{j}=\begin{cases}1,&\text{if
}\sum_{i=1}^{n-1}\left|\mathcal{V}_{E}^{(i)}\right|<j\leq\sum_{i=1}^{n}\left|\mathcal{V}_{E}^{(i)}\right|\\\
0,&\text{otherwise}\end{cases}$

and

$\mathcal{U}_{x^{\mathcal{M}}}(\begin{pmatrix}0,\ldots,0\end{pmatrix})=-1000,\mathcal{U}_{x^{\mathcal{M}}}(b)=0,\forall
b\in\mathcal{B}_{x^{\mathcal{M}}},b\neq\begin{pmatrix}0,\ldots,0\end{pmatrix}$

Intuitively, each individual $\mathcal{M}^{\mathcal{G}_{E}^{(n)}(M)}$ encodes
the presence of the $n$th letter at a certain location on the image, while
$\mathcal{M}$ merges the individual MAMs to encode the presence of exactly one
letter at a certain location on the image. We connect $2$ copies
$\mathcal{M}^{(1)},\mathcal{M}^{(2)}$ of $\mathcal{M}$ to the image with the
sparsifier to model the presence of $2$ noisy, distorted letters in each
image.

###  6.4 cABC sparsification example

See Fig. 2[center right] and Fig. 2[right] in the main text for an example of
sparsifying a noisy, distorted cABC letter. The vertices in the elastic graph
in Fig. 2[right] in the main text represent the sparse set of object part
activations given by sparsifying the binary input image (Fig. 2[center right]
in the main text) with the sparsifier using a single object part learned from
10 training images (lower left of Fig. 2[right] in the main text).

###  6.5 Learning elastic graphs for cABC

Learning of the single object part and sparsifications are done using
$\pi_{01}=0.45,\pi_{10}=0.05$, and a unary potential in log domain of $0$ for
OFF and $-20$ for ON for all part variables to promote sparse object part
activations. We define the vertices in the elastic graph using the sparse
object part activations from MPBP decoding.

Given a sparse set of object part activations ($\mathcal{V}_{E}$), we use Alg.
1 to construct an elastic graph. In our experiments, we used perturbation
factor $7.0$, tolerance $2.0$ and max connection length $200$. These hyper-
parameters were derived by doing a parameter sweep over integers and measuring
performance on a small validation set.

Intuitively, we use the perturbation factor to capture the notion that the
relative displacement of a pair of far-away object parts can vary more than
that of a pair of close-by object parts. For a pair of object parts
$u,v\in\mathcal{V}_{E}$, using $d_{u,v}$ to denote their Euclidean distance,
the associated perturb radius is roughly given by $d_{u,v}$ divided by the
perturb factor. To implement the constrained elasticities, a naive approach is
to add an elastic constraint for every pair of vertices. However, this would
result in an overly dense elastic graph and makes subsequent inference
inefficient. In Alg. 1, we use a heuristic algorithm to add a small number of
elastic constraints. We start from vertices that are closest together, and
progressively add elastic constraints. For a given pair of vertices, we skip
adding their elastic constraint if the desired elastic constraint can already
be enforced using existing elastic constraints (up to the specified
tolerance). We adopt a final refining step to account for rounding errors.
Refer to Alg. 1 for more details. See Fig. 2[right] in the main text for an
example elastic graph.

Input: Elastic graph vertices $\mathcal{V}_{E}$ and the associated reference
locations $(r_{v},c_{v}),\forall v\in\mathcal{V}_{E}$, perturbation factor
$p$, tolerance $t$, max connection length $l$

Output: Elastic graph edges $\mathcal{E}_{E}$ and the associated perturb
radius
$\gamma_{\left\\{u,v\right\\}},\forall\left\\{u,v\right\\}\in\mathcal{E}_{E}$

Procedure  _GetEdges(_$\mathcal{V}_{E}$ , $r$, $c$, $p$, $t$, $l$_)_

$C,d\leftarrow$ GetPotentialEdges ($\mathcal{V}_{E}$, $r$, $c$, $l$);

$\mathcal{E}_{E},\gamma\leftarrow$ AddEdges ($\mathcal{C}$, $d$, $p$, $t$);

$O\leftarrow$ EdgeDepthFirstSearch(_$\mathcal{E}_{E}$ , [], AnyElementOf
($\mathcal{V}_{E}$) _);

$\gamma\leftarrow$ RefineEdges(_$O$ , $d$, $\gamma$, $p$_);

return $\mathcal{E}_{E}$, $\gamma$;

Procedure  _GetPotentialEdges(_$\mathcal{V}_{E}$ , $r$, $c$, $l$_)_

$P\leftarrow[]$

for  _$u$ in $\mathcal{V}_{E}$_ do

for  _$v$ in $\mathcal{V}_{E}$_ do

$d_{u,v}\leftarrow\sqrt{(r_{v}-r_{u})^{2}+(c_{v}-c_{u})^{2}}$

if  _$d_{u,v} <l$ and $\left\\{u,v\right\\}\notin P$ _ then

$P\leftarrow$append($P$, $\left\\{u,v\right\\}$)

end if

end for

end for

$C\leftarrow$sorted($P$) by $d_{u,v}$ ascending

return $C$, $d$;

Procedure  _AddEdges(_$\mathcal{C}$ , $d$, $p$, $t$_)_

$\mathcal{E}_{E}\leftarrow\\{\\}$

$\gamma\leftarrow\\{\\}$

for  _$\left\\{u,v\right\\}$ in $\mathcal{C}$_ do

$i\leftarrow\max\left\\{1,\frac{d_{u,v}}{p}\right\\}$

$n\leftarrow$ ShortestPath($u$,$v$) in $\mathcal{E}_{E}$ with edge weights
$\gamma$

// infinity if no path exists

if  _$n >it$_ then

$\mathcal{E}_{E}\leftarrow\mathcal{E}_{E}\cup\left\\{\left\\{u,v\right\\}\right\\}$

$\gamma_{\left\\{u,v\right\\}}\leftarrow\lceil i\rceil$

end if

end for

return $\mathcal{E}_{E},\gamma$;

Procedure  _EdgeDepthFirstSearch(_$\mathcal{E}_{E}$ , $O$, $u$_)_

for
_$v\in\left\\{v\in\mathcal{V}_{E}|\left\\{u,v\right\\}\in\mathcal{E}_{E}\right\\}$_
do

if  _$\left\\{u,v\right\\}\notin O$_ then

$O\leftarrow$ append(O, $\left\\{u,v\right\\}$)

$O\leftarrow$ concatenate(O, EdgeDepthFirstSearch(_$\mathcal{E}_{E}$ , $O$,
$v$_))

end if

end for

return $O$;

Procedure  _RefineEdges(_$O$ , $d$, $\gamma$, $p$_)_

$\eta\leftarrow 0$;

for  _$\left\\{u,v\right\\}$ in $O$_ do

$i\leftarrow\max\left\\{1,\frac{d_{u,v}}{p}\right\\}$

if  _$|\lceil i\rceil-i+\eta| <|\lfloor i\rfloor-i+\eta|$_ then

$\gamma_{\left\\{u,v\right\\}}=\lceil i\rceil$

$\eta\leftarrow\lceil i\rceil-i+\eta$

else

$\gamma_{\left\\{u,v\right\\}}=\lfloor i\rfloor$

$\eta\leftarrow\lfloor i\rfloor-i+\eta$

end if

end for

return $\gamma$

Algorithm 1 Adding edges to elastic graphs

###  6.6 Efficient inference with the object-specific MAM

In our formulation, we use $\mathcal{M}$ to model the presence of a particular
training letter at a certain location on the image. In practice, only a small
number of training letters at a small number of locations would fit a given
image well. To make inference efficient, we use fast feedforward operations to
identify the rough locations of a small number of training letters (in the
form of a small number of elastic graphs with different anchor points and
small $\eta$), and do MPBP inference only with the relevant part and attention
variables. All the hyper-parameters used in this section are empirically set
with a validation set consisting of $1000$ easy cABC images. The same set of
hyper-parameters are then applied to all 3 difficulty levels (easy, medium and
hard) without change.

We follow notations in Sec. 3.2 in the main text and in Sec. 3. For a given
$M\times M$ image, use $m_{I_{ij}}$ to denote the evidence coming from the
image to the pixel variable $I_{ij},1\leq i,j\leq M$. For a given elastic
graph $\mathcal{G}_{E}(\eta)=(\mathcal{V}_{E},\mathcal{E}_{E},\eta)$, we
define its score to be

$\frac{1}{\left|\mathcal{V}_{E}\right|^{0.76}}\left(\sum_{v\in\mathcal{V}_{E}}\max_{\tilde{r}_{v},\tilde{c}_{v}:~{}0\leq\tilde{r}_{v}-r_{v},~{}\tilde{c}_{v}-c_{v}<\eta}\sum_{(i,j)\in
I(x_{v\tilde{r}_{v}\tilde{c}_{v}}^{\mathcal{G}_{E}(\eta)})}m_{I_{ij}}\right)$

Intuitively, to get the score of an elastic graph $\mathcal{G}_{E}(\eta)$, for
each object part $v\in\mathcal{V}_{E}$, we obtain the score of the object part
at a given location $(\tilde{r}_{v},\tilde{c}_{v})$ by summing up the evidence
from pixels that are part of this object part, i.e. $\sum_{(i,j)\in
I(x_{v\tilde{r}_{v}\tilde{c}_{v}}^{\mathcal{G}_{E}(\eta)})}m_{I_{ij}}$. We
maximize over all the allowed locations
$0\leq\tilde{r}_{v}-r_{v},\tilde{c}_{v}-c_{v}<\eta$ of the object part
$v\in\mathcal{V}_{E}$ to get the score of the object part
$\max_{\tilde{r}_{v},\tilde{c}_{v}:0\leq\tilde{r}_{v}-r_{v},\tilde{c}_{v}-c_{v}<\eta}\sum_{(i,j)\in
I(x_{v\tilde{r}_{v}\tilde{c}_{v}}^{\mathcal{G}_{E}(\eta)})}m_{I_{ij}}$, and we
sum over all the object parts in the elastic graph to get the unnormalized
score of the elastic graph
$\sum_{v\in\mathcal{V}_{E}}\max_{\tilde{r}_{v},\tilde{c}_{v}:~{}0\leq\tilde{r}_{v}-r_{v},~{}\tilde{c}_{v}-c_{v}<\eta}\sum_{(i,j)\in
I(x_{v\tilde{r}_{v}\tilde{c}_{v}}^{\mathcal{G}_{E}(\eta)})}m_{I_{ij}}$. We
normalize the score by $\frac{1}{\left|\mathcal{V}_{E}\right|^{0.76}}$ to
prevent the process from being dominated by elastic graphs with a large number
of vertices.

In our experiments, we first downsample the original $350\times 350$ images to
$256\times 256$ images (i.e. $M=256$), and use circles of radius $4$ as our
only object part. We define $m_{ij}=1.0$ for the pixel $(i,j)$ that is ON, and
$m_{ij}=-0.89$ for the pixel $(i,j)$ that is OFF. To make the elastic graphs
scores informative, instead of using $\eta=256$ to allow the vertices to move
around as much as possible, we use $\eta=15$ to evaluate how well an elastic
graph fits in a local region. To cover the entire image, we shift the anchor
points from $(1,1)$ to the right/downwards with a step size of $13$, i.e. we
consider the elastic graph $\mathcal{G}_{E}(15)$ and its transformed copies
with anchor points $(1+13\times k,1+13\times\ell),k,\ell\in\mathbb{N}$. This
implies that, for each elastic graph $\mathcal{G}_{E}(15)$, we are evaluating
its scores at 400 different locations.

We evaluate the scores for all the elastic graphs and their transformed
copies. For a given anchor point, we rank the elastic graphs with this anchor
point based on their scores, and keep the top $3$ elastic graph at each anchor
point. We aggregate the top $3$ elastic graphs from all $400$ anchor points,
and keep the top $140$ (across all the anchor points) as estimates of the
locations of the most promising elastic graphs.

We take the $140$ most promising elastic graphs and use $\eta=25$ to allow
more invariance in the MAM inference. To parallelize the inference process,
for each elastic graph $\mathcal{G}_{E}(25)$, we use $\sum_{(i,j)\in
I(x_{v\tilde{r}_{v}\tilde{c}_{v}}^{\mathcal{G}_{E}(25)})}m_{I_{ij}}$ as the
evidence for the part variable
$x_{v\tilde{r}_{v}\tilde{c}_{v}}^{\mathcal{G}_{E}(25)}$, and do MPBP inference
in parallel for all the elastic graphs. From the MPBP decodings, for each
$v\in\mathcal{V}_{E}$, we can determine its most likely location, which we
denote as $(\hat{r}_{v},\hat{c}_{v})$. We define
$I(\mathcal{G}_{E}(25))=\cup_{v\in\mathcal{V}_{E}}I(x_{v\hat{r}_{v}\hat{c}_{v}}^{\mathcal{G}_{E}(25)})$
as the set of pixels associated with the elastic graph MPBP decoding. For each
pixel $(i,j)\in I(\mathcal{G}_{E}(25))$, use
$\mathcal{N}((i,j),\mathcal{G}_{E}(25))=\sum_{v\in\mathcal{V}_{E}}\mathbbm{1}_{(i,j)\in
I(x_{v\hat{r}_{v},\hat{c}_{v}}^{\mathcal{G}_{E}(25)})}$ to denote the number
of object parts in the MPBP decoding that covers the pixel $(i,j)$.

As a final inference step, we approximate MPBP inference with the sparsifier
with a heuristic pairwise reasoning step. More concretely, we consider all
${140\choose 2}=9730$ possible pairs of elastic graphs. We define the score of
a given pair of elastic graphs $\mathcal{G}_{E}^{(1)}(25)$ and
$\mathcal{G}_{E}^{(2)}(25)$ as

$\sum_{(i,j)\in I(\mathcal{G}_{E}^{(1)}(25))\cup
I(\mathcal{G}_{E}^{(2)}(25))}\left[m_{I_{ij}}-\left(\mathcal{N}((i,j),\mathcal{G}_{E}^{(1)}(25))+\mathcal{N}((i,j),\mathcal{G}_{E}^{(2)}(25))-1\right)*0.33\right]$

i.e. we sum up the evidence from all the involved pixels, while applying a
small penalty for object parts that overlap with each other.

We pick the pair of elastic graphs with the highest score as our
interpretation of the test image, and heuristically assign the two markers to
classifier cABC test images.

Figure 7: Visualization of MAM detections on realistic images for 6 objects
(_barkely_hide_bones, clorox_utility_brush, cloud_b_plush_bear,
fiskars_scissors_red, creativity_chenille_stems, oral_b_toothbrush_red_) from
the Object Segmentation Training Dataset. Blue dots in the right column
represent object part activations from MPBP inference with MAMs.

##  7 Details for experiments on realistic images

###  7.1 Dataset

We use realistic RGB-D images containing 39 different single objects in totes
from the Object Segmentation Training Dataset [2], available for download at
https://vision.princeton.edu/projects/2016/apc/. For each object, we have
multiple scenes. Each scene has the object in a different pose. For each
scene, we have multiple frames. Each frame has the camera in a different pose.
We use the RGB, depth and object masks associated with each frame as our train
and test data. We randomly sample 70% of the scenes as training data, and use
the remaining 30% as test data. Since we want to test an object-specific MAM
modeling entire objects, we filter out frames in which the objects are only
partially visible due to object and camera poses, by keeping frames with the
largest mask sizes for each scene. For each training scene, we keep the top 3
frames. For each test scene, we keep the top 5 frames. This results in a
dataset with 7797 training frames and 5870 test frames across all objects. See
the left column in Fig. 7 for the visualization of some example images.

###  7.2 Edge detection and heuristic sparsification

For edge detection, we take the maximum response from grayscale filters of 16
orientations over the 3 channels of RGB images, followed by a local
suppression step similar to that used in Canny edge detection. See the middle
column in Fig. 7 for the visualization of the maximum response on test images
from the detection of edges of 16 orientations.

For sparsification, we adopt a heuristic procedure, where we pick points
roughly at equal distances. More concretely, we start from a random point, and
greedily pick points at a distance close to our target distance, until we can
no longer pick new points. From the set of unpicked points, we then randomly
pick a new starting point that is at least the target distance away from
already picked points, and continue the greedy procedure. We repeat until we
can no longer find new points.

###  7.3 Visualization of results

See the right column in Fig. 7 for the visualization of MAM detections on 6
objects from the Object Segmentation Training Dataset. Blue dots represent
object part activations from MPBP inference with MAMs. From the results we can
see that, dispite challenges like deformable objects, similar color to
background, and adversial surface properties (e.g. reflective), our object-
specific MAMs do a good job at detecting the objects, and give interpretable
decodings, which we can use to further understand the pose of the detected
objects.

## References

  * [1] Miguel Lázaro-Gredilla, Yi Liu, D Scott Phoenix, and Dileep George.  Hierarchical compositional feature learning.  arXiv preprint arXiv:1611.02252, 2016.
  * [2] Andy Zeng, Kuan-Ting Yu, Shuran Song, Daniel Suo, Ed Walker Jr, Alberto Rodriguez, and Jianxiong Xiao.  Multi-view self-supervised deep learning for 6d pose estimation in the amazon picking challenge.  In Proceedings of the IEEE International Conference on Robotics and Automation, 2017.


#  $\sigma$-locales and Booleanization in Formal Topology

Francesco Ciraulo111Department of Mathematics, University of Padua, Via
Trieste 63, 35121 Padova (Italy), Email<EMAIL_ADDRESS>URL:
www.math.unipd.it/$\sim$ciraulo

###### Abstract

A $\sigma$-frame is a poset with countable joins and finite meets in which
binary meets distribute over countable joins. Aim of this paper is to present
$\sigma$-frames, actually $\sigma$-locales, as a branch of Formal Topology,
that is, intuitionistic and predicative pointfree topology. We show that every
$\sigma$-frame $L$ can be presented as the lattice of Lindelöf elements (those
whose covers admit countable subcovers) of a formal topology of a specific
kind which, in its turn, corresponds to the free frame over $L$. We then give
a constructive characterization of the smallest dense $\sigma$-sublocale of a
given $\sigma$-locale, thus providing a “$\sigma$-version” of a Boolean
locale.

#### Keywords:

Formal Topology, $\sigma$-frames, overlap algebras, overt locales, strongly
dense sublocales.

#### MSC2010:

06D22, 03F65.

## Introduction

It is well known that the set $B(H)=\\{x\in H\ |\ x=--x\\}$ of stable elements
of a complete Heyting algebra $H$ has a complete Boolean algebra structure.
Actually $B(H)$ is a quotient of $H$ in the category of frames. From the point
of view of the category of locales, this means that every locale $L$ contains
a Boolean sublocale $B(L)$, which can be characterized as the smallest dense
sublocale of $L$.

Sambin [16] (see also [7]) introduced the notion of an _overlap algebra_ as a
“positive” alternative to that of a complete Boolean algebra. One of the main
advantages of his approach is that powersets are examples of overlap algebras
(in fact they are precisely the atomic ones), although they are not Boolean
constructively.

It has recently turned out [4] that overlap algebras can be understood as the
smallest _strongly dense_ sublocales (in the sense of [11]) of overt locales.
The same statement can be given a predicative interpretation by considering a
formal topology $(S,\lhd,\mathrm{\,Pos})$ in place of an overt locale $L$.

The notion of a $\sigma$-locale is a natural generalization of that of a
locale: the underlying lattice is a $\sigma$-frame, rather than a frame, that
is, it is required to have just countable, rather than arbitrary, joins. As
shown in [17], $\sigma$-locales play an important role in the pointfree
approach to measure theory and probability.

The construction of $B(L)$ from $L$ can be mimicked in the case of
$\sigma$-locales [12]. In that case, $B(L)$ is still the smallest dense
$\sigma$-sublocale of $L$; however, it is not Boolean any longer, in general.
The $\sigma$-frames of the form $B(L)$ are called _d-reduced_ (“d” for
“dense”) in [12].

Our aim is to give a positive account of d-reduced $\sigma$-locales. In order
to obtain this, we work with $\sigma$-locales which are _overt_ (in a suitable
sense). The positivity predicate $\mathrm{\,Pos}$ of an overt $\sigma$-locale
$L$ is then used to define a positive version of the _codense_ congruence
relation on $L$ [12], which corresponds to the smallest dense
$\sigma$-sublocale $B(L)$ of $L$. Actually, because of the positive nature of
our definition, the notion of density involved here is intuitionistically
stronger than the usual one.

Our results are constructive in a strong sense, I would dare say. Indeed our
arguments are always intuitionistically valid, predicative and choice-free;
but we need the axiom of countable choice. In fact, I claim that the whole
paper could be formalized in the extensional level of the so-called Minimalist
Foundations [14, 13] augmented with countable choice. In such a foundational
framework, Formal Topology is the “native” way to develop pointfree topology.

Before undertaking our main task, we need to start with some constructive
results about the notion of a countable set.

##  1 A constructive look at countable sets

By a countable set we intuitively mean a set $S$ which is either (empty or)
finite or countably infinite (that is, in bijection with the set $\mathbb{N}$
of natural numbers). Within usual foundations (such as $ZF$ with countable
choice $AC_{\omega}$), this is equivalent to saying that a set is either empty
or enumerable in the sense that there exists an onto map
$\mathbb{N}\twoheadrightarrow S$. This case distinction looks unsuitable for a
constructive definition. Following a quite established tradition (see for
instance [2]), we give the following (seemingly tricky but, as we will see,
definitely convenient) definition.

###### Definition 1

A set $S$ is _countable_ if there exists a sequence $\alpha:\mathbb{N}\to
S+\bot$ such that $S\subseteq\alpha[\mathbb{N}]$.222Equivalently, we could
require $\alpha$ to be surjective.

Here $\bot$ is the singleton set $\\{*\\}$, $S+\bot$ is the disjoint union (or
sum) of $S$ and $\bot$, and $\alpha[\mathbb{N}]$ is the image of $\mathbb{N}$
along $\alpha$. For the sake of notational simplicity, we do not distinguish
between an element of $S$ and its copy inside $S+\bot$. Otherwise, if we were
pedantic (and we are not), we should write $\forall a\in S.\exists
n\in\mathbb{N}.\alpha(n)=i(a)$ (where $i$ is the canonical injection of $S$
into $S+\bot$) instead of the more readable $S\subseteq\alpha[\mathbb{N}]$.

###### Remark 2

The term “Constructive Mathematics” refers, as it is well known, to a
“variety” rather than just one foundational theory. In this paper we adopt a
position which is as neutral as possible with respect to the different
foundational choices. Pragmatically, we shall try to provide definitions and
proofs in such a way that they remain valid and meaningful within virtually
any foundations. This automatically forces us to abandon the so-called Law of
Excluded Middle (LEM), the full Powerset Axiom (PA), and the full Axiom of
Choice (AC). On the contrary, we shall need the Axiom of Countable Choice
$AC_{\omega}$

$\forall n\in\mathbb{N}.\exists x\in
X.R(n,x)\Rightarrow\exists\alpha:\mathbb{N}\to X.\forall
n\in\mathbb{N}.R(n,\alpha(n))$

for every set $X$ and every relation $R\subseteq\mathbb{N}\times X$. If asked
for a concrete theory satisfying these features, we would suggest the
(extensional level of the) Minimalist Foundation [13, 14] augmented with
$AC_{\omega}$.

A subset $D\subseteq S$ is detachable if there exists an operation
$\chi_{D}:S\to 2$ (the characteristic function of $D$), where $2$ is the set
$\\{0,1\\}$ of Boolean values, such that $x\in D\Leftrightarrow\chi_{D}(x)=1$.

###### Proposition 3

A set $S$ is countable if and only if there exists a surjective map
$D\twoheadrightarrow S$ with $D$ a detachable subset of $\mathbb{N}$.

Proof Assume that $S$ is countable and that $\alpha:\mathbb{N}\to S+\bot$ is
the “evidence” of that (as required by the definition). Define $D$ =
$\\{n\in\mathbb{N}\ |\ \alpha(n)\in S\\}$, which is detachable (because one
can decide to which part of a disjoint union an element belongs). The
restriction of $\alpha$ to $D$ is a surjection onto $S$.

Vice versa, given $g:D\twoheadrightarrow S$, define $\alpha(n)$ as either
$g(n)$ or $*$ according to whether $n$ belong to $D$ or not (that is,
according to whether $\chi_{D}(n)$ is 1 or 0). $\square$

Such a characterization has in fact been taken as a definition in [3].
Classically, of course, every set of natural numbers is detachable and so the
previous proposition says just that $S$ is countable if and only if its
cardinality is not greater than $\aleph_{0}$.

Note that there seems to be no general way to decide whether a countable set
is inhabited or not. For instance, the set of even numbers greater than 4
which are not the sum of two odd primes is decidable, hence countable, but we
still do not know if it is empty.

###  1.1 The set of countable subsets

Given a set $S$, a subset $X\subseteq S$ is a countable set if and only if
there exists $\alpha:\mathbb{N}\to S+\bot$ such that
$X=S\cap\alpha[\mathbb{N}]$. We write $\mathcal{P}_{\omega_{1}}(S)$ for the
collection of all countable subsets of $S$. Clearly we have

$\mathcal{P}_{\omega_{1}}(S)\quad\cong\quad(S+\bot)^{\mathbb{N}}/\sim$

where $\alpha\sim\beta$ means $S\cap\alpha[\mathbb{N}]\ =\
S\cap\beta[\mathbb{N}]$. Hence $\mathcal{P}_{\omega_{1}}(S)$ is a set (it is a
quotient of a set).333On the contrary, we do not assume that $\mathcal{P}(S)$,
the collection of all subsets of $S$, is a set. Note that the set
$\mathcal{P}_{\omega}(S)$ of (Kuratowski-)finite subsets of $S$ [8] can be
identified with a subset of $\mathcal{P}_{\omega_{1}}(S)$.

###### Lemma 4

Every detachable subset of a countable set is countable.

Proof Let $\alpha:\mathbb{N}\to S+\bot$ be such that
$S\subseteq\alpha[\mathbb{N}]$, and let $X$ be a detachable subset of $S$.
Define $\beta:\mathbb{N}\to S+\bot$ as follows: put $\beta(n)=\alpha(n)$ if
$\alpha(n)\in X\subseteq S$, and put $\beta(n)=*$ otherwise. Clearly
$S\cap\beta[\mathbb{N}]=X$. $\square$

###### Proposition 5

For every set $S$, $\mathcal{P}_{\omega_{1}}(S)$ is closed under countable
unions.
Moreover, if the diagonal $\Delta\subseteq S\times S$ is detachable, then
$\mathcal{P}_{\omega_{1}}(S)$ is closed under binary intersections.

Proof Let $\\{X_{i}\ |\ i\in I\\}$ be a countable family of countable subsets
of $S$. So there exists $\alpha:\mathbb{N}\to I+\bot$ such that
$I\subseteq\alpha[\mathbb{N}]$. For each $i\in I$, we choose
$\beta_{i}:\mathbb{N}\to S+\bot$ such that $X_{i}=S\cap\beta_{i}[\mathbb{N}]$.
We want to check that $\bigcup_{i\in I}X_{i}$ is countable. Indeed, it is
enumerated by the map $\gamma:\mathbb{N}\to S+\bot$ defined as follows. First,
by means of a suitable (recursive) pairing function, we identify $\mathbb{N}$
with $\mathbb{N}\times\mathbb{N}$. Second, we define the image of the pair
$(n,m)$ to be $\beta_{\alpha(n)}(m)$ if $\alpha(n)\in I$, and $*$ otherwise.

As for the second part of the statement, note that
$\mathcal{P}_{\omega_{1}}(S)$ is closed under binary intersections if and only
if $\\{a\\}\cap\\{b\\}$ is countable for every $a,b\in S$. Indeed, given two
countable subsets $X_{i}=\\{a_{i,n}\ |\ n\in D_{i}\\}$, $i=1,2$, their
intersection $X_{1}\cap X_{2}$ can be written as the countable union
$\bigcup_{n\in D_{1}}\bigcup_{m\in D_{2}}(\\{a_{1,n}\\}\cap\\{a_{2,m}\\})$.
Now if $\Delta\subseteq S\times S$ is detachable, then
$\\{a\\}\cap\\{b\\}\subseteq S$ is detachable as well and hence it is
countable, by the previous lemma, as it is contained in the countable set
$\\{a\\}$. $\square$

The special case $\mathcal{P}_{\omega_{1}}(1)$, where $1=\\{0\\}$, is
sometimes written $\Sigma$; it is a subset of the collection $\Omega$ of all
truth values (that is, the collection $\mathcal{P}(1)$ of all subsets of $1$).
In fact, an element of $\Sigma$ can be identified with (the truth value of) a
proposition of the form $\exists n.[\alpha(n)=0]$, for some
$\alpha:\mathbb{N}\to 2=1+\bot$. So $\Sigma$ is precisely what is known as the
Rosolini dominance [15]; it is the set of “open” (or “semi-decidable”) truth
values in Synthetic Topology [2].444Classically, of course, $\Sigma$ = 2. Note
that this is already implied by the Limited Principle of Omniscience (LPO),
that is, the assertion $\forall f:\mathbb{N}\to 2.[\exists n.f(n)=0\vee\forall
n.f(n)=1]$. In our context, LPO implies $\forall p\in\Sigma.p\vee\neg p$ and
so it forces $\Sigma$ to contain precisely two values.

The second part of the previous proposition can be strengthened, as we are now
going to show. We say that a set $S$ has a semi-decidable equality if there
exists an operation $\psi:S\times S\to\Sigma$ such that
$a=b\Longleftrightarrow\psi(a,b)=1$.

###### Proposition 6

For every set $S$ the following are equivalent:

  1. 1.

$\mathcal{P}_{\omega_{1}}(S)$ is closed under binary intersections;

  2. 2.

equality in $S$ is semi-decidable.

Proof If $\mathcal{P}_{\omega_{1}}(S)$ is closed under binary intersections,
then we can define a map $\psi:S\times S\to\Sigma$ by putting
$\varphi(a,b)=\\{x\in 1\ |\ a=b\\}$. We claim that this is a countable subsets
of 1. By assumption there exists $D\twoheadrightarrow\\{a\\}\cap\\{b\\}$,
which we can compose with the obvious map from $\\{a\\}\cap\\{b\\}$ onto
$\\{x\in 1\ |\ a=b\\}$.555Given any set $S$, there exists precisely one map
from $S$ to the terminal set $1=\\{0\\}$. Such a map factorizes via its image,
which is just $\\{x\in 1\ |\ S\textrm{ is inhabited}\\}$.

Vice versa, given any $a,b\in S$, we have $\psi(a,b)\in\Sigma$ and so there
exists $f:\mathbb{N}\to 2$ such that $\psi(a,b)$ is the truth value of
$\exists n\in\mathbb{N}.f(n)=0$. We can use $f$ to define a map
$\alpha:\mathbb{N}\to S+\bot$ as follows: we put $\alpha(n)=a(=b)$ if $f(n)=0$
and $\alpha(n)=*$ otherwise. Clearly $S\cap\alpha[\mathbb{N}]$ =
$\\{a\\}\cap\\{b\\}$. $\square$

Finally, note that $\mathcal{P}_{\omega_{1}}(S)$ has a largest element if and
only if $S$ itself is countable.

##  2 $\sigma$-frames in Formal Topology

A suplattice is a partially ordered collection $(P,\leq)$ with all set-indexed
joins (hence a bottom element). A base for $P$ is a subset $S\subseteq P$ such
that, for every $p\in P$, (i) $\\{a\in S\ |\ a\leq p\\}$ is a set and (ii)
$p=\bigvee\\{a\in S\ |\ a\leq p\\}$. In that case, $(P,\leq,S)$ is called a
set-based suplattice.666A set-based suplattice has all set-indexed meets too
(hence a top element): $\bigwedge_{i\in I}p_{i}$ is just $\bigvee\\{a\in S\ |\
a\leq p_{i}\textrm{ for all }i\in I\\}$. All the information about
$(P,\leq,S)$ can be encoded as a pair $(S,\lhd)$ where $a\lhd U$ is
$a\leq\bigvee U$, for $a\in S$ and $U\subseteq S$. The structure $(S,\lhd)$ is
called a basic cover and it is characterized abstractly by the following two
properties: (i) $a\lhd U$ whenever $a\in U$, and (ii) if $a\lhd U$ and $u\lhd
V$ for all $u\in U$, then $a\lhd V$. Given $(S,\lhd)$, the suplattice $P$ can
be recovered (up to isomorphism) as a quotient $\mathcal{P}(S)/=_{\lhd}$,
where $U=_{\lhd}V$ means $\forall a\in S.(a\lhd U\Leftrightarrow a\lhd V)$. A
join $\bigvee_{i\in I}[U_{i}]$ in $\mathcal{P}(S)/=_{\lhd}$ is computed as
$[\bigcup_{i\in I}U_{i}]$; in particular, $[U]\leq[V]$ if and only if
$U\subseteq V$.

A frame is a suplattice with binary meets which distribute over joins. Set-
based frames correspond to a special class of basic covers called formal
covers. Actually there is a number of different ways to define explicitly the
notion of a formal cover [6]; in all cases, of course, the resulting category
is (dually) equivalent to that of set-based frames. Here we prefer the
following definition, which is motivated by the following clear fact: given a
set-based frame we can always construct another base which is closed under
finite meets.

###### Definition 7

A _formal cover_ is given by a basic cover $(S,\lhd)$ together with an inf-
semilattice structure $(S,\wedge,\top)$ such that

  1. 1.

$a\lhd\\{\top\\}$ and

  2. 2.

if $a\lhd U$, then $a\wedge b\lhd\\{u\wedge b\ |\ u\in U\\}$

for every $a,b\in S$ and $U\subseteq S$.

Given a formal cover, binary meets in the corresponding frame
$\mathcal{P}(S)/=_{\lhd}$ are computed as $[U]\wedge[V]$ = $[\\{u\wedge v\ |\
u\in U,\ v\in V\\}]$ in terms of the meet operation of $S$; moreover
$[\\{\top\\}]=[S]$ is the top element of the frame.

A $\sigma$-frame is a partial order with countable joins and finite meets, in
which binary meets distribute over countable joins. In this paper, we restrict
our attention to $\sigma$-frames whose carrier is a set. For instance,
$\mathcal{P}_{\omega_{1}}(S)$ is a $\sigma$-frame if $S$ has semi-decidable
equality (propositions 5 and 6) and if, at the same time, $S$ is countable. A
homomorphism of $\sigma$-frames is a map which preserves countable joins and
finite meets.

###### Proposition 8

Let $S$ be a countable set with a semi-decidable equality; then
$\mathcal{P}_{\omega_{1}}(S+1)$ is the free $\sigma$-frame over $S$.

Proof The mapping $a\mapsto\\{a\\}$ defines an injection
$i:S\hookrightarrow\mathcal{P}_{\omega_{1}}(S+1)$. Let $f:S\to L$ be any map
from $S$ to a $\sigma$-frame $L$. First, we extend $f$ to a map $g:S+1\to L$
by mapping the only element of 1 to the top element of $L$. We have to define
a $\sigma$-frame homomorphism $h:\mathcal{P}_{\omega_{1}}(S+1)\to L$ such that
$h\circ i=f$. Since a countable subset $\\{\alpha(d)\ |\ d\in D\\}\subseteq
S+1$ is the countable union of the singletons it contains, the only available
option is to put $h(\\{\alpha(d)\ |\ d\in D\\})$ = $\bigvee\\{g(\alpha(d))\ |\
d\in D\\}$. Checking that it works is routine. $\square$

So $\Sigma=\mathcal{P}_{\omega_{1}}(1)$ is the free $\sigma$-frame on no
generators and hence it is initial in the category of $\sigma$-frames.

###  2.1 $\sigma$-coherent formal topologies

Formal covers are a powerful tool, for instance when it comes to constructing
the free frame over a given $\sigma$-frame. This is done in the following
proposition.

###### Proposition 9

Let $L$ be a $\sigma$-frame. For $a\in L$ and $U\subseteq L$, let us write
$a\lhd_{L}U$ if $a\leq\bigvee W$ for some countable subset $W\subseteq L$.
Then $(L,\lhd_{L})$ is a formal cover and the corresponding frame is free over
$L$.

Proof Checking that $(L,\lhd_{L})$ is a formal cover is quite straightforward.
Just as an example, let us show that if $a\lhd_{L}U$ and $u\lhd_{L}V$ for all
$u\in U$, then $a\lhd_{L}V$. We have $a\leq\bigvee W$ for some countable
$W\subseteq U$ and, for each $u\in W$, we also have $u\leq\bigvee W_{u}$ for
some countable $W_{u}\subseteq V$. So $a\leq\bigvee W\leq\bigvee_{u\in
W}\bigvee W_{u}=\bigvee\bigcup_{u\in W}W_{u}$. Since $\bigcup_{u\in W}W_{u}$
is a countable subset of $V$, we can conclude that $a\lhd_{L}V$.

Let $P$ be the frame $\mathcal{P}(S)/=_{\lhd_{L}}$ and let $m:L\to P$ be the
$\sigma$-frame homomorphism (as is is easy to check) given by
$m(a)=[\\{a\\}]$. Given any $\sigma$-frame homomorphism $f:L\to Q$ from $L$ to
a frame $Q$, we must construct a frame homomorphism $h:P\to Q$ such that
$h\circ m=f$. So $h([U])$ = $h(\bigvee_{a\in U}[\\{a\\}])$ must be equal to
$\bigvee_{a\in U}h([\\{a\\}])$ = $\bigvee_{a\in U}h(m(a))$ = $\bigvee_{a\in
U}f(a)$. If we take this as the definition of $h$, then everything that is to
be checked becomes straightforward. As an example, we here show that $h$ is
well-defined. Let $[U]=[V]\in P$; we claim that $f(u)\leq\bigvee_{v\in V}f(v)$
for every $u\in U$. Since $u\lhd_{L}U$, then also $u\lhd_{L}V$, that is,
$u\leq\bigvee W$ for some countable $W\subseteq V$. So $f(u)\leq\bigvee_{v\in
W}f(v)\leq\bigvee_{v\in V}f(v)$. $\square$

The frame presented by $(L,\lhd_{L})$ is called the frame envelope of $L$ in
[1]. Some results about the frame envelope become strikingly straightforward
in the language of formal topology. For instance, the statement that if $L$ is
compact, then so is its envelope [1] can be proved as follows. Assume
$\top\lhd_{L}U$, that is, $\top\leq\bigvee W$ for some countable $W\subseteq
U$. By compactness of $L$, there is a (Kuratowski-)finite $K\subseteq
W\subseteq U$ such that $\top\leq\bigvee K$. So $\top\lhd_{L}K$ and hence
$(L,\lhd_{L})$ is compact.

Free frames over the category of $\sigma$-frames, as constructed in the
previous proposition, can be characterized explicitly as follows.

Given a frame $P$, say that $a\in P$ is Lindelöf [1] if

$a\leq\bigvee X\quad\Longrightarrow\quad a\leq\bigvee W\textrm{ for some
countable }W\subseteq X$ (1)

for all $X\subseteq P$. Lindelöf elements are closed under countable joins,
but not under finite meets, in general.

A frame $P$ is called $\sigma$-coherent [12] if

  1. 1.

its Lindelöf elements are closed under finite meets (hence they form a
$\sigma$-frame), and

  2. 2.

every element of $P$ is a (not necessarily countable) join of Lindelöf
elements.

In particular, the set $L$ of Lindelöf elements of a $\sigma$-coherent frame
$P$ is a base for $P$. Therefore $P$ can be presented as a formal cover
$(L,\lhd)$ where, as usual, $a\lhd U$ means $a\leq\bigvee U$. However, since
$a\in L$ is Lindelöf, $a\lhd U$ happens precisely when $a\leq\bigvee W$ for
some countable $W\subseteq U$. In other words, $\lhd$ is just $\lhd_{L}$ as
defined in the previous proposition. This immediately gives the following
result.

###### Proposition 10

For a frame $P$, the following are equivalent:

  1. 1.

$P$ is $\sigma$-coherent;

  2. 2.

$P$ is the frame envelope $(L,\lhd_{L})$ of some $\sigma$-frame $L$ (in which
case $L$ is the $\sigma$-frame of Lindelöf elements of $P$);

  3. 3.

$P$ is free over the category of $\sigma$-frames.

Formal covers of the form $(L,\lhd_{L})$ are characterized, up to isomorphism,
as those formal covers $(S,\lhd)$ which satisfy

$a\lhd U\quad\Longrightarrow\quad a\lhd W\textrm{ for some countable subset
}W\subseteq U$ (2)

for every $a\in S$ and $U\subseteq S$. This is a corollary of the following
proposition.

###### Proposition 11

If $(S,\lhd)$ is a formal cover satisfying (2), then its corresponding frame
is $\sigma$-coherent.

Proof Condition (2) means that $[\\{a\\}]$ is Lindelöf for every $a\in S$.
Moreover, an element $[U]$ is Lindelöf (if and) only if $[U]$ = $[W]$ for some
countable $W$. Indeed, from $[U]$ = $\bigvee_{a\in U}[\\{a\\}]$ one gets $[U]$
= $\bigvee_{a\in W}[\\{a\\}]$ for some countable $W\subseteq U$. So the
collection of Lindelöf elements can be identified with the set
$\mathcal{P}_{\omega_{1}}(S)/=_{\lhd}$.777Note that we are not assuming that
$S$ is countable with semi-decidability equality here, so
$\mathcal{P}_{\omega_{1}}(S)$ need not be closed under finite intersections.
If $W_{1}$ and $W_{2}$ are countable, then $\\{w_{1}\wedge w_{2}\ |\ w_{1}\in
W_{1},\ w_{2}\in W_{2}\\}$ is countable too (by pairing), so that Lindelöf
elements are closed under binary meets. $\square$

In view of this fact, we are justified to use the name $\sigma$-coherent
covers for those covers which satisfy (2).

###  2.2 $\sigma$-frames

The previous results show that a $\sigma$-coherent frame is essentially the
same thing as a $\sigma$-frame (namely the $\sigma$-frame of its Lindelöf
elements). This suggests to present the category of $\sigma$-frames as a (non
full) subcategory of the category of frames. In order to do that we have to
consider only those frame homomorphisms which preserve Lindelöf elements (by
freeness, every $\sigma$-frame homomorphism is the restriction of some
particular frame homomorphism between the corresponding envelopes).

In terms of $\sigma$-coherent covers, an arrow
$h:(S_{1},\lhd_{1})\to(S_{2},\lhd_{2})$ represents a $\sigma$-frame
homomorphism between $\mathcal{P}_{\omega_{1}}(S_{1})/=_{\lhd_{1}}$ and
$\mathcal{P}_{\omega_{1}}(S_{2})/=_{\lhd_{2}}$ if, for every $a\in S_{1}$,
$h([\\{a\\}])=[W]$ for some countable $W\subseteq S_{2}$. A convenient way to
present an arrow of this sort is to give a mapping
$S_{1}\to\mathcal{P}_{\omega_{1}}(S_{2})$, that is, a binary relation
$R\subseteq S_{1}\times S_{2}$ such that $\\{a_{2}\in S_{2}\ |\
R(a_{1},a_{2})\\}$ is countable for every $a_{1}\in S_{1}$.

###### Remark 12

There are several important cases in which a formal cover is inductively
generated (according to some general method as describe in [9, 6]). Although
we are not going to give all details, the idea is to construct $\lhd$ as the
smallest (basic) cover which satisfies some set of “axioms” of the form $a\lhd
C(a,i)$, for $a\in S$ and $i$ in a given set $I(a)$.888When $S$ has an inf-
semilattice structure, one can always assume, without loss of generality, that
both $a\lhd\\{\top\\}$ and all $a\wedge b\lhd\\{a\\}$ are among the axioms,
and that $a\wedge b\lhd\\{u\wedge b\ |\ u\in U\\}$ is an axiom whenever $a\lhd
U$ is an axiom. If all $C(a,i)$’s are countable subsets of $S$, then the
generated cover is $\sigma$-coherent: the proof is by induction on the
generation of the cover, of course, and requires $AC_{\omega}$. Many important
examples of generated covers share this property, such as (the pointfree
versions of) the Cantor space, the Baire space, and the (Dedekind) reals.

##  3 Booleanization

A congruence $\sim$ on a $\sigma$-frame $L$ is an equivalence relation which
is compatible with finite meets and countable joins; this says that $L/\sim$
is a $\sigma$-frame as well. From the “dual” point of view of locale theory
[10], $L/\sim$ is a $\sigma$-sublocale of $L$.

By extending the terminology of locale theory to $\sigma$-locales, we say that
$L/\sim$ is a dense $\sigma$-sublocale of $L$ when $\forall x\in L.(x\sim
0\Rightarrow x=0)$. Every $\sigma$-locale $L$ has a smallest dense
$\sigma$-sublocale (see _d-reduced_ $\sigma$-frames in [12]), which
corresponds to the congruence $a\sim b$ defined by $\forall x\in L.(a\wedge
x=0\Leftrightarrow b\wedge x=0)$.

###  3.1 Overlap algebras

It can be argued that complete Boolean algebras loose some of their important
features when LEM is not assumed. For instance, discrete locales, that is,
frames of the form $\mathcal{P}(S)$ for some set $S$, are never Boolean, apart
from the trivial case $S=\emptyset$. Moreover, non-trivial Boolean locales are
never overt.

Recall that a formal cover $(S,\lhd)$ is overt if there is a predicate
$Pos(x)$ on $S$ (the positivity predicate) such that:

  1. 1.

if $a\lhd U$ and $Pos(a)$, then $Pos(b)$ for some $b\in U$;

  2. 2.

$a\lhd\\{x\in\\{a\\}\ |\ Pos(x)\\}$ for every $a\in S$.

The idea is that $Pos(a)$ is a positive way to say that $a$ is not the bottom
element.

###### Definition 13

An overlap algebra [16, 5] is (the frame corresponding to) an overt cover
$(S,\lhd,Pos)$ such that

$\forall b\in S.[Pos(a\wedge b)\Rightarrow\exists u\in U.Pos(u\wedge
b)]\Longrightarrow a\lhd U$ (3)

for every $a\in S$ and $U\subseteq S$.

Discrete covers $(S,\in)$ are example of overlap algebras. Moreover, the
smallest strongly dense sublocale [11] of an overt locale is an overlap
algebra [4]. Classically, overlap algebras are precisely the Boolean locales
(that is, the complete Boolean algebras) [7].

A similar approach applies to $\sigma$-locales, as we now see. We call a
$\sigma$-locale $L$ overt if its envelope $(L,\lhd_{L})$ is overt.999It is
well known that for an overt $(S,\lhd)$ the predicate $Pos(a)$ becomes
equivalent to the “impredicative” formula $\forall U\subseteq S.(a\lhd
U\Rightarrow U\textrm{ is inhabited})$. When $(S,\lhd)$ is $\sigma$-coherent,
that formula can be replaced by $\forall
W\in\mathcal{P}_{\omega_{1}}(S).(a\lhd W\Rightarrow W\textrm{ is inhabited})$.
Explicitly, $L$ is overt if and only if there is a predicate $Pos(x)$ on $L$
such that:

  1. 1.

if $a\leq b$ and $Pos(a)$, then $Pos(b)$;

  2. 2.

if $Pos(\bigvee W)$ for some countable $W$, then $Pos(a)$ for some $a\in W$;

  3. 3.

for every $a$ there is a countable $W\subseteq\\{a\\}$ such that $a=\bigvee W$
and $Pos(b)$ for all $b\in W$.

Note that $\neg Pos(a)$ is (intuitionistically) equivalent to $a=0$.
Classically, therefore, $Pos(a)$ means just $a\neq 0$; note that, in that
case, the three conditions above are always true ($3.$, for instance, says
that either $a=0$ or $a\neq 0$).

###### Definition 14

A $\sigma$-overlap algebra is an overt $\sigma$-frame such that

$\forall z.[Pos(x\wedge z)\Rightarrow Pos(y\wedge z)]\Longrightarrow x\leq y\
.$ (4)

Classically $\sigma$-overlap algebras are precisely the d-reduced
$\sigma$-frames of [12]. Finding examples of $\sigma$-overlap algebras is an
easy task, thanks to the following construction.

###### Proposition 15

Given any overt $\sigma$-locale $L$, the formula

$\forall z\in L.[Pos(x\wedge z)\Leftrightarrow Pos(y\wedge z)]$ (5)

defines a congruence on $L$. The corresponding $\sigma$-sublocale of $L$, say
$B(L)$, is a $\sigma$-overlap algebra.

Proof Checking that (5) defines a congruence is quite straightforward. As an
example, let us check that it is compatible with binary meets. If $\forall
z[Pos(x_{1}\wedge z)\Leftrightarrow Pos(y_{1}\wedge z)]$ and $\forall
z[Pos(x_{2}\wedge z)\Leftrightarrow Pos(y_{2}\wedge z)]$, then
$Pos(x_{1}\wedge x_{2}\wedge z)$ $\Leftrightarrow$ $Pos(y_{1}\wedge
x_{2}\wedge z)$ $\Leftrightarrow$ $Pos(y_{1}\wedge y_{2}\wedge z)$ for all
$z$.

To show that $B(L)$ is a $\sigma$-overlap algebra we must first of all check
that it is overt. This is easy because $Pos$ respects the congruence (5) and
so it makes sense to say that $[x]$ is positive in $B(L)$ if $x$ is positive
in $L$. Finally, if $x$ and $y$ are such that $Pos(x\wedge z)\Rightarrow
Pos(y\wedge z)$ for all $z$, then also $Pos(x\wedge x\wedge z)\Rightarrow
Pos(y\wedge x\wedge z)$ for all $z$, and hence $\forall z.[Pos(x\wedge
z)\Leftrightarrow Pos(y\wedge x\wedge z)]$. So $x$ and $y\wedge x$ are
congruent, that is, $x\leq y$ in $B(L)$. $\square$

The $\sigma$-sublocale $B(L)$ is always dense in $L$. Indeed, if $\forall
z[Pos(a\wedge z)\Leftrightarrow Pos(0\wedge z)]$, then $\forall z.\neg
Pos(a\wedge z)$ because $Pos(0)=Pos(\emptyset)$ cannot hold. In particular,
$\neg Pos(a)$ and so $a=0$.

Actually, $B(L)$ is dense in the following (stronger) sense. We say that
$L/\sim$ is strongly dense in $L$ if $Pos(a)$ implies $Pos(b)$ whenever $a\sim
b$.

###### Proposition 16

For $L$ any overt $\sigma$-locale, $B(L)$ is the smallest strongly-dense
$\sigma$-sublocale of $L$.

Proof Let $L/\sim$ be strongly dense. If $x\sim y$, then $(x\wedge
z)\sim(y\wedge z)$ because $\sim$ is a congruence; hence $Pos(x\wedge
z)\Leftrightarrow Pos(y\wedge z)$ by strong density. This means that $B(L)$ is
$\sigma$-sublocale of $L/\sim$. $\square$

## References

  * [1] Banaschewski B., _The frame envelope of a $\sigma$-frame_, Quaestiones Mathematicae (1993).
  * [2] Bauer A. and Lešnik D., _Metric Spaces in Synthetic Topology_ , Ann. Pure Appl. Logic 163 (2012), pp. 87-100.
  * [3] Bridges D. and Richman F., _Varieties of Constructive mathematics_ , Cambridge University Press, 1987.
  * [4] Ciraulo F., _Overlap Algebras as Almost Discrete Locales_ , arXiv:1601.04830 [math.LO] (2016).
  * [5] Ciraulo F., _Regular opens in Formal Topology and a representation theorem for overlap algebras_ , Ann. Pure Appl. Logic 164 (2013), pp. 421-436.
  * [6] Ciraulo F. and Maietti M. E. and Sambin G., _Convergence in Formal Topology: a unifying notion_ , Journal of Logic and Analysis 5 (2013), pp. 1-45.
  * [7] Ciraulo F. and Sambin G., _The overlap algebra of regular opens_ , J. Pure Appl. Algebra 214 (2010), pp. 1988-1995.
  * [8] Ciraulo F. and Sambin G., _Finiteness in a Minimalist Foundation_ , Lect. Notes Comput. Sc. 4941 (2008), pp. 51–68.
  * [9] Coquand T. and Sambin G. and Smith J. and Valentini S., _Inductively generated formal topologies_ , Ann. Pure Appl. Logic 124 (2003), pp. 71-106.
  * [10] Johnstone P. T., _Stone spaces_ , Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1986.
  * [11] Johnstone P. T., _A constructive “Closed subgroup theorem” for localic groups and groupoids_ , Cahiers Topologie Géom. Différentielle Catég. 30 (1989), pp. 3-23.
  * [12] Madden J. J., _$k$ -frames_, J. Pure Appl. Algebra 70 (1991), pp. 107-127.
  * [13] Maietti M. E., _A minimalist two-level foundation for constructive mathematics_ , Ann. Pure Appl. Logic 160 (2009), pp. 319-354.
  * [14] Maietti M. E. and Sambin G., _Toward a minimalist foundation for constructive mathematics_ , in _From Sets and Types to Topology and Analysis: Practicable Foundations for Constructive Mathematics_ , Crosilla L. and Schuster P. (eds.), Oxford University Press, 2005.
  * [15] Rosolini G., _Continuity and Effectiveness in Topoi_ , PhD thesis, University of Oxford, 1986.
  * [16] Sambin G., _Positive Topology and the Basic Picture. New structures emerging from constructive mathematics_ , Clarendon Press, Oxford, to appear.
  * [17] Simpson A., _Measure, randomness and sublocales_ , Ann. Pure Appl. Logic 163 (2012), pp. 1642-1659.