Atom-canonicity and complete representations for cylindric-like algebras, and omitting types for the clque guarded fragment of first order logic

2014/06/25 by Tarek Sayed Ahmed, Ahmed, Tarek Sayed · 3 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Topology and Set Theory #FOS: Mathematics #Logic (math.LO) #Logic, programming, and type systems #math.LO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1408.3282

arXiv admin note: text overlap with arXiv:1308.6165, arXiv:1307.1016

arxiv created 2014/06/25 · openalex publication_date 2014/06/25 · arxiv updated 2014/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Fix a finite ordinal n>2. We show that there exists an atomic, simple and countable representable CA_n, such that its minimal completion is outside SNr_nCA_n+3. Hence, for any finite k≥ 3, the variety SNr_nCA_n+k is not atom-canonical, so that the variety of CA_n's having n+k-flat representations is not atom-canonical, too. We show, for finite k≥ 3, that S_cNr_nCA_n+k is not elementary, hence the class of CA_n's having complete n+3-smooth representations is not elementary. We obtain analogous results by replacing flat and smooth, respectively, by (the weaker notion of) square; this give a stronger result in both cases and here we can allow k to be infinite. Our results are proved using rainbow constructions for CA's. We lift the negative result on atom-canonicity to the transfinite. We also show that for any ordinal α≥ ω, for any finite k≥ 1, and for any r∈ ω, there exists an atomic algebra A_r∈ SNr_\alphaCA_α+k∼ SNr_nCA_α+k+1, such that Π_r/U A_r∈ RCA_α where U is any non--principal ultrafilter on ω. Reaping the harvest of our algebraic results we investigate a plethora of omitting types theorems for variants of first logic including its finite variable fragments and its packed fragment.

Citations

• Atom-canonicity, relativized representations and omitting types for clique guarded semantics and guarded logics
• On completions, neat embeddings and omittings types, yet again

Cited by

• Problems on neat embeddings solved by rainbow constructions and Monk algebras
• Splitting methods in algebraic logic: Proving results on non-atom-canonicity, non-finite axiomatizability and non-first oder definability for cylindric and relation algebras
• Finite relation algebras and omitting types in modal fragments of first order logic

Related

• Dedekind completions, neat embeddings and omitting types
• Atom-canonicity in algebraic logic in connection to omitting types in modal fragments of L_{ω, ω}
• Atom-canonicity, relativized representations and omitting types for clique guarded semantics and guarded logics
• For finite n≥ 3, and k≥ 4, the variety SNr_n\CA_n+k is not atom canonical
• On neat atom structures for cylindric like algebras