Making progress: Reducibility Candidates and Cut Elimination in the Ill-founded Realm Gianluca Curzi and Graham E. Leigh Abstract . Ill-founded (or non-wellfounded) proof systems have emerged as a natural framework for inductive and coinductive reasoning. In such systems, soundness relies on global correctness criteria, such as the progressivity condition. Ensuring that these criteria are preserved under infinitary cut elimination remains a central technical challenge in ill-founded proof theory. In this paper, we present two cut elimination arguments for ill-founded μ ​ 𝖬𝖠𝖫𝖫 \mu\mathsf{MALL} – a fragment of linear logic extended with fixed-points – based on the reducibility candidates technique of Tait and Girard. In both arguments, preservation of progressivity follows directly from the defining properties of the reducibility candidates. In particular, the second argument is derived from the topological notion of internally closed set developed in previous work by Afshari and Leigh. 1. Introduction Since their early development, infinitary proofs have played a prominent role in modern proof theory. Their systematic study was initiated by Schütte, who showed cut elimination for an infinitary extension of Peano arithmetic [ 31 , 32 ] , where the presence of the \omega -rule – an infinitely branching rule replacing the induction scheme – makes the corresponding notion of proof infinite in breadth while remaining well-founded. Specifically, Schütte’s cut elimination argument was formulated as a transfinite process indexed by ordinals, with termination ensured by a well-founded measure on proof height. This framework was later refined by Mints who emphasised the role of continuity in proof transformations [ 25 ] . Since this pioneering work, infinitary proof systems and their cut elimination techniques have been extensively studied, providing a valuable setting for establishing consistency proofs and conservativity results for theories of arithmetic and analysis (see, e.g., [ 8 , 40 , 38 ] ). Over the past two decades, however, alternative notions of infinitary proof have emerged that relax the requirement of well-foundedness (while often reintroducing finite branching). Motivated by the study of first-order inductive definitions [ 6 , 7 ] , but anticipated in the seminal work of Niwinski and Walukiewicz on the modal \mu -calculus [ 26 ] , ill-founded (or non-wellfounded) proofs offer an ideal proof-theoretic framework for inductive and coinductive reasoning. Research on ill-founded proofs has been applied to a wide range of areas, including automata theory [ 13 ] , games [ 27 ] , theories of arithmetic [ 34 ] , (modal) \mu -calculi [ 35 ] , complexity [ 10 ] , and type theory [ 15 ] . In ill-founded proof systems, soundness is no longer guaranteed by local inductive arguments. Instead, it appeals to global correctness criteria . Among these criteria, the most commonly adopted in the literature is the progressivity (or trace ) condition, typically satisfied whenever a syntactically determined feature occurs infinitely often along each infinite branch of a proof. Other examples of criteria include bouncing threads, induction orders, semantic productivity, and automata-based conditions (see, e.g., [ 35 , 36 , 3 ] ). A major focus of ill-founded proof theory is on circular or cyclic proofs, that is, proofs whose underlying tree is (possibly infinite but) regular – i.e., having only finitely many distinct subtrees. Owing to their finite presentability, cyclic proofs are typically expressed as finite, possibly cyclic, graphs and can be viewed as a natural ill-founded counterpart of traditional inductively presented proofs. A growing body of research in this topic is devoted to the family of fixed-point logics , which integrate finitary logics with least and greatest fixed points. Notable examples include the family of modal \mu -calculi [ 24 ] , fixed-point formulations of intuitionistic logic ( \mu\mathsf{LJ} ) [ 9 , 11 ] and of linear logic and its fragments (such as \mu\mathsf{LL} and \mu\mathsf{MALL} ) [ 5 , 4 ] . When nesting and interleaving of fixed points are permitted, fixed-point logics are well suited to express very general forms of (co)inductive definitions and corresponding (co)inductive reasoning principles. From a computational perspective, fixed-point logics that admit a constructive interpretation – such as \mu\mathsf{LJ} , \mu\mathsf{LL} and \mu\mathsf{MALL} – can be used to model sophisticated (co)inductive data structures and (co)recursion mechanisms. A detailed account of the computational strength of these logics (both in the inductive and cyclic presentation) can be found in [ 11 ] . This paper focuses on \mu\mathsf{MALL} , the fixed-point extension of multiplicative additive linear logic ( \mathsf{MALL} ), which can be obtained from classical logic by removing the structural rules of contraction and weakening. Its key feature is the presence of two (non-equivalent) formulations of the connectives \wedge and \vee : the multiplicatives (resp., \otimes and \invamp ), and the additives (resp., \with and \oplus ). The “exponentials” of linear logic, which control the use of weakening and contraction, can be simulated by fixed points in \mu\mathsf{MALL} [ 5 ] , thus making this logic a general framework for studying the theory of (co-)induction. The introduction of ill-founded proofs challenges one of the central tools of proof theory: cut elimination. When proofs can be infinite in depth , Schütte-style termination arguments are no longer applicable, and a conceptual shift becomes necessary. One approach is to reformulate cut elimination as an infinitary – possibly transfinite, ordinal-indexed – rewriting process that converges to a cut-free proof in the limit. This perspective draws on notions and techniques from topology (such as continuity and metric completion) or coinductive reasoning. In particular, when the rewriting process has a countable number of steps, the existence of the limit proof boils down to showing that all finite approximations can be computed in finitely many steps, a property commonly referred to as productivity . The use of infinite rewriting for cut elimination in an ill-founded setting is not, in itself, a novel idea. Infinitary rewriting techniques have been studied systematically since the 1990s in variety of contexts, including first-order and higher-order rewrite systems [ 16 , 23 ] , and infinitary extensions of the \lambda -calculus [ 22 ] . What ill-founded proof theory brings to this topic, rather, lies in the proof-theoretic methods developed to ensure that the infinitary cut elimination procedures preserve the global correctness conditions mentioned above, thereby yielding sound cut-free limit proofs whenever they are applied to sound proofs. One of the earliest and more general approaches to cut elimination for cyclic and ill-founded proofs was introduced by Santocanale in [ 19 ] for a fragment of \mu\mathsf{MALL} , and was later extended to full \mu\mathsf{MALL} by Baelde et al in [ 4 ] . The core idea is to define a (possibly infinite) rewriting strategy that stepwise pushes cuts upward, giving priority to the bottommost ones. To avoid technical complications such as cut permutations, this approach often resorts to the multicut rule, a macro rule representing a series of consecutive cuts. In recent years, a variety of alternative cut elimination techniques have been proposed, such as the use of fixed-point theorems for contractive maps over ultrametric spaces [ 29 , 30 , 33 ] , notions of run [ 14 ] , or domain-theoretic approaches [ 1 ] . Nonetheless, many of these methods rely on features specific of the systems considered, and do not readily extend to different or more general settings. Proving that infinitary cut elimination preserves the aforementioned global correctness criteria remains a technically challenging – yet central – problem in ill-founded proof theory. Existing arguments in the literature tend to be bespoke and system-specific, and therefore lack full generality and robustness [ 29 , 30 , 33 , 28 , 14 , 1 ] . The present article contributes to the general theory by adapting Tait and Girard’s celebrated reducibility candidates technique to the ill-founded setting. More specifically, we isolate two notions of reducibility candidate. The first, named \mathfrak{N} -reducibility candidates , is defined directly in terms of cut elimination. The second, \mathfrak{E} -reducibility candidates , is based on an alternative, topologically motivated and logic-independent, global condition on proofs which we call external progressivity . In essence, the latter are the ill-founded proofs which explicitly present an invariant for cut elimination. Our work is developed within ill-founded \mu\mathsf{MALL} whose linear structure offers a streamlined and concise exposition, but covers classical and intuitionistic fixed point logics by virtue of the standard embeddings. We prove that progressing proofs belong to both kind of reducibility candidate, thereby confirming that progressing proofs are both externally progressing and normalisable. The argument relies on a modest generalisation of the standard soundness (or computational totality) argument from ill-founded proof theory (see, e.g., [ 11 , 18 ] ). In the case of \mathfrak{N} -reducibility candidates, the result directly implies cut elimination for progressing proofs. An (almost) parallel argument establishes that every progressing proof is externally progressing, generalising an observation from [ 2 ] . As with the standard reducibility candidates arguments for inductive systems, \mathfrak{N} -reducibility merely confirms the existence of a cut elimination strategy. A more insightful and explicit cut elimination argument is developed using \mathfrak{E} -reducibility candidates, where external progressivity provides a direct and straightforward certification of preservation of progressivity when a concrete cut elimination procedures is given. Related work Cut elimination for infinitary \mu\mathsf{MALL} was first developed by Baelde et al. [ 4 ] using the notion of multicut and extending a previous result for a much weaker system by Fortier and Santocanale [ 19 ] . To ensure productivity and preservation of progressivity, however, the authors propose a bespoke argument based on a truth semantics. The concept of externally progressing ill-founded proofs appeared in [ 2 ] as an intermediate notion between progressing and normalisable ill-founded proofs in the context of higher-order intuitionistic arithmetic with fixed-points. Both inclusions – progressing proofs are externally progressing and externally progressing proofs are normalisable – crucially relied on restricting the use of fixed point quantifiers. In contrast to [ 2 ] , our result does not place any specific restriction on the formation of fixed points (beyond positivity). Moreover, thanks to the robustness of the reducibility candidates method and the logic-independent nature of external progressivity, our cut elimination arguments generalise to fixed point logics beyond those treated in [ 4 , 19 ] , such as the higher-order fixed point logics discussed in [ 2 ] . Outline of the paper Section 2 recalls the ill-founded proof system for \mu\mathsf{MALL} , its progressivity condition, and infinitary cut elimination. Section 3 introduces the notion of internally closed set, which is used to define the externally progressing derivations. Section 4 is devoted to reducibility candidates and their properties. Finally, in Section 5 and Section 6 we prove cut elimination ( 61 ) by two reducibility-style arguments, one based on \omega -normalisation ( 60 ) and the other through external progressivity ( 73 ). Conventions on sequences and trees The set of natural numbers is denoted \omega , and is associated with the standard ordering < . A finite sequence over a set X is a function u:\{0,\ldots,n-1\}\to X , often written \langle u(0),\ldots,u(n-1)\rangle . The cardinality of the domain of u is referred to as the length and denoted |u| . The set of finite sequences over X is denoted {X}^{<\omega} . The empty sequence is denoted \langle\rangle\in{X}^{<\omega} , and concatenation of (finite) sequences u and v is denoted u.v . The prefix relation on {X}^{<\omega} is denoted \leq , defined by u\leq v iff there exists w\in{X}^{<\omega} such that v=u.w . A tree is a non-empty set T\subseteq{\omega}^{<\omega} which is prefix closed, that is, if u0\exists\mathfrak{a}\in B\,\mathfrak{a}(i)=\mathfrak{b}(i)\text{ for all }i0 . • no {\color[rgb]{0,0,1}\mu X.X} is principal for \mathsf{r}^{\prime}_{i} . Clearly, \{\mathfrak{b},\mathfrak{b}^{\prime}\} is a IC set, as neither \mathfrak{b} nor \mathfrak{b}^{\prime} bears an internal thread. However, since {\color[rgb]{1,0,0}\nu X.X} is principal for \mathsf{r}_{0} and no {\color[rgb]{0,0,1}\mu X.X} is principal for \mathsf{r}^{\prime}_{i} , there is only one cut elimination strategy, which repeatedly applies non-critical steps permuting downward all \mathsf{r}^{\prime}_{i} . This means that, for all n>1 , \mathfrak{b}(n) will never become a premise of a cut. One of the key results of this paper is that progressing derivations are also externally progressing ( 60 ). Notice that the converse does not hold, as the following example shows. Example 37 . Let use consider the following derivation \vdots \scriptstyle\nu\; {\color[rgb]{1,0,0}X[\nu X.X/X]},{\color[rgb]{0,0,1}Y[\nu Y.Y/Y]} \scriptstyle\nu\; {\color[rgb]{1,0,0}\nu X.X},{\color[rgb]{0,0,1}\nu Y.Y} \vdots \scriptstyle\mu\; {\color[rgb]{0,0.5,0}Y[\mu Y.Y/Y]} \scriptstyle\mu\; {\color[rgb]{0,0.5,0}\mu Y.Y} \scriptstyle\mathsf{cut}\; {\color[rgb]{1,0,0}\nu X.X} It has only two branches, \mathfrak{b} and \mathfrak{b^{\prime}} defined by \mathfrak{b}(n)=\langle 0,\overset{n}{\ldots},0\rangle and \mathfrak{b}(n)=\langle 1,0,\overset{n-1}{\ldots},0\rangle , respectively. Let \tau (resp., \sigma ) be the thread bourne by \mathfrak{b} and whose trace is highlighted with red (resp., blue ) formula occurrences. Moreover, let \sigma^{\perp} be the thread bourne by \mathfrak{b}^{\prime} and whose trace is highlighted with green formula occurrences. Then, the only IC set of the derivation is \{\mathfrak{b},\mathfrak{b^{\prime}}\} , as IC sets are non-empty and {\mathfrak{b}}\scoh_{\sigma}{\mathfrak{b}^{\prime}} . Moreover, \{\mathfrak{b},\mathfrak{b^{\prime}}\} bears the good external thread, \tau , and so the derivation is externally progressing. However, the derivation is not progressing, as the branch \mathfrak{b^{\prime}} bears no good thread. However, the two global conditions match in the cut-free setting. Proposition 38 . A cut-free derivation d is externally progressing iff d is progressing. Proof. By definition, as every thread is external in a cut-free derivation. ∎ Remark 39 . From 38 and 21 it follows that the identity derivation is externally progressing. 4. Reducibility candidates Reducibility candidates were introduced by Girard [ 20 ] for proving normalisation of system \mathsf{F} , a polymorphic calculus, and generalise Tait’s celebrated reducibility (or computability ) method for Gödel’s system \mathsf{T} [ 39 ] . In the context of linear logic, reducibility candidates arise naturally from the so-called orthogonality construction [ 21 ] , a recurring motif of this logic that stems from semantic motivations. Orthogonality-based reducibility candidates were developed by Baelde and Miller to prove normalisation of inductive \mu\mathsf{MALL} in [ 5 ] . This section defines reducibility candidates for ill-founded \mu\mathsf{MALL} via the notion of orthogonality, and outlines their properties. Our constructions smoothly adapt [ 5 ] to our infinitary setting. To recast the Baelde and Miller’s normalisation argument for \omega -normalisation, we will introduce ordinal-indexed approximations of reducibility candidates. 4.1. Orthogonality and reducibility candidates Henceforth, given a set of derivations \mathfrak{R} we will denote with \mathfrak{R}_{\phi} the set of derivations with a distinguished formula \phi in the conclusion. Definition 40 (Orthogonality) . Let \mathfrak{R} be a set of derivations and \phi a formula. The ( \mathfrak{R} -) orthogonality relation over \phi is the relation {\perp_{\phi}^{\mathfrak{R}}}\subseteq\mathfrak{R}_{\phi}\times\mathfrak{R}_{\phi^{\perp}} defined by d\perp_{\phi}^{\mathfrak{R}}d^{\prime} iff \mathsf{cut}_{\phi}(d\mid d^{\prime})\in\mathfrak{R} . For an orthogonality relation {\perp}={\perp_{\phi}^{\mathfrak{R}}} and set of derivations \mathcal{X}\subseteq\mathfrak{R}_{\phi} , we define \mathcal{X}^{\perp}\coloneqq\{d\in\mathfrak{R}_{\phi^{\perp}}\mid e\perp d\text{ for all }e\in\mathcal{X}\} . We write d\perp_{\phi}d^{\prime} (or simply d\perp d^{\prime} ) if the set of derivations \mathfrak{R} (and formula \phi ) can be inferred from context. Thus, unless specified otherwise, when a set \mathcal{X} has been introduced in a context such as “ \mathcal{X}\subseteq\mathfrak{R}_{\phi} ” the relation \perp denotes \perp_{\phi}^{\mathfrak{R}} . In particular, \mathcal{X}^{\perp\perp} means \mathcal{X}^{\perp_{\phi}\perp_{\phi^{\perp}}} . Definition 41 (Reducibility candidate) . Let \mathfrak{R} be a set of derivations. A ( \mathfrak{R} -) reducibility candidate is a set \mathcal{X}\subseteq\mathfrak{R}_{\phi} satisfying \mathcal{X}=\mathcal{X}^{\perp\perp} . Intuitively, a \mathfrak{R} -reducibility candidate is a set of derivations that preserve membership in \mathfrak{R} when interacting by a cut rule with derivations from the dual candidates. In other words, reducibility candidates carve out sets of derivations of \mathfrak{R} satisfying a “composability property”. In this paper we will focus on \mathfrak{N} -reducibility candidates and \mathfrak{E}{} -reducibility candidates. In what follows, the class of derivations \mathfrak{R} is considered fixed (and arbitrary) unless stated otherwise. Orthogonality of derivations satisfies several well-known properties which do not depend on the choice of \mathfrak{R} . Proposition 42 (See, e.g., [ 5 ] ) . For any sets \mathcal{X},\mathcal{Y}\subseteq\mathfrak{R} : • \mathcal{X}\subseteq\mathcal{Y} implies \mathcal{Y}^{\perp}\subseteq\mathcal{X}^{\perp} • (\mathcal{X}\cup\mathcal{Y})^{\perp}=\mathcal{X}^{\perp}\cap\mathcal{Y}^{\perp} • \mathcal{X}\subseteq\mathcal{X}^{\perp\perp} • \mathcal{X}^{\perp\perp\perp}=\mathcal{X}^{\perp} . In other words, \mathcal{X}^{\perp} is always a reducibility candidate. Proposition 43 . \mathfrak{R} -reducibility candidates (ordered by \subseteq ) form a complete lattice. Proof. Given an arbitrary collection of candidates S , it is easy to check that (\bigcup S)^{\perp\perp} is its least upper bound in the lattice, and \bigcap S its greatest lower bound. We just check the minimality of (\bigcup S)^{\perp\perp} : any upper bound \mathcal{Y} satisfies \bigcup S\subseteq\mathcal{Y} , and hence (\bigcup S)^{\perp\perp}\subseteq\mathcal{Y}^{\perp\perp}=\mathcal{Y} . Concerning the greatest lower bound, the only non-trivial thing is that it is a reducibility candidate, but it suffices to observe that \bigcap S=\bigcap_{\mathcal{X}\in S}\mathcal{X}^{\perp\perp}=(\bigcup_{\mathcal{X}\in S}\mathcal{X}^{\perp})^{\perp} . The least reducibility candidate is \emptyset^{\perp\perp} and the greatest is \mathfrak{R} . ∎ Having a complete lattice, we can use the Knaster–Tarski theorem: any monotone function f on reducibility candidates admits a least fixed point \mathsf{lfp}\left(f\right) and a greatest fixed point \mathsf{gfp}\left(f\right) in the lattice of candidates. 4.2. Interpretation We now define an interpretation associating with every formula a reducibility candidate. Notice that the interpretation proceeds inductively on the construction of pre formulas. Definition 44 (Interpretation) . An environment is a mapping \mathcal{E} from the set of propositional variables to reducibility candidates. Let \mathcal{E} be an environment. By \mathcal{E}[X\mapsto\mathcal{X}] we denote the environment which maps X to \mathcal{X} and agrees with \mathcal{E} otherwise. We define, by recursion on a pre formula \phi , a reducibility candidate \llbracket{\phi}\rrbracket^{\mathcal{E}}_{\mathfrak{R}} (also denoted \llbracket{\phi}\rrbracket^{\mathcal{E}} ) called the interpretation of \phi (under \mathcal{E} ) : • \llbracket{X}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}:=\mathcal{E}(X) • \llbracket{\top}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}=\emptyset^{\perp} • \llbracket{\perp}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}:=\left\{{\vbox{\hbox{\kern 7.30826pt\hbox{\vbox{\hbox{\kern 2.87498pt\hbox{\hbox{\hbox{$$}}}\kern 2.87498pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathbf{1}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to5.74997pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 2.12502pt\hbox{$\mathbf{1}$}\kern 2.12502pt$}}}}}\kern 0.0pt}}}\right\}^{\perp} • \llbracket{\phi\invamp\psi}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}:=\left\{\begin{array}[]{c|c}{{{{}{}{}}}{{{}{}{}}}\vbox{\hbox{\kern 5.98598pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$$}}\kern 10.00002pt}\hbox{\hbox{$\hskip 8.0pt$}}\kern 10.00002pt}\hbox{\hbox{$$}}}}}\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{\hbox{$\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 14.00002pt\hbox{\ignorespaces\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{{}{}{{}{}}{{}{}{}{}\lx@xy@spline@}{}}}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern-2.08144pt\raise 7.64386pt\hbox{\hbox{\kern 0.0pt\raise-2.43056pt\hbox{$\textstyle{\scriptstyle d}$}}}}}}}}}}$}}\hbox to0.0pt{\hbox{$$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 14.00002pt\hbox{\hbox{$$}}\kern 14.00002pt}}}\kern 0.0pt}}}\kern 0.0pt\kern 0.0pt\hbox{\kern 5.26392pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{}\hbox to0.0pt{\hbox{$$}\hss}\kern 5.26392pt}\hbox{\kern 5.26392pt\hbox{\hbox{$\Delta,\theta$}}\kern 5.26392pt}}}\kern 0.0pt}\kern 10.00002pt}\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$$}}\kern 10.00002pt}\hbox{\hbox{$\hskip 8.0pt$}}\kern 10.00002pt}\hbox{\hbox{$$}}}}}\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{\hbox{$\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 14.00002pt\hbox{\ignorespaces\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{{}{}{{}{}}{{}{}{}{}\lx@xy@spline@}{}}}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern-3.43387pt\raise 7.64386pt\hbox{\hbox{\kern 0.0pt\raise-2.8978pt\hbox{$\textstyle{\scriptstyle d^{\prime}}$}}}}}}}}}}$}}\hbox to0.0pt{\hbox{$$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 14.00002pt\hbox{\hbox{$$}}\kern 14.00002pt}}}\kern 0.0pt}}}\kern 0.0pt\kern 0.0pt\hbox{\kern 3.0799pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{}\hbox to0.0pt{\hbox{$$}\hss}\kern 3.0799pt}\hbox{\kern 3.0799pt\hbox{\hbox{$\Delta^{\prime},\chi$}}\kern 3.0799pt}}}\kern 0.0pt}}}}\kern 1.43518pt\hbox{\kern 5.26392pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\otimes\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to57.65628pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 3.0799pt}\kern 1.43518pt\hbox{\kern 8.32475pt\hbox{\hbox{$\Delta,\Delta^{\prime},\theta\otimes\chi$}}\kern 6.14073pt}}}\kern 0.0pt}}}&d\in\llbracket{\phi^{\perp}}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}\text{ and }d^{\prime}\in\llbracket{\psi^{\perp}}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}\end{array}\right\}^{\perp} • \llbracket{\phi_{1}\with\phi_{2}}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}:=\left\{\begin{array}[]{c|c}{{{}{}{}}\vbox{\hbox{\kern 14.41774pt\hbox{\vbox{\hbox{\kern 8.3889pt\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$$}}\kern 10.00002pt}\hbox{\hbox{$\hskip 8.0pt$}}\kern 10.00002pt}\hbox{\hbox{$$}}}}}\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{\hbox{$\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 14.00002pt\hbox{\ignorespaces\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{{}{}{{}{}}{{}{}{}{}\lx@xy@spline@}{}}}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern-2.08144pt\raise 7.64386pt\hbox{\hbox{\kern 0.0pt\raise-2.43056pt\hbox{$\textstyle{\scriptstyle d}$}}}}}}}}}}$}}\hbox to0.0pt{\hbox{$$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 14.00002pt\hbox{\hbox{$$}}\kern 14.00002pt}}}\kern 0.0pt}}}\kern 0.0pt\kern 0.0pt\hbox{\kern 2.68953pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{}\hbox to0.0pt{\hbox{$$}\hss}\kern 2.68953pt}\hbox{\kern 2.68953pt\hbox{\hbox{$\Delta,\psi_{i}$}}\kern 2.68953pt}}}\kern 0.0pt}}\kern 8.3889pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\oplus_{i}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to44.77783pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\Delta,\psi_{1}\oplus\psi_{2}$}\kern 0.0pt$}}}}}\kern 0.0pt}}}&\text{for }i\in\{0,1\}\text{ and }d\in\llbracket{\phi_{i}^{\perp}}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}\end{array}\right\}^{\perp} • \llbracket{\nu X\phi}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}:=\displaystyle\bigcap\left\{\mathcal{X}\quad\middle|\quad\mathcal{X}\subseteq\left\{\begin{array}[]{c|c}{{{}{}{}}\vbox{\hbox{\kern 7.64003pt\hbox{\vbox{\hbox{\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\kern 15.53357pt\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$$}}\kern 10.00002pt}\hbox{\hbox{$\hskip 8.0pt$}}\kern 10.00002pt}\hbox{\hbox{$$}}}}}\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{\hbox{$\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 14.00002pt\hbox{\ignorespaces\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{{}{}{{}{}}{{}{}{}{}\lx@xy@spline@}{}}}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern-2.08144pt\raise 7.64386pt\hbox{\hbox{\kern 0.0pt\raise-2.43056pt\hbox{$\textstyle{\scriptstyle d}$}}}}}}}}}}$}}\hbox to0.0pt{\hbox{$$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 14.00002pt\hbox{\hbox{$$}}\kern 14.00002pt}}}\kern 0.0pt}}\kern 15.53357pt}\kern 0.0pt\kern 0.0pt\hbox{\hbox to0.0pt{\hss\hbox{$$}}\vbox{}\hbox to0.0pt{\hbox{$$}\hss}}\hbox{\hbox{\hbox{$\Delta,\phi^{\perp}(\mu X\phi^{\perp})$}}}}}\kern 0.0pt}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mu\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to59.06717pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 9.74307pt\hbox{\hbox{$\kern 0.0pt\hbox{$\Delta,\mu X\phi^{\perp}$}\kern 0.0pt$}}\kern 9.74307pt}}}\kern 0.0pt}}}&d\in\llbracket{\phi^{\perp}}\rrbracket^{\mathcal{E}[X\mapsto\mathcal{X}]}_{\mathfrak{R}}\end{array}\right\}^{\perp}\right\} • In all other cases \llbracket{\phi^{\perp}}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}:=(\llbracket{\phi}\rrbracket^{\mathcal{E}^{\perp}}_{\mathfrak{R}})^{\perp} , where \mathcal{E}^{\perp}_{\mathfrak{R}}:X\mapsto\mathcal{E}_{\mathfrak{R}}(X)^{\perp} . Finally, for \Gamma=\phi_{1},\ldots,\phi_{n} we define \llbracket{\Gamma}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}=\llbracket{\phi_{1}}\rrbracket^{\mathcal{E}}_{\mathfrak{R}}\cap\dotsm\cap\llbracket{\phi_{n}}\rrbracket^{\mathcal{E}}_{\mathfrak{R}} , which is a reducibility candidate by 46 . Henceforth, we omit the environment \mathcal{E} when there are no free variables or the choice is clear from the context. The following properties of interpretations are easy consequences of the definition, recalling that X=X^{\perp} from Section 2.1 . Proposition 45 . For all formulas \phi , \llbracket{\phi}\rrbracket\subseteq\mathfrak{R}_{\phi} . Proposition 46 . For all pre-formulas \phi and \psi : (1) \llbracket{\phi^{\perp}}\rrbracket^{\mathcal{E}}=(\llbracket{\phi}\rrbracket^{\mathcal{E}^{\perp}})^{\perp} . (2) \llbracket{\phi[\psi/X]}\rrbracket^{\mathcal{E}}=\llbracket{\phi}\rrbracket^{\mathcal{E}[X\mapsto\llbracket{\psi}\rrbracket^{\mathcal{E}}]} . Lemma 47 (Monotonicity) . If \mathcal{X}\subseteq\mathcal{Y} are reducibility candidates and \phi is a pre-formula then \llbracket{\phi}\rrbracket^{\mathcal{E}[X\mapsto\mathcal{X}]}\subseteq\llbracket{\phi}\rrbracket^{\mathcal{E}[X\mapsto\mathcal{Y}]}. In particular, \mathcal{X}\mapsto\llbracket{\phi}\rrbracket^{\mathcal{E}[X\mapsto\mathcal{X}]} is a monotone endofunction over the complete lattice of the reducibility candidates. It is important to note that fixed points are not interpreted as bona fide fixed points, i.e., \llbracket{\mu X\phi}\rrbracket^{\mathcal{E}}\neq\llbracket{\phi(\mu X\phi)}\rrbracket^{\mathcal{E}} in general. Rather, we have: Proposition 48 . \llbracket{\nu X\phi}\rrbracket^{\mathcal{E}}:=\left\{\begin{array}[]{c|c}{{{}{}{}}\vbox{\hbox{\kern 7.64003pt\hbox{\vbox{\hbox{\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\kern 15.53357pt\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$$}}\kern 10.00002pt}\hbox{\hbox{$\hskip 8.0pt$}}\kern 10.00002pt}\hbox{\hbox{$$}}}}}\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{\hbox{$\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 14.00002pt\hbox{\ignorespaces\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{{}{}{{}{}}{{}{}{}{}\lx@xy@spline@}{}}}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern-2.08144pt\raise 7.64386pt\hbox{\hbox{\kern 0.0pt\raise-2.43056pt\hbox{$\textstyle{\scriptstyle d}$}}}}}}}}}}$}}\hbox to0.0pt{\hbox{$$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 14.00002pt\hbox{\hbox{$$}}\kern 14.00002pt}}}\kern 0.0pt}}\kern 15.53357pt}\kern 0.0pt\kern 0.0pt\hbox{\hbox to0.0pt{\hss\hbox{$$}}\vbox{}\hbox to0.0pt{\hbox{$$}\hss}}\hbox{\hbox{\hbox{$\Delta,\phi^{\perp}(\mu X\phi^{\perp})$}}}}}\kern 0.0pt}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mu\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to59.06717pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 7.79865pt\hbox{\hbox{$\kern 0.0pt\hbox{$\Delta,\mu X.\phi^{\perp}$}\kern 0.0pt$}}\kern 7.79865pt}}}\kern 0.0pt}}}&d\in\llbracket{\phi^{\perp}(\mu X\phi^{\perp})}\rrbracket^{\mathcal{E}}\end{array}\right\}^{\perp}. Proof. It follows from the Knaster-Tarski theorem, using 47 and 46 . 2 . ∎ 4.3. Ordinal assignments Our cut elimination arguments based on reducibility candidates will rely on an alternative characterisation of fixed points through ordinal-indexed approximations. To this end, we temporarily extend the formal syntax: • for any formulas \mu X\phi and \nu X\phi , and for any ordinal \alpha , the expressions \mu^{\alpha}X\phi and \nu^{\alpha}X\phi are also formulas. Let us stress that indexed quantifiers are only permitted in the case of formulas , so whereas \nu^{\omega}X\nu Y.\,X\oplus Y is permitted, \nu X\nu^{\omega}Y.\,X\oplus Y is not because \nu Y.\,X\oplus Y is not a formula. The interpretation function \llbracket{\cdot}\rrbracket^{\mathcal{E}}_{\mathfrak{R}} is duly expanded by the following condition for all \alpha . • \llbracket{\nu^{\alpha}X\phi}\rrbracket^{\mathcal{E}}:=\displaystyle\bigcap_{\beta<\alpha}\left\{\begin{array}[]{c|c}{{{}{}{}}\vbox{\hbox{\kern 7.64003pt\hbox{\vbox{\hbox{\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\kern 17.478pt\hbox{\hbox{\kern 0.0pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$$}}\kern 10.00002pt}\hbox{\hbox{$\hskip 8.0pt$}}\kern 10.00002pt}\hbox{\hbox{$$}}}}}\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$$}}\vbox{\hbox{$\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern 14.00002pt\hbox{\ignorespaces\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{{}{}{{}{}}{{}{}{}{}\lx@xy@spline@}{}}}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern-2.08144pt\raise 7.64386pt\hbox{\hbox{\kern 0.0pt\raise-2.43056pt\hbox{$\textstyle{\scriptstyle d}$}}}}}}}}}}$}}\hbox to0.0pt{\hbox{$$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 14.00002pt\hbox{\hbox{$$}}\kern 14.00002pt}}}\kern 0.0pt}}\kern 17.478pt}\kern 0.0pt\kern 0.0pt\hbox{\hbox to0.0pt{\hss\hbox{$$}}\vbox{}\hbox to0.0pt{\hbox{$$}\hss}}\hbox{\hbox{\hbox{$\Delta,\phi^{\perp}(\mu X.\phi^{\perp})$}}}}}\kern 0.0pt}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mu\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to62.95602pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 9.74307pt\hbox{\hbox{$\kern 0.0pt\hbox{$\Delta,\mu X.\phi^{\perp}$}\kern 0.0pt$}}\kern 9.74307pt}}}\kern 0.0pt}}}&d\in\llbracket{\phi^{\perp}}\rrbracket^{\mathcal{E}[X\mapsto\llbracket{\nu^{\beta}X\phi}\rrbracket^{\mathcal{E}}]}\end{array}\right\}^{\perp} • \llbracket{\mu^{\alpha}X\phi}\rrbracket^{\mathcal{E}}:=(\llbracket{\nu^{\alpha}X\phi^{\perp}}\rrbracket^{\mathcal{E}^{\perp}})^{\perp} notice that \llbracket{\nu^{0}X\phi}\rrbracket^{\mathcal{E}}=\mathfrak{R} . By the Knaster–Tarski theorem: Proposition 49 . Let \mathfrak{R} be a set of derivations and let \mathrm{Ord} denote the class of all ordinals. For any pre-formula \phi with at most X free: (1) \llbracket{\mu X\phi}\rrbracket=\displaystyle\bigcup\limits_{\alpha\in\mathrm{Ord}}\llbracket{\mu^{\alpha}X\phi}\rrbracket . (2) \llbracket{\nu X\phi}\rrbracket=\displaystyle\bigcap\limits_{\alpha\in\mathrm{Ord}}\llbracket{\nu^{\alpha}X\phi}\rrbracket . Given a formula \phi and a list of ordinals of appropriate length \vec{\alpha} , we can assign ordinals to the \nu -subformulas of \phi in such a way that the interpretation of the resulting formula is an approximation of the interpretation of \phi , that is, \llbracket{\phi^{\vec{\alpha}}}\rrbracket approximates \llbracket{\phi}\rrbracket . A similar reasoning applies to the \mu -subformulas of \phi . This requires the following subtle definition of assignment. Definition 50 (Assignments) . Let \phi be a formula and let \nu X_{k}\phi_{k}<\dots<\nu X_{1}\phi_{1} enumerate the \nu -formulas that are \approx_{\mathrm{FL}} -equivalent to \phi in order of priority. Given a sequence of ordinals \vec{\alpha}=\alpha_{1}\dotsm\alpha_{l} with l\leq k , referred to as a \nu -assignment , we define the formula \phi^{\vec{\alpha}} by recursively replacing each subformula \nu X_{i}\phi_{i} by \nu^{\alpha_{i}}X_{i}\phi_{i} , starting at i=l . The formula \phi_{\vec{\alpha}} is defined analogously with respect to the \mu -subformulas of \phi , in which case \vec{\alpha} is referred to as a \mu -assignment . Assignments are assumed to be ordered lexicographically, i.e., \vec{\alpha}<\vec{\beta} iff \vec{\alpha} is a proper prefix of \vec{\beta} or there exists i with \alpha_{i}<\beta_{i} and \alpha_{j}=\beta_{j} for all j\dotsm>\nu Y_{p}\psi_{p} be the \nu -subformulas of \nu X\phi ordered by the priority ordering (see 3 ). Let j be such that \nu X\phi=\nu X_{j}\psi_{j} and \vec{\alpha}_{n}=\vec{\gamma}\alpha\vec{\delta} where \lvert\vec{\gamma}\rvert=j . Suppose d is not (\vec{\alpha}_{0},\ldots,\vec{\alpha}_{n}) -reducible. By 57 there exists derivations e_{j}\in\llbracket{\theta_{j}^{\vec{\alpha}_{j}}}\rrbracket^{\perp} such that \mathsf{cut}(d\mid e_{0},\ldots,e_{n-1})\not\in\llbracket{(\nu X\phi)^{\vec{\alpha}_{n}}}\rrbracket. As \llbracket{(\nu X\phi)^{\vec{\alpha}_{n}}}\rrbracket=\llbracket{\nu^{\alpha}X\,\phi^{\vec{\gamma}}}\rrbracket , there exists \beta<\alpha and e\in\llbracket{\phi(\nu X\phi)^{\vec{\gamma}\beta}}\rrbracket such that the derivation presented above in ( 1 ) is not in \mathfrak{R}{} . The same sequence of cut elimination steps shows that \mathsf{cut}(d\mid e_{0},\dotsc,e_{n-1},e)\not\in\mathfrak{R}{} , meaning that d_{0} is not (\vec{\beta}_{0},\dotsc,\vec{\beta}_{n}) -reducible where \vec{\beta}_{i}=\vec{\alpha}_{i} for ik and, in particular, there is a finite bound the length of all sequences (\vec{\alpha}_{h_{i}}^{i})_{i} . By 59 , \vec{\alpha}^{i+1}_{h_{i+1}}\leq\vec{\alpha}^{i}_{h_{i}} for all i and \vec{\alpha}^{i+1}_{h_{i+1}}<\vec{\alpha}^{i}_{h_{i}} infinitely often, contradicting the well-foundedness of ordinals. ∎ Using 45 , 60 implies immediately that progressing proofs are also externally progressing and \omega -normalising. This allows us to establish our main result: Corollary 61 (Cut elimination) . If d\in\mathfrak{P} then d\in\mathfrak{N} . As with the standard reducibility candidates methods for inductive systems, the cut elimination argument we above does not exhibit a concrete infinitary procedure for rewriting a derivation into a cut-free one. Also, it does not suggest any approach for proving directly preservation of progressivity, which is managed implicitly by the notion of \mathfrak{N} -reducibility. In the next section we will develop a second, more insightful cut elimination argument for 61 , based on \mathfrak{E} -reducibility. 6. Second cut elimination argument 60 shows that progressing derivations are also externally progressing. Our second cut elimination argument for 61 will rely on this result, where the external progressivity condition allows a straightforward proof of both the existence of the limit cut-free proof ( productivity ) and the sought-after preservation of progressivity. We will formulate this result within a standard cut elimination procedure, where cuts are stepwise pushed upward by the cut elimination rules, giving priority to the bottommost ones. To avoid technicalities related to cut commutations, the procedure will actually manipulate so-called multicut rules , a generalisation of the cut rule representing series of consecutive cuts (see, e.g., [ 4 ] ). 6.1. Multicut \omega -reduction sequences and paths As mentioned earlier, a multicut can be seen as a macro rule for a tree of consecutive cuts. The following definition formalises this idea. Definition 62 (Multicuts) . Let d be a derivation with conclusion \Gamma , and u_{1},\ldots,u_{n} with n>1 be nodes of d . A multicut in d is a tuple \langle v;u_{1},\ldots,u_{n}\rangle where d_{v} is obtained from d_{u_{1}},\ldots,d_{u_{n}} by applying a series of consecutive cut rules. When n=2 the multicut is called cut . Multicuts will be denoted \mathsf{m} . We call u_{1},\ldots,u_{n} (resp., v ) the premises (resp., conclusion ) of the multicut. A cut pair of a multicut is a pair (\phi,\phi^{\perp}) of dual formulas occurring among the premises of the multicut such that, by permuting some cuts, a new multicut can be obtained that includes a cut rule \mathsf{r} with cut formulas \phi and \phi^{\perp} . In this case, we call \phi and \phi^{\perp} cut formulas of the multicut . The tree of \mathsf{m}=\langle v;u_{1},\ldots,u_{n}\rangle (in d ) is the set \mathrm{T}_{d}(\mathsf{m})=\{w\in d\mid\exists i\in\{1,\ldots,n\}(v\leq w\leq u_{i})\} , and the initial segment of \mathsf{m} (in d ) is the set \mathrm{I}_{d}(\mathsf{m})=\{w\in d\mid w