# A Hypersequent Calculus with Clusters for Tense Logic
over Ordinals

David Baelde, Anthony Lick, Sylvain Schmitz

► To cite this version:

David Baelde, Anthony Lick, Sylvain Schmitz. A Hypersequent Calculus with Clusters for Tense Logic over Ordinals. FSTTCS 2018 - 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2018, Ahmedabad, India. pp.15:1–15:19, 10.4230/LIPIcs.FSTTCS.2018.15 . hal-01852077v2

HAL Id: hal-01852077

https://inria.hal.science/hal-01852077v2

Submitted on 13 Dec 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
# A Hypersequent Calculus with Clusters for Tense Logic over Ordinals

**David Baelde**

LSV, ENS Paris-Saclay & CNRS & Inria, Université Paris-Saclay
baelde@lsv.fr

**Anthony Lick**

LSV, CNRS & ENS Paris-Saclay, Université Paris-Saclay
lick@lsv.fr

**Sylvain Schmitz**

LSV, ENS Paris-Saclay & CNRS, Université Paris-Saclay
schmitz@lsv.fr

https://orcid.org/0000-0002-4101-4308

**Abstract**

Prior's tense logic forms the core of linear temporal logic, with both past- and future-looking modalities. We present a sound and complete proof system for tense logic over ordinals. Technically, this is a hypersequent system, enriched with an ordering, clusters, and annotations. The system is designed with proof search algorithms in mind, and yields an optimal coNP complexity for the validity problem. It entails a small model property for tense logic over ordinals: every satisfiable formula has a model of order type at most $\omega^2$. It also allows to answer the validity problem for ordinals below or exactly equal to a given one.

**2012 ACM Subject Classification** Theory of computation $\rightarrow$ Proof theory, Theory of computation $\rightarrow$ Modal and temporal logics

**Keywords and phrases** modal logic, proof system, hypersequent

**Funding** ANR-14-CE28-0005 PRODAQ

# 1 Introduction

Linear temporal logic has become a staple specification language in verification since its introduction by Pnueli [28]. In its most common form, the logic features an ‘until’ temporal modality and ranges over linear time flows of order type $\omega$, i.e. over infinite words, where it enjoys a PSPACE-complete satisfiability problem [34]. A large number of variants with the same complexity has been motivated and introduced in the literature, notably temporal logics with past modalities [23, 21], ranging over arbitrary ordinals [33, 12], or even—with the Stavi modalities added—over arbitrary linear time flows [10, 32].

Linear temporal logic finds its roots in Prior's tense logic [31, 9], which only featured the strict 'past' P and 'future' F modalities. This set of modalities is still interesting in its own right, as it is sufficient for many modelling tasks [35], and is known to lead to a slightly easier NP-complete satisfiability problem both over $\omega$ [34] and over arbitrary linear time flows [26]. While linear tense logic is less expressive than FO($<$), the first-order logic over linear orders with unary predicates, it has nevertheless nice characterisations as it captures instead its two-variable fragment FO$^2$($<$) [13].

In this paper, we investigate tense logic over well-founded linear time flows, i.e. over ordinals, which can be denoted as $K_t L_\ell . 3$ in the taxonomy of modal logics from [6]. We show in particular that

<figure><img src="image_2.png" /></figure>

© David Baelde, Anthony Lick and Sylvain Schmitz;
licensed under Creative Commons License CC-BY-SA
1. the satisfiability problem for $K_tL_\ell.3$ over the class of ordinals is NP-complete, and that

2. a formula $\varphi$ of $K_tL_\ell.3$ has a well-founded linear model if and only if it has a model of order type $\alpha$ for some $\alpha < \omega \cdot (|\varphi| + 2)$; this should be contrasted with the corresponding $\omega^{|\varphi|+2}$ bound proven in [12, Cor. 3.3] for linear temporal logic.

These two results are however just byproducts of our main contribution, which is a sound and complete proof system for $K_tL_\ell.3$ in which proof search runs in coNP.

All the algorithmic results for tense logic mentioned earlier in this introduction have been obtained via *model-theoretic* techniques, by showing that if a formula has a model, then it has a 'small' one, and it is actually possible to proceed similarly for $K_tL_\ell.3$. However, as the resulting algorithms consist essentially in guessing a model, they are impractical as they are unlikely to avoid the (high) worst case complexity of the problem. In the case of the full linear temporal logic, this has motivated the use of *automata-theoretic* techniques [36, 33, 8, 12], typically by building an at most exponential-sized automaton recognising the set of models of the formula: checking the language non-emptiness of the automaton can then be performed on-the-fly in PSPACE and can rely in practice on a rich algorithmic toolset. However, in the case of tense logic, it is not immediate how to tailor this approach to recover the above NP upper bound, because the automata for tense logic may require exponential-size-over $\omega$, this is a consequence of the proof of [13, Thm. 3]. Finally, if one's interest is to check that a formula $\varphi$ is valid, neither the model-theoretic nor the automata-theoretic approach yields a 'natural' certificate that could be checked by simple independent means.

All these considerations motivate our use of *proof-theoretic* techniques. In their simplest form, those can be Hilbert-style axiomatisations which, in the context of modal logic, allow to characterise valid formulas in a way that is modular with respect to the considered classes of models—incidentally, the name $K_tL_\ell.3$ refers to its axiomatisation (see Appendix A). However, these systems are not directly amenable to automated reasoning, which is rather achieved through more structured proof systems, the seminal example being Gentzen's sequent calculus. As the latter is often too limited for modal logics, it has been enriched in various ways, using e.g. labelled sequents [25], display calculus [5, 19], nested sequents [18, 7, 29, 30, 22], or hypersequents [2, 14, 20, 15]. These enriched formalisms remain quite modular and sustain extensions simply by adding a few rules. They can be exploited to provide optimal complexity solutions to the validity problem directly by proof search [17, 24, 4, 11, 3], which may sometimes avoid the worst-case complexity of the problem and rely in practice on various heuristics. Finally, this approach obviously yields a proof of validity as a certificate in case of success.

Our proof system for $K_tL_\ell.3$ is obtained as a natural extension of our earlier work on $K_t4.3$ [3], using additional insights from Avron's sequent calculus for KL [1]. This is satisfying since $K_tL_\ell.3$ is simply obtained from $K_t4.3$—the tense logic of arbitrary linear time flows—by adding well-foundation to the left, i.e. towards the past (see Section 2), and completes the picture as $K_tQ$ the tense logic of dense linear time flows was also handled in [3]. Specifically, we use the framework of ordered hypersequents with clusters introduced in [3] as an elaboration, with terminating proof search, of Indrzejczak's ordered hypersequent calculus for $K_t4.3$ [15, 16]. Conceptually, re-using the framework required to generalise its semantics. The new semantics is more uniform, and allows us to provide purely proof-theoretic soundness, completeness, and complexity arguments in Section 3, unlike in [3] where soundness builds on a model-theoretic result from [26].

Furthermore, our proof system is easily shown in Section 4 to also address the more precise problems of validity over all the well-founded linear time flows
- of order type $\beta < \alpha + 1$ for a given $\alpha$, and

- of order type exactly $\alpha < \omega^2$.

Such a result seems out of reach of axiomatisations, and yields for instance a coNP decision procedure for validity over $\omega$-words. Finally, using the exponential translation of $FO^2(\langle)$ into tense logic given in [13, Thm. 2], our results yield an optimal NEXP upper bound for satisfiability of the former over ordinals, which was already known from [27]. But more importantly they yield a proof system for $FO^2(\langle)$ over ordinals, which would be challenging to construct directly, because eigenvariables cannot be handled in the usual fashion.

# 2 Tense Logic over Ordinals

## 2.1 Syntax

Tense logic features two unary temporal operators, over a countable set $\Phi$ of propositional variables, with the following syntax:

$$ \varphi ::= \perp | p | \varphi \supset \varphi | G\varphi | H\varphi \qquad (\text{where } p \in \Phi) $$

Formulæ $G\varphi$ and $H\varphi$ are called *modal formulæ*. Intuitively, $G\varphi$ expresses that $\varphi$ holds ‘globally’ in all future worlds, while $H\varphi$ expresses that $\varphi$ holds ‘historically’ in all past worlds. Other Boolean connectives may be encoded from $\perp$ and $\supset$, and as usual $F\varphi = \neg G\neg\varphi$ expresses that $\varphi$ will hold ‘in the future’ and $P\varphi = \neg H\neg\varphi$ that it held ‘in the past.’

## 2.2 Ordinal Semantics

In the case of $K_tL_\ell.3$, our formulæ shall be evaluated on Kripke structures $\mathfrak{M} = (\alpha, V)$, where $\alpha$ is an ordinal and $V: \Phi \to \wp(\alpha)$ is a valuation of the propositional variables. Recall that an ordinal $\alpha$ is seen set-theoretically as $\{\beta \in \text{Ord} | \beta < \alpha\}$. An ordinal is either 0 (the empty linear order), a *limit* ordinal $\lambda$ (such that for all $\beta < \lambda$ there exists $\gamma$ with $\beta < \gamma < \lambda$), or a *successor* ordinal $\alpha + 1$.

Given a structure $\mathfrak{M} = (\alpha, V)$, we define the *satisfaction relation* $\mathfrak{M}, \beta \models \varphi$, where $\beta < \alpha$ and $\varphi$ is a formula, by structural induction on $\varphi$:

$$ \mathfrak{M}, \beta \nvDash \perp $$

$$ \mathfrak{M}, \beta \models p $$

$$ \text{iff } \beta \in V(p) $$

$$ \mathfrak{M}, \beta \models \varphi \supset \psi $$

$$ \text{iff if } \mathfrak{M}, \beta \models \varphi \text{ then } \mathfrak{M}, \beta \models \psi $$

$$ \mathfrak{M}, \beta \models G\varphi $$

$$ \text{iff } \mathfrak{M}, \gamma \models \varphi \text{ for all } \beta < \gamma < \alpha $$

$$ \mathfrak{M}, \beta \models H\varphi $$

$$ \text{iff } \mathfrak{M}, \gamma \models \varphi \text{ for all } \gamma < \beta $$

When $\mathfrak{M}, \beta \models \varphi$, we say that $(\mathfrak{M}, \beta)$ is a *model* of $\varphi$.

► **Example 2.1.** The satisfiable formulæ of $K_tL_\ell.3$ are strictly contained in the set of formulæ satisfiable in $K_t4.3$, i.e. over arbitrary linear orders. For instance, the formula $\varphi_0 = Pp \wedge H(p \supset Pp)$ is satisfiable in $K_t4.3$ but not in $K_tL_\ell.3$, because all its models must contain an infinite decreasing sequence of worlds where $p$ is true. Moreover, $K_tL_\ell.3$ can force models to be of order type greater than $\omega$: for instance, the formula $\varphi_1 = G(p \supset Fp) \wedge G(\neg p \supset F\neg p) \wedge F\neg p \wedge F(p \wedge Gp)$ forces to have a first infinite sequence of worlds not satisfying $p$, followed by a second infinite sequence of worlds satisfying $p$, and all its models $(\alpha, V)$ must have $\alpha \ge \omega \cdot 2$.
### 3 Hypersequents with Clusters

As is often the case with modal logics, Gentzen's sequent calculus does not provide a rich enough framework to obtain complete proof systems. The extension we consider is to use hypersequents [2], which are essentially sets of sequents logically interpreted as a disjunction. Indrzejczak has moved to ordered hypersequents [15, 16] (which are lists of hypersequents) to obtain a sound and complete calculus for $K_t$.4.3. We have further enriched the structure of his ordered hypersequents with clusters and annotations [3] to obtain a calculus for $K_t$.4.3 for which proof search terminates and, in fact, yields an optimal complexity decision procedure. We keep the same structure in the present work, but significantly adapt the proof rules, annotation mechanism, and even the semantics of hypersequents; we discuss these differences in more depth when concluding in Section 5. It should be noted that, unlike simple hypersequents, hypersequents with clusters do not have a translation as formulæ.

#### 3.1 Annotated Hypersequents with Clusters

A sequent (denoted $S$) is a pair of two finite sets of formulæ, written $\Gamma \vdash \Delta$. It is satisfied in a world $\gamma$ of a structure $\mathfrak{M}$ if, in that world, the conjunction of the formulæ of $\Gamma$ implies the disjunction of the formulæ of $\Delta$. In that case, we write $\mathfrak{M}, \gamma \models \Gamma \vdash \Delta$.

We define next the basic structure of our hypersequents, then enrich it with annotations to obtain the hypersequents that we shall work with.

**► Definition 3.1 (hypersequent).** A hypersequent is a list of cells, each cell being either a sequent or a non-empty list of sequents called a (syntactic) cluster. We shall use the following abstract syntax, where both operators ‘;’ and ‘||’ are associative with unit ‘•’:

$$H ::= C \mid H; H \qquad (\text{hypersequents})$$

$$C ::= \bullet \mid S \mid \{Cl\} \qquad (\text{cells})$$

$$Cl ::= S \mid Cl \parallel Cl \qquad (\text{cluster contents})$$

Note that this definition allows for empty cells and hypersequents ‘•’, but these notational conveniences will never arise in actual proofs—and should not be confused with the empty sequent ‘|’. We will see that the order of cells in a hypersequent is semantically relevant, but the order of sequents inside a cluster is not. Nevertheless, assuming an ordering as part of the syntactic structure of clusters is useful in order to refer to specific sequents or positions.

**► Definition 3.2.** An annotated sequent is a sequent that may be annotated with $\mathfrak{G}$ formulæ. We simply write $\Gamma \vdash \Delta$ for a sequent carrying no annotation, otherwise we write, e.g., $\Gamma \vdash \Delta$ ($\mathfrak{G}\varphi, \mathfrak{G}\psi, \dots$). Then, annotated hypersequents are hypersequents whose sequents are annotated, with the constraint that an annotation may only occur once in an annotated hypersequent, and that $\varphi$ occurs on the right-hand side of sequents carrying the annotation $\mathfrak{G}\varphi$. Formally, we can see annotations as partial functions from the set of $\mathfrak{G}$ formulæ to the set of positions of the hypersequent.

**► Example 3.3.** For instance, $\Gamma \vdash \Delta, \varphi$ ($\mathfrak{G}\varphi$); $\{\Pi \vdash \Sigma, \psi$ ($\mathfrak{G}\psi$)} is an annotated hypersequent but $\Gamma \vdash \Delta, \varphi, \psi$ ($\mathfrak{G}\varphi, \mathfrak{G}\psi$); $\{\Pi \vdash \Sigma, \psi$ ($\mathfrak{G}\psi$)} is not allowed due to the two occurrences of ($\mathfrak{G}\psi$). Finally, $\vdash \perp$ ($\mathfrak{G}p$) is not an annotated hypersequent as it fails the second condition.

Annotations will impact the semantics of hypersequents: intuitively, counter-models should attach to sequents annotated with ($\mathfrak{G}\varphi$) a world or set of worlds that invalidates $\varphi$ and is (in a sense that will be made clear below) ‘rightmost’ for that property.
## 3.2 Semantics

The semantics of an ordered hypersequent with clusters relies on a notion of embedding which we define next, building on a view of hypersequents as partially ordered structures.

**► Definition 3.4 (partial order of a hypersequent).** Let $H$ be a hypersequent containing $n$ sequents, counting both the sequents found directly in its cells and those in its clusters. In this context, any $i \in [1; n]$ is called a *position* of $H$, and we write $H(i)$ for the $i$-th sequent of $H$. We define a partial order $\preceq$ on the positions of $H$ by setting $i \preceq j$ if and only if either the $i$-th and $j$-th sequents are in the same cluster, or the $i$-th sequent is in a cell that lies strictly to the left of the cell of the $j$-th sequent. We write $i \prec j$ when $i \preceq j$ but $j \not\preceq i$, i.e. $j$ lies strictly to the right of $i$ in $H$. We write $i \sim j$ when $i \preceq j \preceq i$. Finally, the *domain* of $H$ is defined as $\text{dom}(H) = ([1; n], \preceq)$; note that empty cells are ignored in $\text{dom}(H)$.

While a hypersequent is syntactically a finite partial order, its semantics will refer to a linear well-founded order, obtained by 'bulldozing' its clusters into copies of $\omega$. The resulting order type is the object of the next definition.

**► Definition 3.5 (order type).** Let $H$ be a hypersequent. We define its *order type* $o(H)$ by induction on its structure: for cells, $o(\bullet) = 0$, $o(S) = 1$, and $o(\{Cl\}) = \omega$, and for hypersequents, $o(H_1; H_2) = o(H_1) + o(H_2)$. Thus, $o(H) = \omega \cdot k + m$ where $k$ is the number of clusters in $H$ and $m$ the number of non-empty cells to the right of the rightmost cluster.

**► Definition 3.6 (embedding).** Let $H$ be an annotated hypersequent and $\alpha$ an ordinal. We say that $\mu : \text{dom}(H) \to \alpha + 1 \setminus \{0\}$ is an *embedding* of $H$ into $\alpha$, written $H \hookrightarrow_{\mu} \alpha$, if:

- for all $i, j \in \text{dom}(H)$, $i \prec j$ implies $\mu(i) < \mu(j)$ and $i \sim j$ implies $\mu(i) = \mu(j)$; and

- for all $i \in \text{dom}(H)$, $i$ is in a cluster if and only if $\mu(i)$ is a limit ordinal.

Observe that, if $H \hookrightarrow_{\mu} \alpha$, then $o(H) < \alpha + 1$.

**► Definition 3.7 (semantics).** Let $\mathfrak{M} = (\alpha, V)$ be a structure, $H$ a hypersequent, and $\mu$ an embedding $H \hookrightarrow_{\mu} \alpha$. We say that $\mu$ is *annotation-respecting* if, for all $\varphi$ and $i$ such that $H(i)$ carries the annotation $(G\varphi)$ and for all $\gamma < \alpha$ such that $\mathfrak{M}, \gamma \models \neg\varphi$, we have $\gamma < \mu(i)$.

We say that $(\mathfrak{M}, \mu)$ is a *model* of $H$, written $\mathfrak{M}, \mu \models H$, if $\mu$ is annotation-respecting and there exists a position $i$ of $H$ and an ordinal $\beta < \mu(i)$ such that for all $\gamma$ with $\beta \le \gamma < \mu(i)$ we have $\mathfrak{M}, \gamma \models H(i)$.

Following this definition, we say that a hypersequent is *valid* if for any $\mathfrak{M} = (\alpha, V)$ and annotation-respecting $H \hookrightarrow_{\mu} \alpha$, we have $\mathfrak{M}, \mu \models H$. A formula $\varphi$ is valid in the usual sense (i.e., satisfied in every world of every ordinal structure) if and only if the hypersequent $\vdash \varphi$ is valid in our sense.

If a hypersequent $H$ is not valid, then it has a *counter-model*, that is a structure $\mathfrak{M} = (\alpha, V)$ and an annotation-respecting embedding $H \hookrightarrow_{\mu} \alpha$ such that, for every $i \in \text{dom}(H)$ and $\beta < \mu(i)$, there exists $\gamma$ with $\beta \le \gamma < \mu(i)$ such that $\mathfrak{M}, \gamma \not\models H(i)$. For the positions $i \in \text{dom}(H)$ that are not in clusters, $\mu(i)$ is a successor ordinal $\gamma + 1$ and this amounts to asking that $\mathfrak{M}, \gamma \not\models H(i)$. When $i$ is in a cluster, the condition implies the existence of an infinite increasing sequence $(\gamma_j)_j$ of ordinals with limit $\mu(i) = \sup_j \gamma_j$ such that $\mathfrak{M}, \gamma_j \not\models H(i)$ for all $j$.
<figure><img src="image_3.png" /><figcaption>Figure 1 Propositional rules of $\mathbf{HK_tL_\ell.3}$.</figcaption></figure>

## 3.3 Proof System

We now present our proof system for $\mathbf{K_tL_\ell.3}$, called $\mathbf{HK_tL_\ell.3}$. This system deals with annotated hypersequents; from now on, we simply call sequents and hypersequents their annotated versions. The rules of $\mathbf{HK_tL_\ell.3}$ are given in figures 1 to 3: the first group includes the usual propositional rules, the second deals with modalities, and the last one with annotations. The figures make use of some notations which we explain next, before commenting on the rule definitions themselves.

**Notations.** First, we use hypersequents with *holes*. One hypersequents, cells, and clusters are defined by the following syntax:

$$ H \llbracket \rrbracket ::= H ; C \llbracket \rrbracket ; H \qquad C \llbracket \rrbracket ::= \star | \{ Cl \llbracket \rrbracket \} \qquad Cl \llbracket \rrbracket ::= Cl_{\bullet} \parallel \star \parallel Cl_{\bullet} \qquad Cl_{\bullet} ::= \bullet | Cl $$

Two cells and hypersequents have two holes identified by $\star_1$ and $\star_2$:

$$ H \llbracket \rrbracket ::= H ; C \llbracket \rrbracket ; H \mid H[\star_1] ; H[\star_2] \qquad C \llbracket \rrbracket ::= \{ Cl[\star_1] \parallel Cl[\star_2] \} | \{ Cl[\star_2] \parallel Cl[\star_1] \} $$

As usual, $C[S]$ (resp. $C[Cl]$) denotes the same cell with $S$ (resp. $Cl$) substituted for $\star$; two-placeholder cells and hypersequents with holes behave similarly. In terms of the partial orders underlying hypersequents with two holes, observe that the positions $i$ and $j$ associated resp. to $\star_1$ and $\star_2$ are such that $i \preceq j$.

Second, we do not write explicitly the annotations that sequents may carry in rule applications. These annotations are implicitly the same in a conclusion sequent and the corresponding sequents in premises, or updated by adding the explicit annotation; freshly created sequents always have an explicit annotation. Annotations can prevent a rule application if the addition of an annotation would break the single-annotation constraint.

Third, we use a convenient notation for enriching a sequent: if $S$ is a sequent $\Gamma \vdash \Delta$ (A), then $S \times (\Gamma' \vdash \Delta' (A'))$ is the sequent $\Gamma, \Gamma' \vdash \Delta, \Delta' (A, A')$. Moreover, we sometimes need to enrich an arbitrary sequent of a cluster $\{Cl\}$ with a sequent $S$; then $\{Cl\} \times S$ denotes the cluster with its leftmost sequent enriched.

**Rules.** We now comment on the definition of our rules. The propositional rules of Figure 1 are straightforward: they are the usual ones applied to an arbitrary sequent of the hypersequent. The left modal rules of Figure 2 should not be surprising. For instance, in $(G\vdash)$, if the conclusion has a counter-model, then $G\varphi$ holds at some ordinal and thus both $\varphi$ and $G\varphi$ must also hold at strictly greater ordinals. The rule also applies to two distinct sequents inside the same cluster; the soundness proof below shows how this is covered in detail. The $(\{G\vdash\})$ rule allows to proceed in the same way inside a cluster when the sequent 'further to the right' is the original sequent itself, something that our notations do not allow in $(G\vdash)$. Finally, $(H\vdash)$ and $(\{H\vdash\})$ are symmetric to the two previous rules.
$$ (G\vdash) \frac{H[G\varphi, \Gamma\vdash\Delta][\varphi, G\varphi, \Pi\vdash\Sigma]}{H[G\varphi, \Gamma\vdash\Delta][\Pi\vdash\Sigma]} \qquad \frac{H_1; \{Cl_\bullet \parallel \varphi, G\varphi, \Gamma\vdash\Delta \parallel Cl'_\bullet\}; H_2}{H_1; \{Cl_\bullet \parallel G\varphi, \Gamma\vdash\Delta \parallel Cl'_\bullet\}; H_2} \quad \{\text{G}\vdash\} $$

$$ (H\vdash) \frac{H[\varphi, H\varphi, \Pi\vdash\Sigma][H\varphi, \Gamma\vdash\Delta]}{H[\Pi\vdash\Sigma][H\varphi, \Gamma\vdash\Delta]} \qquad \frac{H_1; \{Cl_\bullet \parallel \varphi, H\varphi, \Gamma\vdash\Delta \parallel Cl'_\bullet\}; H_2}{H_1; \{Cl_\bullet \parallel H\varphi, \Gamma\vdash\Delta \parallel Cl'_\bullet\}; H_2} \quad \{\text{H}\vdash\} $$

$$ \frac{H_1; C[\Gamma\vdash\Delta, G\varphi]; \vdash\varphi (G\varphi); C'; H_2 \\ H_1; C[\Gamma\vdash\Delta, G\varphi]; \{\vdash\varphi (G\varphi)\}; C'; H_2 \\ H_1; C[\Gamma\vdash\Delta, G\varphi] \parallel \vdash\varphi (G\varphi)]; C'; H_2 \quad \text{if } C \neq \star \\ H_1; C[\Gamma\vdash\Delta, G\varphi]; C' \times (\vdash H\varphi); H_2 \quad \text{if } C' \neq \bullet \\ H_1; C[\Gamma\vdash\Delta, G\varphi]; C' \times (\vdash\varphi (G\varphi)); H_2 \quad \text{if } C' \neq \bullet \text{ and } C' \neq \{Cl\}}}{H_1; C[\Gamma\vdash\Delta, G\varphi]; C'; H_2} \quad \{\text{H}\vdash\} $$

$$ \frac{H_2; C'; H\varphi\vdash\varphi; C[\Gamma\vdash\Delta, H\varphi]; H_1 \\ H_2; C' \times (\vdash H\varphi); C[\Gamma\vdash\Delta, H\varphi]; H_1 \quad \text{if } C' \neq \bullet \\ H_2; C' \times (H\varphi\vdash\varphi); C[\Gamma\vdash\Delta, H\varphi]; H_1 \quad \text{if } C' \neq \bullet \text{ and } C' \neq \{Cl\}}}{H_2; C'; C[\Gamma\vdash\Delta, H\varphi]; H_1} \quad \{\text{H}\vdash\} $$

■ **Figure 2** Modal rules of $\mathbf{HK_tL_\ell.3}$. In $(\vdash G)$ and $(\vdash H)$, we allow $C' = \bullet$ only when $H_2 = \bullet$.

$$ ((G)) \frac{H_1[\Gamma \vdash \Delta (G \varphi)]; H_2[\Pi \vdash \Sigma, G \varphi]}{H_1; \Gamma \vdash \Delta, G \varphi (G \varphi); H_2} \quad \{((G))\} $$

$$ ((\bar{G})) \frac{H_1[\Gamma \vdash \Delta (\bar{G} \varphi)]; H_2[\Pi, \varphi \vdash \Sigma]}{H_1[\Gamma \vdash \Delta (\bar{G} \varphi)]; H_2[\Pi \vdash \Sigma]} $$

■ **Figure 3** Annotation rules of $\mathbf{HK_tL_\ell.3}$.

The rules $(\vdash G)$ and $(\vdash H)$ are the most complex ones. We shall not try to justify their soundness at this point, but simply make a few remarks that are important to understand their definition. First, these rules are the only ones that may introduce new cells in hypersequents. In the case of $(\vdash G)$, new cells are annotated with the principal formula $G\varphi$, which prevents another application of $(\vdash G)$ on $G\varphi$ (otherwise a premise would carry this annotation at two positions). Second, the principal cell $C[\Gamma\vdash\Delta, G\varphi]$ in $(\vdash G)$ may be the rightmost cell of the conclusion hypersequent, in which case both $C'$ and $H_2$ are empty, and the rule has two or three premises depending on whether the principal cell is a cluster or not. When the principal cell is not rightmost, then $C'$ is not allowed to be empty, and the rule has one or two extra premises depending on whether $C'$ is a cluster or not. The situation is symmetric for $(\vdash H)$.

Finally, the special rules of Figure 3 are, again, best explained through the soundness proof: they correspond to situations that can be ruled out or simplified by taking into account the annotation-respecting nature of our semantics. These rules are important to be able to extract counter-models from proof search failures (i.e., sequents on which no rule applies).

**Examples.** We have designed our rules so that they are all *invertible*: by keeping in premises all the formulæ from the conclusion, we ensure that validity is never lost by applying a rule; this will be shown formally in Proposition 3.11. In practice, keeping all formulæ can be unnecessarily heavy. Fortunately, it is easy to see that the following weakening rules are
admissible:

$$ (\text{weak} \vdash) \frac{H[\Gamma \vdash \Delta]}{H[\Gamma, \varphi \vdash \Delta]} \qquad \frac{H[\Gamma \vdash \Delta]}{H[\Gamma \vdash \varphi, \Delta]} \quad (\vdash \text{ weak}) $$

**► Example 3.8.** The formula $\varphi_0 = Pp \wedge H(p \supset Pp)$ from Example 2.1 is not satisfiable in $K_tL_\ell.3$, so the dual sequent $S_0 = H(p \supset (H(p \supset \bot) \supset \bot)) \vdash H(p \supset \bot)$ is valid. Here is indeed a proof tree, with implicit uses of propositional and weakening rules, and principal formulæ shown in orange.

$$ (\text{ax}) \frac{\begin{array}{c} H(p \supset \bot), p \vdash p ; S_0 \\ \multicolumn{2}{c}{p \supset (H(p \supset \bot) \supset \bot), H(p \supset \bot), p \vdash ; S_0} \\ \multicolumn{2}{c}{H(p \supset \bot), p \vdash ; H(p \supset (H(p \supset \bot) \supset \bot)) \vdash H(p \supset \bot)} \end{array}}{H(p \supset (H(p \supset \bot) \supset \bot)) \vdash H(p \supset \bot)} \quad (\vdash \text{H}) $$

**► Example 3.9.** Since $\varphi_1 = G(p \supset Fp) \wedge G(\neg p \supset F\neg p) \wedge F\neg p \wedge F(p \wedge Gp)$ from Example 2.1 is satisfiable, its dual sequent $S_1 = G(Gp \supset p), G(p \supset (G(p \supset \bot) \supset \bot)) \vdash Gp, G\varphi$ where $\varphi = p \supset \bot \lor (Gp \supset \bot)$ is invalid, although with no counter-models below $\omega \cdot 2$.

In our calculus, proof search for $S_1$ will succeed on branches not considering at least two clusters; we show below in Figure 4 one such branch, with implicit uses of propositional and weakening rules, and principal formulæ shown in orange.

$$ (\text{ax}) \frac{\begin{array}{c} S_1 ; p \vdash p (Gp) ; \{Gp, p \vdash (G\varphi)\} \\ \multicolumn{2}{c}{S_1 ; p \vdash Gp (Gp) ; \{Gp, p \vdash (G\varphi)\}} \\ \multicolumn{2}{c}{S_1 ; Gp \supset p \vdash p (Gp) ; \{Gp, p \vdash (G\varphi)\}} \\ \multicolumn{2}{c}{\vdots} \\ \multicolumn{2}{c}{G(Gp \supset p), G(p \supset (G(p \supset \bot) \supset \bot)) \vdash Gp, G\varphi ; p \vdash (Gp \supset \bot)} \end{array}}{G(Gp \supset p), G(p \supset (G(p \supset \bot) \supset \bot)) \vdash Gp, G(p \supset \bot \lor (Gp \supset \bot))} \quad (\vdash \text{G}) $$

■ **Figure 4** In a proof of $S_1$ (Example 3.9) branches with a non-cluster cell for $(Gp)$ are provable.

However, proof search will fail on the branch shown in Figure 5, which corresponds to the counter-model described in Section 2.

$$ (\text{ax}) \frac{\begin{array}{c} S_1 ; \{\vdash Gp, p (Gp)\} ; \{Gp, p \vdash (G\varphi) \parallel p \vdash G(p \supset \bot) (G(p \supset \bot))\} \\ \multicolumn{2}{c}{S_1 ; \{\vdash Gp, p (Gp)\} ; \{Gp, p \vdash (G\varphi) \parallel p, p \supset (G(p \supset \bot) \supset \bot) \vdash (G(p \supset \bot))\}} \\ \multicolumn{2}{c}{\vdots} \\ \multicolumn{2}{c}{S_1 ; \{\vdash Gp, p (Gp)\} ; \{Gp, p \vdash G(p \supset \bot) (G\varphi)\}} \\ \multicolumn{2}{c}{S_1 ; \{Gp \supset p \vdash p (Gp)\} ; \{p \supset (G(p \supset \bot) \supset \bot), Gp, p \vdash (G\varphi)\}} \\ \multicolumn{2}{c}{\vdots} \\ \multicolumn{2}{c}{G(Gp \supset p), G(p \supset (G(p \supset \bot) \supset \bot)) \vdash Gp, G\varphi ; \{p \vdash (Gp \supset \bot) ; \{Gp, p \vdash (G\varphi)\}\}} \\ \multicolumn{2}{c}{\vdots} \\ \multicolumn{2}{c}{G(Gp \supset p), G(p \supset (G(p \supset \bot) \supset \bot)) \vdash Gp, G\varphi ; \{Gp, p \vdash (G\varphi)\}} \end{array}}{G(Gp \supset p), G(p \supset (G(p \supset \bot) \supset \bot)) \vdash Gp, G(p \supset \bot \lor (Gp \supset \bot))} \quad (\vdash \text{G}) $$

■ **Figure 5** A failed branch in the proof of $S_1$ (Example 3.9).

## 3.4 Soundness

**► Proposition 3.10.** The rules of $HK_tL_\ell.3$ are sound: if the premises of a rule instance are valid, then so is its conclusion.
**Proof.** We show the contrapositive: considering an application of a rule with a conclusion hypersequent $H$ and a counter-model $(\mathfrak{M}, \mu)$ of $H$ with $\mathfrak{M} = (\alpha, V)$ and $H \hookrightarrow \mu \alpha$, we provide a counter-model of one of the premises (or a contradiction when there is no premise).

Since we will often have to extend an embedding with a value for a new position, we define $\mu + (i \mapsto \alpha)$ as the mapping $\mu'$ such that $\mu'(i) = \alpha$, $\mu'(k) = \mu(k)$ for $k < i$ and $\mu'(k+1) = \mu(k)$ for $k \ge i$ in the domain of $\mu$.

A full proof is given in Appendix B, and we cover here only a few key cases. Consider first an application of $(\vdash_G)$ with $\Gamma \vdash \Delta, G\varphi$ at position $i$, when $C'; H_2$ is empty. For any $\beta_i < \mu(i)$ there exists $\gamma_i$ with $\beta_i \le \gamma_i < \mu(i)$ such that $\mathfrak{M}, \gamma_i \not\models H(i)$, hence there also exists $\gamma'_i > \gamma_i$ such that $\mathfrak{M}, \gamma'_i \not\models \varphi$. Let $\gamma$ be the least ordinal that contains all such $\gamma'_i$. We have that $\mu(i) \le \gamma$.

- If $\mu(i) = \gamma$, then $\mu(i)$ must be a limit ordinal. Hence $C \not\equiv \star$ and the third premise $H_3'$ is available. We construct a counter-model $(\mathfrak{M}, \mu')$ for it by taking $\mu' = \mu + (k \mapsto \gamma)$, where $k = i+1$ is the new position in $H_3'$. Indeed, we have that for any $\beta' < \mu'(k)$ there exists $\gamma'$ with $\beta' \le \gamma' < \mu'(k)$ and $\mathfrak{M}, \gamma' \not\models \varphi$ (the inequality can even be made strict). Moreover, the annotation is respected by definition of $\gamma$: there cannot be any $\lambda \ge \gamma$ such that $\mathfrak{M}, \lambda \not\models \varphi$.

- Otherwise we conclude by observing that $(\mathfrak{M}, \mu')$ is a counter-model of one of the first two premises with $\mu' = \mu + (k \mapsto \gamma)$ where $k$ is the newly created position. We check that $\mu'$ is monotone, because $\mu(i) < \gamma$. If $\gamma$ is a successor ordinal, $(\mathfrak{M}, \mu')$ is a counter-model of the first premise simply because the predecessor of $\gamma$ invalidates $\varphi$ and the annotation is respected; both hold by construction. If $\gamma$ is a limit ordinal we have a counter-model $(\mathfrak{M}, \mu')$ of the second premise: we do have that for any $\beta' < \mu'(k)$ there exists $\gamma'$ with $\beta' \le \gamma' < \mu'(k)$ that invalidates $\varphi$, and the annotation is respected by construction.

When $C'; H_2$ is not empty, we need to consider whether $\gamma$ is less than the ordinal to which the positions of $C'$ are mapped by $\mu$, and use the last two premises when it is not the case.

The case of $(\vdash_H)$ is similar, but simpler in that we can take $\gamma = \lambda + 1$ where $\lambda$ is the least ordinal such that $\mathfrak{M}, \lambda \not\models \varphi$. Finally, annotation rules (Figure 3) rely on the annotation-respecting condition on $\mu$: informally, $\varphi$ cannot be falsified at an ordinal beyond $\mu(i)$ when $i$ carries the annotation $(G\varphi)$, thus the conclusions of $((G))$ and $({(G)})$ cannot have counter-models, and $\varphi$ must be satisfied at ordinals corresponding to $\Pi \vdash \Sigma$ for $((\bar{G}))$. ◀

## 3.5 Completeness and Complexity

As in [3], completeness is a by-product of the very simple proof-search behaviour of our calculus. As we shall see, all the rules are invertible and proof search branches are polynomially bounded, as long as obvious pitfalls are avoided in the search strategy. Thus it is useless to backtrack during proof-search. Moreover, proof attempts result in finite (polynomial depth) partial proofs, whose unjustified leaves yield counter-models that amount (by invertibility) to counter-models of the conclusion. Hence the completeness of our calculus. We detail this argument below, and its corollary: proof-search yields an optimal coNP procedure for validity.

► **Proposition 3.11 (invertibility).** In any rule instance, if a premise has a counter-model, then so does its conclusion.

**Proof.** Considering a rule instance with a counter-model $(\mathfrak{M}, \mu)$ of a premise $H$, we build a counter-model $(\mathfrak{M}, \mu')$ of the conclusion $H'$. Depending on the rule that is applied, $H$ and $H'$ will either have exactly the same structure, or $H$ will have a new cell. Accordingly, we take $\mu'$ to be the restriction of $\mu$ to the positions of $H'$ (and adapt it accordingly for the positions
<figure><img src="image_4.png" /><figcaption>Figure 6 Proof search with a failure hypersequent and an immediately provable hypersequent.</figcaption></figure>

that have been shifted). It is indeed a proper annotation-respecting embedding of $H'$ into $\mathfrak{M}$. It is then easy to see that $(\mathfrak{M}, \mu')$ is a counter-model of $H'$, since any sequent $H'(i)$ is contained in the corresponding sequent $H(j): \mathfrak{M}, \mu(j) \not\models H(j)$ implies $\mathfrak{M}, \mu'(i) \not\models H'(i)$. ◀

We characterise next the proof attempts that we consider for proof search, and show how to extract counter-models when such attempts fail.

**Definition 3.12.** We say that a sequent is immediately provable if it is provable by an application of $(H\vdash)$ or $(\{H\vdash\})$ followed by $(\alphax)$. We call *partial proof* a finite derivation tree whose internal nodes correspond to rule applications, but whose leaves may be unjustified hypersequents, and that satisfies two conditions: any rule application should be such that all premises differ from the conclusion; immediately provable sequents must be proven through $(\alphax)$ and $(H\vdash)$ or $(\{H\vdash\})$. Finally, we call *failure hypersequent* a hypersequent that can only be the conclusion of a rule instance when it is also one of its premises.

Obviously, a hypersequent has a proof if and only if it has a partial proof without unjustified leaves. The two conditions on partial proofs amount to a simple proof search strategy that avoids loops. The second one addresses specifically loops arising from repeated applications of $(\vdash H)$, in branches where several new cells are created for the same $H\varphi$ formula: this results in two cells of the form $\Gamma, H\varphi \vdash \varphi, \Delta$ and thus in an immediately provable hypersequent. This is seen, for example, in the first premise of the third application of rule $(\vdash H)$ in Figure 6. Finally, failure hypersequents correspond to points where proof search is stuck, as with the unjustified hypersequent of Figure 6. We show next that such hypersequents are invalid.

**Proposition 3.13.** Any failure hypersequent $H$ has a counter-model.

**Proof sketch, details in Appendix B.** We construct a counter-model over $\alpha = o(H)$, taking $\mu$ as the only possible embedding, notably satisfying $\mu(i) = \omega \cdot k$ if $i$ belongs to the $k$-th cluster of $H$ and $\mu(i) = \omega \cdot k + m$ if $i$ is the $m$-th cell between the $k$-th and the next cluster (if any). We can then take a function $\text{pos}: \alpha \to \text{dom}(H)$ which maps worlds $\beta < \alpha$ to positions of $H$ in a way that respects the partial order induced by $H$. For a position $i$ that does not belong to a cluster, $\text{pos}(\beta) = i$ if and only if $\beta$ is the predecessor of $\mu(i)$. A position $i$ appearing in a cluster must correspond to an infinite sequence of ordinals of limit $\mu(i)$, so that for all $i \sim j$ and $\beta$, if $\text{pos}(\beta) = i$ then there exists $\gamma$ with $\beta < \gamma < \mu(i) = \mu(j)$ such that $\text{pos}(\gamma) = j$; informally, this ensures that positions $i$ and $j$ inside a cluster are 'infinitely interleaved' within $\mu(i) = \mu(j)$. For example, for the unjustified hypersequent of Figure 5, we could set $\text{pos}(0) = 1$, $\text{pos}(i) = 2$ for all other $i < \omega$, $\text{pos}(\omega + 2j) = 3$ and $\text{pos}(\omega + 2j + 1) = 4$ for all $j \ge 0$. We finally define the valuation $V: \Phi \to \wp(\alpha)$ by $V(p) = \{\beta < \alpha \mid \exists \Gamma, \Delta. H(\text{pos}(\beta)) = (p, \Gamma \vdash \Delta)\}$ and let $\mathfrak{M} = (\alpha, V)$.

We claim that $\mathfrak{M}, \gamma \not\models H(\text{pos}(\gamma))$ for all $\gamma < \alpha$: we prove by induction on $\psi$ that, if $\psi$ appears in the left-hand (resp. right-hand) side of $H(\text{pos}(\gamma))$, then $\mathfrak{M}, \gamma \models \psi$ (resp. $\mathfrak{M}, \gamma \not\models \psi$). Most cases follow a standard argument, we only detail the one where $\psi = G\varphi$ occurs on the
right of $H(\text{pos}(\gamma))$. Since $(\vdash\Gamma)$ does not apply, an annotation must already exist for $\Gamma\varphi$. By rules ((G)) and (({G})) this annotation must be on a position $i$ such that $\text{pos}(\gamma) \preceq i$. By definition of annotations, $\varphi$ occurs on the right of $H(i)$. Hence, there exists $\gamma' > \gamma$ such that $i = \text{pos}(\gamma')$, and $\mathfrak{M}, \gamma' \not\models \varphi$, thus $\mathfrak{M}, \gamma \not\models \Gamma\varphi$.

From there we can check that $H \hookrightarrow\mu \alpha$, and the rule (($\bar{G}$)) enforces that $\mu$ is annotation-respecting. It is then easy to conclude that $(\mathfrak{M}, \mu)$ is a counter-model of $H$. ◀

We now turn to establishing that proof search terminates, and always produces branches of polynomial length. For a hypersequent $H$, let $\text{len}(H)$ be its number of sequents (i.e., the size of $\text{dom}(H)$), and $|H|$ the number of distinct subformulæ occurring in $H$.

**Lemma 3.14 (small branch property).** For any partial proof of a hypersequent $H$, any branch of the proof is of length at most $2(|H| + \text{len}(H) + 1) \cdot |H|$.

**Proof.** Let $H$ be a hypersequent, $\mathcal{P}$ a partial proof of it, and $B$ a branch of $\mathcal{P}$. Remark that the number of positions in hypersequents of $\beta$ is bounded by $|H| + \text{len}(H) + 1$: we have at most $\text{len}(H)$ positions initially, and a new position may only be created once per modal formula among at most $|H|$ formulæ plus possibly one more (overall) to create an immediately provable hypersequent. This is by definition of the annotation system for $\Gamma$ formulæ, and because a second cell created by $(\vdash\Gamma)$ on the same $H\varphi$ would belong to an immediately provable sequent. Any rule application adds some subformulæ among $|H|$ to the left or to the right of the turnstile at a position among $|H| + \text{len}(H) + 1$, hence with $2(|H| + \text{len}(H) + 1) \cdot |H|$ choices. Thus $B$ is of length at most $2(|H| + \text{len}(H) + 1) \cdot |H|$. ◀

We conclude that $\mathbf{HK_tL_3}$ is complete, and also enjoys optimal complexity proof search.

**Theorem 3.15 (completeness).** Every valid hypersequent $H$ has a proof in $\mathbf{HK_tL_3}$.

**Proof.** Assume that $H$ is not provable. Consider a partial proof $\mathcal{P}$ of $H$ that cannot be expanded any more: its leaves cannot be obtained as the conclusion of a rule instance. Such a partial proof exists by Lemma 3.14. Any unjustified leaf of that partial proof has a counter-model by Proposition 3.13, and by invertibility it is also a counter-model of $H$. ◀

**Proposition 3.16.** *Proof search in* $\mathbf{HK_tL_3}$ *is in coNP*.

**Proof.** Proof search can be implemented in an alternating Turing machine maintaining the current hypersequent on its tape, where existential states choose which rule to apply (and how) and universal states choose a premise of the rule. By Lemma 3.14, the computation branches are of length bounded by a polynomial. By Proposition 3.11, the non-deterministic choices in existential states can be replaced by arbitrary deterministic choices, thus the resulting Turing machine has only universal states, hence is in coNP. ◀

# 4 Logic on Given Ordinals

We have designed a proof system that is sound and complete for $\mathbf{K_tL_3}$, and enjoys optimal complexity proof search. We now show that this system can easily be enriched to obtain decision procedures not only for tense logic over arbitrary ordinals, but also for tense logic over specific ordinals. We first observe that the logic can only distinguish ordinals up to $\omega^2$, which should be contrasted with [12]. Then we show how to capture validity over ordinals below some $\omega \cdot k + m$, and finally how to reason over a specific ordinal of this form.

**Proposition 4.1 (small model property).** If a hypersequent $H$ has a counter-model, then it has a counter-model of order type $\alpha < \omega \cdot (|H| + \text{len}(H) + 1)$.
**Proof.** This is a corollary of Theorem 3.15. By the proof of Lemma 3.14, the hypersequents in a failure hypersequent—which are not immediately provable—have at most $|H| + \text{len}(H)$ non-empty cells. The counter-model extracted in Proposition 3.13 from a failure hypersequent $H'$ is over $o(H') < \omega \cdot (|H| + \text{len}(H) + 1)$. A counter-model for $H$ is then obtained by Proposition 3.11, with a different embedding but the same structure. ◀

In particular, for a formula $\varphi$, the hypersequent $H = \vdash \varphi$ has $|H| = |\varphi|$ and $\text{len}(H) = 1$, hence the $\omega \cdot (|\varphi| + 2)$ bound announced in the introduction.

Next we observe that we can easily enrich our calculus to obtain a proof system for tense logic over ordinals below a certain type $\alpha$.

**Proposition 4.2.** Let $\alpha$ be an ordinal. The proof system $\mathbf{HK_tL_\ell.3}$ enriched with the following axiom is sound and complete for tense logic over ordinals $\beta \le \alpha$:

$$ \frac{H}{\text{ord}_\alpha} \text{ if } o(H) > \alpha $$

**Proof.** The soundness argument for the rules of $\mathbf{HK_tL_\ell.3}$ (Proposition 3.10) carries over to the restricted semantics, since the underlying structure (and ordinal) is never modified in the argument. Conversely, the completeness argument of Theorem 3.15 can be strengthened because, thanks to the new rule, we can guarantee that any failure hypersequent $H$ is such that $o(H) \le \alpha$, hence the extracted counter-model is also below this bound. ◀

**Example 4.3.** When extending $\mathbf{HK_tL_\ell.3}$ to check for validity below $\omega$, the failing branch of Figure 5 can be completed, as well as the other failing branches since they all involve hypersequents of order type $\omega \cdot 2$, and $S_1$ becomes provable.

We finally show how to capture validity at a fixed ordinal $\alpha < \omega^2$. The basic idea is to start with a hypersequent $H$ such that $o(H) = \alpha = \omega \cdot k + m$ for some finite $k$ and $m$, and take rule $(\text{ord}_\alpha)$ to forbid larger ordinals. The only catch is that we should check that the formula of interest in valid in all possible positions. Let us write $\{\vdash\}^k$ for $\{\vdash\}; \cdots; \{\vdash\}$ with $k$ clusters containing the empty sequent, and $(\vdash)^m$ for $\vdash; \cdots; \vdash$ with $m$ cells containing the empty sequent.

**Proposition 4.4.** The formula $\varphi$ is valid in all structures of order type exactly $\alpha = \omega \cdot k + m$ if and only if $\mathbf{HK_tL_\ell.3}$ extended with $(\text{ord}_\alpha)$ proves all hypersequents of the form

$$ \{\vdash\}^{k_1} ; \vdash \varphi ; \{\vdash\}^{k_2} ; (\vdash)^m \quad \text{and} \quad \{\vdash\}^k ; (\vdash)^{m_1} ; \vdash \varphi ; (\vdash)^{m_2} $$

where $k_1 + k_2 = k$, $k_2 > 0$ and $m_1 + m_2 = m - 1$. In other words, one must consider all hypersequents $H$ containing one sequent $\vdash \varphi$ and otherwise only empty sequents, and such that $o(H) = \omega \cdot k + m$.

For instance, when $k = m = 0$, $\varphi$ vacuously holds in all worlds of $(0, V)$. When $k = 0$ and $m = 1$ we are checking $\vdash \varphi$ only, and $(\text{ord}_\alpha)$ closes any branch where a new cell is created, rendering modal formulæ trivially true. When $k = 1$ and $m = 0$ we are checking $\vdash \varphi ; \{\vdash\}$.

**Proof.** If $\varphi$ holds in all worlds of all structures of the form $(\alpha, V)$ for some $V$, the hypersequents are valid and thus provable in $\mathbf{HK_tL_\ell.3}$ with $(\text{ord}_\alpha)$. We prove the converse by contradiction. Assume that all the hypersequents hold and $\mathfrak{M}, \beta \not\models \varphi$ for some $\mathfrak{M} = (\alpha, V)$ and $\beta < \alpha$. If $\omega \cdot k_1 \le \beta < \omega \cdot (k_1 + 1)$ with $k_1 + 1 \le k$ we can build an embedding to obtain a counter-model of the first kind of sequent. Otherwise, $\omega \cdot k \le \beta < \omega \cdot k + m$ and we derive a counter-model of the second kind of sequent. ◀
**► Example 4.5.** Consider the formula $G\varphi$ for $\varphi = G \perp \supset \perp$. We cannot prove $G\varphi$ in general, since this formula is not satisfied over finite ordinals, as witnessed by the following partial proof and its failure hypersequent (in the left branch) corresponding to a counter-model over the ordinal 2:

$$ (\vdash\supset) \frac{\begin{array}{c} \vdash G\varphi; \ G\perp\vdash\perp, \varphi(G\varphi) \\ \vdash G\varphi; \ \vdash\varphi(G\varphi) \end{array}}{\vdash G\varphi} \qquad \frac{\begin{array}{c} \vdash G\varphi; \ \{G\perp, \perp\vdash\perp, \varphi(G\varphi)\} \\ \vdash G\varphi; \ \{\textcolor{orange}{G\perp\vdash\perp}, \varphi(G\varphi)\} \\ \vdash G\varphi; \ \{\vdash\varphi(G\varphi)\} \end{array}}{\{G\vdash\}} (\perp) \\ (\vdash\supset) \frac{\begin{array}{c} \vdash G\varphi; \ \{\vdash\varphi(G\varphi)\} \\ \vdash G\varphi; \ \vdash\varphi(G\varphi) \end{array}}{\vdash G\varphi} (\perp) $$

According to Proposition 4.4, over $\alpha = \omega$, i.e., $k = 1$ and $m = 0$, we need to prove $\vdash G\varphi; \{\vdash\}$ in **HK<sub>t</sub>L<sub>l</sub>.3** extended with (**ord<sub>ω</sub>**), for which the presence of the cluster will be crucial. The extra rule (**ord<sub>ω</sub>**) is actually not necessary in this case, but simplifies the proof. We start with an application of ($\vdash G$), this time with three premises:

$$ \frac{\vdash G\varphi; \vdash\varphi(G\varphi); \{\vdash\} \quad \vdash G\varphi; \{\vdash\varphi(G\varphi)\}; \{\vdash\} \quad \vdash G\varphi; \{\vdash G\varphi\}}{\vdash G\varphi; \{\vdash\}} (\vdash G) $$

The first premise is derived as follows:

$$ \frac{\begin{array}{c} \vdash G\varphi; \ G\perp\vdash\perp, \varphi(G\varphi); \{\perp\vdash\} \\ \vdash G\varphi; \ \textcolor{orange}{G\perp\vdash\perp}, \varphi(G\varphi); \{\vdash\} \\ \vdash G\varphi; \ \vdash\varphi(G\varphi); \{\vdash\} \end{array}}{\vdash\supset} (\perp) \\ (\vdash\supset) \frac{\begin{array}{c} \vdash G\varphi; \{\perp\vdash\ G\varphi \parallel G\perp\vdash\perp, \varphi(G\varphi)\} \\ \vdash G\varphi; \{\vdash\ G\varphi \parallel \textcolor{orange}{G\perp\vdash\perp}, \varphi(G\varphi)\} \\ \vdash G\varphi; \{\vdash\ G\varphi \parallel \vdash\varphi(G\varphi)\} \end{array}}{\vdash\supset} (\perp) $$

The middle premise can simply be discharged by (**ord<sub>ω</sub>**). For the last premise, we use ($\vdash G$) inside the cluster, which yields three premises: $\vdash G\varphi; \{\vdash G\varphi\}$; $\vdash\varphi(G\varphi)$ and $\vdash G\varphi; \{\vdash G\varphi\}$; $\{\vdash\varphi(G\varphi)\}$ are discharged by (**ord<sub>ω</sub>**), while the last one is derived as follows:

$$ \frac{\begin{array}{c} \vdash G\varphi; \{\perp\vdash\ G\varphi \parallel G\perp\vdash\perp, \varphi(G\varphi)\} \\ \vdash G\varphi; \{\vdash\ G\varphi \parallel \textcolor{orange}{G\perp\vdash\perp}, \varphi(G\varphi)\} \\ \vdash G\varphi; \{\vdash\ G\varphi \parallel \vdash\varphi(G\varphi)\} \end{array}}{\vdash\supset} (\perp) \\ (\vdash\supset) \frac{\begin{array}{c} \vdash G\varphi; \{\vdash\ G\varphi \parallel \vdash\varphi(G\varphi)\} \\ \vdash G\varphi; \{\vdash\ G\varphi \parallel \vdash\varphi(G\varphi)\} \\ \vdash G\varphi; \{\vdash\ G\varphi \parallel \vdash\varphi(G\varphi)\} \end{array}}{\vdash\supset} (\perp) $$

**5 Related Work and Conclusion**

We have designed the first proof system for **K<sub>t</sub>L<sub>l</sub>.3**, i.e. tense logic over ordinals. Thanks to Indrzejczak's ordered hypersequents [15], enriched with clusters and annotations as in [3], our system enjoys optimal complexity proof search, allows to derive small model properties, and can be extended into a proof system for variants of the logic over bounded or fixed ordinals.

Our ($\vdash H$) rule is broadly related to the rule that Avron uses in his system for **KL** [1]. Unlike Avron, we cannot work with standard sequents due to the presence of converse modalities. In turn, this allows us to consider a somewhat simpler right introduction rule for H, which does not have to take into account HΓ antecedents as they will remain available in the principal cell when a new one is created.

The system most closely related to **HK<sub>t</sub>L<sub>l</sub>.3** is obviously the calculus for **K<sub>t</sub>4.3** [3] in which we introduced the notions of clusters and annotations. These were inspired by the small model property of **K<sub>t</sub>4.3** [26], and it is notable that we could put them to work in the considerably richer setting of **K<sub>t</sub>L<sub>l</sub>.3**; it is the main technical contribution of the present paper. In retrospect, we believe that it is possible to present the semantics of **HK<sub>t</sub>L<sub>l</sub>.3**
hypersequents as a particular case of **HK<sub>t</sub>4.3** hypersequents: the semantics $\mu(i)$ of a position in a cluster would be infinite to the left and right for **HK<sub>t</sub>4.3**, but only infinite to the right for **HK<sub>t</sub>L<sub>ℓ</sub>3**. This shift of perspective, together with the addition of rule ((G)), allows to get rid of the somewhat awkward use of different semantics for the soundness and completeness of **HK<sub>t</sub>4.3**. It also frees the proof-theoretic development from the small model property; in fact, proof theory then allows to derive the small model property just as precisely. Of course, there are also fundamental differences between **HK<sub>t</sub>L<sub>ℓ</sub>3** and **HK<sub>t</sub>4.3**: well-foundedness allows us to take $H\phi$ assumptions in rule (H), which renders (H $\phi$) annotations useless; this benefit of well-foundedness for proof search is usual [1, 4].

References

1 Arnon Avron. On modal systems having arithmetical interpretations. *Journal of Symbolic Logic*, 49(3):935–942, 1984. doi:10.2307/2274147.

2 Arnon Avron. Hypersequents, logical consequence and intermediate logics for concurrency. *Annals of Mathematics and Artificial Intelligence*, 4(3–4):225–248, 1991. doi:10.1007/BF01531058.

3 David Baelde, Anthony Lick, and Sylvain Schmitz. A hypersequent calculus with clusters for linear frames. In *Proc. AiML 2018*, volume 12 of *Advances in Modal Logic*, pages 36–55. College Publications, 2018. To appear. https://hal.inria.fr/hal-01756126.

4 David Baelde, Simon Lunel, and Sylvain Schmitz. A sequent calculus for a modal logic on finite data trees. In *Proc. CSL 2016*, volume 62 of *Leibniz International Proceedings in Informatics*, pages 32:1–32:16. LZI, 2016. doi:10.4230/LIPIcs.CSL.2016.32.

5 Nuel D. Belnap. Display logic. *Journal of Philosophical Logic*, 11(4):375–417, 1982.

6 Patrick Blackburn, Marteen de Rijke, and Yde Venema. *Modal Logic*, volume 53 of *Cambridge Tracts in Theoretical Computer Science*. Cambridge University Press, 2001.

7 Kai Brünnler. Deep sequent systems for modal logic. *Archiv für Mathematische Logik und Grundlagenforschung*, 48(6):551–577, 2009. doi:10.1007/s00153-009-0137-3.

8 Véronique Bruyère and Olivier Carton. Automata on linear orderings. *Journal of Computer and System Sciences*, 73(1):1–24, February 2007. doi:10.1016/j.jcss.2006.10.009.

9 Nino B. Cocchiarella. *Tense and Modal Logic: a Study in the Topology of Temporal Reference*. PhD thesis, University of California, Los Angeles, 1965.

10 Julien Cristau. Automata and temporal logic over arbitrary linear time. In *Proc. FSTTCS 2009*, volume 4 of *Leibniz International Proceedings in Informatics*, pages 133–144. LZI, 2009. doi:10.4230/LIPIcs.FSTTCS.2009.2313.

11 Anupam Das and Damien Pous. A cut-free cyclic proof system for Kleene algebra. In *Proc. Tableaux 2017*, volume 10501 of *Lecture Notes in Computer Science*, pages 261–277. Springer, 2017. doi:10.1007/978-3-319-66902-1_16.

12 Stephane Demri and Alexander Rabinovich. The complexity of linear-time temporal logic over the class of ordinals. *Logical Methods in Computer Science*, 6(4), 2010. doi:10.2168/LMCS-6(4:9)2010.

13 Kousha Etessami, Moshe Y. Vardi, and Thomas Wilke. First-order logic with two variables and unary temporal logic. *Information and Computation*, 179(2):279–295, 2002. doi:10.1006/inco.2001.2953.

14 Andrzej Indrzejczak. Cut-free hypersequent calculus for S4.3. *Bulletin of the Section of Logic*, 41(1/2):89–104, 2012.

15 Andrzej Indrzejczak. Linear time in hypersequent framework. *Bulletin of Symbolic Logic*, 22(1):121–144, 2016. doi:10.1017/bsl.2016.2.
16 Andrzej Indrzejczak. Cut elimination theorem for non-commutative hypersequent calculus. *Bulletin of the Section of Logic*, 46(1/2):135-149, 2017. doi:10.18778/0138-0680.46.1.2.10.

17 Max Kanovich. The multiplicative fragment of linear logic is NP-complete. Technical Report X-91-13, Institute for Language, Logic, and Information, 1991.

18 Ryo Kashima. Cut-free sequent calculi for some tense logics. *Studia Logica*, 53(1):119-135, 1994. doi:10.1007/BF01053026.

19 Marcus Kracht. Power and weakness of the modal display calculus. In *Proof Theory of Modal Logic*, pages 93-121. Springer, 1996.

20 Hidenori Kurokawa. Hypersequent calculi for modal logics extending S4. In *JSAI-isAI 2013, volume 8417 of Lecture Notes in Computer Science*, pages 51-68. Springer, 2014. doi:10.1007/978-3-319-10061-6_4.

21 François Laroussinie, Nicolas Markey, and Philippe Schnoebelen. Temporal logic with forgettable past. In *Proc. LICS 2002*, 2002. doi:10.1109/LICS.2002.1029846.

22 Björn Lellmann. Linear nested sequents, 2-sequents and hypersequents. In *Proc. Tableaux 2015, volume 9323 of Lecture Notes in Computer Science*, pages 135-150. Springer, 2015. doi:10.1007/978-3-319-24312-2_10.

23 Orna Lichtenstein, Amir Pnueli, and Lenore D. Zuck. The glory of the past. In *Proc. Workshop on Logics of Programs*, volume 193 of *Lecture Notes in Computer Science*, pages 196-218. Springer, 1985. doi:10.1007/3-540-15648-8_16.

24 Patrick Lincoln, John Mitchell, Andre Scedrov, and Natarajan Shankar. Decision problems for propositional linear logic. *Annals of Pure and Applied Logic*, 56(1-3):239-311, 1992. doi:10.1016/0168-0072(92)90075-B.

25 Sara Negri. Proof analysis in modal logic. *Journal of Philosophical Logic*, 34(5):507-544, 2005. doi:10.1007/s10992-005-2267-3.

26 Hiroakira Ono and Akira Nakamura. On the size of refutation Kripke models for some linear modal and tense logics. *Studia Logica*, 39(4):325-333, 1980. doi:10.1007/BF00713542.

27 Martin Otto. Two variable first-order logic over ordered domains. *Journal of Symbolic Logic*, 66(2):685-702, 2001. doi:10.2307/2695037.

28 Amir Pnueli. The temporal logic of programs. In *FOCS 1977*, pages 46-57. IEEE, 1977. doi:10.1109/SFCS.1977.32.

29 Francesca Poggiolesi. The method of tree-hypersequents for modal propositional logic. In *Proc. Trends in Logic IV*, volume 28 of *Trends in Logic*, pages 31-51. Springer, 2009. doi:10.1007/978-1-4020-9084-4_3.

30 Francesca Poggiolesi. A purely syntactic and cut-free sequent calculus for the modal logic of provability. *The Review of Symbolic Logic*, 2(4):593-611, 2009. doi:10.1017/S1755020309990244.

31 Arthur N. Prior. *Time and Modality*. Oxford University Press, 1957.

32 Alexander Rabinovich. Temporal logics over linear time domains are in PSPACE. *Information and Computation*, 210:40-67, 2012. doi:10.1016/j.ic.2011.11.002.

33 Gareth S. Rohde. *Alternating Automata and the Temporal Logic of Ordinals*. PhD thesis, University of Illinois at Urbana-Champaign, 1997.

34 A. Prasad Sistla and Edmund M. Clarke. The complexity of propositional linear temporal logics. *Journal of the ACM*, 32(3):733-749, 1985. doi:10.1145/3828.3837.

35 A. Prasad Sistla and Lenore D. Zuck. Reasoning in a restricted temporal logic. *Information and Computation*, 102(2):167-195, 1993. doi:10.1006/inco.1993.1006.

36 Moshe Y Vardi and Pierre Wolper. An automata-theoretic approach to automatic program verification. In *LICS 1986*, pages 322-331. IEEE, 1986.
A Axiomatisation

For reference, the logic $K_tL_\ell.3$ can also be defined as the set of theorems generated by necessitation, modus ponens and substitution from classical tautologies and the following axioms [6, Ch. 4]:

$$ G(p \supset q) \supset (Gp \supset Gq) \qquad (K_r) $$

$$ H(p \supset q) \supset (Hp \supset Hq) \qquad (K_\ell) $$

$$ p \supset GPp \qquad (t_r) $$

$$ p \supset HFp \qquad (t_\ell) $$

$$ Fp \wedge Fq \supset F(p \wedge Fq) \vee F(p \wedge q) \vee F(q \wedge Fp) \qquad (.3_r) $$

$$ Pp \wedge Pq \supset P(p \wedge Pq) \vee P(p \wedge q) \vee P(q \wedge Pp) \qquad (.3_\ell) $$

$$ H(H\phi \supset \phi) \supset H\phi \qquad (L_\ell) $$

The first two axioms are simply the Kripke schema, given for each modality. Next we find the t axioms, which force the two modalities to be converses of each other. The canonical models of the trichotomy axioms .3 have accessibility relationships that are non-branching to the left and to the right. Finally, the axiom ($L_\ell$) of Gödel-Löb ensures that the models are transitive and well-founded to the left.

B Detailed Proofs

► **Proposition 3.10.** The rules of $HK_tL_\ell.3$ are sound: if the premises of a rule instance are valid, then so is its conclusion.

*Proof.* We show the contrapositive: considering an application of a rule with a conclusion hypersequent $H$ and a counter-model $(\mathfrak{M}, \mu)$ of $H$ with $\mathfrak{M} = (\alpha, V)$ and $H \hookrightarrow \mu \alpha$ an annotation-respecting embedding, we provide a counter-model of one of the premises (or a contradiction when there is no premise).

Since we will often have to extend an embedding with a value for a new position, we define $\mu + (i \mapsto \alpha)$ as the mapping $\mu'$ such that $\mu'(i) = \alpha$, $\mu'(k) = \mu(k)$ for $k < i$ and $\mu'(k+1) = \mu(k)$ for $k \ge i$ in the domain of $\mu$.

The case of propositional rules (Figure 1) is immediate: The usual reasoning applies to the principal sequent, and the same embedding is used to obtain a counter-model of one of the premises.

Next we turn to the modal rules of Figure 2:

- Consider the case of $(G\vdash)$, applied with $G\varphi, \Gamma \vdash \Delta$ at position $i$ and $\Pi \vdash \Sigma$ at position $j$ such that $i \preceq j$. Remark that the rule ensures that $i \neq j$, but we do not need this assumption to justify it. We show that $(\mathfrak{M}, \mu)$ is an annotation-respecting counter-model of the premise $H'$, concentrating on the only difference with $H$, at position $j$. For clarity we distinguish two cases:

- When $i \prec j$, we also have $\mu(i) < \mu(j)$. Since $(\mathfrak{M}, \mu)$ is a counter-model of $H$, by taking an arbitrary $\beta_i < \mu(i)$ we obtain $\gamma_i$ such that $\beta_i \le \gamma_i < \mu(i)$ such that $\mathfrak{M}, \gamma_i \not\models H(i)$. In particular, $\mathfrak{M}, \gamma_i \models G\varphi$. Now, considering an arbitrary $\beta < \mu(j)$ we need to exhibit $\gamma$ such that $\beta \le \gamma < \mu(j)$ and $\mathfrak{M}, \gamma \not\models H'(j)$. By taking $\beta_j = \max(\beta, \mu(i)) < \mu(j)$ we obtain $\gamma_j$ such that $\beta_j \le \gamma_j < \mu(j)$ and $\mathfrak{M}, \gamma_j \not\models H(j)$. Furthermore, since $\gamma_i < \mu(i) \le \beta_j \le \gamma_j$, we also have $\mathfrak{M}, \gamma_j \models \varphi$ and $\mathfrak{M}, \gamma_j \models G\varphi$, hence $\mathfrak{M}, \gamma_j \not\models H'(j)$.
- When $i \sim j$ we have that $\mu(i) = \mu(j)$ and it is a limit ordinal because we are considering positions in a cluster. Consider an arbitrary $\beta < \mu(i)$. There exists $\gamma_i$ such that $\beta \le \gamma_i < \mu(i)$ and $\mathfrak{M}, \gamma_i \not\models H(i)$. Because $\mu(i)$ is a limit ordinal, $\gamma_i + 1 < \mu(i) = \mu(j)$. Again, there exists $\gamma_j$ such that $\gamma_i + 1 \le \gamma_j < \mu(j)$ and $\mathfrak{M}, \gamma_j \not\models H(j)$. But, since $\gamma_i < \gamma_j$ we also have that $\gamma_j$ satisfies $\varphi$ and $\mathfrak{G}\varphi$, hence $\mathfrak{M}, \gamma_j \not\models H'(j)$.

- The case of rule $(\{G\vdash\})$ is covered by the second part of the previous argument, by taking $i = j$. Indeed, we have $i \sim i$ when $(\{G\vdash\})$ applies at position $i$.

- Consider now an application of rule (H$\vdash$) with $\Pi \vdash \Sigma$ at position $i$ and $H\varphi, \Gamma \vdash \Delta$ at $j$. We have $i \preceq j$, hence $\mu(i) \le \mu(j)$. Consider an arbitrary $\beta < \mu(i)$. There exists $\gamma_i$ such that $\beta \le \gamma_i < \mu(i)$ and $\mathfrak{M}, \gamma_i \not\models H(i)$. We claim, as before, that there exists $\gamma_j$ such that $\gamma_i < \gamma_j < \mu(j)$ and $\mathfrak{M}, \gamma_j \not\models H(j)$. Indeed, if $\mu(i) < \mu(j)$ then there exists $\gamma_j$ with $\mu(i) \le \gamma_j < \mu(j)$ that falsifies $H(j)$. Otherwise $\mu(i) = \mu(j)$ but then this must be a limit ordinal and, by considering $\gamma_i + 1 < \mu(i) = \mu(j)$ we obtain $\gamma_i < \gamma_j < \mu(j)$ that invalidates $H(j)$. Having $\mathfrak{M}, \gamma_j \not\models H(j)$, we also have $\mathfrak{M}, \gamma_j \models H\varphi$. Thus $\gamma_i$ satisfies $\varphi$ and $H\varphi$, and $\mathfrak{M}, \gamma_i \not\models H'(i)$ as needed.

- The case of $(\{H\vdash\})$ is covered by the previous argument.

- Consider an application of $(\vdash_G)$ with $\Gamma \vdash \Delta, G\varphi$ at position $i$. For any $\beta_i < \mu(i)$ there exists $\gamma_i$ with $\beta_i \le \gamma_i < \mu(i)$ such that $\mathfrak{M}, \gamma_i \not\models H(i)$, and thus $\mathfrak{M}, \gamma_i \not\models G\varphi$. Hence there also exists $\gamma'_i > \gamma_i$ such that $\mathfrak{M}, \gamma'_i \not\models \varphi$. Let $\gamma$ be the least ordinal that contains all such $\gamma'_i$. We have that $\mu(i) \le \gamma$.

We now distinguish several cases regarding $\gamma$. When $C'$; $H_2$ is not empty let $j$ be the first position of the conclusion hypersequent that is in $C'$.

- If $\mu(i) = \gamma$, then $\mu(i)$ must be a limit ordinal. Hence $C \not\models \star$ and the third premise $H'_3$ is available. We construct a counter-model $(\mathfrak{M}, \mu')$ for it by taking $\mu' = \mu + (k \mapsto \gamma)$, where $k = i + 1$ is the new position in $H'_3$. Indeed, we have that for any $\beta' < \mu'(k)$ there exists $\gamma'$ with $\beta' \le \gamma' < \mu'(k)$ and $\mathfrak{M}, \gamma' \not\models \varphi$ (the inequality can even be made strict). Moreover, the annotation is respected by definition of $\gamma$: there cannot be any $\lambda \ge \gamma$ such that $\mathfrak{M}, \lambda \not\models \varphi$.

- If $C'$; $H_2$ is empty, or $\gamma < \mu(j)$, we conclude by observing that $(\mathfrak{M}, \mu')$ is a counter-model of one of the first two premises with $\mu' = \mu + (k \mapsto \gamma)$ where $k$ is the position of the new cell in these premises. We check that $\mu'$ is monotone, because $\mu(i) < \gamma$, and $\gamma < \mu(j)$ when it is defined. If $\gamma$ is a successor ordinal, $(\mathfrak{M}, \mu')$ is a counter-model of the first premise simply because the predecessor of $\gamma$ invalidates $\varphi$ and the annotation is respected; both hold by construction. If $\gamma$ is a limit ordinal we have a counter-model $(\mathfrak{M}, \mu')$ of the second premise: we do have that for any $\beta' < \mu'(k)$ there exists $\gamma'$ with $\beta' \le \gamma' < \mu'(k)$ that invalidates $\varphi$, and the annotation is respected by construction.

- Otherwise $\mu(j) \le \gamma$.

* If $\mu(j) < \gamma$, we obtain a counter-model $(\mathfrak{M}, \mu)$ of the fourth premise $H'_4$. We check it for the only position whose sequent has changed between $H$ and $H'_4$, that is position $j$. Take any $\beta_j < \mu(j)$. We know that there exists $\gamma_j$ with $\beta_j \le \gamma_j < \mu(j)$ such that $\mathfrak{M}, \gamma_j \not\models H(j)$. But, since $\gamma_j < \mu(j) < \gamma$, there exists $\delta$ such that $\gamma_j < \delta < \gamma$ and $\mathfrak{M}, \delta \not\models \varphi$. Thus $\mathfrak{M}, \gamma_j \not\models G\varphi$, and $\mathfrak{M}, \gamma_j \not\models H'_4(j)$.

* If $\mu(j) = \gamma$ and is a limit ordinal, we also obtain a counter-model $(\mathfrak{M}, \mu)$ of the fourth premise. This time, for any $\beta_j < \mu(j)$, we know that there exists $\gamma_j$ with $\beta_j \le \gamma_j < \mu(j)$ such that $\mathfrak{M}, \gamma_j \not\models H(j)$. But, since $\gamma_j < \gamma$ and $\gamma$ is a limit ordinal, there still exists $\delta$ such that $\gamma_j < \delta < \gamma$ and $\mathfrak{M}, \delta \not\models \varphi$. Thus $\mathfrak{M}, \gamma_j \not\models G\varphi$, and $\mathfrak{M}, \gamma_j \not\models H'_4(j)$.
* Finally, if $\mu(j) = \gamma$ and is not a limit ordinal, then the position $j$ is not in a cluster, so the fifth premise is available. We claim that it admits $(\mathfrak{M}, \mu)$ as a counter-model. Let $\theta$ be the predecessor of $\gamma = \theta + 1$, which satisfies $\mathfrak{M}, \theta \not\models \varphi$ by definition of $\gamma$. Since $(\mathfrak{M}, \mu)$ is a counter-model of $H$ we also have $\mathfrak{M}, \theta \not\models H(j)$. This allows us to conclude, together with the fact that, as before, the new annotation is respected by definition of $\gamma$ (there cannot be any $\lambda \ge \gamma$ such that $\mathfrak{M}, \lambda \not\models \varphi$).

- Finally we consider an application of rule (†H) with $\Gamma \vdash \Delta, H\varphi$ at position $i$. Let $j$ be the first position of $C'$, if it exists. For any $\beta_i < \mu(i)$ there exists $\gamma_i$ with $\beta_i \le \gamma_i < \mu(i)$ that invalidates $H(i)$, thus there exists $\gamma'_i < \gamma_i < \mu(i)$ such that $\mathfrak{M}, \gamma'_i \not\models \varphi$. Let $\gamma$ be the successor of the least ordinal among all such $\gamma'_i$. We have $\gamma < \mu(i)$.

- If $H_2; C'$ is empty, or $\mu(j) < \gamma$, then $(\mathfrak{M}, \mu')$ is a counter-model of the first premise with $\mu' = \mu + (k \mapsto \gamma)$ where $k$ is the new position in that premise. We do have that the predecessor of $\gamma$ satisfies $H\varphi$ (by minimality) but not $\varphi$ (by definition). Moreover, $\mu'$ is indeed annotation-respecting.

- If $\mu(j) = \gamma$ then $C'$ cannot be a cluster, because $\gamma$ is a successor. In that case $(\mathfrak{M}, \mu)$ directly yields a counter-model of the third premise.

- Otherwise $\gamma < \mu(j)$ and $(\mathfrak{M}, \mu)$ is a counter-model of the second premise.

We finally consider the case of annotation rules (Figure 3):

- Consider an application of ((G)), with $H(i) = \Gamma \vdash \Delta (G\varphi)$ and $H(j) = \Pi \vdash \Sigma, G\varphi$, and $i < j$. By definition of an embedding, we have $\mu(i) < \mu(j)$. Since $(\mathfrak{M}, \mu)$ is a counter-model of $H$, there exists $\gamma_j$ such that $\mu(i) \le \gamma_j < \mu(j)$ and $\mathfrak{M}, \gamma_j \not\models H(j)$. There also exists $\gamma_i < \mu(i)$ such that $\mathfrak{M}, \gamma_i \not\models H(i)$. Hence there exists $\gamma' > \gamma_j$ such that $\mathfrak{M}, \gamma' \not\models \varphi$. A fortiori, $\gamma' > \gamma_i$, so $\mu$ does not respect the annotation on $i$, contradiction.

- Consider an application of (({G})) with $H(i) = \Gamma \vdash \Delta, G\varphi$ ($G\varphi$). For any $\beta < \mu(i)$ there exists $\gamma$ with $\beta < \gamma$ such that $\mathfrak{M}, \gamma \not\models \varphi$. Because $\mu$ is annotation-respecting, we must have $\gamma < \mu(i)$, thus $\mu(i)$ is a limit ordinal. This contradicts the fact that $i$ is not in a cluster.

- Consider an application of ((\bar{G})) with $\Gamma \vdash \Delta (\bar{G}\varphi)$ at position $i$ and $\Pi \vdash \Sigma$ at position $j$, with $i < j$. Since $\mu$ is annotation-respecting we have that, for all $\lambda \ge \mu(i)$, $\mathfrak{M}, \lambda \models \varphi$. Hence $(\mathfrak{M}, \mu)$ is a counter-model of the premise. ◀

**Proposition 3.13.** Any failure hypersequent $H$ has a counter-model.

*Proof.* Let $\alpha = o(H)$. We define $\mu : \text{dom}(H) \to \alpha + 1 \setminus \{0\}$ as follows:

$\mu(i) = m$ if $i$ is the $m$-th cell of $H$ and appears before its first cluster;

$\mu(i) = \omega \cdot k$ if $i$ belongs to the $k$-th cluster of $H$;

$\mu(i) = \omega \cdot k + m$ if $i$ is the $m$-th cell between the $k$-th and the next cluster (if any).

Now let $\text{pos} : \alpha \to \text{dom}(H)$ be a function such that:

(a) $\forall \beta < \beta' < \alpha, \text{pos}(\beta) \preceq \text{pos}(\beta')$

(b) $\forall \beta < \alpha, \forall i \in \text{dom}(H), \beta < \mu(i) \Leftrightarrow (\text{pos}(\beta) \preceq i \text{ or } \text{pos}(\beta) = i)$

(c) $\forall \beta < \alpha, \forall i \in \text{dom}(H), \text{pos}(\beta) \preceq i \Rightarrow \exists \beta < \gamma < \mu(i), i = \text{pos}(\gamma)$

There always exists one such function. Its choice is quite constrained due to the definitions of $\alpha$ and $\mu$. Positions $i$ that are not in a cluster will be such that $i = \text{pos}(\beta)$ for a single $\beta$, typically the predecessor of $\mu(i)$. A position $i$ appearing in a cluster must correspond to an infinite sequence of ordinals of limit $\mu(i)$, so that for all $i \sim j$ and $\beta$, if $\text{pos}(\beta) = i$ then
there exists $\gamma$ with $\beta < \gamma < \mu(i) = \mu(j)$ such that $\text{pos}(\gamma) = j$; informally, this ensures that positions $i$ and $j$ inside a cluster are 'infinitely interleaved' within $\mu(i) = \mu(j)$.

We finally define a valuation $V: \Phi \to \wp(\alpha)$ by $V(p) = \{\beta < \alpha \mid \exists \Gamma, \Delta. H(\text{pos}(\beta)) = (p, \Gamma \vdash \Delta)\}$ and let $\mathfrak{M} = (\alpha, V)$. We now claim that $\mathfrak{M}, \gamma \not\models H(\text{pos}(\gamma))$ for all $\gamma < \alpha$: we prove by induction on $\psi$ that, if $\psi$ appears in the left-hand (resp. right-hand) side of the turnstile in $H(\text{pos}(\gamma))$, then $\mathfrak{M}, \gamma \nvDash \psi$ (resp. $\mathfrak{M}, \gamma \not\Vdash \psi$).

- If $\psi$ is an atom $p \in \Phi$ the results follow by definition of $V$, and because $(ax)$ does not apply to $H$. The propositional cases are obtained by induction hypothesis, because the corresponding rules of Figure 1 have already been applied.

- The cases of modal formulæ on the left-hand side are similar, we only detail that of $H$. If $\psi = H\varphi$ occurs on the left-hand side of $H(\text{pos}(\gamma))$ then by $(H\vdash)$ and $(\{H\vdash\})$, the formula $\varphi$ must occur on the left-hand side of any $H(i)$ with $i \preceq \text{pos}(\gamma)$. Moreover, for all $\gamma' < \gamma$, we have $\text{pos}(\gamma') \preceq \text{pos}(\gamma)$ by (a), so $\mathfrak{M}, \gamma' \nvDash \varphi$, and thus $\mathfrak{M}, \gamma \nvDash \psi$.

- Assume that $\psi = G\varphi$ occurs on the right of $H(\text{pos}(\gamma))$. Since $(\vdash G)$ does not apply, an annotation must already exist for $G\varphi$. By rules ((G)) and ((G)}) this annotation must be on a position $i$ such that $\text{pos}(\gamma) \preceq i$. By definition of annotations, $\varphi$ occurs on the right of $H(i)$. By (c), there exists $\gamma' > \gamma$ such that $i = \text{pos}(\gamma')$. We then have $\mathfrak{M}, \gamma' \not\Vdash \varphi$, thus $\mathfrak{M}, \gamma \not\Vdash G\varphi$.

- Assume finally that $\psi = H\varphi$ occurs on the right of $H(\text{pos}(\gamma))$. We prove by a sub-induction on $\text{pos}(\gamma)$ that $\mathfrak{M}, \gamma \not\models H\varphi$. Since $(\vdash H)$ does not apply, and since the first premise necessarily differs from the conclusion, it must be that there is a cell $C'$ preceding the cell that contains $\text{pos}(\gamma)$, and that the last two premises (if available) would coincide with $H$. Let $i$ be the first position in $C'$. Take an arbitrary $\lambda < \mu(i)$ such that $\text{pos}(\lambda) = i$ (such a $\lambda$ always exists, thanks to (b) and (c) instantiated with $\beta = 0$). Since $i < \text{pos}(\gamma)$ it must be that $\lambda < \gamma$. As noted above, we have either that $H\varphi$ belongs to the right-hand side of $H(i)$, or that $\varphi$ belongs to its left-hand side. In the first case, we obtain $\mathfrak{M}, \lambda \nvDash H\varphi$ by induction hypothesis on $i < \text{pos}(\gamma)$. In the second case we directly have $\mathfrak{M}, \lambda \nvDash \varphi$. We conclude either way that $\mathfrak{M}, \gamma \not\models H\varphi$.

We can check that $H \hookrightarrow \mu \alpha$: the conditions of Definition 3.6 hold by construction.

We must also check that $\mu$ is annotation-respecting. Assume that $H(i)$ carries the annotation $(G\varphi)$, and that there is a world $\mathfrak{M}, \beta \nvDash \varphi$. Let $j = \text{pos}(\beta)$. If $j \preceq i$, then by (c) there exists $\gamma$ with $\beta < \gamma < \mu(i)$ such that $i = \text{pos}(\gamma)$, so $\beta < \mu(i)$ as expected. If $i < j$, then by the rule (($\tilde{G}$)) $\varphi$ occurs on the left of $H(j)$, contradicting $\mathfrak{M}, \beta \nvDash \varphi$. Otherwise, $i = j$ and by (b) we have $\beta < \mu(\text{pos}(\beta)) = \mu(i)$ as expected.

Finally, $(\mathfrak{M}, \mu)$ is a counter-model of $H$. Indeed, for all $i \in \text{dom}(H)$ and $\beta < \mu(i)$ there exists $\gamma$ with $\beta \le \gamma < \mu(i)$ such that $\text{pos}(\gamma) = i$, and hence $\mathfrak{M}, \gamma \not\models H(i)$: if $\text{pos}(\beta) = i$, we can take $\gamma = \beta$, else (b) enforces $\text{pos}(\beta) \preceq i$, and (c) provides one such $\gamma$. $\quad$