Lune

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Characterizing Sets of Theories That Can Be Disjointly CombinedBenjamin Przybocki, Guilherme Vicentin de Toledo, Yoni ZoharPOPL 2026 · 2 citations

Related papers

  1. Ramsey Quantifiers in Linear ArithmeticsPascal Bergsträßer, Moses Ganardi, Anthony W. Lin, Georg ZetzschePOPL 2024 · 2 citations
  2. Complete First-Order Reasoning for Properties of Functional ProgramsAdithya Murali, Lucas Peña, Ranjit Jhala, P. MadhusudanOOPSLA 2023 · 3 citations
  3. A categorical account of composition methods in logicTomas Jakl, Dan Marsden, Nihil ShahLICS 2023 · 3 citations
  4. Mechanized logical relations for termination-insensitive noninterferenceSimon Oddershede Gregersen, Johan Bay, Amin Timany, Lars BirkedalPOPL 2021 · 14 citations
  5. Graduality and parametricity: together again for the first timeMax S. New, Dustin Jamner, Amal AhmedPOPL 2020 · 36 citations
Dusk over the sea between two cliffs drawn in fine vertical lines