Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T09:27:49.815Z Has data issue: false hasContentIssue false

Set-syllogistics meet combinatorics

Published online by Cambridge University Press:  11 May 2015

EUGENIO G. OMODEO
Affiliation:
Dipartimento di Matematica e Geoscienze, Università di Trieste, Via Valerio 12/1, I-34127, Trieste, Italy Email: eomodeo@units.it
ALBERTO POLICRITI
Affiliation:
Dipartimento di Matematica e Informatica, Università di Udine, Via delle Scienze 206, I-33100, Udine, Italy Email: alberto.policriti@uniud.it
ALEXANDRU I. TOMESCU
Affiliation:
Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki, P.O. 68 (Gustaf Hällströmin katu 2b), FI-00014, Helsinki, Finland Email: tomescu@cs.helsinki.fi
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 Φ ↦ $\dot{\Phi}$ and Φ ↦ Φσ of ∃*∀* sentences from pure logic to well-founded Set Theory, so that if $\dot{\Phi}$ 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 | $\dot{\Phi}$ | = $\mathcal{O}$ (|Φ|) and |Φσ| = $\mathcal{O}$ (|Φ|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.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2015