Journal of Mathematical Logic

We classify countable metrically homogeneous graphs of diameter 3.

We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore–Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture.

We study a family of ultraproducts of finite fields with the Frobenius automorphism in this paper. Their theories have the strict order property and TP2. But the coarse pseudofinite dimension of the definable sets is definable and integer-valued. Moreover, we also discuss the possible connection between coarse dimension and transformal transcendence degree in these difference fields.

We show that if $\mathrm{\text{cf}}(2^{{\aleph }_0})={\aleph }_1,$ then any nontrivial ${\aleph }_1$-closed forcing notion of size $\le 2^{{\aleph }_0}$ is forcing equivalent to $\mathrm{\text{Add}}({\aleph }_1,1),$ the Cohen forcing for adding a new Cohen subset of ${\omega }_1.$ We also produce, relative to the existence of suitable large cardinals, a model of $\mathrm{\text{ZFC}}$ in which $2^{{\aleph }_0}={\aleph }_2$ and all ${\aleph }_1$-closed forcing notion of size $\le 2^{{\aleph }_0}$ collapse ${\aleph }_2,$ and hence are forcing equivalent to $\mathrm{\text{Add}}({\aleph }_1,1).$ These results answer a question of Scott Williams from 1978. We also extend a result of Todorcevic and Foreman–Magidor–Shelah by showing that it is consistent that every partial order which adds a new subset of ${\aleph }_2,$ collapses ${\aleph }_2$ or ${\aleph }_3.$

We provide comprehensive, level-by-level characterizations of large cardinals, in the range from weakly compact to strongly compact, by closure properties of powerful images of accessible functors. In the process, we show that these properties are also equivalent to various forms of tameness for abstract elementary classes. This systematizes and extends results of [W. Boney and S. Unger, Large cardinal axioms from tameness in AECs, Proc. Amer. Math. Soc. 145(10) (2017) 4517–4532; A. Brooke-Taylor and J. Rosický, Accessible images revisited, Proc. AMS 145(3) (2016) 1317–1327; M. Lieberman, A category-theoretic characterization of almost measurable cardinals (Submitted, 2018), http://arxiv.org/abs/1809.06963; M. Lieberman and J. Rosický, Classification theory for accessible categories. J. Symbolic Logic 81(1) (2016) 1647–1648].

Answering one of the main questions of [S.-D. Friedman, T. Hyttinen and V. Kulikov, Generalized descriptive set theory and classification theory, Mem. Amer. Math. Soc. 230(1081) (2014) 80, Chap. 7], we show that there is a tight connection between the depth of a classifiable shallow theory $T$ and the Borel rank of the isomorphism relation ${\cong }_T^{\kappa }$ on its models of size $\kappa$, for $\kappa$ any cardinal satisfying ${\kappa }^{<\kappa }=\kappa >2^{{\aleph }_0}$. This is achieved by establishing a link between said rank and the ${{ℒ}}_{\infty \kappa }$-Scott height of the $\kappa$-sized models of $T$, and yields to the following descriptive set-theoretical analog of Shelah’s Main Gap Theorem: Given a countable complete first-order theory $T$, either ${\cong }_T^{\kappa }$ is Borel with a countable Borel rank (i.e. very simple, given that the length of the relevant Borel hierarchy is ${\kappa }^{+}>{\aleph }_1$), or it is not Borel at all. The dividing line between the two situations is the same as in Shelah’s theorem, namely that of classifiable shallow theories. We also provide a Borel reducibility version of the above theorem, discuss some limitations to the possible (Borel) complexities of ${\cong }_T^{\kappa }$, and provide a characterization of categoricity of $T$ in terms of the descriptive set-theoretical complexity of ${\cong }_T^{\kappa }$.

If ${𝒩}$ is a proper Polish metric space and ${ℳ}$ is any countable dense submetric space of ${𝒩}$, then the Scott rank of ${𝒩}$ in the natural first-order language of metric spaces is countable and in fact at most ${\omega }_1^{{ℳ}}+1$, where ${\omega }_1^{{ℳ}}$ is the Church–Kleene ordinal of ${ℳ}$ (construed as a subset of $\omega$) which is the least ordinal with no presentation on $\omega$ computable from ${ℳ}$. If ${𝒩}$ is a rigid Polish metric space and ${ℳ}$ is any countable dense submetric space, then the Scott rank of ${𝒩}$ is countable and in fact less than ${\omega }_1^{{ℳ}}$.

Motivated by a characterization of weakly compact cardinals due to Todorcevic, we introduce a new cardinal characteristic, the $C$-sequence number, which can be seen as a measure of the compactness of a regular uncountable cardinal. We prove a number of $ZFC$ and independence results about the $C$-sequence number and its relationship with large cardinals, stationary reflection, and square principles. We then introduce and study the more general $C$-sequence spectrum and uncover some tight connections between the $C$-sequence spectrum and the strong coloring principle $\mathrm{\text{U}}(\dots )$, introduced in Part I of this series.