The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this (...) jump gives benchmark equivalence relations going up the hyperarithmetic hierarchy and we unveil the complicated highness hierarchy that arises from ${\dotplus }$. (shrink)

Abstract(1)We show that it is possible to add $\kappa ^+$ -Cohen subsets to $\kappa $ with a Prikry forcing over $\kappa $. This answers a question from [9].(2)A strengthening of non-Galvin property is introduced. It is shown to be consistent using a single measurable cardinal which improves a previous result by S. Garti, S. Shelah, and the first author [5].(3)A situation with Extender-based Prikry forcings is examined. This relates to a question of H. Woodin.

A first-order structure $\mathfrak {A}$ is called monadically stable iff every expansion of $\mathfrak {A}$ by unary predicates is stable. In this paper we give a classification of the class $\mathcal {M}$ of $\omega $ -categorical monadically stable structure in terms of their automorphism groups. We prove in turn that $\mathcal {M}$ is the smallest class of structures which contains the one-element pure set, is closed under isomorphisms, and is closed under taking finite disjoint unions, infinite copies, and finite index (...) first-order reducts. Using our classification we show that every structure in $\mathcal {M}$ is first-order interdefinable with a finitely bounded homogeneous structure. We also prove that every structure in $\mathcal {M}$ has finitely many reducts up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathcal {M}$. (shrink)

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. (shrink)

We obtain, for the first time, a modular many-valued semantics for combined logics, which is built directly from many-valued semantics for the logics being combined, by means of suitable universal operations over partial non-deterministic logical matrices. Our constructions preserve finite-valuedness in the context of multiple-conclusion logics, whereas, unsurprisingly, it may be lost in the context of single-conclusion logics. Besides illustrating our constructions over a wide range of examples, we also develop concrete applications of our semantic characterizations, namely regarding the semantics (...) of strengthening a given many-valued logic with additional axioms, the study of conditions under which a given logic may be seen as a combination of simpler syntactically defined fragments whose calculi can be obtained independently and put together to form a calculus for the whole logic, and also general conditions for decidability to be preserved by the combination mechanism. (shrink)

Let $\mathscr {C}$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś–Tarski Theorem from classical model theory implies that $\mathscr {C}$ is definable in first-order logic by a sentence $\varphi $ if and only if $\mathscr {C}$ has a finite set of forbidden induced finite subgraphs. This result provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of forbidden (...) induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from $\varphi $ the corresponding forbidden induced subgraphs. This machinery fails on finite graphs as shown by our results: –There is a class $\mathscr {C}$ of finite graphs that is definable in first-order logic and closed under induced subgraphs but has no finite set of forbidden induced subgraphs.–Even if we only consider classes $\mathscr {C}$ of finite graphs that can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from a first-order sentence $\varphi $ that defines $\mathscr {C}$ and the size of the characterization cannot be bounded by $f(|\varphi |)$ for any computable function f.Besides their importance in graph theory, the above results also significantly strengthen similar known theorems for arbitrary structures. (shrink)

Assume that M is a transitive model of $ZFC+CH$ containing a simplified $(\omega _1,2)$ -morass, $P\in M$ is the poset adding $\aleph _3$ generic reals and G is P-generic over M. In M we construct a function between sets of terms in the forcing language, that interpreted in $M[G]$ is an $\mathbb R$ -linear order-preserving monomorphism from the finite elements of an ultrapower of the reals, over a non-principal ultrafilter on $\omega $, into the Esterle algebra of formal power series. (...) Therefore it is consistent that $2^{\aleph _0}>\aleph _2$ and, for any infinite compact Hausdorff space X, there exists a discontinuous homomorphism of $C(X)$, the algebra of continuous real-valued functions on X. (shrink)

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. (shrink)

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. (shrink)

We consider several variants of Keisler’s isomorphism theorem. We separate these variants by showing implications between them and cardinal invariants hypotheses. We characterize saturation hypotheses that are stronger than Keisler’s theorem with respect to models of size $\aleph _1$ and $\aleph _0$ by $\mathrm {CH}$ and $\operatorname {cov}(\mathsf {meager}) = \mathfrak {c} \land 2^{<\mathfrak {c}} = \mathfrak {c}$ respectively. We prove that Keisler’s theorem for models of size $\aleph _1$ and $\aleph _0$ implies $\mathfrak {b} = \aleph _1$ and $\operatorname (...) {cov}(\mathsf {null}) \le \mathfrak {d}$ respectively. As a consequence, Keisler’s theorem for models of size $\aleph _0$ fails in the random model. We also show that for Keisler’s theorem for models of size $\aleph _1$ to hold it is not necessary that $\operatorname {cov}(\mathsf {meager})$ equals $\mathfrak {c}$. (shrink)

We continue with the study of the Katětov order on MAD families. We prove that Katětov maximal MAD families exist under $\mathfrak {b=c}$ and that there are no Katětov-top MAD families assuming $\mathfrak {s\leq b}.$ This improves previously known results from the literature. We also answer a problem form Arciga, Hrušák, and Martínez regarding Katětov maximal MAD families.

The classes stable, simple, and NSOP $_1$ in the stability hierarchy for first-order theories can be characterised by the existence of a certain independence relation. For each of them there is a canonicity theorem: there can be at most one nice independence relation. Independence in stable and simple first-order theories must come from forking and dividing (which then coincide), and for NSOP $_1$ theories it must come from Kim-dividing. We generalise this work to the framework of Abstract Elementary Categories (AECats) (...) with the amalgamation property. These are a certain kind of accessible category generalising the category of (subsets of) models of some theory. We prove canonicity theorems for stable, simple, and NSOP $_1$ -like independence relations. The stable and simple cases have been done before in slightly different setups, but we provide them here as well so that we can recover part of the original stability hierarchy. We also provide abstract definitions for each of these independence relations as what we call isi-dividing, isi-forking, and long Kim-dividing. (shrink)

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. (shrink)

There exist two main notions of typicality in computability theory, namely, Cohen genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity, which is at the intersection of these two notions of typicality, and show that many basis theorems apply to partition genericity. More precisely, we prove that every co-hyperimmune set and every Kurtz random is partition generic, and that every partition generic set admits weak infinite subsets, for various notions of weakness. In particular, (...) we answer a question of Kjos-Hanssen and Liu by showing that every Kurtz random admits an infinite subset which does not compute any set of positive effective Hausdorff dimension. Partition genericity is a partition regular notion, so these results imply many existing pigeonhole basis theorems. (shrink)

Tangled Type Theory was introduced by Randall Holmes in [3] as a new way of approaching the consistency problem for $\mathrm {NF}$. Although the task of finding models for this theory is far from trivial (considering it is equiconsistent with $\mathrm {NF}$ ), ways of constructing models for certain fragments of it have been discovered. In this article, we present a simpler way of constructing models of predicative Tangled Type Theory and consequently of predicative $\mathrm {NF}$. In these new models (...) of predicative $\mathrm {NF}$, the universe is well-orderable and equinumerous to the set of singletons. (shrink)

As a continuation of the work of the third author in [5], we make further observations on the features of Galois cohomology in the general model theoretic context. We make explicit the connection between forms of definable groups and first cohomology sets with coefficients in a suitable automorphism group. We then use a method of twisting cohomology (inspired by Serre’s algebraic twisting) to describe arbitrary fibres in cohomology sequences—yielding a useful “finiteness” result on cohomology sets.Applied to the special case of (...) differential fields and Kolchin’s constrained cohomology, we complete results from [3] by proving that the first constrained cohomology set of a differential algebraic group over a bounded, differentially large, field is countable. (shrink)

Let M be a short extender mouse. We prove that if $E\in M$ and $M\models $ “E is a countably complete short extender whose support is a cardinal $\theta $ and $\mathcal {H}_\theta \subseteq \mathrm {Ult}(V,E)$ ”, then E is in the extender sequence $\mathbb {E}^M$ of M. We also prove other related facts, and use them to establish that if $\kappa $ is an uncountable cardinal of M and $\kappa ^{+M}$ exists in M then $(\mathcal {H}_{\kappa ^+})^M$ satisfies the (...) Axiom of Global Choice. We prove that if M satisfies the Power Set Axiom then $\mathbb {E}^M$ is definable over the universe of M from the parameter $X=\mathbb {E}^M\!\upharpoonright \!\aleph _1^M$, and M satisfies “Every set is $\mathrm {OD}_{\{X\}}$ ”. We also prove various local versions of this fact in which M has a largest cardinal, and a version for generic extensions of M. As a consequence, for example, the minimal proper class mouse with a Woodin limit of Woodin cardinals models “ $V=\mathrm {HOD}$ ”. This adapts to many other similar examples. We also describe a simplified approach to Mitchell–Steel fine structure, which does away with the parameters $u_n$. (shrink)

In this paper, we characterize the possible cofinalities of the least $\lambda $ -strongly compact cardinal. We show that, on the one hand, for any regular cardinal, $\delta $, that carries a $\lambda $ -complete uniform ultrafilter, it is consistent, relative to the existence of a supercompact cardinal above $\delta $, that the least $\lambda $ -strongly compact cardinal has cofinality $\delta $. On the other hand, provably the cofinality of the least $\lambda $ -strongly compact cardinal always carries a (...) $\lambda $ -complete uniform ultrafilter. (shrink)

We investigate a recently devised polyhedral semantics for intermediate logics, in which formulas are interpreted in n-dimensional polyhedra. An intermediate logic is polyhedrally complete if it is complete with respect to some class of polyhedra. The first main result of this paper is a necessary and sufficient condition for the polyhedral completeness of a logic. This condition, which we call the Nerve Criterion, is expressed in terms of Alexandrov’s notion of the nerve of a poset. It affords a purely combinatorial (...) characterisation of polyhedrally complete logics. Using the Nerve Criterion we show, easily, that there are continuum many intermediate logics that are not polyhedrally complete but which have the finite model property. We also provide, at considerable combinatorial labour, a countably infinite class of logics axiomatised by the Jankov–Fine formulas of ‘starlike trees’ all of which are polyhedrally complete. The polyhedral completeness theorem for these ‘starlike logics’ is the second main result of this paper. (shrink)

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. (shrink)

In this paper we prove that from large cardinals it is consistent that there is a singular strong limit cardinal $\nu $ such that the singular cardinal hypothesis fails at $\nu $ and every collection of fewer than $\operatorname {\mathrm {cf}}(\nu )$ stationary subsets of $\nu ^{+}$ reflects simultaneously. For $\operatorname {\mathrm {cf}}(\nu )> \omega $, this situation was not previously known to be consistent. Using different methods, we reduce the upper bound on the consistency strength of this situation for (...) $\operatorname {\mathrm {cf}}(\nu ) = \omega $ to below a single partially supercompact cardinal. The previous upper bound of infinitely many supercompact cardinals was due to Sharon. (shrink)

Several different versions of the theory of numerosities have been introduced in the literature. Here, we unify these approaches in a consistent frame through the notion of set of labels, relating numerosities with the Kiesler field of Euclidean numbers. This approach allows us to easily introduce, by means of numerosities, ordinals and their natural operations, as well as the Lebesgue measure as a counting measure on the reals.

The Baire algebra of a topological space X is the quotient of the algebra of all subsets of X modulo the meager sets. We show that this Boolean algebra can be endowed with a natural closure operator, resulting in a closure algebra which we denote $\mathbf {Baire}(X)$. We identify the modal logic of such algebras to be the well-known system $\mathsf {S5}$, and prove soundness and strong completeness for the cases where X is crowded and either completely metrizable and continuum-sized (...) or locally compact Hausdorff. We also show that every extension of $\mathsf {S5}$ is the modal logic of a subalgebra of $\mathbf {Baire}(X)$, and that soundness and strong completeness also holds in the language with the universal modality. (shrink)

We give a new characterization of the cardinal invariant $\mathfrak {d}$ as the minimal cardinality of a family $\mathcal {D}$ of tall summable ideals such that an ultrafilter is rapid if and only if it has non-empty intersection with all the ideals in the family $\mathcal {D}$. On the other hand, we prove that in the Miller model, given any family $\mathcal {D}$ of analytic tall p-ideals such that $\vert \mathcal {D}\vert <\mathfrak {d}$, there is an ultrafilter $\mathcal {U}$ which (...) is an $\mathscr {I}$ -ultrafilter for all ideals $\mathscr {I}\in \mathcal {D}$ at the same time, yet $\mathcal {U}$ is not a rapid ultrafilter. As a corollary, we obtain that in the Miller model, given any analytic tall p-ideal $\mathscr {I}$, $\mathscr {I}$ -ultrafilters are dense in the Rudin–Blass ordering, generalizing a theorem of Bartoszyński and S. Shelah, who proved that in such model, Hausdorff ultrafilters are dense in the Rudin–Blass ordering. This theorem also shows some limitations about possible generalizations of a theorem of C. Laflamme and J. Zhu. (shrink)

A short core model induction proof of $\mathsf {AD}^{L(\mathbb {R})}$ from $\mathsf {TD} + \mathsf {DC}_{\mathbb {R}}$.

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$. (shrink)

A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to $2$. In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong $\eta $ -representation with no computable copy that is the simplest possible example.

We introduce and analyze a new axiomatic theory $\mathsf {CD}$ of truth. The primitive truth predicate can be applied to sentences containing the truth predicate. The theory is thoroughly classical in the sense that $\mathsf {CD}$ is not only formulated in classical logic, but that the axiomatized notion of truth itself is classical: The truth predicate commutes with all quantifiers and connectives, and thus the theory proves that there are no truth value gaps or gluts. To avoid inconsistency, the instances (...) of the T-schema are restricted to determinate sentences. Determinateness is introduced as a further primitive predicate and axiomatized. The semantics and proof theory of $\mathsf {CD}$ are analyzed. (shrink)

We introduce and study the model-theoretic notions of absolute connectedness and type-absolute connectedness for groups. We prove that groups of rational points of split semisimple linear groups (that is, Chevalley groups) over arbitrary infinite fields are absolutely connected and characterize connected Lie groups which are type-absolutely connected. We prove that the class of type-absolutely connected group is exactly the class of discretely topologized groups with the trivial Bohr compactification, that is, the class of minimally almost periodic groups.

We answer a question of Usuba by showing that the combinatorial principle $\mathrm {UB}_\lambda $ can fail at a singular cardinal. Furthermore, $\lambda $ can be taken to be $\aleph _\omega.$.

Assuming the existence of suitable large cardinals, we show it is consistent that the Provability logic $\mathbf {GL}$ is complete with respect to the filter sequence of normal measures. This result answers a question of Andreas Blass from 1990 and a related question of Beklemishev and Joosten.

Assuming the existence of a monster model, tameness, and continuity of nonsplitting in an abstract elementary class (AEC), we extend known superstability results: let $\mu>\operatorname {LS}(\mathbf {K})$ be a regular stability cardinal and let $\chi $ be the local character of $\mu $ -nonsplitting. The following holds: 1.When $\mu $ -nonforking is restricted to $(\mu,\geq \chi )$ -limit models ordered by universal extensions, it enjoys invariance, monotonicity, uniqueness, existence, extension, and continuity. It also has local character $\chi $. This generalizes (...) Vasey’s result [37, Corollary 13.16] which assumed $\mu $ -superstability to obtain same properties but with local character $\aleph _0$.2.There is $\lambda \in [\mu,h(\mu ))$ such that if $\mathbf {K}$ is stable in every cardinal between $\mu $ and $\lambda $, then $\mathbf {K}$ has $\mu $ -symmetry while $\mu $ -nonforking in (1) has symmetry. In this case:(a) $\mathbf {K}$ has the uniqueness of $(\mu,\geq \chi )$ -limit models: if $M_1,M_2$ are both $(\mu,\geq \chi )$ -limit over some $M_0\in K_{\mu }$, then $M_1\cong _{M_0}M_2$ ;(b)any increasing chain of $\mu ^+$ -saturated models of length $\geq \chi $ has a $\mu ^+$ -saturated union. These generalize [31] and remove the symmetry assumption in [10, 38].Under $(<\mu )$ -tameness, the conclusions of (1), (2)(a)(b) are equivalent to $\mathbf {K}$ having the $\chi $ -local character of $\mu $ -nonsplitting.Grossberg and Vasey [18, 38] gave eventual superstability criteria for tame AECs with a monster model. We remove the high cardinal threshold and reduce the cardinal jump between equivalent superstability criteria. We also add two new superstability criteria to the list: a weaker version of solvability and the boundedness of the U-rank. (shrink)

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 prove that the first-order logic of CZF is intuitionistic first-order logic. To do so, we introduce a new model of transfinite computation (Set Register Machines) and combine the resulting notion of realisability with Beth semantics. On the way, we also show that the propositional admissible rules of CZF are exactly those of intuitionistic propositional logic.

It is proved in $\mathsf {ZF}$ (without the axiom of choice) that, for all infinite sets M, there are no surjections from $\omega \times M$ onto $\operatorname {\mathrm {\mathscr {P}}}(M)$.

We present an analogue of Gödel’s second incompleteness theorem for systems of second-order arithmetic. Whereas Gödel showed that sufficiently strong theories that are $\Pi ^0_1$ -sound and $\Sigma ^0_1$ -definable do not prove their own $\Pi ^0_1$ -soundness, we prove that sufficiently strong theories that are $\Pi ^1_1$ -sound and $\Sigma ^1_1$ -definable do not prove their own $\Pi ^1_1$ -soundness. Our proof does not involve the construction of a self-referential sentence but rather relies on ordinal analysis.