Decision procedures for elementary sublanguages of set theory IX. Unsolvability of the decision problem for a restricted subclass of the Δ0-formulas in set theory

DOI10.1002/cpa.3160410206zbMath0632.03009OpenAlexW1996920632MaRDI QIDQ3768865

Alberto Policriti, Franco Parlamento

Publication date: 1988

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/cpa.3160410206

zbMATH Keywords

upper boundsdecidabilityset theorydiagonalization lemmaencoding of syntaxsyntactic objects

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Set theory (03E99)

Related Items (4)

The automation of syllogistic. I: Syllogistic normal forms ⋮ Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages ⋮ Banishing Ultrafilters from Our Consciousness ⋮ A derived algorithm for evaluating \(\varepsilon\)-expressions over abstract sets

Cites Work

• Theory of Formal Systems. (AM-47)
• Unnamed Item

This page was built for publication: Decision procedures for elementary sublanguages of set theory IX. Unsolvability of the decision problem for a restricted subclass of the Δ0-formulas in set theory