We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order (...) logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

What precisely are fragments of classical first-order logic showing “modal” behaviour? Perhaps the most influential answer is that of Gabbay 1981, which identifies them with so-called “finite-variable fragments”, using only some fixed finite number of variables (free or bound). This view-point has been endorsed by many authors (cf. van Benthem 1991). We will investigate these fragments, and find that, illuminating and interesting though they are, they lack the required nice behaviour in our sense. (Several new negative results support this claim.) (...) As a counterproposal, then, we define a large fragment of predicate logic characterized by its use of only bounded quantification. This so-called guarded fragment enjoys the above nice properties, including decidability, through an effectively bounded finite model property. (These are new results, obtained by generalizing notions and techniques from modal logic.) Moreover, its own internal finite variable hierarchy turns out to work well. Finally, we shall make another move. The above analogy works both ways. Modal operators are like quantifiers, but quantifiers are also like modal operators. This observation inspires a generalized semantics for first-order predicate logic with accessibility constraints on available assignments (cf. N´emeti 1986, 1992) which moves the earlier quantifier restrictions into the semantics. This provides a fresh look at the landscape of possible predicate logics, including candidates sharing various desirable features with basic modal logic – in particular, its decidability. (shrink)

We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin''s axiom. Finally we apply our results to finite-variable first order logic showing that Henkin and Orey''s omitting types theorem fails for L n, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. L n has been recently (and quite extensively) studied as a (...) many-dimensional modal logic. (shrink)

We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n ≤ w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin's axiom. Finally we apply our results to finite-variable first order logic showing that Henkin and Orey's omitting types theorem fails for Ln, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. Ln has been recently (and quite extensively) studied as a many-dimensional (...) modal logic. (shrink)

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension are elementary.