We investigate which part of Brouwer’s Intuitionistic Mathematics is finitistically justifiable or guaranteed in Hilbert’s Finitism, in the same way as similar investigations on Classical Mathematics (i.e., which part is equiconsistent with $\textbf {PRA}$ or consistent provably in $\textbf {PRA}$ ) already done quite extensively in proof theory and reverse mathematics. While we already knew a contrast from the classical situation concerning the continuity principle, more contrasts turn out: we show that several principles are finitistically justifiable or guaranteed which are classically not. Among them are: (i) fan theorem for decidable fans but arbitrary bars; (ii) continuity principle and the axiom of choice both for arbitrary formulae; and (iii) $\Sigma _2$ induction and dependent choice. We also show that Markov’s principle MP does not change this situation; that neither does lesser limited principle of omniscience LLPO (except the choice along functions); but that limited principle of omniscience LPO makes the situation completely classical.

We show in ZFC that the existence of completely separable maximal almost disjoint families of subsets of $\omega $ implies that the modal logic $\mathbf {S4.1.2}$ is complete with respect to the Čech–Stone compactification of the natural numbers, the space $\beta \omega $ . In the same fashion we prove that the modal logic $\mathbf {S4}$ is complete with respect to the space $\omega ^*=\beta \omega \setminus \omega $ . This improves the results of G. Bezhanishvili and J. Harding in [4], where the authors prove these theorems under stronger assumptions ( $\mathfrak {a=c}$ ). Our proof is also somewhat simpler.

We show that the statement “every universally Baire set of reals has the perfect set property” is equiconsistent modulo ZFC with the existence of a cardinal that we call virtually Shelah for supercompactness (VSS). These cardinals resemble Shelah cardinals and Shelah-for-supercompactness cardinals but are much weaker: if $0^\sharp $ exists then every Silver indiscernible is VSS in L. We also show that the statement $\operatorname {\mathrm {uB}} = {\boldsymbol {\Delta }}^1_2$ , where $\operatorname {\mathrm {uB}}$ is the pointclass of all universally Baire sets of reals, is equiconsistent modulo ZFC with the existence of a $\Sigma _2$ -reflecting VSS cardinal.

We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.

We investigate, in ZFC, the behavior of abstract elementary classes (AECs) categorical in many successive small cardinals. We prove for example that a universal $\mathbb {L}_{\omega _1, \omega }$ sentence categorical on an end segment of cardinals below $\beth _\omega $ must be categorical also everywhere above $\beth _\omega $ . This is done without any additional model-theoretic hypotheses (such as amalgamation or arbitrarily large models) and generalizes to the much broader framework of tame AECs with weak amalgamation and coherent sequences.

We show that assuming modest large cardinals, there is a definable class of ordinals, closed and unbounded beneath every uncountable cardinal, so that for any closed and unbounded subclasses $P, Q, {\langle L[P],\in ,P \rangle }$ and ${\langle L[Q],\in ,Q \rangle }$ possess the same reals, satisfy the Generalised Continuum Hypothesis, and moreover are elementarily equivalent. Examples of such P are Card, the class of uncountable cardinals, I the uniform indiscernibles, or for any n the class $C^{n}{=_{{\operatorname {df}}}}\{ \lambda \, | \, V_{\lambda } \prec _{{\Sigma }_{n}}V\}$ ; moreover the theory of such models is invariant under ZFC-preserving extensions. They also all have a rich structure satisfying many of the usual combinatorial principles and a definable wellorder of the reals. The inner model constructed using definability in the language augmented by the Härtig quantifier is thus also characterized.

The aim of this paper is to shed light on our understanding of large scale properties of infinite strings. We say that one string $\alpha $ has weaker large scale geometry than that of $\beta $ if there is color preserving bi-Lipschitz map from $\alpha $ into $\beta $ with small distortion. This definition allows us to define a partially ordered set of large scale geometries on the classes of all infinite strings. This partial order compares large scale geometries of infinite strings. As such, it presents an algebraic tool for classification of global patterns. We study properties of this partial order. We prove, for instance, that this partial order has a greatest element and also possess infinite chains and antichains. We also investigate the sets of large scale geometries of strings accepted by finite state machines such as Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This connects the work with the complexity theory. We also prove that the quasi-isometry problem is a $\Sigma _2^0$ -complete set, thus providing a bridge with computability theory. Finally, we build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness.

In this paper we study the notion of $C^{(n)}$ -supercompactness introduced by Bagaria in [3] and prove the identity crises phenomenon for such class. Specifically, we show that consistently the least supercompact is strictly below the least $C^{(1)}$ -supercompact but also that the least supercompact is $C^{(1)}$ -supercompact (and even $C^{(n)}$ -supercompact). Furthermore, we prove that under suitable hypothesis the ultimate identity crises is also possible. These results solve several questions posed by Bagaria and Tsaprounis.

Answering a question of Cifú Lopes, we give a syntactic characterization of those continuous sentences that are preserved under reduced products of metric structures. In fact, we settle this question in the wider context of general structures as introduced by the second author.

Any intermediate propositional logic (i.e., a logic including intuitionistic logic and contained in classical logic) can be extended to a calculus with epsilon- and tau-operators and critical formulas. For classical logic, this results in Hilbert’s $\varepsilon $ -calculus. The first and second $\varepsilon $ -theorems for classical logic establish conservativity of the $\varepsilon $ -calculus over its classical base logic. It is well known that the second $\varepsilon $ -theorem fails for the intuitionistic $\varepsilon $ -calculus, as prenexation is impossible. The paper investigates the effect of adding critical $\varepsilon $ - and $\tau $ -formulas and using the translation of quantifiers into $\varepsilon $ - and $\tau $ -terms to intermediate logics. It is shown that conservativity over the propositional base logic also holds for such intermediate ${\varepsilon \tau }$ -calculi. The “extended” first $\varepsilon $ -theorem holds if the base logic is finite-valued Gödel–Dummett logic, and fails otherwise, but holds for certain provable formulas in infinite-valued Gödel logic. The second $\varepsilon $ -theorem also holds for finite-valued first-order Gödel logics. The methods used to prove the extended first $\varepsilon $ -theorem for infinite-valued Gödel logic suggest applications to theories of arithmetic.

We consider a seemingly weaker form of $\Delta ^{1}_{1}$ Turing determinacy.

Let $2 \leqslant \rho < \omega _{1}^{\mathsf {CK}}$ , $\textrm{Weak-Turing-Det}_{\rho }(\Delta ^{1}_{1})$ is the statement:

Every $\Delta ^{1}_{1}$ set of reals cofinal in the Turing degrees contains two Turing distinct, $\Delta ^{0}_{\rho }$ -equivalent reals.

We show in $\mathsf {ZF}^-$ :

$\textrm{Weak-Turing-Det}_{\rho }(\Delta ^{1}_{1})$ implies: for every $\nu < \omega _{1}^{\mathsf {CK}}$ there is a transitive model ${M \models \mathsf {ZF}^{-} + \textrm{``}\aleph _{\nu } \textrm{ exists''.}}$

As a corollary:

• If every cofinal $\Delta ^{1}_{1}$ set of Turing degrees contains both a degree and its jump, then for every $\nu < \omega_1^{\mathsf{CK}}$ , there is atransitive model: $M \models \mathsf{ZF}^{-} + \textrm{``}\aleph_\nu \textrm{ exists''.}$

• • With a simple proof, this improves upon a well-known result of Harvey Friedman on the strength of Borel determinacy (though not assessed level-by-level).

• • Invoking Tony Martin’s proof of Borel determinacy, $\textrm{Weak-Turing-Det}_{\rho }(\Delta ^{1}_{1})$ implies $\Delta ^{1}_{1}$ determinacy.

• • We show further that, assuming $\Delta ^{1}_{1}$ Turing determinacy, or Borel Turing determinacy, as needed:

  • – Every cofinal $\Sigma ^{1}_{1}$ set of Turing degrees contains a “hyp-Turing cone”: ${\{x \in \mathcal {D} \mid d_{0} \leqslant _{T} x \leqslant _{h} d_{0} \}}$ .

  • – For a sequence $(A_{k})_{k < \omega }$ of analytic sets of Turing degrees, cofinal in $\mathcal {D}$ , $\bigcap _{k} A_{k}$ is cofinal in $\mathcal {D}$ .

The Wadge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g., several Hausdorff–Kuratowski (HK)-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q.

Skolem (1956) studied the germs at infinity of the smallest class of real valued functions on the positive real line containing the constant $1$ , the identity function ${\mathbf {x}}$ , and such that whenever f and g are in the set, $f+g,fg$ and $f^g$ are in the set. This set of germs is well ordered and Skolem conjectured that its order type is epsilon-zero. Van den Dries and Levitz (1984) computed the order type of the fragment below $2^{2^{\mathbf {x}}}$ . Here we prove that the set of asymptotic classes within any Archimedean class of Skolem functions has order type $\omega $ . As a consequence we obtain, for each positive integer n, an upper bound for the fragment below $2^{n^{\mathbf {x}}}$ . We deduce an epsilon-zero upper bound for the fragment below $2^{{\mathbf {x}}^{\mathbf {x}}}$ , improving the previous epsilon-omega bound by Levitz (1978). A novel feature of our approach is the use of Conway’s surreal number for asymptotic calculations.

We introduce the $\Sigma _1$ -definable universal finite sequence and prove that it exhibits the universal extension property amongst the countable models of set theory under end-extension. That is, (i) the sequence is $\Sigma _1$ -definable and provably finite; (ii) the sequence is empty in transitive models; and (iii) if M is a countable model of set theory in which the sequence is s and t is any finite extension of s in this model, then there is an end-extension of M to a model in which the sequence is t. Our proof method grows out of a new infinitary-logic-free proof of the Barwise extension theorem, by which any countable model of set theory is end-extended to a model of $V=L$ or indeed any theory true in a suitable submodel of the original model. The main theorem settles the modal logic of end-extensional potentialism, showing that the potentialist validities of the models of set theory under end-extensions are exactly the assertions of S4. Finally, we introduce the end-extensional maximality principle, which asserts that every possibly necessary sentence is already true, and show that every countable model extends to a model satisfying it.

We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property (N) if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1({\mathcal {O}})$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f(x)$ is R-random, then x is R-random as well. If additionally f is known to have bounded variation, then we show f has Luzin’s (N) if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset '$ -Kurtz randomness. This links classical real analysis with algorithmic randomness.

We study the Rudin–Keisler pre-order on Fréchet–Urysohn ideals on $\omega $ . We solve three open questions posed by S. García-Ferreira and J. E. Rivera-Gómez in the articles [5] and [6] by establishing the following results:

• • For every AD family $\mathcal {A},$ there is an AD family $\mathcal {B}$ such that $\mathcal {A}^{\perp } <_{{\textsf {RK}}}\mathcal {B}^{\perp }.$

• • If $\mathcal {A}$ is a nowhere MAD family of size $\mathfrak {c}$ then there is a nowhere MAD family $\mathcal {B}$ such that $\mathcal {I}\left (\mathcal {A}\right ) $ and $\mathcal {I}\left ( \mathcal {B}\right ) $ are Rudin–Keisler incomparable.

• • There is a family $\left \{ \mathcal {B}_{\alpha }\mid \alpha \in \mathfrak {c}\right \} $ of nowhere MAD families such that if $\alpha \neq \beta $ , then $\mathcal {I}\left ( \mathcal {B}_{\alpha }\right ) $ and $\mathcal {I}\left ( \mathcal {B}_{\beta }\right ) $ are Rudin–Keisler incomparable.

Here $\mathcal {I}(\mathcal {A})$ denotes the ideal generated by an AD family $\mathcal {A}$ .

In the context of hyperspaces with the Vietoris topology, for a Fréchet–Urysohn-filter $\mathcal {F}$ we let $\mathcal {S}_{c}\left ( \mathcal {\xi }\left ( \mathcal {F}\right ) \right ) $ be the hyperspace of nontrivial convergent sequences of the space consisting of $\omega $ as discrete subset and only one accumulation point $\mathcal {F}$ whose neighborhoods are the elements of $\mathcal {F}$ together with the singleton $\{\mathcal {F}\}$ . For a FU-filter $\mathcal {F}$ we show that the following are equivalent:

• • $\mathcal {F}$ is a FUF-filter.

• • $\mathcal {S}_{c}\left ( \mathcal {\xi }\left ( \mathcal {F} \right ) \right ) $ is Baire.

We study from the proof complexity perspective the (informal) proof search problem (cf. [17, Sections 1.5 and 21.5]):

• • Is there an optimal way to search for propositional proofs?

We note that, as a consequence of Levin’s universal search, for any fixed proof system there exists a time-optimal proof search algorithm. Using classical proof complexity results about reflection principles we prove that a time-optimal proof search algorithm exists without restricting proof systems iff a p-optimal proof system exists.

To characterize precisely the time proof search algorithms need for individual formulas we introduce a new proof complexity measure based on algorithmic information concepts. In particular, to a proof system P we attach information-efficiency function $i_P(\tau )$ assigning to a tautology a natural number, and we show that:

• • $i_P(\tau )$ characterizes time any P-proof search algorithm has to use on $\tau $ ,

• • for a fixed P there is such an information-optimal algorithm (informally: it finds proofs of minimal information content),

• • a proof system is information-efficiency optimal (its information-efficiency function is minimal up to a multiplicative constant) iff it is p-optimal,

• • for non-automatizable systems P there are formulas $\tau $ with short proofs but having large information measure $i_P(\tau )$ .

We isolate and motivate the problem to establish unconditional super-logarithmic lower bounds for $i_P(\tau )$ where no super-polynomial size lower bounds are known. We also point out connections of the new measure with some topics in proof complexity other than proof search.