Transfinite recursion is an essential component of set theory. In this paper, we seek intrinsically justified reasons for believing in recursion and the notions of higher computation that surround it. In doing this, we consider several kinds of recursion principles and prove results concerning their relation to one another. We then consider philosophical motivations for these formal principles coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while the (...) iterative conception of set has been widely recognized as insufficient to establish replacement and recursion, its supplementation by considerations pertaining to algorithms suggests a new and philosophically well-motivated reason to believe in such principles. (shrink)

In Barrio et al. Barrio Pailos and Szmuc prove that there are systems of logic that agree with classical logic up to any finite meta-inferential level, and disagree with it thereafter. This article presents a generalized sense of meta-inference that extends into the transfinite, and proves analogous results to all transfinite orders.

The relative strengths of first-order theories axiomatized by transfinite induction, for ordinals less-than 0, and formulas restricted in quantifier complexity, is determined. This is done, in part, by describing the provably recursive functions of such theories. Upper bounds for the provably recursive functions are obtained using model-theoretic techniques. A variety of additional results that come as an application of such techniques are mentioned.

We study a transfinite iteration of the ordinal Hessenberg natural sum obtained by taking suprema at limit stages. We show that such an iterated natural sum differs from the more usual transfinite ordinal sum only for a finite number of iteration steps. The iterated natural sum of a sequence of ordinals can be obtained as a mixed sum (in an order‐theoretical sense) of the ordinals in the sequence; in fact, it is the largest mixed sum which satisfies a (...) finiteness condition. We introduce other infinite natural sums which are invariant under permutations and show that all the sums under consideration coincide in the countable case. (shrink)

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that (...) initiated by Turing in his “ordinal logics” and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach. (shrink)

What is the proper way to transfinitely extend the usual hierarchy of finite metainferential levels? McAllister (_Journal of Philosophical Logic, 51_, 1345–1365, 2022; _Belief Revision About Logic_, PhD Thesis, University of Auckland, 2024) has proven that classical logic and numerous other logics are non-unique in classical set theory. On the basis of these results, she argues for a range of philosophical consequences, including problems for logical monism, classical set theory, and the identification of logics. This paper demonstrates that McAllister’s key (...) results are merely artifacts of the level labels which she adds to the transfinite hierarchy. It is proven that, in the absence of labels, every logic is unique in classical set theory. Moreover, I argue that if labels are not innocent additions, but instead influence the results in substantial ways, then they must be left out of the hierarchy. Therefore, in the final analysis, every logic is unique. The various problems which McAllister extracts from non-uniqueness accordingly dissolve. (shrink)

This paper develops transfinite extensions of transitivity and acyclicity in the context of population ethics. They are used to argue that it is better to add good lives, worse to add bad lives, and equally good to add neutral lives, where a life's value is understood as personal value. These conclusions rule out a number of theories of population ethics, feed into an argument for the repugnant conclusion, and allow us to reduce different-number comparisons to same-number ones. Challenges to (...) these arguments are addressed, including the issue of comparing existence and non-existence in terms of personal value, the possibility of minimal quanta of time and life, and the meaningfulness of measuring closeness between outcomes with different population sizes. An asymmetry is uncovered between transfinite cycles of worseness and betterness, supporting a version of the weak procreative asymmetry. Transfinite transitivity principles are also favourably compared to the better-known principles of continuity. (shrink)

In his famous paper Der Wahrheitsbegriff in den formalisierten Sprachen (Polish edition: Nakładem/Prace Towarzystwa Naukowego Warszawskiego, wydzial, III, 1933), Alfred Tarski constructs a materially adequate and formally correct definition of the term “true sentence” for certain kinds of formalised languages. In the case of other formalised languages, he shows that such a construction is impossible but that the term “true sentence” can nevertheless be consistently postulated. In the Postscript that Tarski added to a later version of this paper (Studia Philosophica, (...) 1, 1935), he does not explicitly include limits for the kinds of language for which such a construction is possible. This absence of such limits has been interpreted as an implied claim that such a definition of the term “true sentence” can be constructed for every language. This has far-reaching consequences, not least for the widely held belief that Tarski changed from an universalistic to an anti-universalistic standpoint. We will claim that the consequence of anti-universalism is unwarranted, given that it can be argued that the Postscript is not in conflict with the existence of limits outside of which a definition of “true sentence” cannot be constructed. Moreover, by a discussion of transfinite type theory, we will also be able to accommodate other of the changes made in Tarski’s Postscript within a type-theoretical framework. The awareness of transfinite type theory afforded by this discussion will lead, in turn, to an account of Tarski’s Postscript that shows a gradual change in his logical work, rather than any of the more radical transitions which the Postscript has been claimed to reflect. (shrink)

In this paper we present some metapredicative subsystems of analysis. We deal with reflection principles, $\omega-model$ existence axioms (limit axioms) and axioms asserting the existence of hierarchies. We show several equivalences among the introduced subsystems. In particular we prove the equivalence of $\sum_1^1$ transfinite dependent choice and $\prod_2^1$ reflection on $\omega-models$ of $\sum_1^1-DC$.

In his highly perceptive, if underappreciated introduction to Wittgenstein’s Tractatus, Russell identifies a “lacuna” within Wittgenstein’s theory of number, relating specifically to the topic of transfinite number. The goal of this paper is two-fold. The first is to show that Russell’s concerns cannot be dismissed on the grounds that they are external to the Tractarian project, deriving, perhaps, from logicist ambitions harbored by Russell but not shared by Wittgenstein. The extensibility of Wittgenstein’s theory of number to the case of (...) transfinite cardinalities is, I shall argue, a desideratum generated by concerns intrinsic, and internal to Wittgenstein’s logical and semantic framework. Second, I aim to show that Wittgenstein’s theory of number as espoused in the Tractatus is consistent with Russell’s assessment, in that Wittgenstein meant to leave open the possibility that transfinite numbers could be generated within his system, but did not show explicitly how to construct them. To that end, I show how one could construct a transfinite number line using ingredients inherent in Wittgenstein’s system, and in accordance with his more general theories of number and of operations. (shrink)

This paper begins an axiomatic development of naive set theoryin a paraconsistent logic. Results divide into two sorts. There is classical recapture, where the main theorems of ordinal and Peano arithmetic are proved, showing that naive set theory can provide a foundation for standard mathematics. Then there are major extensions, including proofs of the famous paradoxes and the axiom of choice (in the form of the well-ordering principle). At the end I indicate how later developments of cardinal numbers will lead (...) to Cantor’s theorem, the existence of large cardinals, and a counterexample to the continuum hypothesis. (shrink)

This paper develops a (nontrivial) theory of cardinal numbers from a naive set comprehension principle, in a suitable paraconsistent logic. To underwrite cardinal arithmetic, the axiom of choice is proved. A new proof of Cantor’s theorem is provided, as well as a method for demonstrating the existence of large cardinals by way of a reflection theorem.

In this chapter we present an approach to the classical results due to Gentzen. In 1936, Gentzen proved consistency of arithmetic using transfinite induction up to $$\varepsilon _0$$. We show how to prove transfinite induction up to any $$\alpha <\varepsilon _0$$ within Peano Arithmetic. The proofs exhibit a tradeoff between a strength of a needed fragment of Peano arithmetic and the length of induction up to a given ordinal $$\alpha $$, and the complexity of an induction formula. We (...) introduce the method of idicators to show independence of combinatorial statements from fragments of Peano arithmetics. (shrink)

In this thesis, we study Turing degrees in the context of classical recursion theory. What we are interested in is the partially ordered structures $\mathcal {D}_{\alpha }$ for ordinals $\alpha <\omega ^2$ and $\mathcal {D}_{a}$ for notations $a\in \mathcal {O}$ with $|a|_{o}\geq \omega ^2$.The dissertation is motivated by the $\Sigma _{1}$ -elementary substructure problem: Can one structure in the following structures $\mathcal {R}\subsetneqq \mathcal {D}_{2}\subsetneqq \dots \subsetneqq \mathcal {D}_{\omega }\subsetneqq \mathcal {D}_{\omega +1}\subsetneqq \dots \subsetneqq \mathcal {D}$ be a $\Sigma _{1}$ (...) -elementary substructure of another? For finite levels of the Ershov hierarchy, Cai, Shore, and Slaman [Journal of Mathematical Logic, vol. 12, p. 1250005] showed that $\mathcal {D}_{n}\npreceq _{1}\mathcal {D}_{m}$ for any $n < m$. We consider the problem for transfinite levels of the Ershov hierarchy and show that $\mathcal {D}_{\omega }\npreceq _{1}\mathcal {D}_{\omega +1}$. The techniques in Chapters 2 and 3 are motivated by two remarkable theorems, Sacks Density Theorem and the d.r.e. Nondensity Theorem.In Chapter 1, we first briefly review the background of the research areas involved in this thesis, and then review some basic definitions and classical theorems. We also summarize our results in Chapter 2 to Chapter 4. In Chapter 2, we show that for any $\omega $ -r.e. set D and r.e. set B with $D<_{T}B$, there is an $\omega +1$ -r.e. set A such that $D<_{T}A<_{T}B$. In Chapter 3, we show that for some notation a with $|a|_{o}=\omega ^{2}$, there is an incomplete $\omega +1$ -r.e. set A such that there are no a-r.e. sets U with $A<_{T}U<_{T}K$. In Chapter 4, we generalize above results to higher levels. We investigate Lachlan sets and minimal degrees on transfinite levels and show that for any notation a, there exists a $\Delta ^{0}_{2}$ -set A such that A is of minimal degree and $A\not \equiv _T U$ for all a-r.e. sets U.prepared by Cheng Peng.E-mail: [email protected]. (shrink)

William Lane Craig has argued that there cannot be actual infinities because inverse operations are not well-defined for infinities. I point out that, in fact, there are mathematical systems in which inverse operations for infinities are well-defined. In particular, the theory introduced in John Conway's *On Numbers and Games* yields a well-defined field that includes all of Cantor's transfinite numbers.

We define the paraconsistent supra-logic Pσ by a type-shift from the booleans o of propositional logic Po to the supra-booleans σ of the propositional type logic P obtained as the propositional fragment of the transfinite type theory Q defined by Peter Andrews (North-Holland Studies in Logic 1965) as a classical foundation of mathematics. The supra-logic is in a sense a propositional logic only, but since there is an infinite number of supra-booleans and arithmetical operations are available for this and (...) other types, virtually anything can be specified. The supra-logic is a generalization of Lukasiewicz's three-valued logic, with the intermediate value duplicated many times and ordered such that none of the copies of this value imply other ones, but it differs from Lukasiewicz's many-valued logics as well as from logics based on bilattices. There are several automated theorem provers for classical higher order logic (finite type theory) and it should be possible to modify these to our needs. (shrink)

We extend the hierarchy defined in [5] to cover all hyperarithmetical reals. An intuitive idea is used or the definition, but a characterization of the related classes is obtained. A hierarchy theorem and two fixed point theorems are presented.

Transfinite ordinal numbers enter mathematical practice mainly via the method of definition by transfinite recursion. Outside of axiomatic set theory, there is a significant mathematical tradition in works recasting proofs by transfinite recursion in other terms, mostly with the intention of eliminating the ordinals from the proofs. Leaving aside the different motivations which lead each specific case, we investigate the mathematics of this action of proof transforming and we address the problem of formalising the philosophical notion of (...) elimination which characterises this move. (shrink)

Ordinal functions may be iterated transfinitely in a natural way by taking pointwise limits at limit stages. However, this has disadvantages, especially when working in the class of normal functions, as pointwise limits do not preserve normality. To this end we present an alternative method to assign to each normal function f a family of normal functions Hyp[f]=〈fξ〉ξ∈OnHyp[f]=〈fξ〉ξ∈On, called its hyperation, in such a way that f0=idf0=id, f1=ff1=f and fα+β=fα∘fβfα+β=fα∘fβ for all α, β.Hyperations are a refinement of the Veblen hierarchy (...) of f. Moreover, if f is normal and has a well-behaved left-inverse g called a left adjoint, then g can be assigned a cohyperationcoH[g]=〈gξ〉ξ∈OncoH[g]=〈gξ〉ξ∈On, which is a family of initial functions such that gξgξ is a left adjoint to fξfξ for all ξ. (shrink)

This paper studies several systems of the transfinite iteration and autonomous progression of self-applicable truth and determines their proof-theoretic strength.

We apply Mints’ technique for proving the termination of the epsilon substitution method via cut-elimination to the system of Peano Arithmetic with Transfinite Induction given by Arai.

In the context of reverse mathematics, effective transfinite recursion refers to a principle that allows us to construct sequences of sets by recursion along arbitrary well orders, provided that each set is ‐definable relative to the previous stages of the recursion. It is known that this principle is provable in. In the present note, we argue that a common formulation of effective transfinite recursion is too restrictive. We then propose a more liberal formulation, which appears very natural and (...) is still provable in. (shrink)

Let T be a second-order arithmetical theory, Λ a well-order, λ < Λ and X ⊆ ℕ. We use $[\lambda |X]_T^{\rm{\Lambda }}\varphi$ as a formalization of “φ is provable from T and an oracle for the set X, using ω-rules of nesting depth at most λ”.For a set of formulas Γ, define predicative oracle reflection for T over Γ ) to be the schema that asserts that, if X ⊆ ℕ, Λ is a well-order and φ ∈ Γ, then$$\forall \,\lambda (...) < {\rm{\Lambda }}\,.$$In particular, define predicative oracle consistency ) as Pred–O–RFN{0=1}.Our main result is as follows. Let ATR0 be the second-order theory of Arithmetical Transfinite Recursion, ${\rm{RCA}}_0^{\rm{*}}$ be Weakened Recursive Comprehension and ACA be Arithmetical Comprehension with Full Induction. Then,$${\rm{ATR}}_0 \equiv {\rm{RCA}}_0^{\rm{*}} + {\rm{Pred - O - Cons\ }}\left \equiv {\rm{RCA}}_0^{\rm{*}} + \,{\rm{Pred - O - Cons\ }}\left \equiv {\rm{RCA}}_0^{\rm{*}} + \,{\rm{Pred - O - RFN}}\,_{{\bf{\Pi }}_2^1 } \left.$$We may even replace ${\rm{RCA}}_0^{\rm{*}}$ by the weaker ECA0, the second-order analogue of Elementary Arithmetic.Thus we characterize ATR0, a theory often considered to embody Predicative Reductionism, in terms of strong reflection and consistency principles. (shrink)

The author here constructs a system of simple type theory in which the type hierarchy does not extend merely to any finite height, but to an infinite height; this added part allows him to prove the existence of infinite sets within the theory, instead of taking it as an axiom in the usual simple type theory. The system has been presented in such sufficient generality so as to make it able to accommodate current scientific theories; the author has turned in (...) the direction of using type theory rather than set theory as the underlying logic of scientific theories. The system is formalized in Church's lambda-calculus notation; the semantics of the system are treated in great detail and appear to be the most complete study so far in print. The system is shown to contain at each type a "basic logic" somewhat similar to first-order logic; the author also shows that Peano's axioms for arithmetic appear as theorems when cast in suitable form. This book is one of a number of recent studies of type theory; together they represent a revival of interest in the subject, both as a foundation for mathematics and as an object of interest in itself. The book stems from Andrews' Princeton doctoral thesis.—P. J. M. (shrink)

Context: Consistency of mathematical constructions in numerical analysis and the application of computerized proofs in the light of the occurrence of numerical chaos in simple systems. Purpose: To show that a computer in general and a numerical analysis in particular can add its own peculiarities to the subject under study. Hence the need of thorough theoretical studies on chaos in numerical simulation. Hence, a questioning of what e.g. a numerical disproof of a theorem in physics or a prediction in numerical (...) economics could mean. Method: An algebraic simple model system is subjected to a deeper structure of underlying variables. With an algorithm simulating the steps in taking a limit of second order difference quotients the error terms are studied at the background of their algebraic expression. Results: With the algorithm that was applied to a simple quadratic polynomial system we found unstably amplified round-off errors. The possibility of numerical chaos is already known but not in such a simple system as used in our paper. The amplification of the errors implies that it is not possible with computer means to constructively show that the algebra and numerical analysis will ‘on the long run’ converge to each other and the error term will vanish. The algebraic vanishing of the error term cannot be demonstrated with the use of the computer because the round-off errors are amplified. In philosophical terms, the amplification of the round-off error is equivalent to the continuum hypothesis. This means that the requirement of (numerical) construction of mathematical objects is no safeguard against inference-only conclusions of qualities of (numerical) mathematical objects. Unstably amplified round-off errors are a same type of problem as the ordering in size of transfinite cardinal numbers. The difference is that the former problem is created within the requirements of constructive mathematics. This can be seen as the reward for working numerically constructive. (shrink)

If α and β are ordinals, α ≤ β, and $\beta \nleq \alpha$ , then α + 1 ≤ β. The first result of this paper shows that the restriction of this statement to countable well orderings is provably equivalent to ACA 0 , a subsystem of second order arithmetic introduced by Friedman. The proof of the equivalence is reminiscent of Dekker's construction of a hypersimple set. An application of the theorem yields the equivalence of the set comprehension scheme ACA (...) 0 and an arithmetical transfinite induction scheme. (shrink)