Search

A subset $S$ of a cardinal $\kappa$ is Ramsey if for every function $f:[S]^{, Comment: this is the final version uploaded to JSL

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 $$\limsup $$ of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the $$\limsup $$ 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 (wITTMs). 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.

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 $$\varDelta _0$$ formulae are provable in $$\mathbf {I}\varvec{\Sigma }_n$$. It is shown to be larger than the proof-theoretic ordinal $$|\mathbf {I}\varvec{\Sigma }_n|$$ by power of base 2. We also show a similar result for the structural transfinite induction, defined with fundamental sequences.

We show that for any $\omega $ -r.e. degree $\boldsymbol{d}$ and $n$ -r.e. degree $\boldsymbol{b}$ with $\boldsymbol{d}\lt \boldsymbol{b}$ , there is an $(\omega +1)$ -r.e. degree $\boldsymbol{a}$ strictly between $\boldsymbol{d}$ and $\boldsymbol{b}$ . We also show that there is a maximal incomplete $(\omega +1)$ -r.e. degree. As a corollary, $\mathcal{D}_{\omega }$ is not a $\Sigma _{1}$ -elementary substructure of $\mathcal{D}_{\omega +1}$ .

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 $\Delta^0_1$-definable relative to the previous stages of the recursion. It is known that this principle is provable in $\mathbf{ACA}_0$. 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 $\mathbf{ACA}_0$.

In recent work Philip Welch has proven the existence of ‘ineffable liars’ for Hartry Field’s theory of truth. These are offered as liar-like sentences that escape classification in Field’s transfinite hierarchy of determinateness operators. In this article I present a slightly more general characterization of the ineffability phenomenon, and discuss its philosophical significance. I show the ineffable sentences to be less ‘liar-like’ than they appear in Welch’s presentation. I also point to some open technical problems whose resolution would greatly clarify the philosophical issues raised by the ineffability phenomenon.

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 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(\leq \textbf {0}')}$ 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 (2012), 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, there is an $\omega +1$ -r.e. set A such that $D. 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. In Chapter 4, we generalize above results to higher levels (up to $\varepsilon _{0}$ ). 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.Abstract prepared by Cheng Peng.E-mail: pengcheng@nankai.edu.cn

Martin’s conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states that every function which is above the identity is eventually equal to a transfinite iterate of the jump. If true, it would provide an explanation for the unique role of the Turing jump in computability theory and rule out many types of constructions on the Turing degrees.In this thesis, we will introduce a few tools which we use to prove several cases of Martin’s conjecture. It turns out that both these tools and these results on Martin’s conjecture have some interesting consequences both for Martin’s conjecture and for a few related topics.The main tool that we introduce is a basis theorem for perfect sets, improving a theorem due to Groszek and Slaman. We also introduce a general framework for proving certain special cases of Martin’s conjecture which unifies a few pre-existing proofs. We will use these tools to prove three main results about Martin’s conjecture: that it holds for regressive functions on the hyperarithmetic degrees (answering a question of Slaman and Steel), that part 1 holds for order preserving functions on the Turing degrees, and that part 1 holds for a class of functions that we introduce, called measure preserving functions.This last result has several interesting consequences for the study of Martin’s conjecture. In particular, it shows that part 1 of Martin’s conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. This suggests several possible strategies for working on part 1 of Martin’s conjecture, which we will discuss.The basis theorem that we use to prove these results also has some applications outside of Martin’s conjecture. We will use it to prove a few theorems related to Sacks’ question about whether it is provable in $\mathsf {ZFC}$ that every locally countable partial order of size continuum embeds into the Turing degrees. We will show that in a certain extension of $\mathsf {ZF}$ (which is incompatible with $\mathsf {ZFC}$ ), this holds for all partial orders of height two, but not for all partial orders of height three. Our proof also yields an analogous result for Borel partial orders and Borel embeddings in $\mathsf {ZF}$ , which shows that the Borel version of Sacks’ question has a negative answer.We will end the thesis with a list of open questions related to Martin’s conjecture, which we hope will stimulate further research.Abstract prepared by Patrick Lutz.E-mail: pglutz@berkeley.edu

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 $\oplus$ and $\otimes$), each satisfying its own set of algebraic laws. In 1909, Jacobsthal considered a third, intermediate way of multiplying ordinals (denoted $\times$), defined by transfinite iteration of natural addition, as well as the notion of exponentiation defined by transfinite iteration of his multiplication, which we denote $\alpha^{\times\beta}$. (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 will denote this $\alpha^{\otimes\beta}$. We show that $\alpha^{\otimes(\beta\oplus\gamma)} = (\alpha^{\otimes\beta}) \otimes(\alpha^{\otimes\gamma})$ and that $\alpha^{\otimes(\beta\times\gamma)}=(\alpha^{\otimes\beta})^{\otimes\gamma}$; note the use of Jacobsthal's multiplication in the latter. We also demonstrate the impossibility of defining a "natural exponentiation" satisfying reasonable algebraic laws., Comment: 18 pages, 3 tables

The class forcing theorem, which asserts that every class forcing notion $\mathbb{P}$ admits a forcing relation $\Vdash_{\mathbb{P}}$, that is, a relation satisfying the forcing relation recursion -- it follows that statements true in the corresponding forcing extensions are forced and forced statements are true -- is equivalent over G\"odel-Bernays set theory GBC to the principle of elementary transfinite recursion $\text{ETR}_{\text{Ord}}$ for class recursions of length $\text{Ord}$. It is also equivalent to the existence of truth predicates for the infinitary languages $\mathcal{L}_{\text{Ord},\omega}(\in,A)$, allowing any class parameter $A$; to the existence of truth predicates for the language $\mathcal{L}_{\text{Ord},\text{Ord}}(\in,A)$; to the existence of $\text{Ord}$-iterated truth predicates for first-order set theory $\mathcal{L}_{\omega,\omega}(\in,A)$; to the assertion that every separative class partial order $\mathbb{P}$ has a set-complete class Boolean completion; to a class-join separation principle; and to the principle of determinacy for clopen class games of rank at most $\text{Ord}+1$. Unlike set forcing, if every class forcing notion $\mathbb{P}$ has a forcing relation merely for atomic formulas, then every such $\mathbb{P}$ has a uniform forcing relation applicable simultaneously to all formulas. Our results situate the class forcing theorem in the rich hierarchy of theories between GBC and Kelley-Morse set theory KM., Comment: 34 pages. Commentary concerning this paper can be made at http://jdh.hamkins.org/class-forcing-theorem

By Solovay’s celebrated completeness result [31] on formal provability we know that the provability logic ${\textbf {GL}}$ describes exactly all provable structural properties for any sound and strong enough arithmetical theory with a decidable axiomatisation. Japaridze generalised this result in [22] by considering a polymodal version ${\mathsf {GLP}}$ of ${\textbf {GL}}$ with modalities $[n]$ for each natural number n referring to ever increasing notions of provability. Modern treatments of ${\mathsf {GLP}}$ tend to interpret the $[n]$ provability notion as “provable in a base theory T together with all true $\Pi ^0_n$ formulas as oracles.” In this paper we generalise this interpretation into the transfinite. In order to do so, a main difficulty to overcome is to generalise the syntactical characterisations of the oracle formulas of complexity $\Pi ^0_n$ to the hyper-arithmetical hierarchy. The paper exploits the fact that provability is $\Sigma ^0_1$ complete and that similar results hold for stronger provability notions. As such, the oracle sentences to define provability at level $\alpha $ will recursively be taken to be consistency statements at lower levels: provability through provability whence the name of the paper. The paper proves soundness and completeness for the proposed interpretation for a wide class of theories, namely for any theory that can formalise the recursion described above and that has some further very natural properties. Some remarks are provided on how the recursion can be formalised into second order arithmetic and on lowering the proof-theoretical strength of these systems of second order arithmetic.

We study the computational strength of resetting $\alpha$-register machines, a model of transfinite computability introduced by P. Koepke in \cite{K1}. Specifically, we prove the following strengthening of a result from \cite{C}: For an exponentially closed ordinal $\alpha$, we have $L_{\alpha}\models$ZF$^{-}$ if and only if COMP$^{\text{ITRM}}_{\alpha}=L_{\alpha+1}\cap\mathfrak{P}(\alpha)$, i.e. if and only if the set of $\alpha$-ITRM-computable subsets of $\alpha$ coincides with the set of subsets of $\alpha$ in $L_{\alpha+1}$. Moreover, we show that, if $\alpha$ is exponentially closed and $L_{\alpha}\not\models$ZF$^{-}$, then COMP$^{\text{ITRM}}_{\alpha}=L_{\beta(\alpha)}\cap\mathfrak{P}(\alpha)$, where $\beta(\alpha)$ is the supremum of the $\alpha$-ITRM-clockable ordinals, which coincides with the supremum of the $\alpha$-ITRM-computable ordinals. We also determine the set of subsets of $\alpha$ computable by an $\alpha$-ITRM with time bounded below $\delta$ when $\delta>\alpha$ is an exponentially closed ordinal smaller than the supremum of the $\alpha$-ITRM-clockable ordinals. Moreover, we obtain some sufficient and necessary conditions on ordinals $\alpha$ for which the $\alpha$-wITRM-clockable ordinals are bounded by $\alpha$.

We show that arithmetical transfinite recursion is equivalent to a suitable formalization of the following: For every ordinal $\alpha$ there exists an ordinal $\beta$ such that $1+\beta\cdot(\beta+\alpha)$ (ordinal arithmetic) admits an almost order preserving collapse into $\beta$. Arithmetical comprehension is equivalent to a statement of the same form, with $\beta\cdot\alpha$ at the place of $\beta\cdot(\beta+\alpha)$. We will also characterize the principles that any set is contained in a countable coded $\omega$-model of arithmetical transfinite recursion resp. arithmetical comprehension., Comment: This is the accepted version of a paper published in The Journal of Symbolic Logic

We establish natural criteria under which normally iterable premice are iterable for stacks of normal trees. Let $\Omega$ be a regular uncountable cardinal. Let $m, Comment: 120 pages. Changes this version: Corrected definition of k-maximal iteration tree (for MS-premice with superstrongs; see Footnote 11). Corrected small errors in section 2 and its application (see Footnote 16). Changed definition of putative tree (see Footnote 13). Small corrections/improvements in Thm 4.47, Cor 7.6, Lem 9.8, Sec 9.1.4. Updated bibliography. Other minor edits

In the late 1980s, Selivanov used typed Boolean combinations of arithmetical sets to extend the Ershov hierarchy beyond Δ 2 0 sets. Similar to the Ershov hierarchy, Selivanov's fine hierarchy { Σ γ } γ e 0 proceeds through transfinite levels below e 0 to cover all arithmetical sets. In this paper we use a 0‴ construction to show that the Σ 3 0 Turing degrees are properly contained in the Σ ω ω + 2 Turing degrees (to be defined); intuitively, the latter class consists of “non-uniformly Σ 3 0 sets” in the sense that will be clarified in the introduction. The question whether the hierarchy was proper at this level with respect to Turing reducibility remained open for over 20 years.

We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion ( ATR 0 ) from the point of view of computability-theoretic reducibilities, in particular Weihrauch reducibility. Our main result states that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. This answers a question of Marcone. We obtain a similar result for Fraisse's conjecture restricted to well-orderings.

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.

Game characterizations of classes of functions in descriptive set theory have their origins in the seminal work of Wadge, with further developments by several others. In this thesis we study such characterizations from several perspectives. We define modifications of Semmes's game characterization of the Borel functions, obtaining game characterizations of the Baire class $\alpha$ functions for each fixed $\alpha < \omega_1$. We also define a construction of games which transforms a game characterizing a class $\Lambda$ of functions into a game characterizing the class of functions which are piecewise $\Lambda$ on a countable partition by $\Pi^0_\alpha$ sets, for each $0 < \alpha < \omega_1$. We then define a parametrized Wadge game by using computable analysis, and show how the parameters affect the class of functions that is characterized by the game. As an application, we recast our games characterizing the Baire classes into this framework. Furthermore, we generalize our game characterizations of function classes to generalized Baire spaces, show how the notion of computability on Baire space can be transferred to generalized Baire spaces, and show that this is appropriate for computable analysis by defining a representation of Galeotti's generalized real line and analyzing the Weihrauch degree of the intermediate value theorem for that space. Finally, we show how the game characterizations of function classes discussed lead in a natural way to a stratification of each class into a hierarchy, intuitively measuring the complexity of functions in that class. This idea and the results presented open new paths for further research.

Compactness is one of the core notions of analysis: it connects local properties to global ones and makes limits well-behaved. We study the computational properties of the compactness of Cantor space $2^{\mathbb{N}}$ for uncountable covers. The most basic question is: how hard is it to compute a finite sub-cover from such a cover of $2^{\mathbb{N}}$? Another natural question is: how hard is it to compute a sequence that covers $2^{\mathbb{N}}$ minus a measure zero set from such a cover? The special and weak fan functionals respectively compute such finite sub-covers and sequences. In this paper, we establish the connection between these new fan functionals on one hand, and various well-known comprehension axioms on the other hand, including arithmetical comprehension, transfinite recursion, and the Suslin functional. In the spirit of Reverse Mathematics, we also analyse the logical strength of compactness in Nonstandard Analysis. Perhaps surprisingly, the results in the latter mirror (often perfectly) the computational properties of the special and weak fan functionals. In particular, we show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely $\Pi_2^1$-CA$_0$), and even into Schweber's higher-order framework (namely $\Sigma_{1}^{2}$-separation)., Comment: To appear in Annals of Pure and Applied Logic

We analyze the descriptive complexity of several $\Pi^1_1$ ranks from classical analysis which are associated to Denjoy integration. We show that $VBG, VBG_\ast, ACG$ and $ACG_\ast$ are $\Pi^1_1$-complete, answering a question of Walsh in case of $ACG_\ast$. Furthermore, we identify the precise descriptive complexity of the set of functions obtainable with at most $\alpha$ steps of the transfinite process of Denjoy totalization: if $|\cdot|$ is the $\Pi^1_1$-rank naturally associated to $VBG, VBG_\ast$ or $ACG_\ast$, and if $\alpha, Comment: 17 pages

We examine recursive monotonic functions on the Lindenbaum algebra of $EA$. We prove that no such function sends every consistent φ to a sentence with deductive strength strictly between φ and $\left( {\varphi \wedge Con\left( \varphi \right)} \right)$. We generalize this result to iterates of consistency into the effective transfinite. We then prove that for any recursive monotonic function f, if there is an iterate of $Con$ that bounds f everywhere, then f must be somewhere equal to an iterate of $Con$.

In this article I investigate the phenomenon of minimum models of second-order set theories, focusing on Kelley--Morse set theory $\mathsf{KM}$, G\"odel--Bernays set theory $\mathsf{GB}$, and $\mathsf{GB}$ augmented with the principle of Elementary Transfinite Recursion. The main results are the following. (1) A countable model of $\mathsf{ZFC}$ has a minimum $\mathsf{GBC}$-realization if and only if it admits a parametrically definable global well-order. (2) Countable models of $\mathsf{GBC}$ admit minimal extensions with the same sets. (3) There is no minimum transitive model of $\mathsf{KM}$. (4) There is a minimum $\beta$-model of $\mathsf{GB} + \mathsf{ETR}$. The main question left unanswered by this article is whether there is a minimum transitive model of $\mathsf{GB} + \mathsf{ETR}$., Comment: 30 pages

We study the complexity of term rewrite systems compatible with the Knuth-Bendix order, if the signature of the rewrite system is potentially infinite. We show that the known bounds on the derivation height are essentially preserved, if the rewrite system fulfils some mild conditions. This allows us to obtain bounds on the derivational height of non simply terminating rewrite systems. As a corollary, we re-establish an essentially optimal 2-recursive upper bound on the derivational complexity of finite rewrite systems compatible with a Knuth-Bendix order. Furthermore we link our main result to results on generalised Knuth-Bendix orders and to recent results on transfinite Knuth-Bendix orders.

Revision sequences are a kind of transfinite sequences which were introduced by Herzberger and Gupta in 1982 (independently) as the main mathematical tool for developing their respective revision theories of truth. We generalise revision sequences to the notion of cofinally invariant sequences, showing that several known facts about Herzberger's and Gupta's theories also hold for this more abstract kind of sequences and providing new and more informative proofs of the old results.

In [7] , open questions are raised regarding the computational strengths of so-called ∞-α-Turing machines, a family of models of computation resembling the infinite-time Turing machine (ITTM) model of [2] , except with α-length tape (for α ≥ ω ). Let T α denote the machine model of tape length α (so T ω is just the ITTM model). Define that T α is computationally stronger than T β (abbreviated T α ≻ T β ) precisely when T α can compute all T β -computable functions f : 2 min ( α , β ) → 2 min ( α , β ) , plus more. The following results are found: (1) T ω 1 ≻ T ω . (2) There are countable ordinals α such that T α ≻ T ω , the smallest of which is precisely γ, the supremum of ordinals clockable by T ω . In fact, there is a hierarchy of countable T α s of increasing strength corresponding to the transfinite (weak) Turing-jump operator ∇ . (3) There is a countable ordinal μ such that neither T μ ⪰ T ω 1 nor T μ ⪯ T ω 1 —that is, the models T μ and T ω 1 are computation-strength incommensurable (and the same holds if countable μ ′ > μ replaces μ). A similar fact holds for any larger uncountable device replacing T ω 1 . (4) Further observations are made about countable T α .

Define a second order tree to be a map between trees (with fixed codomain). We show that many properties of ordinary trees have analogs for second order trees. In particular, we show that there is a notion of “definition by recursion on a well-founded second order tree” which generalizes “definition by transfinite recursion”. We then use this new notion of definition by recursion to prove an analog of Lusin’s Separation theorem for closure spaces of global sections of a second order tree.

Provability logics are modal or polymodal systems designed for modeling the behavior of Godel’s provability predicate and its natural extensions. If Λ is any ordinal, the Godel-Lob calculus GLP Λ contains one modality [λ] for each λ

This article reports that some robustness of the notions of predicativity and of autonomous progression is broken down if as the given infinite total entity we choose some mathematical entities other than the traditionalω. Namely, the equivalence between normal transfinite recursion scheme and newdependent transfinite recursionscheme, which does hold in the context of subsystems of second order number theory, does not hold in the context of subsystems of second order set theory where the universeVof sets is treated as the given totality (nor in the contexts of those ofn+3-th order number or set theories, where the class of alln+2-th order objects is treated as the given totality).

In this paper we introduce hyperations and cohyperations, which are forms of transnite iteration of ordinal functions. Hyperations are iterations of normal functions. Unlike iteration by pointwise convergence, hyperation preserves normality. The hyperationhf i 2On of a normal function f is a sequence of normal functions so that f 0 = id, f 1 = f and for all ; we have that f + = f f . These conditions do not determine f uniquely; in addition, we require thathf i 2On be minimal in an appropriate sense. We study hyperations systematically and show that they are a natural renement of Veblen progressions. Next, we dene cohyperations, very similar to hyperations except that they are left-additive: given ; , f + = f f . Cohyperations iterate initial functions which are functions that map initial segments to initial segments. We systematically study co-hyperations and see how they can be employed to dene left inverses to hyperations. Hyperations provide an alternative presentation of Veblen progressions and can be useful where a more ne-grained analysis of such sequences is

For any ordinal Λ, we can define a polymodal logic GLPΛ, with a modality [ξ] for each ξ < Λ. These represent provability predicates of increasing strength. Although GLPΛ has no Kripke models, Ignatiev showed that indeed one can construct a Kripke model of the variable-free fragment with natural number modalities, denoted . Later, Icard defined a topological model for which is very closely related to Ignatiev's.In this paper we show how to extend these constructions for arbitrary Λ. More generally, for each Θ, Λ we build a Kripke model and a topological model , and show that is sound for both of these structures, as well as complete, provided Θ is large enough.

Schmerl and Beklemishev's work on iterated reflection achieves two aims: It introduces the important notion of $\Pi^0_1$-ordinal, characterizing the $\Pi^0_1$-theorems of a theory in terms of transfinite iterations of consistency; and it provides an innovative calculus to compute the $\Pi^0_1$-ordinals for a range of theories. The present note demonstrates that these achievements are independent: We read off $\Pi^0_1$-ordinals from a Sch\"utte-style ordinal analysis via infinite proofs, in a direct and transparent way., Comment: This is a pre-print (before peer-review) of an article published in the Archive for Mathematical Logic. The final authenticated version is available online at https://doi.org/10.1007/s00153-018-0639-y. It can also be accessed via https://rdcu.be/2YJI (view only). Note that the journal version contains some improvements over the present pre-print

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.

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

This paper begins an axiomatic development of naive set theory—the consequences of a full comprehension principle—in 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.

Cantor’s theory of cardinal numbers offers a way to generalize arithmetic from finite sets to infinite sets using the notion of one-to-one association between two sets. As is well known, all countable infinite sets have the same ‘size’ in this account, namely that of the cardinality of the natural numbers. However, throughout the history of reflections on infinity another powerful intuition has played a major role: if a collection A is properly included in a collection B then the ‘size’ of A should be less than the ‘size’ of B (part–whole principle). This second intuition was not developed mathematically in a satisfactory way until quite recently. In this article I begin by reviewing the contributions of some thinkers who argued in favor of the assignment of different sizes to infinite collections of natural numbers (Thabit ibn Qurra, Grosseteste, Maignan, Bolzano). Then, I review some recent mathematical developments that generalize the part–whole principle to infinite sets in a coherent fashion (Katz, Benci, Di Nasso, Forti). Finally, I show how these new developments are important for a proper evaluation of a number of positions in philosophy of mathematics which argue either for the inevitability of the Cantorian notion of infinite number (Gödel) or for the rational nature of the Cantorian generalization as opposed to that, based on the part–whole principle, envisaged by Bolzano (Kitcher).

In this paper we prove that, in the Cohen extension (adding ℵ 2 -generic reals) of a model M of ZFC+CH containing a simplified ( ω 1 , 1 ) -morass, η 1 -orderings without endpoints having cardinality of the continuum, and satisfying specified technical conditions, are order-isomorphic. Furthermore, any order-isomorphism in M between countable subsets of the η 1 -orderings can be extended to an order-isomorphism between the η 1 -orderings in the Cohen extension of M . We use the simplified ( ω 1 , 1 ) -morass, and commutativity conditions with morass maps on terms in the forcing language, to extend countable partial functions on terms in the forcing language that are forced in all generic extensions to be order-preserving injections. This technique provides for the construction of functions in Cohen extensions adding ℵ 2 generic reals for which the only known arguments require transfinite constructions of order type no greater than ω 1 in models of ZFC+CH. The specific example presented in this paper is an extension of Tarski’s classic result that in models of ZFC+CH, η 1 -orderings are order-isomorphic.

In [10] it is claimed that the set of predicate tautologies of all complete BL-chains and the set of all standard tautologies (i. e., the set of predicate formulas valid in all standard BL-algebras) coincide. As noticed in [11], this claim is wrong. In this paper we show that a complete BL-chain B satisfies all standard BL-tautologies iff for any transfinite sequence (ai: i ∈ I) of elements of B, the condition ∧i ∈ I (a2i) = (∧i ∈ Iai)2 holds in B. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

We define a class of finite state automata acting on transfinite sequences, and use these automata to prove that no singular cardinal can be defined by a monadic second order formula over the ordinals. A formula φ is monadic second order (monadic for short) if each of its variables is assigned a type, either the type “first order” or the type “second order.” When interpreting the formula over a structure with universe A, the first order variables are taken to range over elements of A, and the second order variables are taken to range over subsets (or subclasses) of A. For more on monadic theories we refer the reader to Gurevich [4]. Let us here note that monadic formulae do not allow, at least not directly, talking about sets of pairs of elements of A. In particular they need not introduce Godel sentences, and they need not allow the defining of cardinality. Let ON be the class of all ordinals. The following are examples of statements about ordinals and sets of ordinals that can be expressed in the monadic language over (ON

We describe a "slow" version of the hierarchy of uniform reflection principles over Peano Arithmetic ($\mathbf{PA}$). These principles are unprovable in Peano Arithmetic (even when extended by usual reflection principles of lower complexity) and introduce a new provably total function. At the same time the consistency of $\mathbf{PA}$ plus slow reflection is provable in $\mathbf{PA}+\operatorname{Con}(\mathbf{PA})$. We deduce a conjecture of S.-D. Friedman, Rathjen and Weiermann: Transfinite iterations of slow consistency generate a hierarchy of precisely $\varepsilon_0$ stages between $\mathbf{PA}$ and $\mathbf{PA}+\operatorname{Con}(\mathbf{PA})$ (where $\operatorname{Con}(\mathbf{PA})$ refers to the usual consistency statement)., Comment: This version has been accepted for publication in the Annals of Pure and Applied Logic

This paper presents a systematic study of the prehistory of the traditional subsystems of second-order arithmetic that feature prominently in the reverse mathematics program of Friedman and Simpson. We look in particular at: (i) the long arc from Poincar\'e to Feferman as concerns arithmetic definability and provability, (ii) the interplay between finitism and the formalization of analysis in the lecture notes and publications of Hilbert and Bernays, (iii) the uncertainty as to the constructive status of principles equivalent to Weak K\"onig's Lemma, and (iv) the large-scale intellectual backdrop to arithmetical transfinite recursion in descriptive set theory and its effectivization by Borel, Lusin, Addison, and others., Comment: Forthcoming in The Review of Symbolic Logic

Hilbert proposed the epsilon substitution method as a basis for consistency proofs. Hilbert’s Ansatz for finding a solving substitution for any given finite set of transfinite axioms is, starting with the null substitution S 0 , to correct false values step by step and thereby generate the process S 0 , S 1 , … . The problem is to show that the approximating process terminates. After Gentzen’s innovation, Ackermann [W. Ackermann, Zur Widerspruchsfreiheit der Zahlentheorie, Math. Ann. 117 (1940) 162–194] succeeded in proving the termination of the process for the first order arithmetic. In this note we report recent progress on the subject, and expound basic ideas of the epsilon substitution method a la Ackermann for the theory Π 1 0 -FIX of non-monotonic Π 1 0 inductive definitions.

Gödel has emphasized the important role that his philosophical views had played in his discoveries. Thus, in a letter to Hao Wang of December 7, 1967, explaining why Skolem and others had not obtained the completeness theorem for predicate calculus, Gödel wrote:This blindness (or prejudice, or whatever you may call it) of logicians is indeed surprising. But I think the explanation is not hard to find. It lies in a widespread lack, at that time, of the required epistemological attitude toward metamathematics and toward non-finitary reasoning. …I may add that my objectivist conception of mathematics and metamathematics in general, and of transfinite reasoning in particular, was fundamental also to my other work in logic.How indeed could one think of expressing metamathematics in the mathematical systems themselves, if the latter are considered to consist of meaningless symbols which acquire some substitute of meaning only through metamathematics?Or how could one give a consistency proof for the continuum hypothesis by means of my transfinite model Δ if consistency proofs have to be finitary?In a similar vein, Gödel has maintained that the “realist” or “Platonist” position regarding sets and the transfinite with which he is identified was part of his belief system from his student days. This can be seen in Gödel's replies to the detailed questionnaire prepared by Burke Grandjean in 1974. Gödel prepared three tentative mutually consistent replies, but sent none of them.

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

Hilbert proposed the epsilon substitution method as a basis for consistency proofs. Hilbert's Ansatz for finding a solving substitution for any given finite set of transfinite axioms is, starting with the null substitution S0, to correct false values step by step and thereby generate the process S0,S1,…. The problem is to show that the approximating process terminates. After Gentzen's innovation, Ackermann (Maths. Ann. 117 (1940) 162) succeeded to prove termination of the process for first order arithmetic.Inspired by G. Mints (draft June 1, 2000) as an Ariadne's thread we formulate the epsilon substitution method for the theory ID1(Π10∨Σ10) of non-iterated inductive definitions for disjunctions of simply universal and existential operators, and give a termination proof of the H-process based on Ackermann (Maths. Ann. 117 (1940) 162). The termination proof is based on transfinite induction up to the Howard ordinal.

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 (concerning computations related to the hierarchy) are presented.

This paper expands upon a way in which we might rationally doubt that there are multiple sizes of infinity. The argument draws its inspiration from recent work in the philosophy of truth and philosophy of set theory. More specifically, elements of contextualist theories of truth and multiverse accounts of set theory are brought together in an effort to make sense of Cantor’s troubling theorem. The resultant theory provides an alternative philosophical perspective on the transfinite, but has limited impact on everyday mathematical practice.

We use the theory of domains with totality to construct some logics generalizing ω-logic and β-logic and we prove a completenes theorem for these logics. The key application is E-logic, the logic related to the functional 3E. We prove a compactness theorem for sets of sentences semicomputable in 3E.

We show how Kreisel's representation theorem for sets in the analytical hierarchy can be generalized to sets defined by positive induction and use this to estimate the complexity of constructions in the theory of domains with totality.

We give a characterisation of an extension of the Kleene-Kreisel continuous functionals to objects of transfinite types using limit spaces of transfinite types.

We prove Fraïssé’s conjecture within the system of [Formula: see text]-comprehension. Furthermore, we prove that Fraïssé’s conjecture follows from the [Formula: see text]-bqo-ness of 3 over the system of Arithmetic Transfinite Recursion, and that the [Formula: see text]-bqo-ness of 3 is a [Formula: see text]-statement strictly weaker than [Formula: see text]-comprehension.