As is well-known, the Bernays-Schonfinkel-Ramsey class of all prenex there exists *for all* V-sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are is an element of and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem for the BSR class is proved by following a purely semantic approach the remaining part of the decidability result being postponed to a forthcoming paper.

The Bernays Schoenfinkel Ramsey class for set theory: semidecidability

POLICRITI, Alberto
2010-01-01

Abstract

As is well-known, the Bernays-Schonfinkel-Ramsey class of all prenex there exists *for all* V-sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are is an element of and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem for the BSR class is proved by following a purely semantic approach the remaining part of the decidability result being postponed to a forthcoming paper.
File in questo prodotto:
File Dimensione Formato  
OmodeoPolicriti-JSL-2010.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 230.22 kB
Formato Adobe PDF
230.22 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/860042
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 7
social impact