Article · Wikipedia archive · Last revised Jul 7, 2026

Decidable sublanguages of set theory

In mathematical logic, various sublanguages of set theory are decidable. They are referred to as syllogistics. Together with the operations of set algebra, decidable languages include:Sets with monotone, additive, and multiplicative functions, but without quantifiers. Sets with restricted quantifiers.

Last revised
Jul 7, 2026
Read time
≈ 1 min
Length
148 w
Citations
4
Source
Wikipedia ↗

In mathematical logic, various sublanguages of set theory are decidable.12 They are referred to as syllogistics. Together with the operations of set algebra, decidable languages include:

  • Sets with monotone, additive, and multiplicative functions, but without quantifiers.3
  • Sets with restricted quantifiers.4
References

References

  1. Cantone, D., E. G. Omodeo and A. Policriti, "Set Theory for Computing. From Decision Procedures to Logic Programming with Sets," Monographs in Computer Science, Springer, 2001.
  2. "Decision procedures for elementary sublanguages of set theory: XIII. Model graphs, reflection and decidability", by Franco Parlamento and Alberto Policriti Journal of Automated Reasoning, Volume 7, Issue 2 (June 1991), Pages: 271 - 284
  3. "A Decision Procedure for a Sublanguage of Set Theory Involving Monotone, Additive, and Multiplicative Functions", by Domenico Cantone and et al.
  4. "A tableau-based decision procedure for a fragment of set theory involving a restricted form of quantification", by Domenico Cantone, Calogero G. Zarba, Viale A. Doria, 1997