For which infinite cardinals $\kappa $ is there a partition of the real line ${\mathbb R}$ into precisely $\kappa $ Borel sets? Work of Lusin, Souslin, and Hausdorff shows that ${\mathbb R}$ can be partitioned into $\aleph _1$ Borel sets. But other than this, we show that the spectrum of possible sizes of partitions of ${\mathbb R}$ into Borel sets can be fairly arbitrary. For example, given any $A \subseteq \omega $ with $0,1 \in A$, there is a forcing extension in which ${A = \{ n :\, \text {there is a partition of } {{\mathbb R}} \text { into }\aleph _n\text { Borel sets}\}}$. We also look at the corresponding question for partitions of ${\mathbb R}$ into closed sets. We show that, like with partitions into Borel sets, the set of all uncountable $\kappa $ such that there is a partition of ${\mathbb R}$ into precisely $\kappa $ closed sets can be fairly arbitrary.

We can measure the complexity of a logical formula by counting the number of alternations between existential and universal quantifiers. Suppose that an elementary first-order formula $\varphi $ (in $\mathcal {L}_{\omega ,\omega }$) is equivalent to a formula of the infinitary language $\mathcal {L}_{\infty ,\omega }$ with n alternations of quantifiers. We prove that $\varphi $ is equivalent to a finitary formula with n alternations of quantifiers. Thus using infinitary logic does not allow us to express a finitary formula in a simpler way.

Cohesive powers of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let $\omega $, $\zeta $, and $\eta $ denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of $\omega $. If $\mathcal {L}$ is a computable copy of $\omega $ that is computably isomorphic to the usual presentation of $\omega $, then every cohesive power of $\mathcal {L}$ has order-type $\omega + \zeta \eta $. However, there are computable copies of $\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to $\omega + \zeta \eta $. For example, we show that there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \eta $. Our most general result is that if $X \subseteq \mathbb {N} \setminus \{0\}$ is a Boolean combination of $\Sigma _2$ sets, thought of as a set of finite order-types, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where $\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$ denotes the shuffle of the order-types in X and the order-type $\omega + \zeta \eta + \omega ^*$. Furthermore, if X is finite and non-empty, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X)$.

Generalizing the notion of a tight almost disjoint family, we introduce the notions of a tight eventually different family of functions in Baire space and a tight eventually different set of permutations of $\omega $. Such sets strengthen maximality, exist under $\mathsf {MA} (\sigma \mathrm {-centered})$ and come with a properness preservation theorem. The notion of tightness also generalizes earlier work on the forcing indestructibility of maximality of families of functions. As a result we compute the cardinals $\mathfrak {a}_e$ and $\mathfrak {a}_p$ in many known models by giving explicit witnesses and therefore obtain the consistency of several constellations of cardinal characteristics of the continuum including $\mathfrak {a}_e = \mathfrak {a}_p = \mathfrak {d} < \mathfrak {a}_T$, $\mathfrak {a}_e = \mathfrak {a}_p < \mathfrak {d} = \mathfrak {a}_T$, $\mathfrak {a}_e = \mathfrak {a}_p =\mathfrak {i} < \mathfrak {u}$, and $\mathfrak {a}_e=\mathfrak {a}_p = \mathfrak {a} < non(\mathcal N) = cof(\mathcal N)$. We also show that there are $\Pi ^1_1$ tight eventually different families and tight eventually different sets of permutations in L thus obtaining the above inequalities alongside $\Pi ^1_1$ witnesses for $\mathfrak {a}_e = \mathfrak {a}_p = \aleph _1$.

Moreover, we prove that tight eventually different families are Cohen indestructible and are never analytic.

Sahlqvist theory is extended to the fragments of the intuitionistic propositional calculus that include the conjunction connective. This allows us to introduce a Sahlqvist theory of intuitionistic character amenable to arbitrary protoalgebraic deductive systems. As an application, we obtain a Sahlqvist theorem for the fragments of the intuitionistic propositional calculus that include the implication connective and for the extensions of the intuitionistic linear logic.

Lindström’s theorem obviously fails as a characterization of first-order logic without identity ($\mathcal {L}_{\omega \omega }^{-} $). In this note, we provide a fix: we show that $\mathcal {L}_{\omega \omega }^{-} $ is a maximal abstract logic satisfying a weak form of the isomorphism property (suitable for identity-free languages and studied in [11]), the Löwenheim–Skolem property, and compactness. Furthermore, we show that compactness can be replaced by being recursively enumerable for validity under certain conditions. In the proofs, we use a form of strong upwards Löwenheim–Skolem theorem not available in the framework with identity.

We investigate pseudopowers of singular cardinals and deduce some consequences for covering numbers at singular cardinals of uncountable cofinality.

We investigate iterating the construction of $C^{*}$, the L-like inner model constructed using first order logic augmented with the “cofinality $\omega $” quantifier. We first show that $\left (C^{*}\right )^{C^{*}}=C^{*}\ne L$ is equiconsistent with $\mathrm {ZFC}$, as well as having finite strictly decreasing sequences of iterated $C^{*}$s. We then show that in models of the form $L[U]$ we get infinite decreasing sequences of length $\omega $, and that an inner model with a measurable cardinal is required for that.

We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ over $\mathsf {RCA}_0$. For each fixed $k \geq 3$, the Rival–Sands theorem for infinite partial orders of width $\leq \!k$ is equivalent to $\mathsf {ADS}$ over $\mathsf {RCA}_0$. The Rival–Sands theorem for infinite partial orders that are decomposable into the union of two chains is equivalent to $\mathsf {SADS}$ over $\mathsf {RCA}_0$. Here $\mathsf {RCA}_0$ denotes the recursive comprehension axiomatic system, $\mathsf {I}\Sigma ^0_{2}$ denotes the $\Sigma ^0_2$ induction scheme, $\mathsf {ADS}$ denotes the ascending/descending sequence principle, and $\mathsf {SADS}$ denotes the stable ascending/descending sequence principle. To the best of our knowledge, these versions of the Rival–Sands theorem for partial orders are the first examples of theorems from the general mathematics literature whose strength is exactly characterized by $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$, by $\mathsf {ADS}$, and by $\mathsf {SADS}$. Furthermore, we give a new purely combinatorial result by extending the Rival–Sands theorem to infinite partial orders that do not have infinite antichains, and we show that this extension is equivalent to arithmetical comprehension over $\mathsf {RCA}_0$.

After reviewing various natural bi-interpretations in urelement set theory, including second-order set theories with urelements, we explore the strength of second-order reflection in these contexts. Ultimately, we prove that second-order reflection with the abundant atom axiom is bi-interpretable and hence also equiconsistent with the existence of a supercompact cardinal. The proof relies on a reflection characterization of supercompactness, namely, a cardinal $\kappa $ is supercompact if and only if every $\Pi ^1_1$ sentence true in a structure M (of any size) containing $\kappa $ in a language of size less than $\kappa $ is also true in a substructure $m\prec M$ of size less than $\kappa $ with $m\cap \kappa \in \kappa $.

We study the isomorphism relation on Borel classes of locally compact Polish metric structures. We prove that isomorphism on such classes is always classifiable by countable structures (equivalently: Borel reducible to graph isomorphism), which implies, in particular, that isometry of locally compact Polish metric spaces is Borel reducible to graph isomorphism. We show that potentially $\boldsymbol {\Pi }^{0}_{\alpha + 1}$ isomorphism relations are Borel reducible to equality on hereditarily countable sets of rank $\alpha $, $\alpha \geq 2$. We also study approximations of the Hjorth-isomorphism game, and formulate a condition ruling out classifiability by countable structures.

We prove that the category $\mathsf {SBor}$ of standard Borel spaces is the (bi-)initial object in the 2-category of countably complete Boolean (countably) extensive categories. This means that $\mathsf {SBor}$ is the universal category admitting some familiar algebraic operations of countable arity (e.g., countable products and unions) obeying some simple compatibility conditions (e.g., products distribute over disjoint unions). More generally, for any infinite regular cardinal $\kappa $ , the dual of the category $\kappa \mathsf {Bool}_{\kappa }$ of $\kappa $ -presented $\kappa $ -complete Boolean algebras is (bi-)initial in the 2-category of $\kappa $ -complete Boolean ( $\kappa $ -)extensive categories.

We employ the lens provided by formal truth theory to study axiomatizations of Peano Arithmetic ${\textsf {(PA)}}$. More specifically, let Elementary Arithmetic ${\textsf {(EA)}}$ be the fragment $\mathsf {I}\Delta _0 + \mathsf {Exp}$ of ${\textsf {PA}}$, and let ${\textsf {CT}}^-[{\textsf {EA}}]$ be the extension of ${\textsf {EA}}$ by the commonly studied axioms of compositional truth ${\textsf {CT}}^-$. We investigate both local and global properties of the family of first order theories of the form ${\textsf {CT}}^-[{\textsf {EA}}] +\alpha $, where $\alpha $ is a particular way of expressing “${\textsf {PA}}$ is true” (using the truth predicate). Our focus is dominantly on two types of axiomatizations, namely: (1) schematic axiomatizations that are deductively equivalent to ${\textsf {PA}}$ and (2) axiomatizations that are proof-theoretically equivalent to the canonical axiomatization of ${\textsf {PA}}$.

Propositional modal logic over relational frames is naturally extended with propositional quantifiers by letting them range over arbitrary sets of worlds of the relevant frame. This is also known as second-order propositional modal logic. The propositionally quantified modal logic of a class of relational frames is often not axiomatizable, although there are known exceptions, most notably the case of frames validating the strong modal logic $\mathrm {S5}$. Here, we develop new general methods with which many of the open questions in this area can be answered. We illustrate the usefulness of these methods by applying them to a range of examples, which provide a detailed picture of which normal modal logics define classes of relational frames whose propositionally quantified modal logic is axiomatizable. We also apply these methods to establish new results in the multimodal case.

The paper introduces a broad family of metrics applicable to finite and countably infinite strings, or, by extension, to formal structures serving as semantics for countable languages. The main focus is on applications to sets of pointed Kripke models, a semantics for modal logics. For the resulting metric spaces, the paper classifies topological properties including which metrics are topologically equivalent, providing sufficient conditions for compactness, characterizing clopen sets and isolated points, and characterizing the metrical topologies by a concept of logical convergence. We then apply the approach to maps from dynamic epistemic logic, showing that product updates with action models yield continuous maps, hence allowing for an interpretation of the iterated updates as discrete time dynamical systems.

We show that in many extender models, e.g., the minimal one with infinitely many Woodin cardinals or the minimal with a Woodin cardinal that is a limit of Woodin cardinals, there are no generic embeddings with critical point $\omega _1$ that resemble the stationary tower at the second Woodin cardinal. The meaning of “resemble” is made precise in the paper (see Definition 0.3).

We show that Miller partition forcing preserves selective independent families and P-points, which implies the consistency of $\mbox {cof}(\mathcal {N})=\mathfrak {a}=\mathfrak {u}=\mathfrak {i}<\mathfrak {a}_T=\omega _2$. In addition, we show that Shelah’s poset for destroying the maximality of a given maximal ideal preserves tight mad families and so we establish the consistency of $\mbox {cof}(\mathcal {N})=\mathfrak {a}=\mathfrak {i}=\omega _1<\mathfrak {u}=\mathfrak {a}_T=\omega _2$.

Following the finitist’s rejection of the complete totality of the natural numbers, a finitist language allows only propositional connectives and bounded quantifiers in the formula-construction but not unbounded quantifiers. This is opposed to the currently standard framework, a first-order language. We conduct axiomatic studies on the notion of truth in the framework of finitist arithmetic in which at least smash function $\#$ is available. We propose finitist variants of Tarski ramified truth theories up to rank $\omega $, of Kripke–Feferman truth theory and of Friedman–Sheard truth theory, and show that all of these have the same strength as the finitist arithmetic of one higher level along Grzegorczyk hierarchy. On the other hand, we also show that adding Burgess-style groundedness schema, adjusted to the finitist setting, makes Kripke–Feferman truth theory as strong as primitive recursive arithmetic. Meanwhile, we obtain some basic results on finitist theories of (full and hat) inductive definitions and on the second order axiom of hat inductive definitions for positive operators.

There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

We investigate properties of the ineffability and the Ramsey operator, and a common generalization of those that was introduced by the second author, with respect to higher indescribability, as introduced by the first author. This extends earlier investigations on the ineffability operator by James Baumgartner, and on the Ramsey operator by Qi Feng, by Philip Welch et al., and by the first author.