Random models and the gödel case of the decision problem

&
Journal of Symbolic Logic 48 (4):1120-1124 (1983)
  Copy   BIBTEX

Abstract

In a paper of 1933 Godel proved that every satisfiable first-order ∀ 2 ∃ * sentence has a finite model. Actually he constructed a finite model in an ingenious and sophisticated way. In this paper we use a simple and straightforward probabilistic argument to establish existence of a finite model of an arbitrary satisfiable ∀ 2 ∃ * sentence

Categories

Keywords

Reprint years

DOI

10.2307/2273674

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,010

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On the Decision Problem for Two-Variable First-Order Logic.Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
On the decision problem for two-variable first-order logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
Yuri Gurevich and Saharon Shelah. On finite rigid structures. The journal of symbolic logic, vol. 61 , pp. 549–562. [REVIEW]Alexei P. Stolboushkin - 2000 - Bulletin of Symbolic Logic 6 (3):353-355.
A test for expandability.Enrique Casanovas - 1998 - Archive for Mathematical Logic 37 (4):221-234.
Stretchings.O. Finkel & J. P. Ressayre - 1996 - Journal of Symbolic Logic 61 (2):563-585.
Turning decision procedures into disprovers.André Rognes - 2009 - Mathematical Logic Quarterly 55 (1):87-104.
Decidability of Inquisitive Modal Logic via Filtrations.Stipe Marić & Tin Perkov - forthcoming - Studia Logica:1-19.
Probabilistic characterisation of models of first-order theories.Soroush Rafiee Rad - 2021 - Annals of Pure and Applied Logic 172 (1):102875.
Decidability of cylindric set algebras of dimension two and first-order logic with two variables.Maarten Marx & Szabolcs Mikulas - 1999 - Journal of Symbolic Logic 64 (4):1563-1572.
Superrosy dependent groups having finitely satisfiable generics.Clifton Ealy, Krzysztof Krupiński & Anand Pillay - 2008 - Annals of Pure and Applied Logic 151 (1):1-21.

Analytics

Added to PP
2009-01-28

Downloads
57 (#376,745)

6 months
17 (#173,529)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references