FM2024Top-tier venue
The Nonexistence of Unicorns and Many-Sorted Löwenheim-Skolem Theorems
Benjamin Przybocki, Guilherme Vicentin de Toledo, Yoni Zohar, Clark W. Barrett
Abstract
Abstract Stable infiniteness, strong finite witnessability, and smoothness are model-theoretic properties relevant to theory combination in satisfiability modulo theories. Theories that are strongly finitely witnessable and smooth are called strongly polite and can be effectively combined with other theories. Toledo, Zohar, and Barrett conjectured that stably infinite and strongly finitely witnessable theories are smooth and therefore strongly polite. They called counterexamples to this conjecture unicorn theories, as their existence seemed unlikely. We prove that, indeed, unicorns do not exist. We also prove versions of the Löwenheim–Skolem theorem and the Łoś–Vaught test for many-sorted logic.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Related papers
- Ramsey Quantifiers in Linear ArithmeticsPascal Bergsträßer, Moses Ganardi, Anthony W. Lin, Georg ZetzschePOPL 2024 · 2 citations
- Complete First-Order Reasoning for Properties of Functional ProgramsAdithya Murali, Lucas Peña, Ranjit Jhala, P. MadhusudanOOPSLA 2023 · 3 citations
- A categorical account of composition methods in logicTomas Jakl, Dan Marsden, Nihil ShahLICS 2023 · 3 citations
- Mechanized logical relations for termination-insensitive noninterferenceSimon Oddershede Gregersen, Johan Bay, Amin Timany, Lars BirkedalPOPL 2021 · 14 citations
- Graduality and parametricity: together again for the first timeMax S. New, Dustin Jamner, Amal AhmedPOPL 2020 · 36 citations
