We present a cut elimination argument that witnesses the conservativity of the compositional axioms for truth (without the extended induction axiom) over any theory interpreting a weak subsystem of arithmetic. In doing so we also fix a critical error in Halbach’s original presentation. Our methods show that the admission of these axioms determines a hyper-exponential reduction in the size of derivations of truth-free statements.

We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we characterize which of these linear orders are computably categorical.

D’Aquino, Knight, and Starchenko classified the countable real closed fields with integer parts that are nonstandard models of Peano Arithmetic. We rule out some possibilities for extending their results to the uncountable and study real closures of ɷ1-like models of PA.

Soare [20] proved that the maximal sets form an orbit in ${\cal E}$. We consider here ${\cal D}$-maximal sets, generalizations of maximal sets introduced by Herrmann and Kummer [12]. Some orbits of ${\cal D}$-maximal sets are well understood, e.g., hemimaximal sets [8], but many are not. The goal of this paper is to define new invariants on computably enumerable sets and to use them to give a complete nontrivial classification of the ${\cal D}$-maximal sets. Although these invariants help us to better understand the ${\cal D}$-maximal sets, we use them to show that several classes of ${\cal D}$-maximal sets break into infinitely many orbits.

We prove that the statement “there is a k such that for every f there is a k-bounded diagonally nonrecursive function relative to f” does not imply weak König’s lemma over ${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that every k-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of ${\rm{I\Sigma }}_2^0$.

We study ultrafilters on ω2 produced by forcing with the quotient of ${\cal P}$(ω2) by the Fubini square of the Fréchet filter on ω. We show that such an ultrafilter is a weak P-point but not a P-point and that the only nonprincipal ultrafilters strictly below it in the Rudin–Keisler order are a single isomorphism class of selective ultrafilters. We further show that it enjoys the strongest square-bracket partition relations that are possible for a non-P-point. We show that it is not basically generated but that it shares with basically generated ultrafilters the property of not being at the top of the Tukey ordering. In fact, it is not Tukey-above [ω1]<ω, and it has only continuum many ultrafilters Tukey-below it. A tool in our proofs is the analysis of similar (but not the same) properties for ultrafilters obtained as the sum, over a selective ultrafilter, of nonisomorphic selective ultrafilters.

In this paper we investigate the structure of uncountable maximal antichains of Silver forcing and show that they have to be at least of size d, where d is the dominating number. Part of this work can be used to show that the additivity of the Silver forcing ideal has size at least the unbounding number b. It follows that every reasonable amoeba Silver forcing adds a dominating real.

We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we study degree spectra and the successor relation.

The mad spectrum is the set of all cardinalities of infinite maximal almost disjoint families on ω. We treat the problem to characterize those sets ${\rm {\cal A}} $ which, in some forcing extension of the universe, can be the mad spectrum. We give a complete solution to this problem under the assumption $\vartheta ^{ < \vartheta } = \vartheta $, where $\vartheta = {\rm{min}}\left( {\rm {\cal A}} \right) $.

We analyze the strength of the existence of idempotent ultrafilters in higher-order reverse mathematics.

Let $\left( {{{\cal U}_{{\rm{idem}}}}} \right)$ be the statement that an idempotent ultrafilter on ℕ exists. We show that over $ACA_0^\omega$, the higher-order extension of ACA0, the statement $\left( {{{\cal U}_{{\rm{idem}}}}} \right)$ implies the iterated Hindman’s theorem (IHT) and we show that $ACA_0^\omega + \left( {{{\cal U}_{{\rm{idem}}}}} \right)$ is ${\rm{\Pi }}_2^1$-conservative over $ACA_0^\omega + IHT$ and thus over $ACA_0^ +$.

We consider ${\cal S}$, the class of finite semilattices; ${\cal T}$, the class of finite treeable semilattices; and ${{\cal T}_m}$, the subclass of ${\cal T}$ which contains trees with branching bounded by m. We prove that ${\cal E}{\cal S}$, the class of finite lattices with linear extensions, is a Ramsey class. We calculate Ramsey degrees for structures in ${\cal S}$, ${\cal T}$, and ${{\cal T}_m}$. In addition to this we give a topological interpretation of our results and we apply our result to canonization of linear orderings on finite semilattices. In particular, we give an example of a Fraïssé class ${\cal K}$ which is not a Hrushovski class, and for which the automorphism group of the Fraïssé limit of ${\cal K}$ is not extremely amenable (with the infinite universal minimal flow) but is uniquely ergodic.

It is a celebrated result of McKinsey and Tarski [28] that S4 is the logic of the closure algebra Χ+ over any dense-in-itself separable metrizable space. In particular, S4 is the logic of the closure algebra over the reals R, the rationals Q, or the Cantor space C. By [5], each logic above S4 that has the finite model property is the logic of a subalgebra of Q+, as well as the logic of a subalgebra of C+. This is no longer true for R, and the main result of [5] states that each connected logic above S4 with the finite model property is the logic of a subalgebra of the closure algebra R+.

In this paper we extend these results to all logics above S4. Namely, for a normal modal logic L, we prove that the following conditions are equivalent: (i) L is above S4, (ii) L is the logic of a subalgebra of Q+, (iii) L is the logic of a subalgebra of C+. We introduce the concept of a well-connected logic above S4 and prove that the following conditions are equivalent: (i) L is a well-connected logic, (ii) L is the logic of a subalgebra of the closure algebra $\xi _2^ + $ over the infinite binary tree, (iii) L is the logic of a subalgebra of the closure algebra ${\bf{L}}_2^ + $ over the infinite binary tree with limits equipped with the Scott topology. Finally, we prove that a logic L above S4 is connected iff L is the logic of a subalgebra of R+, and transfer our results to the setting of intermediate logics.

Proving these general completeness results requires new tools. We introduce the countable general frame property (CGFP) and prove that each normal modal logic has the CGFP. We introduce general topological semantics for S4, which generalizes topological semantics the same way general frame semantics generalizes Kripke semantics. We prove that the categories of descriptive frames for S4 and descriptive spaces are isomorphic. It follows that every logic above S4 is complete with respect to the corresponding class of descriptive spaces. We provide several ways of realizing the infinite binary tree with limits, and prove that when equipped with the Scott topology, it is an interior image of both C and R. Finally, we introduce gluing of general spaces and prove that the space obtained by appropriate gluing involving certain quotients of L2 is an interior image of R.

We prove that, for 1 ≤ p < q < ∞, the partially ordered set P(ω)/Fin can be embedded into Borel equivalence relations between ℝω/ℓp and ℝω/ℓq. Since there is an antichain of size continuum in P(ω)/Fin, there are continuum many pairwise incomparable Borel equivalence relations between ℝω/ℓp and ℝω/ℓq.

We give model theoretic criteria for the existence of ∃∀ and ∀∃- formulas in the ring language to define uniformly the valuation rings ${\cal O}$ of models $\left( {K,\,{\cal O}} \right)$ of an elementary theory Σ of henselian valued fields. As one of the applications we obtain the existence of an ∃∀-formula defining uniformly the valuation rings ${\cal O}$ of valued henselian fields $\left( {K,\,{\cal O}} \right)$ whose residue class field k is finite, pseudofinite, or hilbertian. We also obtain ∀∃-formulas φ2 and φ4 such that φ2 defines uniformly k[[t]] in k(t) whenever k is finite or the function field of a real or complex curve, and φ4 replaces φ2 if k is any number field.

We prove that the consequence relation in the Full Non-associative Lambek Calculus is undecidable. An encoding of the halting problem for 2-tag systems using finitely many sequents in the language {⋅,∨} is presented. Therefore already the consequence relation in this fragment is undecidable. Moreover, the construction works even when the structural rules of exchange and contraction are added.

We give a valuation theoretic characterization for a real closed field to be recursively saturated. This builds on work in [9], where the authors gave such a characterization for κ-saturation, for a cardinal $\kappa \ge \aleph _0 $. Our result extends the characterization of Harnik and Ressayre [7] for a divisible ordered abelian group to be recursively saturated.

We investigate ideals of the form {A ⊆ ω: Σn∈Axn is unconditionally convergent} where (xn)n∈ω is a sequence in a Polish group or in a Banach space. If an ideal on ω can be seen in this form for some sequence in X, then we say that it is representable in X.

After numerous examples we show the following theorems: (1) An ideal is representable in a Polish Abelian group iff it is an analytic P-ideal. (2) An ideal is representable in a Banach space iff it is a nonpathological analytic P-ideal.

We focus on the family of ideals representable in c0. We characterize this property via the defining sequence of measures. We prove that the trace of the null ideal, Farah’s ideal, and Tsirelson ideals are not representable in c0, and that a tall Fσ P-ideal is representable in c0 iff it is a summable ideal. Also, we provide an example of a peculiar ideal which is representable in ℓ1 but not in ℝ.

Finally, we summarize some open problems of this topic.

In this paper we investigate the reverse mathematics of higher-order analogues of the theory $$ATR_0$$ within the framework of higher order reverse mathematics developed by Kohlenbach [11]. We define a theory $$RCA_0^3$$, a close higher-type analogue of the classical base theory $$RCA_0$$ which is essentially a conservative subtheory of Kohlenbach’s base theory $$RCA_{\rm{0}}^\omega$$. Working over $$RCA_0^3$$, we study higher-type analogues of statements classically equivalent to $$ATR_0$$, including open and clopen determinacy, and examine the extent to which $$ATR_0$$ remains robust at higher types. Our main result is the separation of open and clopen determinacy for reals, using a variant of Steel’s tagged tree forcing; in the presentation of this result, we develop a new, more flexible framework for Steel-type forcing.

Let M be a C-minimal structure and T its canonical tree (which corresponds in an ultrametric space to the set of closed balls with radius different than ∞ ordered by inclusion). We present a description of definable locally constant functions f : M → T in C-minimal structures having a canonical tree with infinitely many branches at each node and densely ordered branches. This provides both a description of definable subsets of T in one variable and analogues of known results in algebraically closed valued fields.

The resurrection axioms are forms of forcing axioms that were introduced recently by Hamkins and Johnstone, who developed on earlier ideas of Chalons and Veličković. In this note, we introduce a stronger form of resurrection (which we call unbounded resurrection) and show that it gives rise to families of axioms which are consistent relative to extendible cardinals, and which imply the strongest known instances of forcing axioms, such as Martin’s Maximum++. In addition, we study the unbounded resurrection postulates in terms of consistency lower bounds, obtaining, for example, failures of the weak square principle.