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={The 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},pages={1–14},copyright={Creative Commons Attribution 4.0 International},}
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
The construction and application of knowledge graphs have seen a rapid increase across many disciplines in recent years. Additionally, the problem of uncovering relationships between developments in the COVID-19 pandemic and social media 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.
@misc{https://doi.org/10.48550/arxiv.2110.04932,doi={10.48550/ARXIV.2110.04932},url={https://arxiv.org/abs/2110.04932},author={Flocco, Dominic and Palmer-Toy, Bryce and Wang, Ruixiao and Zhu, Hongyu and Sonthalia, Rishi and Lin, Junyuan and Bertozzi, Andrea L. and Brantingham, P. Jeffrey},keywords={Social and Information Networks (cs.SI), Computation and Language (cs.CL), FOS: Computer and information sciences, FOS: Computer and information sciences},title={An Analysis of COVID-19 Knowledge Graph Construction and Applications},publisher={arXiv},year={2021},copyright={arXiv.org perpetual, non-exclusive license},}