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.

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...) in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (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)

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.

We show that for any ω-r.e. degree d and n-r.e. degree b with d

Mathematical Logic in Philosophy of Mathematics

Direct download (3 more)  

 

Export citation  

 

Bookmark   1 citation  

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 (...) class='Hi'>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)

The general notions of object- and metalanguage are discussed and as a special case of this relation an arbitrary first order language with an infinite model is expanded by a predicate symbol T0 which is interpreted as truth predicate for . Then the expanded language is again augmented by a new truth predicate T1 for the whole language plus T0. This process is iterated into the transfinite to obtain the Tarskian hierarchy of languages. It is shown that there (...) are natural points for stopping this process. The sets which become definable in suitable hierarchies are investigated, so that the relevance of the Tarskian hierarchy to some subjects of philosophy of mathematics are clarified. (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)

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.

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)

We study large cardinal properties associated with Ramseyness in which homogeneous sets are demanded to satisfy various transfinite degrees of indescribability. Sharpe and Welch [25], and independently Bagaria [1], extended the notion of $\Pi ^1_n$ -indescribability where $n<\omega $ to that of $\Pi ^1_\xi $ -indescribability where $\xi \geq \omega $. By iterating Feng’s Ramsey operator [12] on the various $\Pi ^1_\xi $ -indescribability ideals, we obtain new large cardinal hierarchies and corresponding nonlinear increasing hierarchies of normal ideals. We (...) provide a complete account of the containment relationships between the resulting ideals and show that the corresponding large cardinal properties yield a strict linear refinement of Feng’s original Ramsey hierarchy. We isolate Ramsey properties which provide strictly increasing hierarchies between Feng’s $\Pi _\alpha $ -Ramsey and $\Pi _{\alpha +1}$ -Ramsey cardinals for all odd $\alpha <\omega $ and for all $\omega \leq \alpha <\kappa $. We also show that, given any ordinals $\beta _0,\beta _1<\kappa $ the increasing chains of ideals obtained by iterating the Ramsey operator on the $\Pi ^1_{\beta _0}$ -indescribability ideal and the $\Pi ^1_{\beta _1}$ -indescribability ideal respectively, are eventually equal; moreover, we identify the least degree of Ramseyness at which this equality occurs. As an application of our results we show that one can characterize our new large cardinal notions and the corresponding ideals in terms of generic elementary embeddings; as a special case this yields generic embedding characterizations of $\Pi ^1_\xi $ -indescribability and Ramseyness. (shrink)

We formulate epsilon substitution method for theories (H)α0 of absolute jump hierarchies, and give two termination proofs of the H-process: The first proof is an adaption of Mints M, Mints-Tupailo-Buchholz MTB, i.e., based on a cut-elimination of a specially devised infinitary calculus. The second one is an adaption of Ackermann Ack. Each termination proof is based on transfinite induction up to an ordinal θ(α0+ ω)0, which is best possible.

Ratajczyk, Z., Subsystems of true arithmetic and hierarchies of functions, Annals of Pure and Applied Logic 64 95–152. The combinatorial method coming from the study of combinatorial sentences independent of PA is developed. Basing on this method we present the detailed analysis of provably recursive functions associated with higher levels of transfinite induction, I, and analyze combinatorial sentences independent of I. Our treatment of combinatorial sentences differs from the one given by McAloon [18] and gives more natural sentences. The (...) same method give also a combinatorial technique with no use of the cut-elimination theorem which is appropriate to study proof-theoretic strength of subsystems of first order arithmetic and some of their expansions. It was used to analyze iterated reflection principle and system of transfinite induction with a satisfaction class. (shrink)

Where AR is the set of arithmetic Turing degrees, 0 (ω ) is the least member of { $\mathbf{\alpha}^{(2)}|\mathbf{a}$ is an upper bound on AR}. This situation is quite different if we examine HYP, the set of hyperarithmetic degrees. We shall prove (Corollary 1) that there is an a, an upper bound on HYP, whose hyperjump is the degree of Kleene's O. This paper generalizes this example, using an iteration of the jump operation into the transfinite which is based (...) on results of Jensen and is detailed in [3] and [4]. In $\S1$ we review the basic definitions from [3] which are needed to state the general results. (shrink)

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. (shrink)

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)

The systems Kα of transfinite cumulative types up to α are extended to systems K∞α that include a natural infinitary inference rule, the so-called limit rule. For countable α a semantic completeness theorem for K∞α is proved by the method of reduction trees, and it is shown that every model of K∞α is equivalent to a cumulative hierarchy of sets. This is used to show that several axiomatic first-order set theories can be interpreted in K∞α, for suitable α.

We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite (but constructive) order types, consisting of complements of effectively (...) exhaustible sets, as well as another closely related concept, yield a rich hierarchy within the whole class Δta2. The presentation always first reports analogies between Hausdorff's difference hierarchy within the Borel class ΔB2 and Ershov's hierarchy within the class Δ02 of the arithmetical hierarchy; after that the counterparts for Δta2 are developed. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite order types, consisting of complements of effectively exhaustible sets, (...) as well as another closely related concept, yield a rich hierarchy within the whole class Δta2. The presentation always first reports analogies between Hausdorff's difference hierarchy within the Borel class ΔB2 and Ershov's hierarchy within the class Δ02 of the arithmetical hierarchy; after that the counterparts for Δta2 are developed. (shrink)

We extend the hierarchy of finite-dimensional Ellentuck spaces to infinite dimensions. Using uniform barriers [Formula: see text] on [Formula: see text] as the prototype structures, we construct a class of continuum many topological Ramsey spaces [Formula: see text] which are Ellentuck-like in nature, and form a linearly ordered hierarchy under projections. We prove new Ramsey-classification theorems for equivalence relations on fronts, and hence also on barriers, on the spaces [Formula: see text], extending the Pudlák–Rödl theorem for barriers on (...) the Ellentuck space. The inspiration for these spaces comes from continuing the iterative construction of the forcings [Formula: see text] to the countable transfinite. The [Formula: see text]-closed partial order [Formula: see text] is forcing equivalent to [Formula: see text], which forces a non-p-point ultrafilter [Formula: see text]. This work forms the basis for further work classifying the Rudin–Keisler and Tukey structures for the hierarchy of the generic ultrafilters [Formula: see text]. (shrink)

A theory of the transfinite Tarskian hierarchy of languages is outlined and compared to a notion of partial truth by Kripke. It is shown that the hierarchy can be embedded into Kripke's minimal fixed point model. From this results on the expressive power of both approaches are obtained.

It is shown that the classes of discrete parts, A ∩ ℕk, of approximately resp. weakly decidable subsets of Euclidean spaces, A ⊆ ℝk, coincide and are equal to the class of ω-r. e. sets which is well-known as the first transfinite level in Ershov's hierarchy exhausting Δ02.

It is widely accepted that classical logic is trivialized in the presence of a transparent truth-predicate. In this paper, we will explain why this point of view must be given up. The hierarchy of metainferential logics defined in Barrio et al. and Pailos recovers classical logic, either in the sense that every classical inferential validity is valid at some point in the hierarchy ), or because a logic of a transfinite level defined in terms of the (...) class='Hi'>hierarchy shares its validities with classical logic. Each of these logics is consistent with transparent truth—as is shown in Pailos —, and this suggests that, contrary to standard opinions, transparent truth is after all consistent with classical logic. However, Scambler presents a major challenge to this approach. He argues that this hierarchy cannot be identified with classical logic in any way, because it recovers no classical antivalidities. We embrace Scambler’s challenge and develop a new logic based on these hierarchies. This logic recovers both every classical validity and every classical antivalidity. Moreover, we will follow the same strategy and show that contingencies need also be taken into account, and that none of the logics so far presented is enough to capture classical contingencies. Then, we will develop a multi-standard approach to elaborate a new logic that captures not only every classical validity, but also every classical antivalidity and contingency. As a€truth-predicate can be added to this logic, this result can be interpreted as showing that, despite the claims that are extremely widely accepted, classical logic does not trivialize in the context of transparent truth. (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.

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ödel–Bernays set theory $\text {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 }$, allowing any class parameter A; to the existence of truth predicates for the language $\mathcal {L}_{\text {Ord},\text {Ord}}$ ; to the existence of $\text {Ord}$ -iterated truth predicates for first-order set theory $\mathcal {L}_{\omega,\omega }$ ; 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 $\text {GBC}$ and Kelley–Morse set theory $\text {KM}$. (shrink)

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 Fraïssé's conjecture restricted to well-orderings.

When we are faced with a choice among acts, but are uncertain about the true state of the world, we may be uncertain about the acts’ “choiceworthiness”. Decision theories guide our choice by making normative claims about how we should respond to this uncertainty. If we are unsure which decision theory is correct, however, we may remain unsure of what we ought to do. Given this decision-theoretic uncertainty, meta-theories attempt to resolve the conflicts between our decision theories...but we may be (...) unsure which meta-theory is correct as well. This reasoning can launch a regress of ever-higher-order uncertainty, which may leave one forever uncertain about what one ought to do. There is, fortunately, a class of circumstances under which this regress is not a problem. If one holds a cardinal understanding of subjective choiceworthiness, and accepts certain other criteria, one’s hierarchy of metanormative uncertainty ultimately converges to precise definitions of “subjective choiceworthiness” for any finite set of acts. If one allows the metanormative regress to extend to the transfinite ordinals, the convergence criteria can be weakened further. Finally, the structure of these results applies straightforwardly not just to decision-theoretic uncertainty, but also to other varieties of normative uncertainty, such as moral uncertainty. (shrink)

§1. I will start with a quick definition of descriptive set theory: It is the study of the structure of definable sets and functions in separable completely metrizable spaces. Such spaces are usually called Polish spaces. Typical examples are ℝn, ℂn, Hilbert space and more generally all separable Banach spaces, the Cantor space 2ℕ, the Baire space ℕℕ, the infinite symmetric group S∞, the unitary group, the group of measure preserving transformations of the unit interval, etc.In this theory sets are (...) classified in hierarchies according to the complexity of their definitions and the structure of sets in each level of these hierarchies is systematically analyzed. In the beginning we have the Borel sets in Polish spaces, obtained by starting with the open sets and closing under the operations of complementation and countable unions, and the corresponding Borel hierarchy. After this come the projective sets, obtained by starting with the Borel sets and closing under the operations of complementation and projection, and the corresponding projective hierarchy.There are also transfinite extensions of the projective hierarchy and even much more complex definable sets studied in descriptive set theory, but I will restrict myself here to Borel and projective sets, in fact just those at the first level of the projective hierarchy, i.e., the Borel (), analytic () and coanalytic () sets. (shrink)

In [12], Ernst Zermelo described a succession of models for the axioms of set theory as initial segments of a cumulative hierarchy of levelsUαVα. The recursive definition of theVα's is:Thus, a little reflection on the axioms of Zermelo-Fraenkel set theory shows thatVω, the first transfinite level of the hierarchy, is a model of all the axioms ofZFwith the exception of the axiom of infinity. And, in general, one finds that ifκis a strongly inaccessible ordinal, thenVκis a model (...) of all of the axioms ofZF. Doubtless, when cast as a first-order theory,ZFdoes not characterize the structures 〈Vκ,∈∩〉 forκa strongly inaccessible ordinal, by the Löwenheim-Skolem theorem. Still, one of the main achievements of [12] consisted in establishing that a characterization of these models can be attained when one ventures into second-order logic. For let second-orderZFbe, as usual, the theory that results fromZFwhen the axiom schema of replacement is replaced by its second-order universal closure. Then, it is a remarkable result due to Zermelo that second-orderZFcan only be satisfied in models of the form 〈Vκ,∈∩〉 forκa strongly inaccessible ordinal. (shrink)

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 model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals α such that Tα≻TωTα≻Tω, the (...) smallest of which is precisely γ , the supremum of ordinals clockable by TωTω. In fact, there is a hierarchy of countable TαTαs of increasing strength corresponding to the transfinite Turing-jump operator ▼. There is a countable ordinal μ such that neither Tμ⪰Tω1Tμ⪰Tω1 nor Tμ⪯Tω1Tμ⪯Tω1—that is, the models TμTμ and Tω1Tω1 are computation-strength incommensurable . A similar fact holds for any larger uncountable device replacing Tω1Tω1. Further observations are made about countable TαTα. (shrink)

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. (shrink)

I use modal logic and transfinite set-theory to define metaphysical foundations for a general theory of computation. A possible universe is a certain kind of situation; a situation is a set of facts. An algorithm is a certain kind of inductively defined property. A machine is a series of situations that instantiates an algorithm in a certain way. There are finite as well as transfinite algorithms and machines of any degree of complexity (e.g., Turing and super-Turing machines and (...) more). There are physically and metaphysically possible machines. There is an iterative hierarchy of logically possible machines in the iterative hierarchy of sets. Some algorithms are such that machines that instantiate them are minds. So there is an iterative hierarchy of finitely and transfinitely complex minds. (shrink)

A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is Σ02 complete. (...) Various notions of boundedness are discussed and classified. For example, the index set of the recursively bounded classes is Σ03 complete and the index set of the recursively bounded classes which have infinitely many recursive members is Π04 complete. Consideration of the Cantor-Bendixson derivative leads to index sets in the transfinite levels of the hyperarithmetic hierarchy. (shrink)

We consider fragments of uniform reflection for formulas in the analytic hierarchy over theories of second order arithmetic. The main result is that for any second order arithmetic theory $T_0$ extending $\mathsf {RCA}_0$ and axiomatizable by a $\Pi ^1_{k+2}$ sentence, and for any $n\geq k+1$, $$\begin{align*}T_0+ \mathrm{RFN}_{\varPi^1_{n+2}} \ = \ T_0 + \mathrm{TI}_{\varPi^1_n}, \end{align*}$$ $$\begin{align*}T_0+ \mathrm{RFN}_{\varSigma^1_{n+1}} \ = \ T_0+ \mathrm{TI}_{\varPi^1_n}^{-}, \end{align*}$$ where T is $T_0$ augmented with full induction, and $\mathrm {TI}_{\varPi ^1_n}^{-}$ denotes the schema of transfinite (...) induction up to $\varepsilon _0$ for $\varPi ^1_n$ formulas without set parameters. (shrink)

The independence phenomenon in set theory, while pervasive, can be partially addressed through the use of large cardinal axioms. One idea sometimes alluded to is that maximality considerations speak in favour of large cardinal axioms consistent with ZFC, since it appears to be `possible' to continue the hierarchy far enough to generate the relevant transfinite number. In this paper, we argue against this idea based on a priority of subset formation under the iterative conception. In particular, we argue (...) that there are several conceptions of maximality that justify the consistency but falsity of large cardinal axioms. We argue that the arguments we provide are illuminating for the debate concerning the justification of new axioms in iteratively-founded set theory. (shrink)

In this article, as implied by the title, I intend to argue for the unattainability of Cantor’s Absolute at least in terms of the proof-theoretical means of set-theory and of the theory of large cardinals. For this reason a significant part of the article is a critical review of the progress of set-theory and of mathematical foundations toward resolving problems which to the one or the other degree are associated with the concept of infinity especially the one beyond that of (...) the natural intuition of natural numbers. Naturally the review includes the foundation and development of the theory of large cardinals, especially after Cohen’s revolutionary introduction of the forcing method, insofar as it paved the way toward a transcendence of the delimitative character of Gödel’s constructible universe L and further toward ever stronger infinity assumptions. Given that Cantor in his theory of transfinite numbers defined the mathematical absolute in ontological rather than concrete mathematical terms, I proceed in the last section to a philosophical discussion with certain prompts from phenomenology regarding the transposability of the formal conception of the infinite to the level of subjective constitution and argue in these terms on the infeasibility of acceding to an ‘absolute’ infinite cardinality. Of course the argumentation is strongly based on a view of the set-theoretical universe V of von Neumann’s cumulative hierarchy as a formal representative of the essential traits one would seek from a model of Cantor’s Absolute. It is also based on the conclusions reached from the whole discussion within the context of formal-theoretical structures as such. (shrink)

If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. (...) They have infinitely complex bodies. Transfinite games anchor their social relations. (shrink)

Resumen: Este artículo presenta un acercamiento al cuento “El Aleph” de Jorge Luis Borges a partir del tema de los universos paralelos desde dos perspectivas, el concepto matemático de transinfinito y la observación de lo cotidiano. Siguiendo la jerarquía del multiverso de Max Tegmark, se propone extender su contenido filosófico definiendo cómo “El Aleph” argumenta la idea de multiverso. Por un lado, el cuento de Borges es capaz de reflejar el estado espacio-temporal abigarrado de otros universos simultáneos que coexisten con (...) el propio y, por otro lado, puede comprimir toda esa complejidad en su mínima representación, el punto. Este colapso de lo complejo a lo simple en el cuento de Borges demuestra que la percepción de otras realidades, de otros universos, yace en la aparente insignificancia de lo cotidiano.: This article presents an approach to the short story “The Aleph” by Jorge Luis Borges based on the parallel universes subject from two perspectives, the mathematical concept of transfinite, and the everyday life observation. Following Max Tegmark’s hierarchy of the multiverse, it is set out to extend its philosophical content by defining how “The Aleph” argues the idea of the multiverse. On the one hand, this short story is capable of reflecting the motley spatio-temporal state of other simultaneous coexisting universes and, on the other hand, it can compress all its complexity into the simplest figure for its representation, the point. This collapse from the complex to the simple in Borges’ short story shows that the perception of other realities, of other universes, lies in the apparent insignificance of the everyday life. (shrink)

We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture the observable fact that (...) people do correct their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the TxtBe-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n ≥ 0, there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that make n + 1 corrections to those that make n corrections. The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. For u a notation in Kleene's general system $(O,\, < _o )$ of ordinal notations for constructive ordinals, we introduce the concept of an u-correction grammar, where u is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if u and v are notations for constructive ordinals such that $u\, < _o \,v$ , then there are classes of c.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that— above "ω-many" corrections—it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of c.e. languages, where u is a notation in O for any ordinal, can be simulated by TxtBe-learning ω-correction grammars, where ω is any notation for the smallest infinite ordinal ω. (shrink)

Kruskal proved that finite trees are well-quasi-ordered by hom(e)omorphic embeddability. Friedman observed that this statement is not provable in predicative analysis. Friedman also proposed (see in [Simpson]) some stronger variants of the Kruskal theorem dealing with finite labeled trees under home(e)omorphic embeddability with a certain gap-condition, where labels are arbitrary finite ordinals from a fixed initial segment of ω. The corresponding limit statement, expressing that for all initial segments of ω these labeled trees are well-quasi-ordered, is provable in Π 1 (...) 1 -CA, but not in the analogous theory Π 1 1 -CA 0 with induction restricted to sets. Schutte and Simpson proved that the one-dimensional case of Friedman's limit statement dealing with finite labeled intervals is not provable in Peano arithmetic. However, Friedman's gap-condition fails for finite trees labeled with transfinite ordinals. In [Gordeev 1] I proposed another gap-condition and proved the resulting one-dimensional modified statements for all (countable) transfinite ordinal-labels. The corresponding universal modified one-dimensional statement UM 1 is provable in (in fact, is equivalent to) the familiar theory ATR 0 whose proof-theoretic ordinal is Γ 0 . In [Gordeev 1] I also announced that, in the general case of arbitrarily-branching finite trees labeled with transfinite ordinals, in the proof-theoretic sense the hierarchy of the limit modified statements $\mathbf{M}_{ (which are denoted by LM λ in the present note) is as strong as the hierarchy of the familiar theories of iterated inductive definitions (more precisely, see [Gordeev 1, Concluding Remark 3]). In this note I present a "positive" proof of the full universal modified statement UM, together with a short proof of the crucial "reverse" results which is based on Okada's interpretation of the well-established ordinal notations of Buchholz corresponding to the theories of iterated inductive definitions. Formally the results are summarized in $\S5$ below. (shrink)

I consider the natural infinitary variations of the games Wordle and Mastermind, as well as their game‐theoretic variations Absurdle and Madstermind, considering these games with infinitely long words and infinite color sequences and allowing transfinite game play. For each game, a secret codeword is hidden, which the codebreaker attempts to discover by making a series of guesses and receiving feedback as to their accuracy. In Wordle with words of any size from a finite alphabet of n letters, including infinite (...) words or even uncountable words, the codebreaker can nevertheless always win in n steps. Meanwhile, the mastermind number, defined as the smallest winning set of guesses in infinite Mastermind for sequences of length ω over a countable set of colors without duplication, is uncountable, but the exact value turns out to be independent of, for it is provably equal to the eventually different number, which is the same as the covering number of the meager ideal. I thus place all the various mastermind numbers, defined for the natural variations of the game, into the hierarchy of cardinal characteristics of the continuum. (shrink)

"Ontology and the Foundations of Mathematics" consists of three papers concerned with ontological issues in the foundations of mathematics. Chapter 1, "Numbers and Persons," confronts the problem of the inscrutability of numerical reference and argues that, even if inscrutable, the reference of the numerals, as we ordinarily use them, is determined much more precisely than up to isomorphism. We argue that the truth conditions of a variety of numerical modal and counterfactual sentences place serious constraints on the sorts of items (...) to which numerals, as we ordinarily use them, can be taken to refer: Numerals cannot be taken to refer to objects that exist contingently such as people, mountains, or rivers, but rather must be taken to refer to objects that exist necessarily such as abstracta. ;Chapter 2, "Modern Set Theory and Replacement," takes up a challenge to explain the reasons one should accept the axiom of replacement of Zermelo-Fraenkel set theory, when its applications within ordinary mathematics and the rest of science are often described as rare and recondite. We argue that this is not a question one should be interested in; replacement is required to ensure that the element-set relation is well-founded as well as to ensure that the cumulation of sets described by set theory reaches and proceeds beyond the level o of the cumulative hierarchy. A more interesting question is whether we should accept instances of replacement on uncountable sets, for these are indeed rarely used outside higher set theory. We argue that the best case for replacement comes not from direct, intuitive considerations, but from the role replacement plays in the formulation of transfinite recursion and the theory of ordinals, and from the fact that it permits us to express and assert the content of the modern cumulative view of the set-theoretic universe as arrayed in a cumulative hierarchy of levels. ;Chapter 3, "A No-Class Theory of Classes," makes use of the apparatus of plural quantification to construe talk of classes as plural talk about sets, and thus provide an interpretation of both one- and two-sorted versions of first-order Morse-Kelley set theory, an impredicative theory of classes. We argue that the plural interpretation of impredicative theories of classes has a number of advantages over more traditional interpretations of the language of classes as involving singular reference to gigantic set-like entities, only too encompassing to be sets, the most important of these being perhaps that it makes the machinery of classes available for the formalization of much recent and very interesting work in set theory without threatening the universality of the theory as the most comprehensive theory of collections, when these are understood as objects. (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.