On completions, neat embeddings and omittings types, yet again

2013/07/02 by Tarek Sayed Ahmed, Ahmed, Tarek Sayed · 6 citations
Computer Science · Mathematics · #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #math.LO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1307.1016

arXiv admin note: text overlap with arXiv:1305.4570, arXiv:1304.1149, arXiv:1302.1368, arXiv:1305.5269, arXiv:1305.4532

arxiv created 2013/07/02 · openalex publication_date 2013/07/02 · arxiv updated 2013/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we investigate using the methodology of algebraic logic, deep algebraic results to prove three new omitting types theorems for finite variable fragments of first order logic. As a sample, we show that it T is an L_n theory and |T|=lambda, lambda a regular cardinal, if T admits elimination of quantifiers, then T omits < 2^λ many non isolated \it maximal types. This is basically a result of Shelah's restricted to L_n. that is not completely representable. We also show, using a rainbow construction for cylindric algebras, that the omitting types theorem fails for L_n even if we consider clique guarded semantics. This is done by constructing a an atomic \A∈ \PEA_n with countably many atoms (which are coloured graphs) who Sc (Pinter's) reduct is not in S_c\Nr_n\Sc_n+3, but A is elementary equivalent to a countable completely representable (polyadic equality) algebra. Various connections between the notions of strong representability and complete representability are given in terms of neat embeddings. Several examples, using rainbow constructions and Monk-like algebras are also given to show that our results are best possible. As a sample we show that, assuming the existence of certain finite relation algebras, that for any k∈ ω, there exists \A∈ \sf RPEA_n∩ \Nr_n\PEA_n+k such that Rd_{\sf Sc}\Cm\At\A∉ S\Nr_n\Sc_n+k+1. This implies that for any finite n≥ 3, for any k≥ 0, there is an L_n theory and a type Γsuch that Gamma is realized in every n+k+1 relativized smooth model, but cannot be isolated by a witness using n+k variables.

Citations

• Blowing up and blurring finite Monk and rainbow algebras
• On some open problems in Algebraic logic
• On the finitizability problem in algebraic logic; recent results
• Various interplays between relation and cylindric algebras
• Strongly representable algebras

Cited by

• Strongly representable atom structures and neat embeddings
• Atom-canonicity, relativized representations and omitting types for clique guarded semantics and guarded logics
• Cylindric and polyadic algebras, new perspectives
• Dedekind completions, neat embeddings and omitting types
• Algebraic analysis of temporal and topological finite variable fragments, using cylindric modal algebras
• Atom-canonicity and complete representations for cylindric-like algebras, and omitting types for the clque guarded fragment of first order logic

Related

• Dedekind completions, neat embeddings and omitting types
• Atom-canonicity, relativized representations and omitting types for clique guarded semantics and guarded logics
• A universal approach to Omitting types for various multimodal and quantifier logics
• Atom-canonicity in algebraic logic in connection to omitting types in modal fragments of L_{ω, ω}
• Atom-canonicity and complete representations for cylindric-like algebras, and omitting types for the clque guarded fragment of first order logic