首页   按字顺浏览 期刊浏览 卷期浏览 THE DECISION PROBLEM FOR RESTRICTED UNIVERSAL QUANTIFICATION IN SET THEORY AND THE AXIO...
THE DECISION PROBLEM FOR RESTRICTED UNIVERSAL QUANTIFICATION IN SET THEORY AND THE AXIOM OF FOUNDATION

 

作者: Franco Parlamento,   Alberto Policriti,  

 

期刊: Mathematical Logic Quarterly  (WILEY Available online 1992)
卷期: Volume 38, issue 1  

页码: 143-156

 

ISSN:0942-5616

 

年代: 1992

 

DOI:10.1002/malq.19920380110

 

出版商: WILEY‐VCH Verlag Berlin GmbH

 

关键词: Set‐satisfiability problem;Antifoundation axioms

 

数据来源: WILEY

 

摘要:

AbstractThe still unsettled decision problem for the restricted purely universal formulae ((∀)0‐formulae) of the first order set‐theoretic language based over =, ∈ is discussed in relation with the adoption or rejection of the axiom of foundation. Assuming the axiom of foundation, the related finite set‐satisfiability problem for the very significant subclass of the (∀)0‐formulae consisting of the formulae involving only nested variables of level 1 is proved to be semidecidable on the ground of a reflection property over the hereditarily finite sets, and various extensions of this result are obtained. When variables are restricted to range only over sets, in universes with infinitely many urelements the set‐satisfiability problem is shown to be solvable provided the axiom of foundation is assumed; if it is not, then the decidability of a related derivability problem still holds. That, in turn, suggests the alternative adoption of an antifoundation axiom under which the set‐satisfiability problem is also solvable (of course with different answers). Turning to set theory without urelements, assuming a form of Boffa's antifoundation axiom, the complement of the set‐satisfiability problem for the full class of Δ0‐formulae is shown to be semidecidable; a result that is known not to hold, for the set‐satisfiability problem itself, even for a very restricted sub

 

点击下载:  PDF (775KB)



返 回