Logo del repository
  1. Home
 
Opzioni

Set-syllogistics meet combinatorics

Omodeo, Eugenio G.
•
Tomescu, Alexandru I.
•
POLICRITI, Alberto
2015
  • journal article

Periodico
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE
Abstract
This paper considers ∃*∀* prenex sentences of pure first-order predicate calculus with equality. This is the set of formulas which Ramsey's treated in a famous article of 1930. We demonstrate that the satisfiability problem and the problem of existence of arbitrarily large models for these formulas can be reduced to the satisfiability problem for ∃*∀* prenex sentences of Set Theory (in the relators ∈, =). We present two satisfiability-preserving (in a broad sense) translations Φ ↦ (Formula presented.) and Φ ↦ Φσ of ∃*∀* sentences from pure logic to well-founded Set Theory, so that if (Formula presented.) is satisfiable (in the domain of Set Theory) then so is Φ, and if Φσ is satisfiable (again, in the domain of Set Theory) then Φ can be satisfied in arbitrarily large finite structures of pure logic. It turns out that |(Formula presented.)| = (Formula presented.)(|Φ|) and |Φσ| = (Formula presented.)(|Φ|2). Our main result makes use of the fact that ∃*∀* sentences, even though constituting a decidable fragment of Set Theory, offer ways to describe infinite sets. Such a possibility is exploited to glue together infinitely many models of increasing cardinalities of a given ∃*∀* logical formula, within a single pair of infinite sets.
DOI
10.1017/S0960129515000122
WOS
WOS:000391570500012
Archivio
http://hdl.handle.net/11390/1119226
info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-84929018216
Diritti
open access
Soggetti
  • Computer Science Appl...

  • Mathematics (miscella...

Web of Science© citazioni
0
Data di acquisizione
Mar 14, 2024
Visualizzazioni
1
Data di acquisizione
Jun 8, 2022
Vedi dettagli
google-scholar
Get Involved!
  • Source Code
  • Documentation
  • Slack Channel
Make it your own

DSpace-CRIS can be extensively configured to meet your needs. Decide which information need to be collected and available with fine-grained security. Start updating the theme to match your nstitution's web identity.

Need professional help?

The original creators of DSpace-CRIS at 4Science can take your project to the next level, get in touch!

Realizzato con Software DSpace-CRIS - Estensione mantenuta e ottimizzata da 4Science

  • Impostazioni dei cookie
  • Informativa sulla privacy
  • Accordo con l'utente finale
  • Invia il tuo Feedback