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.
@misc{https://doi.org/10.48550/arxiv.2602.22398,doi={10.48550/ARXIV.2602.22398},url={https://arxiv.org/abs/2602.22398},author={Zhu, Hongyu},keywords={Logic (math.LO), FOS: Mathematics, FOS: Mathematics, 03C65, 03C10, 03E15},title={A Complete Bounded Theory with Unbounded Types},publisher={arXiv},year={2026},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
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={Proc. Amer. Math. Soc.},fjournal={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},}