We consider two variants of transfinite induction, one with monotonicity assumption on the predicate and one with the induction hypothesis only for cofinally many below. The latter can be seen as a transfinite analogue of the successor induction, while the usual transfinite induction is that of cumulative induction. We calculate the supremum of ordinals along which these schemata for \ formulae are provable in \. It is shown to be larger than the proof-theoretic ordinal \ by (...) power of base 2. We also show a similar result for the structural transfinite induction, defined with fundamental sequences. (shrink)

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)

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)

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)

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)

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)

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.

§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)

Ordinal Computability discusses models of computation obtained by generalizing classical models, such as Turing machines or register machines, to transfinite working time and space. In particular, recognizability, randomness, and applications to other areas of mathematics, including set theory and model theory, are covered.

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)

In 1936, Gerhard Gentzen published a proof of consistency for Peano Arithmetic using transfinite induction up to ε0, which was considered a finitistically acceptable procedure by both Gentzen and Paul Bernays. Gentzen’s method of arithmetising ordinals and thus avoiding the Platonistic metaphysics of set theory traces back to the 1920s, when Bernays and David Hilbert used the method for an attempted proof of the Continuum Hypothesis. The idea that recursion on higher types could be used to simulate the (...) limit-building in transfinite recursion seems to originate from Bernays. The main difficulty, which was already discovered in Gabriel Sudan’s nearly forgotten paper of 1927, was that measuring transfinite ordinals requires stronger methods than representing them. This paper presents a historical account of the idea of nominalistic ordinals in the context of the Hilbert Programme as well as Gentzen and Bernays’ finitary interpretation of transfinite induction. (shrink)

An approach to ordinal analysis is presented which is finitary, but highlights the semantic content of the theories under consideration, rather than the syntactic structure of their proofs. In this paper the methods are applied to the analysis of theories extending Peano arithmetic with transfinite induction and transfinite arithmetic hierarchies.

For any ordinal $\Lambda$, we can define a polymodal logic $\mathsf{GLP}_\Lambda$, with a modality $[\xi]$ for each $\xi < \Lambda$. These represent provability predicates of increasing strength. Although $\mathsf{GLP}_\Lambda$ has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted $\mathsf{GLP}^0_\omega$. Later, Icard defined a topological model for $\mathsf{GLP}^0_\omega$ which is very closely related to Ignatiev's. In this paper we show how to extend these constructions for arbitrary $\Lambda$. (...) More generally, for each $\Theta,\Lambda$ we build a Kripke model $\mathfrak I^\Theta_\Lambda$ and a topological model $\mathfrak T^\Theta_\Lambda$, and show that $\mathsf{GLP}^0_\Lambda$ is sound for both of these structures, as well as complete, provided $\Theta$ is large enough. (shrink)

Provability logics are modal or polymodal systems designed for modeling the behavior of Gödel’s provability predicate and its natural extensions. If Λ is any ordinal, the Gödel-Löb calculus GLPΛ contains one modality [λ] for each λ < Λ, representing provability predicates of increasing strength. GLPω has no non-trivial Kripke frames, but it is sound and complete for its topological semantics, as was shown by Icard for the variable-free fragment and more recently by Beklemishev and Gabelaia for the full logic. In (...) this paper we generalize Beklemishev and Gabelaia’s result to GLPΛ for countable Λ. We also introduce provability ambiances, which are topological models where valuations of formulas are restricted. With this we show completeness of GLPΛ for the class of provability ambiances based on Icard polytopologies. (shrink)

The proposition that a decreasing sequence of ordinals necessarily terminates has been given a new, and perhaps unexpected, importance by the rôle which it plays in Gentzen's proof of the freedom from contradiction of the “reine Zahlentheorie.” Gödel's construction of non-demonstrable propositions and the establishment of the impossibility of a proof of freedom from contradiction, within the framework of a certain type of formal system, showed that a proof of freedom from contradiction could be found only by transcending the (...) axioms and proof processes of that formal system. Gentzen's proof succeeds by utilisingtransfinite inductionto prove that certain sequences of reduction processes, enumerated by ordinals less than ε (the first ordinal to satisfy ε = ὡ) are finite. Were it possible to provethe restricted ordinal theorem, that a descending sequence of ordinals, less thanε, is finite, in Gentzen's “reine Zahlentheorie,” then it would be possible to determine a contradiction in that number system. In his paper, Gentzen proves the theorem of transfinite induction, which he requires, by an intuitive argument. There is also a method of reducing transfinite induction, for ordinals less than ε, to a number-theoretic principle given by Hilbert and Bernays, and a similar method by Ackermann. None of these proofs of transfinite induction isfinitist. (shrink)

We show in this paper that the theory of ordinal addition of any fixed ordinal ωα, with α less than ωω, admits a quantifier elimination. This in particular gives a new proof for the decidability result first established in 1965 by R. Büchi using transfinite automata. Our proof is based on the Ehrenfeucht games, and we show that quantifier elimination go through generalized power.RésuméOn montre ici que, pour tout ordinal α inférieur à ωω, la théorie additive de ωα admet (...) une élimination des quantificateurs. On obtient ainsi une nouvelle preuve de la décidabilité de ces théories . On utilise ici les jeux d'Ehrenfeucht, avec un formalisme à la Ferrante et Rackoff, et on montre que le fait d'admettre une élimination des quantificateurs se transmet par produit généralisé. (shrink)

Where $\underline{a}$ is a Turing degree and ξ is an ordinal $ , the result of performing ξ jumps on $\underline{a},\underline{a}^{(\xi)}$ , is defined set-theoretically, using Jensen's fine-structure results. This operation appears to be the natural extension through $(\aleph_1)^{L^\underline{a}}$ of the ordinary jump operations. We describe this operation in more degree-theoretic terms, examine how much of it could be defined in degree-theoretic terms and compare it to the single jump operation.

This article provides the proof-theoretic analysis of the transfinitely iterated fixed point theories $\widehat{ID}_\alpha and \widehat{ID}_{ the exact proof-theoretic ordinals of these systems are presented.

This article provides the proof-theoretic analysis of the transfinitely iterated fixed point theories $\widehat{ID}_\alpha and \widehat{ID}_{<\alpha};$ the exact proof-theoretic ordinals of these systems are presented.

There are two well‐known ways of doing arithmetic with ordinal numbers: the “ordinary” addition, multiplication, and exponentiation, which are defined by transfinite iteration; and the “natural” (or “Hessenberg”) addition and multiplication (denoted ⊕ and ⊗), each satisfying its own set of algebraic laws. In 1909, Jacobsthal considered a third, intermediate way of multiplying ordinals (denoted × ), defined by transfinite iteration of natural addition, as well as the notion of exponentiation defined by transfinite iteration of his (...) multiplication, which we denote. (Jacobsthal's multiplication was later rediscovered by Conway.) Jacobsthal showed these operations too obeyed algebraic laws. In this paper, we pick up where Jacobsthal left off by considering the notion of exponentiation obtained by transfinitely iterating natural multiplication instead; we shall denote this. We show that and that ; note the use of Jacobsthal's multiplication in the latter. We also demonstrate the impossibility of defining a “natural exponentiation” satisfying reasonable algebraic laws. (shrink)

Transitive extensional well founded relations provide an intuitionistic notion of ordinals which admits transfinite induction. However these ordinals are not directed and their successor operation is poorly behaved, leading to problems of functoriality. We show how to make the successor monotone by introducing plumpness, which strengthens transitivity. This clarifies the traditional development of successors and unions, making it intuitionistic; even the (classical) proof of trichotomy is made simpler. The definition is, however, recursive, and, as their name suggests, (...) the plump ordinals grow very rapidly. Directedness must be defined hereditarily. It is orthogonal to the other four conditions, and the lower powerdomain construction is shown to be the universal way of imposing it. We treat ordinals as order-types, and develop a corresponding set theory similar to Osius' transitive set objects. This presents Mostowski's theorem as a reflection of categories, and set-theoretic union is a corollary of the adjoint functor theorem. Mostowski's theorem and the rank for some of the notions of ordinal are formulated and proved without the axiom of replacement, but this seems to be unavoidable for the plump rank. The comparison between sets and toposes is developed as far as the identification of replacement with completeness, and there are some suggestions for further work in this area. Each notion of set or ordinal defines a free algebra for one of the theories discussed by Joyal and Moerdijk, namely joins of a family of arities together with an operation s satisfying conditions such as x ≤ sx, monotonicity or s(x ∨ y) ≤ sx ∨ sy. Finally we discuss the fixed point theorem for a monotone endofunction s of a poset with least element and directed joins. This may be proved under each of a variety of additional hypotheses. We explain why it is unlikely that any notion of ordinal obeying the induction scheme for arbitrary predicates will prove the pure result. (shrink)

This article provides an ordinal analysis of Σ11 transfinite dependent choice.

Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations, equation image. Other cases are done for all transfinite notations in a very natural, proper subsystem equation image of equation (...) image, where equation image has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in equation image. (shrink)

α-recursion lifts classical recursion theory from the first transfinite ordinal ω to an arbitrary admissible ordinal α [10]. Idealized computational models for α-recursion analogous to Turing machine models for classical recursion have been proposed and studied [4] and [5] and are applicable in computational approaches to the foundations of logic and mathematics [8]. They also provide a natural setting for modeling extensions of the algorithmic logic described in [1] and [2]. On such models, an α-Turing machine can complete a (...) θ-step computation for any ordinal θ < α. Here we consider constraints on the physical realization of α-Turing machines that arise from the structure of physical spacetime. In particular, we show that an α-Turing machine is realizable in a spacetime constructed from R only if α is countable. While there are spacetimes where uncountable computations are possible and while they may even be empirically distinguishable from a standard spacetime, there is good reason to suppose that such nonstandard spacetimes are nonphysical. We conclude with a suggestion for a revision of Church’s thesis appropriate as an upper bound for physical computation. (shrink)

We redefine a system of varieties definable by a schema of equations to include finite dimensions. Then we present a technique using ultraproducts enabling one to lift results proved for every finite dimension to the transfinite. Let \(\bf Ord\) denote the class of all ordinals. Let \(\langle \mathbf{K}_{\alpha}: \alpha\in \bf Ord\rangle\) be a system of varieties definable by a schema. Given any ordinal \(\alpha\), we define an operator \(\mathsf{Nr}_{\alpha}\) that acts on \(\mathbf{K}_{\beta}\) for any \(\beta>\alpha\) giving an algebra (...) in \(\mathbf{K}_{\alpha}\), as an abstaction of taking \(\alpha\)-neat reducts for cylindric algebras. We show that for any positive \(k\), and any infinite ordinal \(\alpha\) that \(\mathbf{S}\mathsf{Nr}_{\alpha}\mathbf{K}_{\alpha+k+1}\) cannot be axiomatized by a finite schema over \(\mathbf{S}\mathsf{Nr}_{\alpha}\mathbf{K}_{\alpha+k}\) given that the result is valid for all finite dimensions greater than some fixed finite ordinal. We apply our results to cylindric algebras and Halmos quasipolyadic algebras with equality. As an application to our algebraic result we obtain a strong incompleteness theorem (in the sense that validitities are not captured by finitary Hilbert style axiomatizations) for an algebraizable extension of \(L_{\omega,\omega}\). (shrink)

Audrito and Viale introduced the new large cardinal notion of an (α)‐uplifting cardinal (for an ordinal α). We shall show that this notion cannot be defined (or expressed) in the standard first‐order language of set theory for every tranfinite α.

This is a text for a one or two semester course on axiomatic set theory; the goal is to introduce and develop one system of set theory in a complete and thorough way, presupposing only the elusive "mathematical maturity" of the reader. There are nine chapters which begin with a development of propositional and predicate logic oriented toward set theory and develop the Zermelo-Fraenkel system in exceptional detail. The book starts slowly, the first 120 pages being devoted to logical preliminaries (...) and the introduction of axioms; it gathers speed, however, and the remaining chapters include treatment of the algebra of classes, relations and functions, order of various sorts and Zorn's lemma, real numbers and equivalence classes, the equipollence of sets, similarity as a relation of sets, the ordinal numbers and their arithmetic, the cardinal numbers and their arithmetic. These later chapters are extremely detailed and comprehensive, presenting a wealth of material. There are numerous exercises, many quite difficult, at the end of each chapter, along with a summary of that chapter's content. Because of the single-mindedness of the book, there is little reference to other systems of set theory, but this is not a drawback at all. The presentation is orthodox, but not dull; careful, but not generally pedantic or repetitive. This makes it a good text for self-study.—P. J. M. (shrink)

“A little masterpiece of originality and clarity.”—George Steiner “A necessary book.”—Roberto Saviano “A wonderful little book that will delight you.”—François Busnel International Best Seller / Now in English for the First Time In this thought-provoking and extremely timely work, Nuccio Ordine convincingly argues for the utility of useless knowledge and against the contemporary fixation on utilitarianism—for the fundamental importance of the liberal arts and against the damage caused by their neglect. Inspired by the reflections of great philosophers and writers (e.g., (...) Plato, Dante, Montaigne, Shakespeare, Borges, and Calvino), Ordine reveals how the obsession for material goods and the cult of utility ultimately wither the spirit, jeopardizing not only schools and universities, art, and creativity, but also our most fundamental values—human dignity, love, and truth. Also included is Abraham Flexner’s 1939 essay “The Usefulness of Useless Knowledge,” which originally prompted Ordine to write this book. Flexner—a founder and the first director of the Institute for Advanced Study in Princeton—offers an impassioned defense of curiosity-driven research and learning. (shrink)

In this highly original study, Nuccio Ordine uses the figure of the ass as a lens through which to focus on the thought and writings of the great Renaissance humanist philosopher Giordano Bruno.

The five participants in this dialogue critically discuss Zeno of Elea's paradox of Achilles and the tortoise. They consider a number of solutions to and restatements of the paradox, together with their philosophical implications. Among the issues investigated include the appearance-reality distinction, Aristotle's distinction between actual and potential infinity, the concept of a continuum, Cantor's continuum hypothesis and theory of transfinite ordinals, and, as a solution to Zeno's puzzle, the distinction between infinite and indeterminate or inexhaustible divisibility.

Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only if the (...) content of that cell has stabilized before that limit step and is then equal to this constant value. We call these machines weak infinite time Turing machines. We study different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. We show that some of these models are equivalent to each other concerning their computational strength. We show that wITTMs decide exactly the arithmetic relations on natural numbers. (shrink)

Pensar en el cine como ocasión y potencia del pensamiento significa en efecto, en primer lugar, sustraer la imagen contemporánea del dominio de los estudios especializados y, en segundo lugar, pensar a partir de aquello que el cine crea (como recordaba Deleuze): esto es, las imágenes mismas. El cine redescubre su potencia a través de sus propias formas. Entrevistas de la revista italiana Fata Morgana con: Jacques Rancière, Roberto Esposito, Jean-luc Nancy, Slavoj Zizek, Julia Kristeva, Werner Herzog, Raúl Ruiz, Yervant (...) Gianikian, Ángela Ricci Lucchi, Edgar Reitz, Paul Schraoer, Georges Didi-Huberman, Jean-Louis Comolli, Nuccio Ordine. (shrink)

Quantum mechanics involves a generalized form of information, that of quantum information. It is the transfinite generalization of information and re-presentable by transfinite ordinals. The physical world being in the current of time shares the quality of “choice”. Thus quantum information can be seen as the universal substance of the world serving to describe uniformly future, past, and thus the present as the frontier of time. Future is represented as a coherent whole, present as a choice among (...) infinitely many alternatives, and past as a well-ordering obtained as a result of a series of choices. The concept of quantum information describes the frontier of time, that “now”, which transforms future into past. Quantum information generalizes information from finite to infinite series or collections. The concept of quantum information allows of any physical entity to be interpreted as some nonzero quantity of quantum information. The fundament of quantum information is the concept of ‘quantum bit’, “qubit”. A qubit is a choice among an infinite set of alternatives. It generalizes the unit of classical information, a bit, which refer to a finite set of alternatives. The qubit is also isomorphic to a ball in Euclidean space, in which two points are chosen. (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.