On representing concepts in finite models

Mathematical Logic Quarterly 47 (4):513-523 (2001)
  Copy   BIBTEX

Abstract

We present a method of transferring Tarski's technique of classifying finite order concepts by means of truth-definitions into finite mode theory. The other considered question is the problem of representability relations on words or natural numbers in finite models. We prove that relations representable in finite models are exactly those which are of degree ≤ o′. Finally, we consider theories of sufficiently large finite models. For a given theory T we define sl as the set of all sentences true in almost all finite models for T. For theories of sufficiently large models our version of Tarski's technique becomes practically the same as the classica one. We investigate also degrees of undecidability for theories of sufficiently large finite models. We prove for some special theory ST that its degree is stronger than 0′ but still not more than Σ02.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

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

Through your library

Similar books and articles

Arithmetic of Divisibility in Finite Models.Andrzej Mostowski - 2004 - Mathematical Logic Quarterly 50:169-174.
Computational Semantics for Monadic Quantifiers.Marcin Mostowski - 1998 - Journal of Applied Non--Classical Logics 8 (1-2):107--121.
Inconsistent models of arithmetic part I: Finite models. [REVIEW]Graham Priest - 1997 - Journal of Philosophical Logic 26 (2):223-235.
Modal logic over finite structures.Eric Rosen - 1997 - Journal of Logic, Language and Information 6 (4):427-439.
The model theory of finitely generated finite-by-Abelian groups.Francis Oger - 1984 - Journal of Symbolic Logic 49 (4):1115-1124.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.

Analytics

Added to PP
2009-05-24

Downloads
18 (#711,820)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Marcin Mostowski
Last affiliation: Jagiellonian University

Citations of this work

The Potential in Frege’s Theorem.Will Stafford - 2023 - Review of Symbolic Logic 16 (2):553-577.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
Truth definitions in finite models.Leszek Aleksander Kołodziejczyk - 2004 - Journal of Symbolic Logic 69 (1):183-200.

Add more citations

References found in this work

No references found.

Add more references