In [12], Schwichtenberg showed that the System T definable functionals are closed under a rule-like version Spector’s bar recursion of lowest type levels 0 and 1. More precisely, if the functional Y which controls the stopping condition of Spector’s bar recursor is T-definable, then the corresponding bar recursion of type levels 0 and 1 is already T-definable. Schwichtenberg’s original proof, however, relies on a detour through Tait’s infinitary terms and the correspondence between ordinal recursion for $\alpha < {\varepsilon _0}$ and primitive recursion over finite types. This detour makes it hard to calculate on given concrete system T input, what the corresponding system T output would look like. In this paper we present an alternative (more direct) proof based on an explicit construction which we prove correct via a suitably defined logical relation. We show through an example how this gives a straightforward mechanism for converting bar recursive definitions into T-definitions under the conditions of Schwichtenberg’s theorem. Finally, with the explicit construction we can also easily state a sharper result: if Y is in the fragment Ti then terms built from $BR^{\mathbb{N},\sigma } $ for this particular Y are definable in the fragment ${T_{i + {\rm{max}}\left\{ {1,{\rm{level}}\left( \sigma \right)} \right\} + 2}}$.

Let Msw denote the least iterable inner model with a strong cardinal above a Woodin cardinal. By [11], Msw has a fully iterable core model, ${K^{{M_{{\rm{sw}}}}}}$, and Msw is thus the least iterable extender model which has an iterable core model with a Woodin cardinal. In V, ${K^{{M_{{\rm{sw}}}}}}$ is an iterate of Msw via its iteration strategy Σ.

We here show that Msw has a bedrock which arises from ${K^{{M_{{\rm{sw}}}}}}$ by telling ${K^{{M_{{\rm{sw}}}}}}$ a specific fragment ${\rm{\bar{\Sigma }}}$ of its own iteration strategy, which in turn is a tail of Σ. Hence Msw is a generic extension of $L[{K^{{M_{{\rm{sw}}}}}},{\rm{\bar{\Sigma }}}]$, but the latter model is not a generic extension of any inner model properly contained in it.

These results generalize to models of the form Ms (x) for a cone of reals x, where Ms (x) denotes the least iterable inner model with a strong cardinal containing x. In particular, the least iterable inner model with a strong cardinal above two (or seven, or boundedly many) Woodin cardinals has a 2-small core model K with a Woodin cardinal and its bedrock is again of the form $L[K,{\rm{\bar{\Sigma }}}]$.

Analysability of finite U-rank types are explored both in general and in the theory ${\rm{DC}}{{\rm{F}}_0}$. The well-known fact that the equation $\delta \left( {{\rm{log}}\,\delta x} \right) = 0$ is analysable in but not almost internal to the constants is generalized to show that $\underbrace {{\rm{log}}\,\delta \cdots {\rm{log}}\,\delta }_nx = 0$ is not analysable in the constants in $\left( {n - 1} \right)$-steps. The notion of a canonical analysis is introduced–-namely an analysis that is of minimal length and interalgebraic with every other analysis of that length. Not every analysable type admits a canonical analysis. Using properties of reductions and coreductions in theories with the canonical base property, it is constructed, for any sequence of positive integers $\left( {{n_1}, \ldots ,{n_\ell }} \right)$, a type in ${\rm{DC}}{{\rm{F}}_0}$ that admits a canonical analysis with the property that the ith step has U-rank ${n_i}$.

BON+ is an applicative theory and closely related to the first order parts of the standard systems of explicit mathematics. As such it is also a natural framework for abstract computations. In this article we analyze this aspect of BON+ more closely. First a point is made for introducing a new operation τN, called truncation, to obtain a natural formalization of partial recursive functions in our applicative framework. Then we introduce the operational versions of a series of notions that are all equivalent to semi-decidability in ordinary recursion theory on the natural numbers, and study their mutual relationships over BON+ with τN.

We show there exists a complete theory in a language of size continuum possessing a unique atomic model which is not constructible. We also show it is consistent with $ZFC + {\aleph _1} < {2^{{\aleph _0}}}$ that there is a complete theory in a language of size ${\aleph _1}$ possessing a unique atomic model which is not constructible. Finally we show it is consistent with $ZFC + {\aleph _1} < {2^{{\aleph _0}}}$ that for every complete theory T in a language of size ${\aleph _1}$, if T has uncountable atomic models but no constructible models, then T has ${2^{{\aleph _1}}}$ atomic models of size ${\aleph _1}$.

This article contributes to the general program of extending techniques and ideas of effective algebra to computable metric space theory. It is well-known that relative computable categoricity (to be defined) of a computable algebraic structure is equivalent to having a c.e. Scott family with finitely many parameters (e.g., [1]). The first main result of the article extends this characterisation to computable Polish metric spaces. The second main result illustrates that just a slight change of the definitions will give us a new notion of categoricity unseen in the countable case (to be stated formally). The second result also shows that the characterisation of computably categorical closed subspaces of ${\Cal R}^n $ contained in [17] cannot be improved. The third main result extends the characterisation to not necessarily separable structures of cardinality κ using κ-computability.

We investigate two weak fragments of the double negation shift schema, which are motivated, respectively, from Spector’s consistency proof of ACA0 and from the negative translation of RCA0, as well as double negated variants of logical principles. Their interrelations over both intuitionistic arithmetic and analysis are completely solved.

We introduce the notion of infinitary interpretation of structures. In general, an interpretation between structures induces a continuous homomorphism between their automorphism groups, and furthermore, it induces a functor between the categories of copies of each structure. We show that for the case of infinitary interpretation the reversals are also true: every Baire-measurable homomorphism between the automorphism groups of two countable structures is induced by an infinitary interpretation, and every Baire-measurable functor between the set of copies of two countable structures is induced by an infinitary interpretation. Furthermore, we show that the complexities are maintained in the sense that if the functor is ${\bf{\Delta }}_\alpha ^0$, then the interpretation that induces it is ${\rm{\Delta }}_\alpha ^{in}$ up to ${\bf{\Delta }}_\alpha ^0$ equivalence.

We investigate which filters on ω can contain towers, that is, a modulo finite descending sequence without any pseudointersection (in ${[\omega ]^\omega }$). We prove the following results:

1. (1) Many classical examples of nice tall filters contain no towers (in ZFC).

2. (2) It is consistent that tall analytic P-filters contain towers of arbitrary regular height (simultaneously for many regular cardinals as well).

3. (3) It is consistent that all towers generate nonmeager filters (this answers a question of P. Borodulin-Nadzieja and D. Chodounský), in particular (consistently) Borel filters do not contain towers.

4. (4) The statement “Every ultrafilter contains towers.” is independent of ZFC (this improves an older result of K. Kunen, J. van Mill, and C. F. Mills).

Furthermore, we study many possible logical (non)implications between the existence of towers in filters, inequalities between cardinal invariants of filters (${\rm{ad}}{{\rm{d}}^{\rm{*}}}\left( {\cal F} \right)$, ${\rm{co}}{{\rm{f}}^{\rm{*}}}\left( {\cal F} \right)$, ${\rm{no}}{{\rm{n}}^{\rm{*}}}\left( {\cal F} \right)$, and ${\rm{co}}{{\rm{v}}^{\rm{*}}}\left( {\cal F} \right)$), and the existence of Luzin type families (of size $\ge {\omega _2}$), that is, if ${\cal F}$ is a filter then ${\cal X} \subseteq {[\omega ]^\omega }$ is an ${\cal F}$-Luzin family if $\left\{ {X \in {\cal X}:|X \setminus F| = \omega } \right\}$ is countable for every $F \in {\cal F}$.

We explore the structural properties of the inner model L(Vδ+1) under the assumption that δ is a singular limit of Berkeley cardinals each of which is itself limit of extendible cardinals, lifting some of the main results of the theory of the axiom I0 to the level of Berkeley cardinals, the strongest known large cardinal axioms. Berkeley cardinals have been recently introduced in [1] and contradict the Axiom of Choice.1 In fact, our background theory will be ZF.

Ellis’ Theorem (i.e., “every compact Hausdorff right topological semigroup has an idempotent element”) is known to be proved only under the assumption of the full Axiom of Choice (AC); AC is used in the proof in the disguise of Zorn’s Lemma.

In this article, we prove that in ZF, Ellis’ Theorem follows from the Boolean Prime Ideal Theorem (BPI), and hence is strictly weaker than AC in ZF. In fact, we establish that BPI implies the formally stronger (than Ellis’ Theorem) statement “for every family ${\cal A} = \{ ({S_i},{ \cdot _i},{{\cal T}_i}):i \in I\}$ of nontrivial compact Hausdorff right topological semigroups, there exists a function f with domain I such that $f\left( i \right)$ is an idempotent of ${S_i}$, for all $i \in I$”, which in turn implies ACfin (i.e., AC for sets of nonempty finite sets).

Furthermore, we prove that in ZFA, the Axiom of Multiple Choice (MC) implies Ellis’ Theorem for abelian semigroups (i.e., “every compact Hausdorff right topological abelian semigroup has an idempotent element”) and that the strictly weaker than MC (in ZFA) principle LW (i.e., “every linearly ordered set can be well-ordered”) implies Ellis’ Theorem for linearly orderable semigroups (i.e., “every compact Hausdorff right topological linearly orderable semigroup has an idempotent element”); thus the latter formally weaker versions of Ellis’ Theorem are strictly weaker than BPI in ZFA. Yet, it is shown that no choice is required in order to prove Ellis’ Theorem for well-orderable semigroups.

We also show that each one of the (strictly weaker than AC) statements “the Tychonoff product $2^{\Cal R} $ is compact and Loeb” and $BPI_{\Cal R}$ (BPI for filters on ${\Cal R}$) implies “there exists a free idempotent ultrafilter on ω” (which in turn is not provable in ZF). Moreover, we prove that the latter statement does not imply $BP{I_\omega }$ (BPI for filters on ω) in ZF, hence it does not imply any of $AC_{\Cal R} $ (AC for sets of nonempty sets of reals) and $BPI_{\Cal R} $ in ZF, either.

In addition, we prove that the statements “there exists a free ultrafilter on ω”, “there exists a free ultrafilter on ω which is not idempotent”, and “for every IP set $A \subseteq \omega$, there exists a free ultrafilter ${\cal F}$ on ω such that $A \in {\cal F}$” are pairwise equivalent in ZF.

A Turing degree d is the degree of categoricity of a computable structure ${\cal S}$ if d is the least degree capable of computing isomorphisms among arbitrary computable copies of ${\cal S}$. A degree d is the strong degree of categoricity of ${\cal S}$ if d is the degree of categoricity of ${\cal S}$, and there are computable copies ${\cal A}$ and ${\cal B}$ of ${\cal S}$ such that every isomorphism from ${\cal A}$ onto ${\cal B}$ computes d. In this paper, we build a c.e. degree d and a computable rigid structure ${\cal M}$ such that d is the degree of categoricity of ${\cal M}$, but d is not the strong degree of categoricity of ${\cal M}$. This solves the open problem of Fokina, Kalimullin, and Miller [13].

For a computable structure ${\cal S}$, we introduce the notion of the spectral dimension of ${\cal S}$, which gives a quantitative characteristic of the degree of categoricity of ${\cal S}$. We prove that for a nonzero natural number N, there is a computable rigid structure ${\cal M}$ such that $0\prime$ is the degree of categoricity of ${\cal M}$, and the spectral dimension of ${\cal M}$ is equal to N.

For G a group definable in a saturated model of a NIP theory T, we prove that there is a smallest type-definable subgroup H of G such that the quotient G / H is stable. This generalizes the existence of G00, the smallest type-definable subgroup of G of bounded index.

We give an example of a dense o-minimal structure in which there is a definable quotient that cannot be eliminated, even after naming parameters. Equivalently, there is an interpretable set which cannot be put in parametrically definable bijection with any definable set. This gives a negative answer to a question of Eleftheriou, Peterzil, and Ramakrishnan. Additionally, we show that interpretable sets in dense o-minimal structures admit definable topologies which are “tame” in several ways: (a) they are Hausdorff, (b) every point has a neighborhood which is definably homeomorphic to a definable set, (c) definable functions are piecewise continuous, (d) definable subsets have finitely many definably connected components, and (e) the frontier of a definable subset has lower dimension than the subset itself.

We prove that, in the choiceless Solovay model, every set of reals is H-Ramsey for every happy family H that also belongs to the Solovay model. This gives a new proof of Törnquist’s recent theorem that there are no infinite mad families in the Solovay model. We also investigate happy families and mad families under determinacy, applying a generic absoluteness result to prove that there are no infinite mad families under $A{D^ + }$.

This article presents a proof that Buss’s $S_2^2$ can prove the consistency of a fragment of Cook and Urquhart’s PV from which induction has been removed but substitution has been retained. This result improves Beckmann’s result, which proves the consistency of such a system without substitution in bounded arithmetic $S_2^1$.

Our proof relies on the notion of “computation” of the terms of PV. In our work, we first prove that, in the system under consideration, if an equation is proved and either its left- or right-hand side is computed, then there is a corresponding computation for its right- or left-hand side, respectively. By carefully computing the bound of the size of the computation, the proof of this theorem inside a bounded arithmetic is obtained, from which the consistency of the system is readily proven.

This result apparently implies the separation of bounded arithmetic because Buss and Ignjatović stated that it is not possible to prove the consistency of a fragment of PV without induction but with substitution in Buss’s $S_2^1$. However, their proof actually shows that it is not possible to prove the consistency of the system, which is obtained by the addition of propositional logic and other axioms to a system such as ours. On the other hand, the system that we have considered is strictly equational, which is a property on which our proof relies.

Simpson [6] showed that every countable model ${\cal M} \models PA$ has an expansion $\left( {{\cal M},X} \right) \models P{A^{\rm{*}}}$ that is pointwise definable. A natural question is whether, in general, one can obtain expansions of a nonprime model in which the definable elements coincide with those of the underlying model. Enayat [1] showed that this is impossible by proving that there is ${\cal M} \models PA$ such that for each undefinable class X of ${\cal M}$, the expansion $\left( {{\cal M},X} \right)$ is pointwise definable. We call models with this property Enayat models. In this article, we study Enayat models and show that a model of $PA$ is Enayat if it is countable, has no proper cofinal submodels and is a conservative extension of all of its elementary cuts. We then show that, for any countable linear order γ, if there is a model ${\cal M}$ such that $Lt\left( {\cal M} \right) \cong \gamma$, then there is an Enayat model ${\cal M}$ such that $Lt\left( {\cal M} \right) \cong \gamma$.

In this article the lightface ${\rm{\Pi }}_1^1$-Comprehension axiom is shown to be proof-theoretically strong even over ${\rm{RCA}}_0^{\rm{*}}$, and we calibrate the proof-theoretic ordinals of weak fragments of the theory ${\rm{I}}{{\rm{D}}_1}$ of positive inductive definitions over natural numbers. Conjunctions of negative and positive formulas in the transfinite induction axiom of ${\rm{I}}{{\rm{D}}_1}$ are shown to be weak, and disjunctions are strong. Thus we draw a boundary line between predicatively reducible and impredicative fragments of ${\rm{I}}{{\rm{D}}_1}$.

Answering a special case of a question of Chernikov and Simon, we show that any non-dividing formula over a model M in a distal NIP theory is a member of a consistent definable family, definable over M.

In [G. Curi, On Tarski’s fixed point theorem. Proc. Amer. Math. Soc., 143 (2015), pp. 4439–4455], a notion of abstract inductive definition is formulated to extend Aczel’s theory of inductive definitions to the setting of complete lattices. In this article, after discussing a further extension of the theory to structures of much larger size than complete lattices, as the class of all sets or the class of ordinals, a similar generalization is carried out for the theory of co-inductive definitions on a set. As a corollary, a constructive version of the general form of Tarski’s fixed point theorem is derived.