On representing concepts in finite models

被引:0
作者
Mostowski, M [1 ]
机构
[1] Univ Warsaw, Inst Philosophy, Dept Log, PL-00047 Warsaw, Poland
关键词
finite model theory; finite order logic; truth-definition; degrees of unsolvability; representability;
D O I
10.1002/1521-3870(200111)47:4<513::AID-MALQ513>3.0.CO;2-J
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We present a, method of transferring Tarski's technique of classifying finite order concepts by means of truth-definitions into finite model 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 less than or equal to 0'. Finally, we consider theories of sufficiently large finite models. For a given theory T we define sl(T) 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 classical 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 Sigma (0)(2).
引用
收藏
页码:513 / 523
页数:11
相关论文
共 5 条
  • [1] LEIVANT D, 1994, HDB LOGIC ARTIFICIAL, P228
  • [2] Arity and alternation in second-order logic
    Makowsky, JA
    Pnueli, YB
    [J]. ANNALS OF PURE AND APPLIED LOGIC, 1996, 78 (1-3) : 189 - 202
  • [3] MOSTOWSKI M, 1993, TRUTH DEFINITIONS FI
  • [4] TARSKI A., 1933, Pojecie prawdy w jezykach nauk dedukcyjnych
  • [5] [No title captured]