In ordinal analysis of impredicative theories so-called collapsing functions are of central importance. Unfortunately, the definition procedure of these functions makes essential use of uncountable cardinals whereas the notation system that they call into being corresponds to a recursive ordinal. It has long been claimed that, instead, one should manage to develop such functions directly on the basis of admissible ordinals. This paper is meant to show how this can be done. Interpreting the collapsing functions as operating (...) directly on admissible sets also renders a new and perspicuous approach to well-ordering proofs possible. MSC: 03F15, 03F35. (shrink)

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, (...) respectively. We emphasize the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory. (shrink)

The notion of a function from ℕ to ℕ defined by recursion on ordinal notations is fundamental in proof theory. Here this notion is generalized to functions on the universe of sets, using notations for well orderings longer than the class of ordinals. The generalization is used to bound the rate of growth of any function on the universe of sets that is Σ1-definable in Kripke–Platek admissible set theory with an axiom of infinity. Formalizing the argument provides an (...) ordinal analysis. (shrink)

We give upper and lower bounds for the strength of ordinal definable determinacy in a small admissible set. The upper bound is roughly a premouse with a measurable cardinal $\kappa$ of Mitchell order $\kappa^{++}$ and $\omega$ successors. The lower bound are models of ZFC with sequences of measurable cardinals, extending the work of Lewis, below a regular limit of measurable cardinals.

When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of $\alpha$-finiteness. As examples we discuss bothcodings of models of (...) arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal $\alpha$ is effectively close to $\omega$ (where this closeness can be measured by size or by cofinality) then such constructions maybe performed in the $\alpha$-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natu. (shrink)

Abstract.This paper is the second in a series of three culminating in an ordinal analysis of Π12-comprehension. Its objective is to present an ordinal analysis for the subsystem of second order arithmetic with Δ12-comprehension, bar induction and Π12-comprehension for formulae without set parameters. Couched in terms of Kripke-Platek set theory, KP, the latter system corresponds to KPi augmented by the assertion that there exists a stable ordinal, where KPi is KP with an additional axiom stating that every (...) set is contained in an admissible set. (shrink)

Abstract.This paper is the first in a series of three which culminates in an ordinal analysis of Π12-comprehension. On the set-theoretic side Π12-comprehension corresponds to Kripke-Platek set theory, KP, plus Σ1-separation. The strength of the latter theory is encapsulated in the fact that it proves the existence of ordinals π such that, for all β>π, π is β-stable, i.e. Lπ is a Σ1-elementary substructure of Lβ. The objective of this paper is to give an ordinal analysis of a (...) scenario of not too complicated stability relations as experience has shown that the understanding of the ordinal analysis of Π12-comprehension is greatly facilitated by explicating certain simpler cases first.This paper introduces an ordinal representation system based on ν-indescribable cardinals which is then employed for determining an upper bound for the proof–theoretic strength of the theory KPi+ ∀ρ ∃ππ is π+ρ-stable, where KPi is KP augmented by the axiom saying that every set is contained in an admissible set. (shrink)

L’admission des femmes à l’ordination presbytérale ou au pastorat dans les Églises issues de la Réforme est liée à la situation historique particulière des États-Unis. Actuellement, aucun argument biblique ou théologique n’est jugé insurmontable pour l’ordination des femmes. Il existe certes de vives tensions, mais des ruptures effectives interviennent plutôt à la suite de l’ordination d’hommes et de femmes homosexuels. L’admission des femmes au ministère ordonné semble reposer sur l’hypothèse qu’un clergé mixte à tous les degrés du sacrement de l’ordre (...) assure à une Église la stabilité et la paix interne. Les débats au sein de ces Églises ont montré la faiblesse d’une interprétation de l’Écriture en termes de complémentarité entre l’homme et la femme. Ils les ont aussi conduites à une redécouverte de la grande variété de la tradition ecclésiale en la matière. L’article pose la question des enseignements que l’Église catholique romaine devrait à l’avenir tirer de l’expérience des Églises chrétiennes des États-Unis. (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)

In this article we show how to use the result in Jäger and Probst [7] to adapt the technique of pseudo-hierarchies and its use in Avigad [1] to subsystems of set theory without foundation. We prove that the theory KPi0 of admissible sets without foundation, extended by the principle (Σ-FP), asserting the existence of fixed points of monotone Σ operators, has the same proof-theoretic ordinal as KPi0 extended by the principle (Σ-TR), that allows to iterate Σ operations along (...) ordinals. By Jäger and Probst [6] we conclude that the metapredicative Mahlo ordinal φ ω00 is also the ordinal of KPi0+(Σ-FP). Hence the relationship between fixed points and iteration persists in the framework of set theory without foundation. (shrink)

The known results about Σ 1 -completeness, Σ 1 -compactness, ordinal omitting etc. are given a unified treatment, which yields many new examples. It is shown that the unifying theorem is best possible in several ways, assuming V = L.

Darwiche and Pearl’s seminal 1997 article outlined a number of baseline principles for a logic of iterated belief revision. These principles, the DP postulates, have been supplemented in a number of alternative ways. Most suggestions have resulted in a form of ‘reductionism’ that identifies belief states with orderings of worlds. However, this position has recently been criticised as being unacceptably strong. Other proposals, such as the popular principle (P), aka ‘Independence’, characteristic of ‘admissible’ operators, remain commendably more modest. In (...) this paper, we supplement the DP postulates and (P) with a number of novel conditions. While the DP postulates constrain the relation between a prior and a posterior conditional belief set, our new principles notably govern the relation between two posterior conditional belief sets obtained from a common prior by different revisions. We show that operators from the resulting family, which subsumes both lexicographic and restrained revision, can be represented as relating belief states associated with a ‘proper ordinal interval’ (POI) assignment, a structure more fine-grained than a simple ordering of worlds. We close the paper by noting that these operators satisfy iterated versions of many AGM era postulates, including Superexpansion, that are not sound for admissible operators in general. (shrink)

This article analyzes through a linguistic lens three official documents of the Roman Catholic Church on women’s ordination; it also identifies various discursive tactics utilized by text creators to reinforce gender hierarchy within the Church. Drawing from Fairclough’s three dimensional discourse framework, we examine the ideological message embedded in the linguistic features and the role each text plays within a matrix of power relations. Through close readings of Inter Insigniores: On the Question of Admission of Women to the Ministerial Priesthood, (...) Ordinatio Sacerdotalis of John Paul II, and Women and the Priesthood, we demonstrate how discourse analysis can serve as a useful tool for identifying logical fallacies, inconsistencies, dilemmas, and manipulative tactics in religious discourses. (shrink)

Let o(κ) denote the Mitchell order of κ. We show how to reduce long games which run to the first ordinal admissible in the play, to iteration games on models with a cardinal κ so that (1) κ is a limit of Woodin cardinals: and (2) o(κ) = κ⁺⁺. We use the reduction to derive several optimal determinacy results on games which run to the first admissible in the play.

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.

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

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)

We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, (...) unresetting and resetting infinite-time register machines, and α-Turing machines for countable admissible ordinals α. (shrink)

Let α be any countable admissible ordinal greater than ω. There is a transitive set A such that A is admissible, locally countable, On A = α, and A satisfies Σ 1 -separation. In fact, if B is any nonstandard model of $KP + \forall x \subseteq \omega$ (the hyperjump of x exists), the ordinal standard part of B is greater than ω, and every standard ordinal in B is countable in B, then HC B (...) ∩ (standard part of B) satisfies Σ 1 -separation. (shrink)

LetZ2,Z3, andZ4denote 2nd, 3rd, and 4thorder arithmetic, respectively. We let Harrington’s Principle, HP, denote the statement that there is a realxsuch that everyx-admissible ordinal is a cardinal inL. The known proofs of Harrington’s theorem “$Det\left$implies 0♯exists” are done in two steps: first show that$Det\left$implies HP, and then show that HP implies 0♯exists. The first step is provable inZ2. In this paper we show thatZ2+ HP is equiconsistent with ZFC and thatZ3+ HP is equiconsistent with ZFC + there exists (...) a remarkable cardinal. As a corollary,Z3+ HP does not imply 0♯exists, whereas Z4+ HP does. We also study strengthenings of Harrington’s Principle over 2ndand 3rdorder arithmetic. (shrink)

Let A be a standard transitive admissible set. Σ 1 -separation is the principle that whenever X and Y are disjoint Σ A 1 subsets of A then there is a Δ A 1 subset S of A such that $X \subseteq S$ and $Y \cap S = \varnothing$ . Theorem. If A satisfies Σ 1 -separation, then (1) If $\langle T_n\mid n is a sequence of trees on ω each of which has at most finitely many infinite paths (...) in A then the function $n\mapsto$ (set of infinite paths in A through T n ) is in A. (2) If A is not closed under hyperjump and α = On A then A has in it a nonstandard model of V = L whose ordinal standard part is α. Theorem. Let α be any countable admissible ordinal greater than ω. Then there is a model of Σ 1 -separation whose height is α. (shrink)

The notion of a weakly scattered theory T is defined. T need not be scattered. For each a model of T, let sr() be the Scott rank of . Assume sr() ≤ ω\sp A \sb 1 for all a model of T. Let σ\sp T \sb 2 be the least Σ₂ admissible ordinal relative to T. If T admits effective k-splitting as defined in this paper, then θσ\cal Aθ\cal A$ a model of T.

This paper is an investigation of the relationship between G\"odel's second incompleteness theorem and the well-foundedness of jump hierarchies. It follows from a classic theorem of Spector's that the relation $\{(A,B) \in \mathbb{R}^2 : \mathcal{O}^A \leq_H B\}$ is well-founded. We provide an alternative proof of this fact that uses G\"odel's second incompleteness theorem instead of the theory of admissible ordinals. We then derive a semantic version of the second incompleteness theorem, originally due to Mummert and Simpson, from this result. (...) Finally, we turn to the calculation of the ranks of reals in this well-founded relation. We prove that, for any $A\in\mathbb{R}$, if the rank of $A$ is $\alpha$, then $\omega_1^A$ is the $(1 + \alpha)^{\text{th}}$ admissible ordinal. It follows, assuming suitable large cardinal hypotheses, that, on a cone, the rank of $X$ is $\omega_1^X$. (shrink)

R. M. Friedberg demonstrated the existence of a recursive functional that agrees with no Banach-Mazur functional on the class of recursive functions. In this paper Friedberg's result is generalized to both α-recursive functionals and weak α-recursive functionals for all admissible ordinals α such that $\lambda , where α * is the Σ 1 -projectum of α and λ is the Σ 2 -cofinality of α. The theorem is also established for the metarecursive case, α = ω 1 , where (...) α * = λ = ω. (shrink)

Let A and B be subsets of the reals. Say that A κ ≥ B, if there is a real a such that the relation "x ∈ B" is uniformly Δ 1 (a, A) in L[ ω x,a,A 1 , x,a,A]. This reducibility induces an equivalence relation $\equiv_\kappa$ on the sets of reals; the $\equiv_\kappa$ -equivalence class of a set is called its Kleene degree. Let K be the structure that consists of the Kleene degrees and the induced partial order (...) K ≥. A substructure of K that is of interest is P, the Kleene degrees of the Π 1 1 sets of reals. If sharps exist, then there is not much to P, as Steel [9] has shown that the existence of sharps implies that P has only two elements: the degree of the empty set and the degree of the complete Π 1 1 set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in P; in the context of V = L, Hrbacek has shown that P is dense and has no minimal pairs. The Hrbacek results led Simpson [6] to make the following conjecture: if V = L, then p forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if V = L, then Godel's maximal thin Π 1 1 set is the infimum of two strictly larger elements of P. The second main result deals with the notion of jump in K. Let A' be the complete Kleene enumerable set relative to A. Say that A is low-n if A (n) has the same degree as $\varnothing^{(n)}$ , and A is high-n if A (n) has the same degree as $\varnothing^{(n + 1)}$ . Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete Π 1 1 set in L. They have also shown that various other Π 1 1 sets are neither high nor low in L. Legrand [5] extended their results by showing that, if there is a real x such that x # does not exist, then there is an element of P that, for all n, is neither low-n nor high-n. In § 2, ZFC is used to show that, for all n, if A is Π 1 1 and low-n then A is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp]. (shrink)

Contents: Recursive Enumerability and the Jump Operator; On the Degrees Less Than 0'; A Simple Set Which Is Not Effectively Simple; The Recursively Enumerable Degrees Are Dense; Metarecursive Sets (with G Kreisel); Post's Problem, Admissible Ordinals and Regularity; On a Theorem of Lachlan and Marlin; A Minimal Hyperdegree (with R O Gandy); Measure-Theoretic Uniformity in Recursion Theory and Set Theory; Forcing with Perfect Closed Sets; Recursion in Objects of Finite Type; The a-Finite Injury Method (with S G Simpson); Remarks (...) Against Foundational Activity; Countable Admissible Ordinals and Hyperdegrees; The 1-Section of a Type n Object; The k-Section of a Type n Object; Post's Problem, Absoluteness and Recursion in Finite Types; Effective Bounds on Morley Rank; On the Number of Countable Models; Post's Problem in E-Recursion; The Limits of E-Recursive Enumerability; Effective Versus Proper Forcing. (shrink)

Roughly speaking, a pattern is a finite sequence coding the set of natural numbers n for which the Σ n + 1 projectum is less than the Σ n projectum for a given admissible ordinal. We prove that for each pattern there exists an ordinal realizing it. Several results on the orderings of patterns are given. We conclude the paper with remarks on ▵ n projecta. The main technique, used throughout the paper, is Jensen's Uniformisation Theorem.

If one regards an ordinal number as a generalization of a counting number, then it is natural to begin thinking in terms of computations on sets of ordinal numbers. This is precisely what Takeuti [22] had in mind when he initiated the study of recursive functions on ordinals. Kreisel and Sacks [9] too developed an ordinal recursion theory, called metarecursion theory, which specialized to the initial segment of the ordinals bounded by.The notion of admissibility was introduced by (...) Kripke [11] and Platek [14] and served to generalize metarecursion theory. Kripke called ordinal α admissible if it satisfied certain closure properties of infinitary computations. It was shown that admissibility could be equivalently formulated in terms of the replacement schema of ZF set theory and that α =is an admissible ordinal. The study of a recursion theory on an initial segment of the ordinals bounded by some arbitrary admissible α became known as α-recursion theory.Kripke [10] employed a Gödel numbering scheme to perform an arithmetiza-tion of α -recursion theory and created an analogue to Kleene'sT-predicate of ordinary recursion theory. TheT-predicate then served as the basis for showing that analogues of the major results of unrelativized o.r.t. held in α-recursion theory; namely, the α-Enumeration Theorem,T Theorem, α-Recursion Theorem, and α-Universal Function Theorem. (shrink)

Several stepping up lemmas are proved which are then used to investigate the connection between definable partition relations and admissible ordinals.

A number of authors have noted that the key steps in Fitch’s argument are not intuitionistically valid, and some have proposed this as a reason for an anti-realist to accept intuitionistic logic (e.g. Williamson 1982, 1988). This line of reasoning rests upon two assumptions. The first is that the premises of Fitch’s argument make sense from an anti-realist point of view – and in particular, that an anti-realist can and should maintain the principle that all truths are knowable. The second (...) is that we have some independent reason for thinking that classical logic is not appropriate in this area. This paper explores these two assumptions in the context of Michael Dummett’s version of anti-realism, with particular reference to the argument from indefinite extensibility developed at various points in Dummett’s writings (e.g. Dummett 1991 Ch. 24). -/- Dummett argues that certain concepts, the indefinitely extensible concepts, are such that we cannot form a clear and determinate conception of all the objects that fall under them. The most familiar examples of indefinitely extensible concepts are mathematical. Dummett discusses the concepts ordinal number, real number, and natural number, which are indefinitely extensible because any conception that one might form of their complete extension can be extended to a more inclusive conception (as, for example, in Cantor’s proof of the non-denumerability of the set of real numbers). This paper argues that the concept of a truth is indefinitely extensible. This gives a Dummettian anti-realist an independent motivation for rejecting the classical understanding of the quantifiers in this area. At the same time, however, it places in doubt the admissibility of the knowability principle, which seems to involve quantification over the “totality” of truths. As Dummett is at pains to point out (1991: 316), some sentences that purport to quantify over the extension of an indefinitely extensible concept plainly have a truth-value (we can truly say, for example, that every ordinal number has a successor, even though when we say that we are not quantifying over the set of all ordinals). But is the knowability principle one of these sentences? (shrink)

The paper characterizes the second order arithmetic theorems of a set theory that features a recursively Mahlo universe; thereby complementing prior proof-theoretic investigations on this notion. It is shown that the property of being recursively Mahlo corresponds to a certain kind of β-model reflection in second order arithmetic. Further, this leads to a characterization of the reals recursively computable in the superjump functional.

A constructivisation of the cut-elimination proof for sequent calculi for classical, intuitionistic and minimal infinitary logics with geometric rules—given in earlier work by the second author—is presented. This is achieved through a procedure where the non-constructive transfinite induction on the commutative sum of ordinals is replaced by two instances of Brouwer’s Bar Induction. The proof of admissibility of the structural rules is made ordinal-free by introducing a new well-founded relation based on a notion of embeddability of derivations. Additionally, conservativity (...) for classical over intuitionistic/minimal logic for the seven (finitary) Glivenko sequent classes is here shown to hold also for the corresponding infinitary classes. (shrink)

The language $L_A(\Finv)$ is formed by adding the quantifier $\Finv x$ , "few x", to the infinitary logic L A on an admissible set A. A complete axiomatization is obtained for models whose universe is the set of ordinals of A and where $\Finv x$ is interpreted as there exist A-finitely many x. For well-behaved A, every consistent sentence has a model with an A-recursive diagram. A principal tool is forcing for $L_A(\Finv)$.

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals (...) associated with the jump operator satisfy a Spector criterion, and correspond to the L ζ -stables. It also implies that the machines devised are "Σ 2 Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment. (shrink)

In this article we provide wellordering proofs for metapredicative systems of explicit mathematics and admissible set theory featuring suitable axioms about the Mahloness of the underlying universe of discourse. In particular, it is shown that in the corresponding theories EMA of explicit mathematics and KPm 0 of admissible set theory, transfinite induction along initial segments of the ordinal φω00, for φ being a ternary Veblen function, is derivable. This reveals that the upper bounds given for these two (...) systems in the paper Jager and Strahm [11] are indeed sharp. (shrink)

The language $L_A$ is formed by adding the quantifier $\Finv x$ , "few x", to the infinitary logic L A on an admissible set A. A complete axiomatization is obtained for models whose universe is the set of ordinals of A and where $\Finv x$ is interpreted as there exist A-finitely many x. For well-behaved A, every consistent sentence has a model with an A-recursive diagram. A principal tool is forcing for $L_A$.