One measure of the complexity of a first-order theory, and similarly
a type, is the complexity of the formulas required to axiomatize it. We
say a theory is bounded if there is an axiomatization involving only
\(\forall_n\)-formulas for some finite
\(n\), and unbounded otherwise. One
might expect bounded theories to have only bounded types. In fact, an
analogue holds in infinitary logic, where the complexity of a Scott
sentence roughly agrees with the complexity of the most complicated
automorphism orbit. Our main result, however, shows this is not the case
in the first-order setting: Namely, there can be a bounded theory, in
fact \(\forall_1\)-axiomatizable, which
has unbounded types.
@article{Bdd_Unbdd,doi={10.1017/jsl.2026.10208},journal={Journal of Symbolic Logic},url={https://doi.org/10.1017/jsl.2026.10208},author={Zhu, Hongyu},keywords={Logic (math.LO), FOS: Mathematics, FOS: Mathematics, 03C65, 03C10, 03E15},title={A Complete Bounded Theory with Unbounded Types},year={2026},copyright={Creative Commons Attribution 4.0 International},note={Published online ahead of print},}
Infinite Belligerent Jump Inversion and Computable Scott Analysis
Scott analysis provides two fundamental tools for studying countable
structures: Scott sentences, which characterize structures up to
isomorphism, and back-and-forth relations, which measure structural
similarity. A recurring phenomenon in computable structure theory is
that many notions naturally associated with level \(\alpha\) of Scott analysis have effective
complexity at approximately \(2\alpha\)
jumps. This discrepancy appears both in the complexity of the
back-and-forth relations and in the passage from arbitrary infinitary
formulas to computable infinitary formulas.
We develop two new coding tools, the Belligerent Pairs Theorem and
Belligerent Jump Inversion Theorem, which allow information at
complexity level \(2\alpha\) to be
reflected in computable structures whose distinguishing features already
appear at level \(\alpha\). These
results extend Harrison-Trainor’s finite unfriendly jump inversion
uniformly throughout the computable ordinals.
As applications, we determine the optimal interaction between syntactic
complexity and oracle complexity for computable Scott sentences and for
formulas distinguishing computable structures. For every computable
infinite ordinal \(\alpha\), we
determine the oracle needed to compute a \(\Pi^{\mathrm{in}}_\alpha\) Scott sentence
for a computable structure which has a \(\Pi^{\mathrm{in}}_\alpha\) Scott sentence.
Any computable structure with a \(\Pi^{\mathrm{in}}_\alpha\) Scott sentence
has a computable \(\Pi^{\mathrm{in}}_{2\alpha}\) Scott
sentence. We show that both of these bounds are sharp. We prove
analogous optimal results for formulas witnessing failure of the \(\alpha\)-back-and-forth relation. We also
obtain further applications, including a resolution of a question of
Chen, Gonzalez, and Harrison-Trainor concerning the complexity of
back-and-forth classes.
@misc{andrews2026infinitebelligerentjumpinversion,title={Infinite Belligerent Jump Inversion and Computable Scott Analysis},author={Andrews, Uri and Gonzalez, David and Zhu, Hongyu},year={2026},archiveprefix={arXiv},primaryclass={math.LO},url={https://arxiv.org/abs/2607.10935},doi={10.48550/arXiv.2607.10935},pubstate={Submitted},}
2025
The Borel Complexity of the Class of Models of
First-Order Theories
Uri
Andrews, David
Gonzalez, Steffen
Lempp, Dino
Rossegger, and Hongyu
Zhu
Proceedings of the American Mathematical Society, 2025
We investigate the descriptive complexity of the set of models of
first-order theories. Using classical results of Knight and Solovay, we
give a sharp condition for complete theories to have a \(\boldsymbolΠ_ω^0\)-complete set of models.
We also give sharp conditions for theories to have a \(\boldsymbolΠ^0_n\)-complete set of models.
Finally, we determine the Turing degrees needed to witness the
completeness.
@article{AGLRZ,author={Andrews, Uri and Gonzalez, David and Lempp, Steffen and Rossegger, Dino and Zhu, Hongyu},title={The {B}orel Complexity of the Class of Models of First-Order
Theories},journal={Proceedings of the American Mathematical Society},volume={153},year={2025},number={9},pages={4013--4024},issn={0002-9939,1088-6826},mrclass={03C62 (03C52 03E15)},mrnumber={4936351},doi={10.1090/proc/17308},url={https://doi.org/10.1090/proc/17308},}
2021
An Analysis of COVID-19 Knowledge Graph Construction and Applications
Dominic
Flocco, Bryce
Palmer-Toy, Ruixiao
Wang, Hongyu
Zhu, Rishi
Sonthalia, Junyuan
Lin, Andrea L.
Bertozzi, and P.
Jeffrey Brantingham
In 2021 IEEE International Conference on Big Data (Big Data), Dec 2021
The construction and application of knowledge graphs have seen a rapid increase across many disciplines in re-cent years. Additionally, the problem of uncovering relationships between developments in the COVID-19 pandemic and social me-dia behavior is of great interest to researchers hoping to curb the spread of the disease. In this paper we present a knowledge graph constructed from COVID-19 related tweets in the Los Angeles area, supplemented with federal and state policy announcements and disease spread statistics. By incorporating dates, topics, and events as entities, we construct a knowledge graph that describes the connections between these useful information. We use natural language processing and change point analysis to extract tweet-topic, tweet-date, and event-date relations. Further analysis on the constructed knowledge graph provides insight into how tweets reflect public sentiments towards COVID-19 related topics and how changes in these sentiments correlate with real-world events.
@inproceedings{9671479,author={Flocco, Dominic and Palmer-Toy, Bryce and Wang, Ruixiao and Zhu, Hongyu and Sonthalia, Rishi and Lin, Junyuan and Bertozzi, Andrea L. and Jeffrey Brantingham, P.},booktitle={2021 IEEE International Conference on Big Data (Big Data)},title={An Analysis of COVID-19 Knowledge Graph Construction and Applications},year={2021},volume={},number={},pages={2631-2640},keywords={COVID-19;Correlation;Social networking (online);Pandemics;Conferences;Time series analysis;Blogs;knowledge graph;Twitter;COVID-19;natural language processing;graph embedding;link prediction},doi={10.1109/BigData52589.2021.9671479},issn={},month=dec,}
Ongoing Projects
In preparation
Degree Spectra of Structures with Low Scott Rank
Uri
Andrews, David
Gonzalez, Joseph S.
Miller, and Hongyu
Zhu