Politeness suffices for theory combination

Let Σ1\Sigma_1 and Σ2\Sigma_2 be disjoint signatures, and let T1{\mathcal{T}}_1 and T2{\mathcal{T}}_2 be decidable theories over them. Let T1T2{\mathcal{T}}_1\oplus{\mathcal{T}}_2 be the theory over Σ1Σ2\Sigma_1\cup\Sigma_2 axiomatized by the union of the axioms of T1{\mathcal{T}}_1 and T2{\mathcal{T}}_2. A theory is polite when it is both smooth and finitely witnessable, where smoothness and finite witnessability are as defined in the source. Politeness conjecture. T1T2{\mathcal{T}}_1\oplus{\mathcal{T}}_2 is decidable, provided that T2{\mathcal{T}}_2 is polite. This conjecture asserts that politeness is sufficient for theory combination. It was stated as a theorem in earlier work, but the proof was later refuted; the claim consequently remained conjectural.

Sources & referencesView supporting material

Primary source

Guilherme V. Toledo, Benjamin Przybocki and Yoni Zohar, “Being polite is not enough (and other limits of theory combination)”, arXiv:2505.04870 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.