An Infinitary Lambda Calculus with Global Trace Condition (Extended Abstract)
Stefano Berardi, Ugo de’ Liguoro, Daisuke Kimura, Daniel Osorio-Valencia · 2026
Read An Infinitary Lambda Calculus with Global Trace Condition (Extended Abstract) by Stefano Berardi, Ugo de’ Liguoro, Daisuke Kimura, Daniel Osorio-Valencia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-23573.txt.
Introduction
Berardi, de' Liguoro, Kimura, and Osorio-Valencia extend a logic system for infinite computations, in a 2026 extended abstract on proof theory. Lambda calculus is the formal backbone of functional programming, and its infinitary version allows terms, meaning expressions, that run on without end. The authors enrich that calculus with zero, successor, and conditional operations, plus a type system modeled on Gödel's System T, a classic scheme for defining computable functions.
They then add a Global Trace Condition, a rule borrowed from cyclic proof theory that watches how a computation unfolds over time. For well-typed terms meeting that condition, every infinite reduction, any sequence of simplification steps, converges strongly. A key payoff follows: any closed term of natural-number type reaches an actual numeral under every reduction path. For regular terms, the calculus defines the total functions of Gödel's System T exactly, no more and no fewer.
Catalog record
| CREATOR | Stefano Berardi, Ugo de’ Liguoro, Daisuke Kimura, Daniel Osorio-Valencia |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.23573
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Infinitary Lambda Calculus with Global Trace Condition (Extended Abstract) Stefano Berardi, Ugo de’ Liguoro, Daisuke Kimura, Daniel Osorio-Valencia Abstract We consider an extension of the infinitary lambda calculus by Kennaway et al., with zero, successor, and conditional, and a type system akin to Gödel’s system T. For terms that can be typed in this system, we define the Global Trace Condition (GTC), adapting the concept from Brotherston and Simpson’s Cyclic Proofs, and show that any infinite reduction of a well-typed term satisfying the GTC is strongly convergent. As a corollary, we obtain the proof that any closed term of type Nat reduces to some numeral through any reduction by levels. We argue that the Church-Rosser in the limit holds for our calculus and, when restricted to regular terms, the calculus defines exactly the total functions defined in Das’s Cyclic System T (an infinitary version of System T without λ \lambda ), and hence in Gödel’s System T. Computer Science Department, Turin University, Torino, Italy 0000-0001-5427-0020 Computer Science Department, Turin University, Torino, Italy 0000-0003-4609-2783 Department of Information Science, Toho University, Japan 0000-0001-6287-692X Computer Science Department, Turin University, Torino, Italy 0009-0002-4820-1867 ccs Theory of computation, Logic, Proof theory, Type Theory keywords Cyclic proofs, Cyclic terms, Fixed-point definition, global trace condition, Lambda calculus, Infinitary lambda calculus † † runningauthor: S. Berardi et al. † † copyright: Stefano Berardi and Ugo de’ Liguoro and Daisuke Kimura and Daniel Osorio † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Infinitary Lambda Terms We extend the infinitary \lambda -calculus \Lambda^{\infty} [ 5 , 4 ] . of Kennaway et alii, by adding the constant 0 and the function symbols {\tt succ} and {\tt cond} . Then we define the subset {{\sf GTC}\mbox{-}\Lambda^{\infty}_{T}} of terms satisfying the Global Trace Condition (GTC), and for them we prove that all reductions are strongly convergent and all terms are total. {{\sf GTC}\mbox{-}\Lambda^{\infty}_{T}} is an extension with variables and \lambda of CT , Cyclic System T of Das [ 2 , 3 ] . Our definition of {{\sf GTC}\mbox{-}\Lambda^{\infty}_{T}} is by consecutive restrictions. We first define the set {{\sf Row}\mbox{-}\Lambda^{\infty}_{T}} of infinitary row-terms with \lambda and conditional, most of which are meaningless, for which neither \alpha -renaming nor substitution is sound. Then we define the subset {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} of row-terms with finitely many free variables, for which we can consistently define \alpha -renaming and substitution. Then we define the subset {\sf WTyped} of infinitary terms with finitely many variables that are well-typed. Eventually, we restrict well-typed infinitary terms by adding GTC, a sufficient condition for totality. Definition 1 (Types and the set {{\sf Row}\mbox{-}\Lambda^{\infty}_{T}} of Row-Terms) . Let {\sf Type} be the set inductively defined by \begin{array}[]{l}{\sf Type}\ni A,B::=N\mid(A\to B)\end{array} Then the set {{\sf Row}\mbox{-}\Lambda^{\infty}_{T}} is coinductively defined by \begin{array}[]{l}{{\sf Row}\mbox{-}\Lambda^{\infty}_{T}}\ni t,s::=x\mid(\lambda x{:}A.t)\mid(t\,s)\mid 0\mid{\tt succ}(t)\mid{\tt cond}(t,s)\end{array} where x ranges over a denumerable set {\sf Var} of term variables. As usual, we omit unnecessary braces, assuming that \to associates to the right and term application associates to the left. We abbreviate by A_{1},\ldots,A_{n}\to B , and by \vec{A}\to B when the A_{i} are understood, the type (A_{1}\to\cdots(A_{n}\to B)\cdots) , and say that the A_{i} are in argument position . {\sf Type} is the set of simple types generated by the single atomic type N , whose intended interpretation is the set of natural numbers. Row-terms are possibly infinite terms representing elements of the metric completion of finite ones, namely those with a finite syntactic tree. Unlike [ 5 ] and following [ 6 ] , we consider the subset {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} of raw terms with finite {{\rm FV}}(t) , the set of free variables occurring in t , which admits the obvious corecursive definition. We also adapt the slightly different metric from [ 6 ] to account for truncation. Definition 2 . Let {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}}+\bot be {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} extended with the constant \bot . Then for all n\in\mathbb{N} we define the map {(-)}^{[n]}:{{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}}\to{{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}}+\bot by {t}^{[0]}=\bot and \begin{array}[]{l}\begin{array}[]{rcl@{\hspace{0.8cm}}rcl@{\hspace{0.8cm}}rcl}{x}^{[n+1]}&=&x\hfil\hskip 22.76228pt&{(ts)}^{[n+1]}&=&{t}^{[n]}{s}^{[n]}\hfil\hskip 22.76228pt&{(\lambda x{:}A.t)}^{[n+1]}&=&\lambda x{:}A.{t}^{[n]}\\[2.84526pt] {{\tt 0}}^{[n+1]}&=&{\tt 0}\hfil\hskip 22.76228pt&{{\tt succ}(t)}^{[n+1]}&=&{\tt succ}({t}^{[n]})\hfil\hskip 22.76228pt&{{\tt cond}(t,s)}^{[n+1]}&=&{\tt cond}({t}^{[n]},{s}^{[n]})\end{array}\end{array} The metric \textit{d}:({{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}}+\bot)^{2}\to[0,1] is \textit{d}(t,s)=2^{-m} where m is the last n\in\mathbb{N} such that {t}^{[n]}={s}^{[n]} if it exists, \textit{d}(t,s)=0 otherwise. The choice of {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} makes it easier and unproblematic to define \alpha -equivalence and substitution, which are as follows. Definition 3 ( \alpha -Equivalence on {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} ) . Let =_{\alpha} be the ordinary \alpha -equivalence over finite terms of system T + \bot . For any t,u\in{{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} define \begin{array}[]{l}t=^{\infty}_{\alpha}u\qquad\mbox{iff}\qquad\forall n\in\mathbb{N}.\;{t}^{[n]}=_{\alpha}{u}^{[n]}\end{array} Proposition 4 . The relation =^{\infty}_{\alpha} is a congruence over {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} . In view of the above, we consider the terms in {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} up to \alpha -equivalence, and define substitution corecursively as follows. Definition 5 (Substitution on {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} ) . For t,s\in{{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} and x\in{\sf Var} the substitution of s for x in t , written t[x:=s] , is corecursively defined by: 1. x[x:=s]=s , and y[x:=s]=y for {\sf Var}\ni y\neq x 2. (t\,t^{\prime})[x:=s]=(t[x:=s])(t^{\prime}[x:=s]) 3. (\lambda y{:}A.t)[x:=s]=\lambda z{:}A.(t[y:=z])[x:=s] for the first z\not\in\{y\}\cup{{\rm FV}}(t)\cup{{\rm FV}}(s) 4. 0[x:=s]=0 and {\tt succ}(t)[x:=s]={\tt succ}(t[x:=s]) 5. {\tt cond}(t,t^{\prime})[x:=s]={\tt cond}(t[x:=s],t^{\prime}[x:=s]) In the clause 3. above, the required z always exists because {{\rm FV}}(t)\cup{{\rm FV}}(s) is finite, and its choice is immaterial by \alpha -equivalence. Finally, a row term is regular if its syntactic tree is regular. We call {{\sf Reg}\mbox{-}\Lambda^{\infty}_{T}} the set of regular terms, which is clearly a (proper) subset of {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} . Reduction rules for {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} , also called notions of reduction in the literature, include the usual \beta -reduction and an additional rule for the conditional. Definition 6 (Reduction rules) . Let f , t and u be terms in {{\sf FinVar}\mbox{-}\Lambda^{\infty}_{T}} . We define the \beta -reduction relation \mathbin{\mapsto}_{\beta} and the {\tt cond} -reduction relation \mathbin{\mapsto}_{\tt cond} as follows: \beta -reduction: (\lambda x{:}A.t)(u)\mathbin{\mapsto}_{\beta}t[x:=u] , {\tt cond} -reduction: {\tt cond}(u,f)(0)\mathbin{\mapsto}_{\tt cond}u and {\tt cond}(u,f)({\tt succ}(t))\mathbin{\mapsto}_{\tt cond}f(t) . As usual, the relation \mathbin{\mapsto} is the compatible closure of \mathbin{\mapsto}_{\beta}\,\cup\,\mathbin{\mapsto}_{\tt cond} , and \mathbin{\mapsto}^{*} is its reflexive and transitive closure. 2 Well-typed terms and Global Trace Condition wk \mathord{\hbox to6.25pt{\vbox to6.83pt{\pgfpicture\makeatletter\hbox{\hskip 3.125pt\lower-3.41666pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \hbox{\hskip-3.125pt\raise-3.41666pt\hbox{\lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{-3.41666pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{69}}\hss}\lxSVG@closescope }}}} \lxSVG@closescope }}} \lxSVG@closescope \hbox to0.0pt{}{{ {}{}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}\vdash t:\mathord{\hbox to6.54pt{\vbox to7.14pt{\pgfpicture\makeatletter\hbox{\;\lower-3.57222pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \hbox{\hskip-3.26909pt\raise-3.57222pt\hbox{\lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{-3.57222pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{69}}\hss}\lxSVG@closescope }}}} \lxSVG@closescope }}} \lxSVG@closescope \hbox to0.0pt{}{{ {}{}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}\rightarrow N\hfil\lx@intercol \Gamma\subseteq\Gamma^{\prime} \mathord{\hbox to9.06pt{\vbox to7.52pt{\pgfpicture\makeatletter\hbox{\hskip 4.52779pt\lower-3.75891pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \hbox{\hskip-4.52779pt\raise-3.75891pt\hbox{\lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{-3.75891pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{69}}\hss}\lxSVG@closescope }}}} \lxSVG@closescope }}} \lxSVG@closescope \hbox to0.0pt{}{{ {}{}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}\vdash t:\mathord{\hbox to6.54pt{\vbox to7.14pt{\pgfpicture\makeatletter\hbox{\;\lower-3.57222pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \hbox{\hskip-3.26909pt\raise-3.57222pt\hbox{\lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{-3.57222pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{69}}\hss}\lxSVG@closescope }}}} \lxSVG@closescope }}} \lxSVG@closescope \hbox to0.0pt{}{{ {}{}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}\rightarrow N var x:A\in\Gamma\hfil\lx@intercol \Gamma\vdash x:A \lambda \mathord{\hbox to6.25pt{\vbox to6.83pt{\pgfpicture\makeatletter\hbox{\hskip 3.125pt\lower-3.41666pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \hbox{\hskip-3.125pt\raise-3.41666pt\hbox{\lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{-3.41666pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{69}}\hss}\lxSVG@closescope }}}} \lxSVG@closescope }}} \lxSVG@closescope \hbox to0.0pt{}{{ {}{}{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}},\mathord{\hbox to21.55pt{\vbox to6.83pt{\pgfpicture\makeatletter\hbox{\hskip 10.77425pt\lower-3.41666pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin}