×

zbMATH — the first resource for mathematics

Omitting types for finite variable fragments and complete representations of algebras. (English) Zbl 1143.03035
A novel application of algebraic logic to first-order logic is given. The last author has already proved in [Stud. Log. 72, No. 2, 285–309 (2002; Zbl 1019.03047)] that a version of the omitting types theorem fails, in a certain sense, in finite variable fragments of first-order logic; also, complete representations were discussed there. In the paper under review, a new construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension \(n\) with \(n > 2\). In particular, the constructed algebras are one-generated. This construction is used to prove a stronger version of the mentioned negative result, which goes back to a conjecture in [loc. cit.]. It is shown that one binary relation in the language suffices, and that there is no upper bound on the number of extra variables needed in the so-called witness formula. The proof of the new theorem uses methods of algebraic logic; the theorem is actually given also an algebraic form that is even stronger than the logical one.

MSC:
03G15 Cylindric and polyadic algebras; relation algebras
03B10 Classical first-order logic
03C40 Interpolation, preservation, definability
Citations:
Zbl 1019.03047
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] Non-finite axiomatizability results in algebraic logic 57 pp 832– (1992)
[2] Model Theory (1994)
[3] DOI: 10.1023/A:1021364629235 · Zbl 1010.03053
[4] DOI: 10.1023/A:1004275029985 · Zbl 0919.03013
[5] Modal Logic and Process Algebra. A Bisimulation Perspective 53 pp 1– (1995)
[6] On omega-consistency and related properties 21 pp 246– (1956)
[7] The Bulletin of Symbolic Logic 5 pp 88– (1999)
[8] Studia Logica 50 pp 465– (1991)
[9] Handbook of Philosophical Logic 2 pp 133– (2001) · Zbl 0996.03001
[10] Fundamenta Informaticae 5 pp 261– (1982)
[11] Two-variable logic fails the omitting type property (2007)
[12] Algebra Universalis
[13] DOI: 10.1093/jigpal/5.5.699 · Zbl 0886.03044
[14] DOI: 10.1002/mana.19700460105 · Zbl 0182.32301
[15] Atomic representable relation and cylindric algebras with non representable completions (1997)
[16] Non-finitizability of classes of representable cylindric algebras 34 pp 331– (1969)
[17] Mathematical Logic Quarterly 52 pp 44– (2006)
[18] DOI: 10.1090/S0002-9939-1991-1033959-7
[19] Cylindric algebras of sentences 58 pp 743– (1993)
[20] Non-finite axiomatizability results for cylindric and relational algebras 54 pp 951– (1989)
[21] DOI: 10.1007/s00012-007-1987-3 · Zbl 1122.03063
[22] DOI: 10.2307/2372123 · Zbl 0045.31505
[23] DOI: 10.1007/3-540-48242-3_17
[24] Interpolation in the guarded fragment, Studia Logica 70 pp 273– (2002)
[25] DOI: 10.1016/S0168-0072(97)00015-8 · Zbl 0898.03025
[26] Relation algebra reducts of cylindric algebras and an application to proof theory 67 pp 197– (2002) · Zbl 1005.03052
[27] DOI: 10.2178/bsl/1182353893
[28] DOI: 10.1090/S0002-9939-01-06232-3 · Zbl 1002.03054
[29] Relation Algebras by Games 147 (2002) · Zbl 1018.03002
[30] DOI: 10.1016/S0168-0072(01)00085-9 · Zbl 1001.03058
[31] DOI: 10.1016/S0168-0072(01)00084-7 · Zbl 1001.03057
[32] A formalization of set theory without variables 41 (1987)
[33] Complete representations in algebraic logic 62 pp 816– (1997) · Zbl 0893.03025
[34] Logic, Semantics, Metamathematics: Papers from 1923 to 1938 (1956)
[35] DOI: 10.1007/s00012-007-1999-z · Zbl 1135.03029
[36] Cylindric Algebras Parts I, II (1985)
[37] Séminaire de Mathématiques Supérieures 21 (1967)
[38] DOI: 10.1023/A:1012447223176 · Zbl 0993.03085
[39] Mathematical Interpretation of Formal Systems pp 85– (1955) · Zbl 0066.00902
[40] Journal of Applied Non-classical Logics 15 pp 465– (2006)
[41] A generalization of the concept of {\(\omega\)}-consistency 19 pp 183– (1954)
[42] DOI: 10.2178/bsl/1130335206 · Zbl 1111.03053
[43] DOI: 10.1002/malq.19990450304 · Zbl 0933.03041
[44] Algebra Universalis 51 pp 301– (2004)
[45] On the restraining power of guards 64 pp 1719– (1999) · Zbl 0958.03027
[46] DOI: 10.1305/ndjfl/1091030854 · Zbl 1071.03041
[47] Logic Journal of IGPL
[48] Journal of Applied Non-Classical Logics 3 pp 300– (2000)
[49] Studia Logica 72 pp 1– (2002)
[50] DOI: 10.1093/jigpal/8.4.497 · Zbl 0973.03008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.