1. Dedications to Phil Scott

We would like to dedicate this paper to Phil Scott (1947–2023).

From Robin: I have so many memories of time spent with Phil that it is hard to know where to start. In the early 1990s, Phil was instrumental in getting me an introduction at the University of Calgary and whence the job I have enjoyed since then. Even back then – in fact, maybe, especially back then – Phil was highly influential and respected. The book with Lambek, “Introduction to higher order categorical logic,” had truly changed the categorical world.

Phil loved visiting Edinburgh, and in 2018 he conspire to have us spend sabbatical time there together. My wife, Polly, and I had long wanted to hike the West Highland Way (which starts near Glasgow). Doing this before our Edinburgh sojourn seemed like a perfect moment. I was therefore to meet my wife, who would be returning from adventures further north, at the start of the hike. Somehow, I needed to leave, in Edinburgh as I passed through on trains from Oxford, a bag of stuff not needed on the hike. Phil concocted a simple logistical plan: as he would already be in Edinburgh, he would meet my midday train at the Edinburgh railway station: I would hand-off my bag to him and hop back on the train to Glasgow.

Well, of course, everything went wrong. The night before the line to Edinburgh from England had been subject to major tree falls due to a storm. When a train finally got through – in the late evening – it was packed with unhappy passengers standing like sardines in the aisles. As Phil did not believe in cell phones, there was no way to let him know how badly delayed I was. When the train finally arrived at Edinburgh the passengers literally poured onto the platform. This included me with a huge suitcase (on wheels) which I had been supposed to hand-off over six hours earlier. I had no idea what I was now going to do with the bag!!

Imagine, however, my disbelief as clinging to the hand-rail at the bottom of the exit stairway, being rudely buffeted by the frustrated crowd pouring forth from the train, stood Phil and his wife Marcia. Relief hardly does justice to my reaction. Unbelievably they had waited for over six hours for a train to get through!

The hand-off went smoothly … and the sabbatical was a special and memorable one!

Phil was hugely generous (and reliable!) … and a friend I sorely miss.

From JS: Phil was both a friend and a mentor. Phil was an important figure in the early stages of my academic studies and had quite an impact on the direction of my research interests. Phil was my first math professor in undergrad at the University of Ottawa: he was the one who taught me how to do proper proofs. I took many classes from him in undergrad, and Phil quickly became my favorite lecturer. Near the end of undergrad when I was trying to decide what area of research to study, Phil was the one who first mentioned category theory to me by introducing me to star-autonomous categories and Linear Logic. I credit Phil for why and how I became a category theorist. After my time at the University of Ottawa, Phil continued to be a mentor: he was always very supportive and happy to discuss my latest research interests or new results. But more importantly, Phil became a friend. We would often catch up at conferences or whenever I was passing through Ottawa again. We also both visited Edinburgh at the same time and often went on hikes together. Phil’s passing is a great loss for many communities, including the Canadian mathematics community and the category theory community. Phil was incredibly kind, a fantastic mentor, and a great friend to many of us. Condolences to his loved ones. May he rest in peace.

3. Restriction Categories

In this background section, we review restriction categories and the necessary basic theory for the story of this paper such as restriction idempotents, the canonical partial order on maps, and restriction zero maps, as well as some main examples. For a more in-depth introduction to restriction categories, we invite the reader to see (Cockett and Lack Reference Cockett and Lack2002, Reference Cockett and Lack2003, Reference Cockett and Lack2007), (Cockett and Manes Reference Cockett and Manes2009), and Cockett and Garner (Reference Cockett and Garner2014).

Definition 1. For a category $\mathbb{X}$ , a restriction operator $\overline{(\phantom{f})}$ (Cockett and Lack Reference Cockett and Lack2002, Section 2.1.1) is a family of operators:

such that the following four axioms hold:

• [R.1] $\overline{f}f = f$ , for all $f: A \to B$ ;

• [R.2] $\overline{f} \overline{g} = \overline{g} \overline{f}$ , for all $f: A \to B$ and $g: A \to C$ ;

• [R.3] $\overline{\overline{g}f} = \overline{g} \overline{f}$ , for all $f: A \to B$ and $g: A \to C$ ;

• [R.4] $f\overline{g} = \overline{fg} f$ , for all $f: A \to B$ and $g: B \to C$ .

For a map $f: A \to B$ , the map ${\overline{f}: A \to A}$ is called the restriction of f. A restriction category is a category equipped with a restriction operator. Furthermore, in a restriction category:

1. (i) A total map (Cockett and Lack Reference Cockett and Lack2002, Section 2.1.2) is a map ${f: A \to B}$ such that $\overline{f} = 1_A$ ;

2. (ii) For parallel maps $f: A \to B$ and $g: A \to B$ , we say that $f \leq g$ if $\overline{f}g= f$ (Cockett and Lack Reference Cockett and Lack2002, Section 2.1.4;)

3. (iii) A restriction idempotent (Cockett and Lack Reference Cockett and Lack2002, Section 2.3.3) is a map $e: A \to A$ such that $\overline{e} = e$ . For every object $A \in \mathbb{X}$ , we denote by $\mathcal{O}(A)$ the set of restriction idempotents of type $A \to A$ .

The main intuition for a restriction category is that maps f are partial and the restriction $\overline{f}$ captures the domain of definition of f. As we will see in Example 3.1, the standard intuition for $\overline{f}$ is checking if $x \in A$ is in the domain of f or not, that is, $\overline{f}(x)=x$ when f(x) is defined and $\overline{f}(x)$ is undefined when f(x) is undefined. Thus, total maps are interpreted as maps which are everywhere defined.

The intuition for the partial order $\leq$ is that $f \leq g$ means whenever f is defined, g is also defined and is equal to f. Moreover, this partial order enriches every restriction category $\mathbb{X}$ over posets. Thus, each homset $(\mathbb{X}(A,B), \leq)$ is a poset and composition is monotone, that is, if $f \leq g$ then for suitable maps h and k, $h f k \leq h g k$ . Also observe that $f \leq g$ implies that $\overline{f} \leq \overline{g}$ (though the converse is not necessarily true).

Restriction idempotents correspond to the domain of definition of maps, and thus $\mathcal{O}(A)$ may be interpreted as certain special subsets of the object A. The name restriction idempotent is justified since a restriction idempotent e is indeed idempotent, $e e= e$ . In particular, every restriction $\overline{f}$ is a restriction idempotent, so we have $\overline{\overline{f}} = \overline{f}$ and $\overline{f}\,\overline{f}=\overline{f}$ . Furthermore, $\mathcal{O}(A)$ has a natural bounded meet-semilattice structure, where the meet is given by composition, $e_0 \wedge e_1 = e_0 e_1$ , and the top element is the identity $1_A$ . The induced partial order on $\mathcal{O}(A)$ on this lattice structure is the same as the restriction order. Thus, for restriction idempotents, $e_0 \leq e_1$ if and only if $e_0 e_1 = e_0$ , and also $e \leq 1_A$ .

A key notion for the story of this paper is restriction zero maps: these are intuitively maps which are nowhere defined. Categorically speaking, a restriction zero map is a zero map in the usual sense whose restriction is also a zero map. Recall a category has zero maps if for every pair of objects A and B there is a map $0: A \to B$ which satisfies the annihilation property, that is, $f0=0=0f$ for all maps f.

Observe that for any map f, $0 \leq f$ . Thus, restriction zero maps are the bottom elements for each homset. Moreover, the restriction zero map of type $0: A \to A$ is a restriction idempotent, and is, therefore, the bottom element of $\mathcal{O}(A)$ .

We conclude this background section by providing two running examples of restriction categories. For a list of many other examples of restriction categories, see (Cockett and Lack Reference Cockett and Lack2002, Section 2.1.3).

Example 3.1. Let $\mathsf{PAR}$ be the category whose objects are sets and whose maps are partial functions between sets. Then $\mathsf{PAR}$ is a restriction category (Cockett and Lack Reference Cockett and Lack2002, Example 2.1.3.1) where the restriction of a partial function $f: X \to Y$ is the partial function ${\overline{f}: X \to X}$ defined as follows:

\[ \overline{f}(x) = \begin{cases} x & \text{if }\, f(x) \downarrow \\\uparrow & \text{if } \,f(x) \uparrow \end{cases} \]

where $\downarrow$ means defined and $\uparrow$ means undefined. The total maps in $\mathsf{PAR}$ are precisely the functions that are everywhere defined – thus the subcategory of total maps of $\mathsf{PAR}$ is simply the category of sets and functions. For partial functions $f: X \to Y$ and $g: X \to Y$ , we have that $f \leq g$ if $g(x)=f(x)$ whenever $f(x) \downarrow$ . The restriction idempotents for a set X are in bijective correspondence to subsets of X Cockett et al. (2012b, Example 2.2.1). In particular, for every subset $U \subseteq X$ , define the partial function $e_U : X \to X$ as follows:

\begin{align*} e_U(x) \colon = \begin{cases} x & \text{ if } x \in U \\ \uparrow & \text{ if } x \notin U \end{cases} \end{align*}

Then clearly $\overline{e_U} = e_U$ , so $e_U$ is a restriction idempotent, and every restriction idempotent is of this form. In particular, note that $\overline{f} = e_{\mathsf{dom}(f)}$ . So $\mathcal{O}(X)$ is isomorphic to the powerset $\mathcal{P}(X)$ of X, $\mathcal{O}(X) \cong \mathcal{P}(X)$ . Lastly, $\mathsf{PAR}$ has restriction zero maps where $0: X \to Y$ is the partial function which is nowhere defined, that is, $0(x) \uparrow$ for all $x \in X$ .

4. Interference

In this section, we introduce the concept of an interference relation, which is a relation on maps of restriction category with restriction zeroes which tells us when two maps that have the same domain should be viewed as being formally disjoint. Formal disjointness must certainly imply that where one map is defined, the other is undefined, but could possibly also ask for more. This concept of disjointness plays key a role in the definition of an iteration operator, since in particular it is used to determine the termination condition of iterations.

[⊥.0] Zero: $1_A \perp 0$ ;

[⊥.1] Symmetry: If $f \perp g$ , then $g \perp f$ ;

[⊥.2] Anti-reflexive: If $f \perp f$ , then $f = 0$ ;

[⊥.3] Downward closed: If $f^\prime \perp g^\prime$ , $f \leq f^\prime$ , and $g \leq g^\prime$ , then $f \perp g$ ;

[⊥.4] Composition: If $f \perp g$ , then for all suitable maps h, k, and $k^\prime$ , we have that $hfk \perp hgk^\prime$ ;

[⊥.5] Restriction: If $f \perp g$ , then $\overline{f} \perp \overline{g}$ .

It turns out that for an interference relation $\perp$ , maps are $\perp$ -disjoint if and only if their restrictions are $\perp$ -disjoint. As such this implies that an interference relation induces a restrictional coherence (Cockett and Manes Reference Cockett and Manes2009, Definition 6.1) on parallel maps.

Thus, an interference relation is completely determined by its behavior on restriction idempotents. This means that an interference relation can equivalently be defined as a family of relations on restriction idempotents.

[ $\mathcal{O}\!\boldsymbol{\perp}$ .0] Zero: $1_A \perp 0$ ;

[ $\mathcal{O}\!\boldsymbol{\perp}$ .1] Symmetry: If $e \perp e^\prime$ , then $e^\prime \perp e$ ;

[ $\mathcal{O}\!\boldsymbol{\perp}$ .2] Anti-Reflexive: If $e \perp e$ , then $e = 0$ ;

[ $\mathcal{O}\!\boldsymbol{\perp}$ .3] Downward Closed: If $e^\prime_1 \perp e^\prime_2$ , $e_1 \leq e^\prime_1$ , and $e_2 \leq e_2^\prime$ , then $e_1 \perp e_2$ ;

[ $\mathcal{O}\!\boldsymbol{\perp}$ .4] Pre-Composition: If $e \perp e^\prime$ in $\mathcal{O}(A)$ , then for any h with codomain A, $\overline{he} \perp \overline{he^\prime}$ .

Conversely, starting with a restrictional interference relation $\perp^\mathcal{O}$ , we need to show that $\perp$ satisfies the six axioms [ $\boldsymbol{\perp}$ .0] to [ $\boldsymbol{\perp}$ .5].

[⊥.0] By [ $\mathcal{O}\!\boldsymbol{\perp}$ .0], $1_A \perp^\mathcal{O} 0$ . However, since $1_A$ and 0 are both restriction idempotents, we also have that $\overline{1_A} \perp^\mathcal{O} \overline{0}$ , which tells us that $1_A \perp 0$ .

[⊥.1] Suppose that $f \perp g$ , meaning $\overline{f} \perp^\mathcal{O} \overline{g}$ . By [ $\mathcal{O}\!\boldsymbol{\perp}$ .1], this means that $\overline{g} \perp^\mathcal{O} \overline{f}$ , so we have that $g \perp f$ .

[⊥.2] Suppose that $f \perp f$ , that is $\overline{f} \perp^\mathcal{O} \overline{f}$ . By [ $\mathcal{O}\!\boldsymbol{\perp}$ .2], this means that $\overline{f}=0$ . However, by [R.1], $\overline{f}=0$ implies that $f=0$ .

[⊥.3] Suppose that $f^\prime \perp g^\prime$ , meaning $\overline{f^\prime} \perp^\mathcal{O} \overline{g^\prime}$ , and that $f \leq f^\prime$ and $g \leq g^\prime$ . This implies that $\overline{f} \leq \overline{f^\prime}$ and $\overline{g} \leq \overline{g^\prime}$ as well. So by [ $\mathcal{O}\!\boldsymbol{\perp}$ .3], we have that $\overline{f} \perp^\mathcal{O} \overline{g}$ , and so $f \perp g$ .

[⊥.4] First recall that in a restriction category, we have the identity $\overline{fg} = \overline{f \overline{g}}$ (Cockett and Lack Reference Cockett and Lack2002, Lemma 2.1.(iii)). Now suppose that $f \perp g$ , meaning $\overline{f} \perp^\mathcal{O} \overline{g}$ . Then for any suitable h, by [ $\mathcal{O}\!\boldsymbol{\perp}$ .4] we have that $\overline{h\overline{f}} \perp^\mathcal{O} \overline{h\overline{g}}$ . However, by the previous mentioned identity, we may rewrite this as $\overline{hf} \perp^\mathcal{O} \overline{hg}$ . Now observe that for any suitable k and $k^\prime$ , $\overline{hfk} \leq \overline{hf}$ and $\overline{hgk^\prime} \leq \overline{hg}$ . Then by [ $\mathcal{O}\!\boldsymbol{\perp}$ .3], we have that $\overline{hfk} \perp^\mathcal{O} \overline{hgk^\prime}$ . As such, we have that $hfk \perp hgk^\prime$ .

[⊥.5] Suppose that $f \perp g$ , meaning $\overline{f} \perp^\mathcal{O} \overline{g}$ . However, since $\overline{f}$ and $\overline{g}$ are restriction idempotents, we can rewrite this as $\overline{\overline{f}}\perp^\mathcal{O} \overline{\overline{g}}$ , meaning that $\overline{f} \perp \overline{g}$ .

So $\perp$ is indeed an interference relation on maps.

It remains to explain why these constructions are inverses of each other. Clearly, starting with a restrictional interference relation $\perp^\mathcal{O}$ , building its associated interference relation on maps, $\perp = \{ (f,g) \vert\, \overline{f} \perp^\mathcal{O} \overline{g} \}$ and then taking the induced restrictional interference relation, $\{ (\overline{f},\overline{g}) \vert\, f \perp g \}$ gives us back the starting restrictional interference relation $\perp^\mathcal{O}$ . Conversely, starting with an interference relation on maps $\perp$ , building its associated restrictional interference relation $\perp^\mathcal{O}$ , and then taking the induced interference relation on maps results back to $\perp$ by Lemma 4.

From now on, we will make no distinction between an interference relation and its corresponding restrictional interference relation and shall denote them both by $\perp$ . Here are some other basic yet important properties of interference relations:

1. (i) For all maps f, $f \perp 0$ ;

2. (ii) If $f \perp g$ , then $\overline{f}g=0$ , $\overline{g}f=0$ , and $\overline{f}\,\overline{g} = 0$ ;

3. (iii) If f is total, then $f \perp g$ if and only if $g=0$ .

4. (iv) If e is a restriction idempotent, then $e \perp f$ if and only if $e \perp \overline{f}$ .

5. (v) If $f \perp g$ , then $f \perp \overline{g}$ and $\overline{f} \perp g$ .

In particular notice that Lemma 7(ii) says that if maps are $\perp$ -disjoint, then they are disjoint in the usual restriction category sense (Cockett and Manes Reference Cockett and Manes2009, Proposition 6.2).

1. (i) By [<texmath>inline330</texmath>.0], $1_A \perp 0$ . Using [ $\boldsymbol{\perp}$ .4], pre-composing both sides by f, we get that $f \perp 0$ .

2. (ii) First note that $\overline{f}g=0$ , $\overline{g}f=0$ , and $\overline{f}\,\overline{g} = 0$ are all equivalent conditions (Cockett and Manes Reference Cockett and Manes2009, Proposition 6.2). So suppose that $f \perp g$ . We will show that $\overline{f}\overline{g} = 0$ from the anti-reflexivity of $\perp$ . So first if $f \perp g$ , then by [ $\boldsymbol{\perp}$ .5], $\overline{f} \perp \overline{g}$ . Now note that $\overline{f}\,\overline{g\,} \overline{f} = \overline{f}\,\overline{g}$ and $\overline{f}\,\overline{g}\, \overline{g} = \overline{f}\,\overline{g}$ . So by [ $\boldsymbol{\perp}$ .4], pre-composing both sides by $\overline{f}\,\overline{g}$ we get that $\overline{f}\,\overline{g} \perp \overline{f}\,\overline{g}$ . Then [<texmath>inline348</texmath>.2] implies that $\overline{f}\,\overline{g} = 0$ .

3. (iii) The $\Leftarrow$ direction is simply [ $\boldsymbol{\perp}$ .0]. So for the $\Rightarrow$ direction, suppose that f is total and that $f \perp g$ . Then by (ii), we have that $\overline{f}g = 0$ . However since f is total, $\overline{f}=1$ . So we have that $g=0$ .

4. (iv) This follows immediately from Lemma 4.

5. (v) This follows from (iv) and [ $\boldsymbol{\perp}$ .5].

A restriction category with restriction zeroes can have multiple different interference relations. In fact, there are always at least two possible ones: a minimal one $\perp_\delta$ and a maximal one $\perp_0$ (with respect to the usual ordering of relations). The minimal interference relation $\perp_\delta$ is the relation which only relates maps to zero, that is, $f \perp_\delta g$ if and only if $f=0$ or $g=0$ . On the other hand, the maximal interference relation $\perp_0$ is the relation which says that two maps are disjoint if, whenever one is defined, the other is not. Thus, $f \perp_0 g$ if and only if $\overline{f}g =0$ (equivalently $\overline{g}f = 0$ ) or, in other words, they are disjoint in the sense of (Cockett and Manes Reference Cockett and Manes2009, Proposition 6.2).

1. (i) $\perp_0$ is an interference relation with its associated restrictional interference relation given by $e \perp_0 e^\prime$ if and only if $ee^\prime =0$ ;

2. (ii) $\perp_\delta$ is an interference relation with its associated restrictional interference relation given by $e \perp_\delta e^\prime$ if and only if $e=0$ or $e^\prime=0$ .

Furthermore, for every interference relation $\perp$ on $\mathbb{X}$ , we have that $\perp_\delta \subseteq \perp \subseteq \perp_0$ .

[𝓞⊥.0] By the annihilation property, we have that $1_A 0 = 0$ , so $1_A \perp_0 0$ .

[𝓞⊥.1] Recall that restriction idempotents commute, that is, $e e^\prime = e^\prime e$ . Therefore, if $e \perp_0 e^\prime$ , which means that $e e^\prime =0$ , then $e^\prime e =0$ as well, and so $e^\prime \perp_0 e$ .

[𝓞⊥.2] Recall that restriction idempotents are idempotents, that is, if $e \in \mathcal{O}(A)$ , then $ee=e$ . Then if $e \perp_0 e$ , which implies that $ee=0$ , then we get that $e=0$ .

[𝓞⊥.3] Recall that for restriction idempotents, $e_1 \leq e^\prime_1$ and $e_2 \leq e_2^\prime$ imply that $e_1 e^\prime_1= e_1$ and $e^\prime_2 e_2 = e_2$ . Then if $e^\prime_1 \perp_0 e^\prime_2$ , which means $e^\prime_1 e^\prime_2 =0$ , then we also get that $e_1 e_2 = e_1 e^\prime_1 e^\prime_2 e_2 = e_1 0 e_2 = 0$ . So $e_1 e_2=0$ and so $e_1 \perp_0 e_2$ .

[𝓞⊥.4] First note that using [R.3] and [R.4], it follows that $\overline{he}\,\overline{he^\prime} = \overline{h e e^\prime}$ . So if $e \perp_0 e^\prime$ , which means $ee^\prime =0$ , then we get that $\overline{he} \overline{he^\prime} = \overline{h e e^\prime} = \overline{h 0} = \overline{0}=0$ . So have that $\overline{he} \perp_0 \overline{he^\prime}$ .

So $\perp_0$ is a restrictional interference relation, and it is straightforward to see that its induced interference relation is precisely as defined above. So we conclude that $\perp_0$ is an interference relation.

It remains to explain why $\perp_0$ is maximal and $\perp_\delta$ is minimal among interference relations. However, we have already done this, since for any interference relation $\perp$ , that $\perp \subseteq \perp_0$ is precisely the statement of Lemma 7(ii), while that $\perp_\delta \subseteq \perp$ is precisely Lemma 7(i).

Thus, having an interference relation is chosen structure rather than a property and we say that:

Nevertheless, to avoid heavy nomenclature, we will say that $\mathbb{X}$ is a $\perp$ -restriction category as a short hand for saying that $(\mathbb{X}, \perp\!)$ is an interference restriction category. We conclude this section with our main examples of interference relations:

5. Disjoint Joins

In this section, we discuss the notion of disjoint joins in an interference restriction category. Since the homsets of a restriction category are posets, we can consider the join (Cockett and Manes Reference Cockett and Manes2009, Definition 6.7) of suitable parallel maps to be the join in usual sense, meaning the least upper bound with respect to $\leq$ . However, for the story of this paper, we do not need all joins to exists like in a join restriction category (Cockett and Manes Reference Cockett and Manes2009, Definition 10.1) but instead only require the joins of $\perp$ -disjoint maps. As such, we call such joins: $\perp$ -disjoint joins, or simply $\perp$ -joins, and denote them using $\sqcup$ instead of $\vee$ , to further emphasize that the maps we are working with are intuitively disjoint. Readers familiar with joins in a restriction category may recall that joins can only be defined for maps that are compatible (Cockett and Manes Reference Cockett and Manes2009, Proposition 6.3). Recall that parallel maps f and g are compatible, written as $f \smile g$ , if $\overline{f}g = \overline{g}f$ . However, by Lemma 7(ii), if $f \perp g$ , then $\overline{g}f=0=\overline{f}g$ , and so $f \smile g$ . Therefore, we can indeed consider the join of parallel $\perp$ -disjoint maps. More generally, one can define define joins with respect to a restrictional coherence (Cockett and Manes Reference Cockett and Manes2009, Definition 6.7). Thus, since every interference relation is a restrictional coherence, the following definition is (Cockett and Manes Reference Cockett and Manes2009, Definition 6.7) for the special case of an interference relation.

[⊔.1] $f_i \leq \bigsqcup \limits_{i\in I} f_i$ for all $i \in I$ ;

[⊔.2] If $g: A \to B$ is a map such that $f_i \leq g$ for all $i \in I$ , then $\bigsqcup \limits_{i\in I} f_i \leq g$ .

Note that $\perp$ -joins are necessarily unique since [ $\boldsymbol{\sqcup}$ .1] and [ $\boldsymbol{\sqcup}$ .2] say that they are least upper-bounds, which are always unique. For a finite family indexed by $I= \lbrace 0, \unicode{x2026}, n+1 \rbrace$ , we write their $\perp$ -join as $\bigsqcup \limits_{i\in I} f_i = f_0 \sqcup ... \sqcup f_{n+1}$ . In the special case of a singleton $\lbrace f \rbrace$ , its $\perp$ -join is just f, while for the case of the empty set, the $\perp$ -join of nothing is simply the zero map. When the $\perp$ -joins of all suitable families of $\perp$ -disjoint maps exists, we may also ask that they be compatible with composition. In Cockett and Manes (Reference Cockett and Manes2009, Definition 6.7), preservations of joins by pre-composition was called being stable, while preservations of joins by post-composition was called being universal. It turns out that being stable implies being universal (Cockett and Manes Reference Cockett and Manes2009, Lemma 6.10.(2)), so we only need to ask that pre-composition preserves $\perp$ -joins. Since for most of the story of this paper, we only really need binary $\perp$ -joins, and we take the time to define this case explicitly.

[⊔.3] For any map $h: A^\prime \to A$ , $h \left( f \sqcup g \right) = hf \sqcup hg$ .

Similarly, a $\perp$ -restriction category $\mathbb{X}$ is said to have all (finite) $\perp$ -joins if for every (finite) family of pairwise $\perp$ -disjoint parallel maps ${\lbrace f_i: A \to B \rbrace_{i \in I}}$ , their $\perp$ -join ${\bigsqcup \limits_{i\in I} f_i: A \to B}$ exists and:

[⊔.4] For any map $h: A^\prime \to A$ , $h \bigsqcup \limits_{i\in I} f_i = \bigsqcup \limits_{i\in I} h f_i$ .

Since a $\perp$ -join is a join in the sense of Cockett and Manes (Reference Cockett and Manes2009, Definition 6.7), it therefore satisfies the same properties, some of which can be found in Cockett et al. (Reference Cockett, Cruttwell and Gallagher2011, Proposition 2.14) and Cockett and Lemay (Reference Cockett and Lemay2024, Lemma 4.3). In the result below, which highlights some useful identities, I is an arbitrary indexing set: if I has size two we recover the binary case, if I is finite we recover the finite case.

1. (i) $\overline{f_j} \bigsqcup \limits_{i\in I} f_i = f_j$ for all $j \in I$ ;

2. (ii) $\overline{\bigsqcup \limits_{i\in I} f_i} = \bigsqcup \limits_{i\in I} \overline{f_i}$ ;

3. (iii) $k \left(\bigsqcup \limits_{i\in I} f_i \right)k^\prime = \bigsqcup \limits_{i\in I} k f_i k^\prime$ ;

4. (iv) If $\bigsqcup \limits_{i\in I} f_i \perp h$ , then $f_j \perp h$ for all $j \in I$ .

It is important to note that while having finite $\perp$ -joins obviously implies having binary $\perp$ -joins, the converse is not necessarily true. Indeed, having binary $\perp$ -joins does not imply we can build arbitrary finite $\perp$ -joins since the converse of Lemma 12(iv) does not hold in general. To see this, suppose we have three parallel maps such that $f \perp g$ , $g \perp h$ , and $f \perp h$ . Then we get their binary $\perp$ -joins $f \sqcup g$ , $g \sqcup h$ , and $f \sqcup h$ . However, since we do not necessarily have that say $f \sqcup g$ and h are $\perp$ -disjoint, we would not be able to construct $\left( f \sqcup g \right) \sqcup h$ . Thus, we also need to ask that $\perp$ -joins preserve $\perp$ -disjointness.

[⊔.4] For every map $h: A \to C$ such that $f_i \perp h$ for all $i \in I$ , then $\bigsqcup \limits_{i\in I} f_i \perp h$ .

A (finitely) disjoint $\perp$ -restriction category is a $\perp$ -restriction category $\mathbb{X}$ that has all (finite) $\perp$ -joins and every (finite) $\perp$ -join is strong.

We can now show that having strong binary $\perp$ -joins is equivalent to having strong finite $\perp$ -joins.

Before finally giving examples, let us quickly take a look at disjoint joins for the maximal and minimal interference relations. We first show that for the maximal relation $\perp_0$ , every $\perp_0$ -join is strong. In particular, this means that if we have binary $\perp_0$ -joins, then we have all finite $\perp_0$ -joins as well. A finitely disjoint $\perp_0$ -restriction category was called an $\perp$ -restriction category in (Cockett and Manes Reference Cockett and Manes2009, Definition 7.5) (not be confused with our use of $\perp$ -restriction category for an interference restriction category which may not have $\perp$ -joins).

On the other hand, for the minimal interference relation $\perp_\delta$ , all $\perp_\delta$ -joins exist trivially and are trivially strong.

Here are now the disjoint joins in our main examples.

Example 5.1. $\mathsf{PAR}$ has all $\perp_0$ -joins. For an $i\in I$ indexed family of parallel partial functions ${f_i: X \to Y}$ which are pairwise $\perp_0$ -disjoint, which recall means that when $f_i(x) \downarrow$ then $f_j(x) \uparrow$ for all $j\neq i$ , their $\perp_0$ -join is the partial function $\bigsqcup \limits_{i\in I} f_i: X \to Y$ defined as follows:

\[ \left(\bigsqcup \limits_{i\in I} f_i \right)(x) = \begin{cases} f_i(x) & \text{if there exists a (necessarily unique) $i\in I$ such that } f_i(x) \downarrow \\\uparrow & \text{otherwise} \end{cases}\]

In particular, this means that $\mathsf{PAR}$ is a disjoint $\perp_0$ -restriction category.

We conclude this section by explaining how every interference restriction category embeds into a disjoint interference restriction category. This is similar to the join construction given in Cockett and Manes (Reference Cockett and Manes2009, Section 10), but which is simplified since we only want disjoint joins and not all joins. So let $\mathbb{X}$ be a $\perp$ -restriction category. For a family of pairwise $\perp$ -disjoint parallel maps $F \subseteq \mathbb{X}(A,B)$ , let $\downarrow \!\! F = \lbrace g: A \to B \vert\, \exists f \in F \text{ s.t. } g \leq f \rbrace$ . Note that $\downarrow \!\! F$ need not be itself a family of pairwise $\perp$ -disjoint parallel maps, and also that it is never empty since we always have that $0 \in\, \downarrow \!\! F$ . Then, abusing notation slightly, define the disjoint $\perp$ -restriction category $\mathsf{DJ}[(\mathbb{X},\perp\!)]$ as follows:

1. (i) The objects of $\mathsf{DJ}[(\mathbb{X},\perp\!)]$ are the same as $\mathbb{X}$ ;

2. (ii) A map $A \to B$ in $\mathsf{DJ}[(\mathbb{X},\perp\!)]$ is a $S = \downarrow \!\! F$ where $F \subseteq \mathbb{X}(A,B)$ is a family of pairwise $\perp$ -disjoint parallel maps;

3. (iii) Identity maps are the set of restriction idempotents $\mathcal{O}(A): A \to A$ ;

4. (iv) Composition of $S: A \to B$ and $T: B \to C$ is defined as $ST = \lbrace fg \vert\, f \in S, g\in T \rbrace$ ;

5. (v) The restriction of $S: A \to B$ is defined as the set of the restrictions, $\overline{S} = \lbrace \overline{f} \vert\, f\in S \rbrace$ ;

6. (vi) The restriction zero maps are the singletons $\lbrace 0 \rbrace: A \to B$ ;

7. (vii) The interference relation is defined as $S \perp T$ if for all $f\in S$ and $g \in T$ , $f \perp g$ ;

8. (viii) For a family index by a set I of pairwise $\perp$ -disjoint parallel maps $S_i: A \to B$ , their $\perp$ -join is defined as their union $\bigsqcup\limits_{i \in I} S_i := \bigcup\limits_{i \in I} S_i$ .

Now since we want to give an embedding, we also need to explain what we mean by a functor between interference restriction categories. So if $\mathbb{X}$ and $\mathbb{Y}$ are restriction categories, then a restriction functor (Cockett and Lack Reference Cockett and Lack2002, Section 2.2.1) is a functor ${\mathcal{F}: \mathbb{X} \to \mathbb{Y}}$ which preserves the restrictions, $\overline{\mathcal{F}(f)} = \mathcal{F}(\overline{f})$ . If $(\mathbb{X},\perp\!)$ and $(\mathbb{Y},\perp\!)$ are interference restriction categories, then an interference restriction functor $\mathcal{F}: (\mathbb{X},\perp\!) \to (\mathbb{Y},\perp\!)$ is a restriction functor $\mathcal{F}: \mathbb{X} \to \mathbb{Y}$ which preserves the restrictions zeroes, $\mathcal{F}(0) = 0$ , and also preserves the interference relation in the sense that if $f \perp g$ , then $\mathcal{F}(f) \perp \mathcal{F}(g)$ . If there is no confusion, we will simply write an interference restriction functor as ${\mathcal{F}: \mathbb{X} \to \mathbb{Y}}$ and say that it is a $\perp$ -restriction functor.

Now let us explain why $\perp$ is an interference relation.

[⊥.0] By Lemma 7(i), we have that for all $e \in \mathcal{O}(A)$ , $e \perp 0$ . Thus, $\mathcal{O}(A) \perp \lbrace 0 \rbrace$ .

[⊥.1] Suppose that $S \perp T$ , that is, all $f \in S$ and $g \in T$ , we have that $f \perp g$ . Then by [ $\boldsymbol{\perp}$ .1], we also have that $g \perp f$ for all $g \in T$ and $f \in S$ . So $T \perp S$ .

[⊥.2] Suppose that $S \perp S$ , that is, for all $f \in S$ , $f \perp f$ . But then by [ $\boldsymbol{\perp}$ .2], $f =0$ for all $f \in S$ . So, $S = \lbrace 0 \rbrace$ .

[⊥.3] By the same arguments as in the proof of (Cockett and Manes Reference Cockett and Manes2009), Proposition 10.5, we get that $S \leq S^\prime$ in $\mathsf{DJ}[(\mathbb{X},\perp\!)]$ if and only if $S \subseteq S^\prime$ . So now suppose that $S^\prime \perp T^\prime$ , and also that $S \leq S^\prime$ and $T \leq T^\prime$ , or in other words, $S \subseteq S^\prime$ and $T \subseteq T^\prime$ . Then for all $f \in S$ and $g \in T$ , we also have that $f \in S^\prime$ and $g \in T^\prime$ , and thus $f \perp g$ . So $S \perp T$ .

[⊥.4] Suppose that $S \perp T$ , that is, all $f \in S$ and $g \in T$ , we have that $f \perp g$ . Now given suitable $U = \downarrow H$ and $V = \downarrow K$ , consider USV and UTV. Then a $x \in USV$ is of the form u f v for some $u \in U$ , $f \in S$ , and $v \in V$ , and similarly a $y \in UTV$ is of the form $x = u^\prime g v^\prime$ for some $u^\prime \in U$ , $g \in T$ , and $v^\prime \in V$ . Now since $u, u^\prime \in U$ , there are $h, h^\prime \in H$ such that $u \leq h$ and $u^\prime \leq h^\prime$ . If $h \neq h^\prime$ , then $h \perp h^\prime$ , and then by [ $\boldsymbol{\perp}$ .3], we have that $u \perp u^\prime$ . So by [ $\boldsymbol{\perp}$ .4], we get that $x = u f v \perp u^\prime g v^\prime = y$ . Now consider instead if $h = h^\prime$ . Now since $f \perp g$ , by [ $\boldsymbol{\perp}$ .4] we get $h f v \perp h g v^\prime$ . Then since $u \leq h$ and $u\prime \leq h$ , we get that $u f v \leq h fv$ and $u^\prime g v^\prime \leq h^\prime g v^\prime$ , so by [ $\boldsymbol{\perp}$ .3] we get that $x = u f v \perp u^\prime g v^\prime = y$ . So $USV \perp UTV$ .

[⊥.5] Suppose that $S \perp T$ , that is, all $f \in S$ and $g \in T$ , that $f \perp g$ . Then by [ $\boldsymbol{\perp}$ .5] we also have that $\overline{f} \perp \overline{g}$ for all $\overline{f} \in \overline{S}$ and $\overline{g} \in \overline{T}$ . So $\overline{S} \perp \overline{T}$ .

Thus, $\mathsf{DJ}[(\mathbb{X},\perp\!)]$ is a $\perp$ -restriction category. It remains to discuss the disjoint joins. Now given a family of families of parallel $\perp$ -disjoint maps $F_i \subseteq \mathbb{X}(A,B)$ such that $F_i \perp F_j$ for all $i \neq j$ (that is, $f \perp g$ for all $f \in F_i$ and $g \in F_j$ ), then their union $\bigcup\limits_{i \in I} F_i \subseteq \mathbb{X}(A,B)$ is also a family of pairwise $\perp$ -disjoint parallel maps. Then by the same arguments as in the proof of (Cockett and Manes Reference Cockett and Manes2009, Proposition 10.5), we see that for a family of pairwise $\perp$ -disjoint maps $S_i = \downarrow \!\! F_i$ , that $\bigsqcup\limits_{i \in I} S_i = \downarrow\left(\bigcup\limits_{i \in I} F_i \right)$ . By using again the same arguments as in the proof of (Cockett and Manes Reference Cockett and Manes2009, Proposition 10.5), we get that [ $\boldsymbol{\sqcup}$ .1], [ $\boldsymbol{\sqcup}$ .2], and [ $\boldsymbol{\sqcup}$ .3] hold. Finally, it remains to show [ $\boldsymbol{\sqcup}$ .4]. So consider family of pairwise $\perp$ -disjoint maps $S_i$ and another map T such that $S_i \perp T$ for all $i \in I$ . Then clearly $\bigcup\limits_{i \in I} S_i \perp T$ as well, and so [ $\boldsymbol{\sqcup}$ .4] holds. So we conclude that $\mathsf{DJ}[(\mathbb{X},\perp\!)]$ is a disjoint $\perp$ -restriction category.

Finally, it remains to show that $\mathcal{I}$ is an interference restriction functor. By the same arguments as in the proof of (Cockett and Manes Reference Cockett and Manes2009, Theorem 10.6), we get that $\mathcal{I}$ is a faithful restriction functor. Moreover, it preserves restriction zeroes since $\mathcal{I}(0) = \downarrow \!\! \lbrace 0 \rbrace = Z$ . Now suppose that $f \perp g$ in $(\mathbb{X},\perp\!)$ . Then by [ $\boldsymbol{\sqcup}$ .3], for all $f^\prime \leq f$ and $g \prime \leq g$ , we get that $f^\prime \perp g^\prime$ . Thus, $\mathcal{I}(f) = \downarrow \!\! \lbrace f \rbrace \perp \downarrow \!\! \lbrace g \rbrace = \mathcal{I}(g)$ , and so we get that $\mathcal{I}$ is indeed a $\perp$ -restriction functor.

6. Kleene Wands

In this section, we introduce the notion of a Kleene wand for an interference restriction category with binary disjoint joins by adapting the definition of Kleene wand from Cockett et al. (2012a, Section 4). The main result of this paper is that for an extensive restriction category, to have an iteration (or trace) operator on the coproduct is equivalent to having a Kleene wand. As such, the axioms of a Kleene wand are analogs to of that of an iteration operator. However, while iteration operators require the presence of coproducts, a Kleene wand can be defined without them. Thus, Kleene wands capture iteration in settings without coproducts. An itegory is an interference restriction category with binary disjoint joins and Kleene wands. It is also worth noting that the definition of a Kleene wand in Cockett et al. (2012a, Section 4) was for the maximal interference relation $\perp_0$ and in a setting with restriction products (Cockett and Lack Reference Cockett and Lack2007, Section 4.1). So here, we adapt some of the axioms for an arbitrary interference relation but do not consider having restriction products.

Definition 18. For a $\perp$ -restriction category $\mathbb{X}$ with all binary $\perp$ -joins, a Kleene wand is a family of operators (indexed by pairs of objects $X, A \in \mathbb{X}$ ):

such that the following axioms hold:

Iteration: For maps $f: X \to X$ and $g: X \to A$ , if $f \perp g$ , then

Naturality: For maps $f: X \to X$ , $g: X \to A$ , and $h: A \to B$ , if $f \perp g$ , then

Dinaturality: For maps $f: X \to Y$ , $g: X \to A$ , and $k: Y \to X$ , if $f \perp g$ then

Diagonal: For maps $f: X \to X$ , $f^\prime: X \to X$ , and $g: X \to A$ , if $f \perp f^\prime$ and $f \sqcup f^\prime \perp g$ , then and .

A $\perp$ -itegory is a pair , consisting of a $\perp$ -restriction category $\mathbb{X}$ with all binary $\perp$ -joins and a Kleene wand .

We note that [.4] is well defined by Lemma 12(iv). The axioms of a Kleene wand are analogs of the axioms of an iteration operator but expressed in a setting without coproducts. We first observe that if we have strong disjoint joins, then the fourth axiom can be simplified.

Diagonal: For maps $f: X \to X$ , $f^\prime: X \to X$ , and $g: X \to A$ , if $f \perp f^\prime$ , $f \perp g$ , and $f^\prime \perp g$ , then

Intuitively, the Kleene wand “iterates” the endomorphism f until the “guard” g is satisfied and then produces that output. This intuition is indeed justified by successive applications of the iteration axiom.

Lemma 20. Let $\mathbb{X}$ be a $\perp$ -restriction category, and $f: X \to X$ and ${g: X \to A}$ maps such that $f \perp g$ . Then for all $n,m \in \mathbb{N}$ and $n\neq m$ , $f^ng \perp f^m g$ (where by convention, $f^0=1_X$ ). Furthermore, if is a $\perp$ -itegory, then for all $n \in \mathbb{N}$ , the following equality holds:

(1)

So in particular, for all $n \in \mathbb{N}$ .

Now suppose is a $\perp$ -itegory. We prove (1) by induction on n. The base case $n=0$ is precisely [.1], since . So suppose that we have shown that (1) for all $0 \leq k \leq n$ . We now show it for the case $n+1$ by showing that is the $\perp$ -join of the family . By the induction hypothesis and [ $\boldsymbol{\sqcup}$ .1], we already have that for all $0 \leq k \leq n$ and also that . So we also need to explain why is greater than $f^{n+1}g$ and . However using [.1] and [ $\boldsymbol{\sqcup}$ .3], observe that . So since , by [ $\boldsymbol{\sqcup}$ .1] and transitivity, we get that and . So [ $\boldsymbol{\sqcup}$ .1] holds for $n+1$ . Now suppose that we have a map h such that $f^k g \leq h$ for all $0 \leq k \leq n+1$ and . By [ $\boldsymbol{\sqcup}$ .2], we also get that , or in other words, . So by the induction hypothesis and [ $\boldsymbol{\sqcup}$ .2], we get that . So [ $\boldsymbol{\sqcup}$ .2] holds for $n+2$ . So we conclude that is the $\perp$ -join of . Thus, (1) holds for all $n \in \mathbb{N}$ as desired.

The above lemma suggests that a natural example of a Kleene wand should be the disjoint join of all $f^n g$ when it exists. This formula clearly realizes the intuition that f is iterated until it falls in the domain of g. In fact, in Theorem 6, we will show that for a disjoint interference restriction category, this formula always defines a Kleene wand. In the meantime, here are our main examples of Kleene wands:

Example 6.1. $\mathsf{PAR}$ has a Kleene wand with respect to $\perp_0$ defined as follows for $\perp_0$ -disjoint partial functions ${f: X \to X}$ and $g: X \to A$ :

Note that this is well defined since for all $m,n \in \mathbb{N}$ with $m\neq n$ , if $g(f^m(x)) \downarrow$ then $g(f^n(x)) \uparrow$ . Thus, is a $\perp_0$ -itegory.

Here are some other useful basic properties about Kleene wands.

1. (i)

2. (ii)

3. (iii)

4. (iv) If $f \perp g \sqcup g^\prime$ , then and

5. (v) If f is total, then .

6. (vi) If g is total, then .

1. (i) This follows from [R.1] and [.2], since .

2. (ii) By Lemma 7(i), $0 \perp g$ . So using [.1], we have that .

3. (iii) Using (i), we get that .

4. (iv) Suppose that $f \perp g \sqcup g^\prime$ . By Lemmas 7(iv) and 12(ii), we also get that $f \perp \overline{g} \sqcup \overline{g^\prime}$ . As such, we can take their Kleene wand: . Next note that by Lemmas 7(i) and 12(iii), we get that $(\overline{g} \sqcup \overline{g^\prime})g= g$ and $(\overline{g} \sqcup \overline{g^\prime})g^\prime= g^\prime$ . Therefore, by [.2], we get that and . Now since $g \perp g^\prime$ , by [ $\boldsymbol{\perp}$ .4] we get that . So we have that . Finally, using (i) and Lemma 12(iii) and (ii), we compute that:

   
   So as desired.

5. (v) If f is total, then by Lemma 7(iii), $f \perp g$ implies that $g=0$ . So by (iii), .

6. (vi) If g is total, then by Lemma 7(iii), $f \perp g$ implies that $f=0$ . So by (ii), .

We now turn our attention to discussing uniformity and inductivity of Kleene wands. These are analogs of their namesakes for iteration/trace operators, which are often desirable properties of well-behaved iteration/trace operators (Hasegawa Reference Hasegawa2004).

1. (i) Uniform if when $f \perp g$ and $f^\prime \perp g^\prime$ , and $hg^\prime = g$ and $hf^\prime= fh$ , then ;

2. (ii) Lax uniform if when $f \perp g$ and $f^\prime \perp g^\prime$ , and $g \leq hg^\prime$ and $fh\leq hf^\prime$ , then ;

3. (iii) Colax uniform if when $f \perp g$ and $f^\prime \perp g^\prime$ , and $g \geq hg^\prime$ and $fh \geq hf^\prime$ , then .

Basic uniformity simply asks that the iteration behaves equivariently for homomorphic iteration data. The (co)lax versions of uniformity ask that (co)lax homomorphism between iteration data produces a commensurate (co)lax behavior between iterants. Here are some equivalent alternative descriptions of uniformity.

1. (i) is uniform if and only if when $f \perp g$ and $f^\prime \perp g^\prime$ , and $a g^\prime = g b$ and $af^\prime= fa$ , then ;

2. (ii) is lax uniform if and only if when $f \perp g$ and $f^\prime \perp g^\prime$ , and $g b \leq a g^\prime$ and $fa \leq af^\prime$ , then ;

3. (iii) is colax uniform if and only if when $f \perp g$ and $f^\prime \perp g^\prime$ , and $g b \geq a g^\prime$ and $fa \geq af^\prime$ , then ;

From the alternative description of (co)lax uniformity, we can show that a (co)lax uniform Kleene wand is monotone.

Note that being uniform and lax (resp. colax) uniform implies being colax (resp. lax) uniform, and also that being both lax and colax uniform implies being uniform.

1. (i) is uniform and lax uniform;

2. (ii) is uniform and colax uniform;

3. (iii) is lax uniform and colax uniform.

By a similar argument, we can also that $(ii) \Rightarrow (iii)$ , since we would need to show that being uniform and colax uniform implies being lax uniform. So it remains to show that $(iii) \Rightarrow (i)$ . So suppose that is both lax uniform and colax uniform. Now also suppose that $f \perp g$ and $f^\prime \perp g^\prime$ , and also that $hg^\prime = g$ and $hf^\prime= fh$ . Of course, this says that $hg^\prime \leq g$ and $hf^\prime \leq fh$ , as well as $hg^\prime \geq g$ and $hf^\prime \geq fh$ . So by applying lax uniformity we get that , while applying colax uniformity gives us that . So by antisymmetry, we get that , and conclude that is uniform. Thus, is strongly uniform as desired.

We can now define what it means for a Kleene wand to be (strongly) inductive.

1. (i) Inductive if when $f \perp g$ , $f h \leq h$ , and $g \leq h$ then

2. (ii) Strongly inductive if it is both strongly uniform and inductive.

A (strongly) inductive $\perp$ -itegory is an itegory whose Kleene wand is (strongly) inductive.

We first note that an inductive Kleene wand, if one exists, is the minimal one among Kleene wands and, moreover, there is at most one inductive Kleene wand.

1. (i) For any other Kleene wand , we have for all $f \perp g$ that .

2. (ii) is the unique inductive Kleene wand on $\mathbb{X}$ .

We now show that for a strongly inductive Kleene wand, there is an equivalent axiomatization which is much simpler.

If $f \perp g$ , then ;

If $f \perp g$ , $f^\prime \perp g^\prime$ , and $a g^\prime = g b$ and $af^\prime= fa$ , then ;

If $f \perp g$ , $f h \leq h$ , and $g \leq h$ then .

For the $\Leftarrow$ direction, we need to show that satisfies [.1], [.2], [.3], and [.4]:

[.1]: It suffices to show that . By [Alt..1] and since composition is monotone, we first get that . So we have and . Thus applying [Alt..3], we get that . So by antisymmetry, we obtain that .

[.2]: If $f \perp g$ , then starting with $f \perp g$ and $f \perp gh$ , setting $a=1$ and $b=h$ , by applying [Alt..3] we get as desired.

[.3]: If $f \perp g$ , then starting with $hf \perp hg$ and $fh \perp g$ , setting $a=h$ and $b=1$ , by applying [Alt..3] we get as desired.

[.4]: Suppose that $f \perp g$ and $f \sqcup g \perp h$ , which by Lemma 12(iv) also implies that $f \perp h$ and $g \perp h$ . We first show that . We first observe that using [.1] we can compute that:

So we have that . This implies both that and . Then applying [Alt..3], we get that .

Next, we show that as well. So first observe that using [.1] again, we can compute that . This implies both that and . Thus applying [Alt..3], we get that . On the other hand, we also have that and . So applying [Alt..3] here gives us that . However, by [.2], we have that . So we then get that . Therefore, bringing this all together, we have that and . Then applying [Alt..3] again, we get . So by antisymmetry, we conclude that as desired.

So is a Kleene wand. We must also show that is inductive and strongly uniform. However, [Alt..3] is precisely the statement that is inductive, while Lemma 23(i) tells us that [Alt..3] is an equivalent way of saying is uniform. So it remains to show that is lax uniform as well. So suppose that $f \perp g$ and $f^\prime \perp g^\prime$ , and also that $g \leq hg^\prime$ and $fh\leq hf^\prime$ . By [Alt..1], recall that we have that and . Pre-composing by h, we then get and . By transitivity, we have that and . Therefore, applying [Alt..3], we get that . So we have that is also lax uniform. Therefore, we conclude that is a strongly inductive Kleene wand.

By the above proposition, we can now easily show that in a setting with all disjoint joins, there is a canonical strongly inductive Kleene wand. So every (countable) disjoint interference restriction category is canonically a strongly inductive itegory.

Theorem. Let $\mathbb{X}$ be a disjoint $\perp$ -restriction category. Then $\mathbb{X}$ has a strongly inductive Kleene wand defined as follows for $\perp$ -disjoint maps $f: X \to X$ and $g: X \to A$ :

(2)

where by convention $f^0 = 1_X$ . Thus, is a strongly inductive $\perp$ -itegory.

[Alt. .1]: Using [ $\boldsymbol{\sqcup}$ .4], we easily compute that:

So we have that , which of course means that .

[Alt. .2]: Suppose that $a g^\prime = g b$ and $af^\prime= fa$ . Then by Lemma 12(ii), we easily compute that:

\begin{align*} a \left( \bigsqcup \limits_{n \in \mathbb{N}} {f^\prime}^n g^\prime \right) = \bigsqcup \limits_{n \in \mathbb{N}} a {f^\prime}^n g^\prime = \bigsqcup \limits_{n \in \mathbb{N}} f^n a g^\prime = \bigsqcup \limits_{n \in \mathbb{N}} f^n g b = \left( \bigsqcup \limits_{n \in \mathbb{N}} f^n g \right) b\end{align*}

So .

[Alt. .3]: Suppose that $f h \leq h$ and $g \leq h$ . Note that $fh \leq h$ implies that $f^n h \leq h$ for all $n \in \mathbb{N}$ as well. Then we see that $f^n g \leq f^n h \leq h$ . So $f^n g \leq h$ for all $n \in \mathbb{N}$ . So by [ $\boldsymbol{\sqcup}$ .2], $\bigsqcup \limits_{n \in \mathbb{N}} f^n g \leq h$ , which we rewrite as .

So we conclude that is a strongly inductive Kleene wand as desired.

Moreover, using the construction from Proposition 17, we observe that every interference restriction category embeds into a strongly inductive itegory.

In particular, we can in fact embed any restriction with restriction zeroes into a strongly inductive itegory by considering the maximal interference restriction $\perp_0$ . It is not difficult to see that the induced interference restriction on $\mathsf{DJ}[ (\mathbb{X},\perp_0\!)]$ will also be the maximal one.

We conclude this section by observing that the minimal interference relation has a unique but trivial Kleene wand, which is also strongly inductive.

Lemma 32. Let $\mathbb{X}$ be a restriction category with restriction zeroes. Then is a strongly inductive $\perp_\delta$ -itegory where is defined as follows:

(3)

Moreover is the unique Kleene wand for $(\mathbb{X}, \perp_\delta\!)$ .

7. Kleene Upper-Stars

In this section, we take a detour to discuss Kleene wands in the classical restriction category setting, that is, in the presence of relative complements. In such a setting, we will show that Kleene wands are in fact completely determined by how they act on their endomorphism input. Thus, in the classical setting, Kleene wands are equivalent to an operator on endomorphisms, which we call a Kleene upper-star.

We begin by discussing relative complements in a disjoint interference restriction category. Relative complements for join restriction categories were introduced in (Cockett and Manes Reference Cockett and Manes2009, Section 13). Here, we slightly adjust the definition instead for disjoint $\perp$ -restriction categories, where in particular, the relative complement is not simply disjoint in the sense of (Cockett and Manes Reference Cockett and Manes2009, Proposition 6.2) but $\perp$ -disjoint.

[\.1] $g \backslash f \perp f$

[\.2] $(g \backslash f) \sqcup f =g$

A classical $\perp$ -restriction category is a $\perp$ -restriction category $\mathbb{X}$ with all binary $\perp$ -joins such that all $\perp$ -relative complements exists.

Intuitively, $g \backslash f$ is undefined when f is defined and is equal to g whenever f is undefined. Moreover, a $\perp$ -relative complement is a relative complement in the sense of Cockett and Manes (Reference Cockett and Manes2009, Section 13) (which we can now call a $\perp_0$ -relative complement), and so satisfies the same properties, some of which can be found in (Cockett and Manes Reference Cockett and Manes2009, Lemma 13.14) and Cockett and Lemay (Reference Cockett and Lemay2024, Lemma 4.9).

Recall that $\mathcal{O}(A)$ is a bounded meet-semilattice, so every restriction idempotent $e: A \to A$ is always less than or equal to the identity $1_A: A \to A$ , so $e \leq 1_A$ . As such, we can consider the relative complement of a restriction idempotent in the identity, which we denote as $e^c := 1_A \backslash e$ . It turns out that having complements of restriction idempotents is sufficient to have all relative complements.