Source author record

Tarek Sayed Ahmed

Tarek Sayed Ahmed appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

42works
1topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

42 published item(s)

preprint2020arXiv

An infinite stratum of representability; some cylindric algebras are more representable than others

Let $2<n<m\leq ω$. Let $\CA_n$ denote the class of cylindric algebras of dimension $n$ and $\RCA_n$ denote the class of representable $\CA_n$s. We say that $\A\in \RCA_n$ is representable up to $m$ if $\Cm\At\A$ has an $m$-square representation. An $m$ square represenation is locally relativized represenation that is classical locally only on so called $m$-squares'. Roughly if we zoom in by a movable window to an $m$ square representation, there will become a point determinded and depending on $m$ where we mistake the $m$ square-representation for a genuine classical one. When we zoom out the non-representable part gets more exposed. For $2<n<m<l\leq ω$, an $l$ square represenation is $m$-square; the converse however is not true. The variety $\RCA_n$ is a limiting case coinciding with $\CA_n$s having $ω$-square representations. Let $\RCA_n^m$ be the class of algebras representable up to $m$. We show that $\RCA_n^{m+1}\subsetneq \bold \RCA_n^m$ for $m\geq n+2$.

preprint2020arXiv

Completely representable neat reducts

For an ordinal $α$, $\sf PEA_α$ denotes the class of polyadic equality algebras of dimension $α$. We show that for several classes of algebras that are reducts of $\PEA_ω$ whose signature contains all substitutions and finite cylindrifiers, if $\B$ is in such a class, and $\B$ is atomic, then for all $n<ω$, $\Nr_n\B$ is completely representable as a $\PEA_n$. Conversely, we show that for any $2<n<ω$, and any variety $\sf V$, between diagonal free cylindric algebras and quasipolyadic equality algebras of dimension $n$, the class of completely representable algebras in $\sf V$ is not elementary.

preprint2020arXiv

Space and time via Topological and Tense cylindric algebras

Let $α$ be an arbritary ordinal, and $2<n<ω$. In \cite{3} accepted for publication in Quaestiones Mathematicae, we studied using algebraic logic, interpolation, amalgamation using $α$ many variables for topological logic with $α$ many variables briefly $\sf TopL_α$. This is a sequel to \cite{3}; the second part on modal cylindric algebras, where we study algebraically other properties of $\sf TopL_α$. Modal cylindric algebras are cylindric algebras of infinite dimension expanded with unary modalities inheriting their semantics from a unimodal logic $\sf L$ such as $\sf K5$ or $\sf S4$. Using the methodology of algebraic logic, we study topological (when $\sf L=S4$), in symbols $\sf TCA_α$. We study completeness and omitting types $\sf OTT$s for $\sf TopL_ω$ and $\sf TenL_ω$, by proving several representability results for locally finite such algebras. Furthermore, we study the notion of atom-canonicity for both ${\sf TCA}_{n}$ and ${\sf TenL}_n$, a well known persistence property in modal logic, in connection to $\sf OTT$ for ${\sf TopL}_n$ and ${\sf TeLCA}_n$, respectively. We study representability, omitting types, interpolation and complexity isssues (such as undecidability) for topological cylindric algebras. In a sequel to this paper, we introduce temporal cyindric algebras and point out the way how to amalgamate algebras of space (topological algebars) and algebras of time (temporal algebras) forming topological-temporal cylindric algebras that lend themselves to encompassing spacetime gemetries, in a purely algebraic manner.

preprint2016arXiv

Atom-canonicity in algebraic logic in connection to omitting types in modal fragments of L_{ω, ω}

Fix 2<n<ω. Let L_n denote first order logic restricted to the first n variables. CA_n denotes the class of cylindric algebras of dimension n and for m>n, Nr_n\CA_m(\subseteq CA_n) denotes the class of n-neat reducts of CA_m's. The existence of certain finite relation algebras and finite CA_n's lacking relativized complete representations is shown to imply that the omitting types theorem (OTT) fails for L_n with respect to clique guarded semantics (which is an equivalent formalism of its packed fragments), and for the multi-dimensional modal logic S5^n. Several such relation and cylindric algebras are explicitly exhibited using rainbow constructions and Monk-like algebras. Certain CA_n constructed to show non-atom canonicity of the variety S\Nr_n\CA_{n+3} are used to show that Vaught's theorem (VT) for L_{ω, ω}, looked upon as a special case of OTT for L_{ω, ω}, fails almost everywhere (a notion to be defined below) when restricted to L_n. That VT fails everywhere for L_n, which is stronger than failing almost everywhere as the name suggests, is reduced to the existence, for each n<m<ω, of a finite relation algebra R_m having a so-called m-1 strong blur, but R_m has no m-dimensional relational basis. VT for other modal fragments and expansions of L_n, like its guarded fragments, n-products of uni-modal logics like K^n, and first order definable expansions, is approached. It is shown that any multi-modal canonical logic L, such that $K^n\subseteq L\subseteq S5^n$, L cannot be axiomatized by canonical equations. In particular, L is not Sahlqvist. Elementary generation and di-completeness for L_n and its clique guarded fragments are proved. Positive omitting types theorems are proved for L_n with respect to standard semantics.

preprint2015arXiv

A brief history of algebraic logic from neat embeddings to rainbow constructions

We take a long magical tour in algebraic logic, starting from classical results on neat embeddings due to Henkin, Monk and Tarski, all the way to recent results in algebraic logic using so--called rainbow constructions invented by Hirsch and Hodkinson. Highlighting the connections with graph theory, model theory, and finite combinatorics, this article aspires to present topics of broad interest in a way that is hopefully accessible to a large audience. The paper has a survey character but it contains new approaches to old ones. We aspire to make our survey fairly comprehensive, at least in so far as Tarskian algebraic logic, specifically, the theory of cylindric algebras, is concerned. Other topics, such as abstract algebraic logic, modal logic and the so--called (central) finitizability problem in algebraic logic will be dealt with; the last in some detail. Rainbow constructions are used to solve problems adressing classes of cylindric--like algebras consisting of algebras having a neat embedding property. The hitherto obtained results generalize seminal results of Hirsch and Hodkinson on non--atom canonicity, non--first order definabiity and non--finite axiomatizability, proved for classes of representable cylindric algebras of finite dimension$>2$. We show that such results remain valid for cylindric algebras possesing relativized {\it clique guarded} representations that are {\it only locally} well behaved. The paper is written in a way that makes it accessible to non--specialists curious about the state of the art in Tarskian algebraic logic. Reaching the boundaries of current research, the paper also aspires to be informative to the practitioner, and even more, stimulates her/him to carry on further research in main stream algebraic logic.

preprint2015arXiv

A solution to the finitizability problem for quantifier logics with equality

We consider countable so-called rich subsemigroups of (ωω,\circ); each such semigroup $T$ gives a variety CPEA_T that is axiomatizable by a finite schema of equations taken in a countable subsignature of that of ω-dimensional cylindric-polyadic algebras with equality where substitutions are restricted to maps in T. It is shown that for any such T, A\in CPEA_T iff A is representable as a concrete set algebra of ω-ary relations. The operations in the signature are set-theoretically interpreted like in polyadic equality set algebras, but such operations are relativized to a union of cartesian spaces that are not necessarily disjoint. This is a form of guarding semantics. We show that CPEA_T is canonical and atom-canonical. Imposing an extra condition on T, we prove that atomic algebras in CPEA_T are completely representable and that CPEA_T has the super amalgamation property. If T is rich and {\it finitely represented}, it is shown that CPEA_T is term definitionally equivalent to a finitely axiomatizable Sahlqvist variety. Such semigroups exist. This can be regarded as a solution to the central finitizability problem in algebraic logic for first order logic {\it with equality} if we do not insist on full fledged commutativity of quantifiers. The finite dimensional case is approached from the view point of guarded and clique guarded (relativized) semantics of fragments of first order logic using finitely many variables. Both positive and negative results are presented.

preprint2015arXiv

Finite relation algebras and omitting types in modal fragments of first order logic

Let 2<n\leq l<m< ω. Let L_n denote first order logic restricted to the first n variables. We show that the omitting types theorem fails dramatically for the n--variable fragments of first order logic with respect to clique guarded semantics, and for its packed n--variable fragments. Both are modal fragments of L_n. As a sample, we show that if there exists a finite relation algebra with a so--called strong l--blur, and no m--dimensional relational basis, then there exists a countable, atomic and complete L_n theory T and type Γ, such that Γis realizable in every so--called m--square model of T, but any witness isolating Γcannot use less than $l$ variables. An $m$--square model M of T gives a form of clique guarded semantics, where the parameter m, measures how locally well behaved M is. Every ordinary model is k--square for any n<k<ω, but the converse is not true. Any model M is ω--square, and the two notions are equivalent if M is countable. Such relation algebras are shown to exist for certain values of l and m like for n\leq l<ωand m=ω, and for l=n and m\geq n+3. The case l=n and m=ωgives that the omitting types theorem fails for L_n with respect to (usual) Tarskian semantics: There is an atomic countable L_n theory T for which the single non--principal type consisting of co--atoms cannot be omitted in any model M of T. For n<ω, positive results on omitting types are obained for L_n by imposing extra conditions on the theories and/or the types omitted. Positive and negative results on omitting types are obtained for infinitary variants and extensions of L_{ω, ω}.

preprint2015arXiv

Problems on neat embeddings solved by rainbow constructions and Monk algebras

This paper is a survey of recent results and methods in (Tarskian) algebraic logic. We focus on cylindric algebras. Fix 2<n<ω. Rainbow constructions are used to solve problems on classes consisting of algebras having a neat embedding property substantially generalizing seminal results of Hodkinson as well as Hirsch and Hodkinson on atom-canonicity and complete representations, respectively. For proving non-atom-canonicity of infinitely many varieties approximating the variety of representable algebras of dimension n, so-called blow up and blur constructions are used. Rainbow constructions are compared to constructions using Monk-like algebras and cases where both constructions work are given. When splitting methods fail. rainbow constructions are used to show that diagonal free varieties of representable diagonal free algebras of finite dimension n, do no admit universal axiomatizations containing only finitely many variables. Notions of representability, like complete, weak and strong are lifted from atom structures to atomic algebras and investigated in terms of neat embedding properties. The classical results of Monk and Maddux on non-finite axiomatizability of the classes of representable relation and cylindric algebras of finite dimension n are reproved using also a blow up and blur construction. Applications to n-variable fragments of first order logic are given. The main results of the paper are summarized in tabular form at the end of the paper.

preprint2015arXiv

Splitting methods in algebraic logic: Proving results on non-atom-canonicity, non-finite axiomatizability and non-first oder definability for cylindric and relation algebras

We deal with various splitting methods in algebraic logic. The word `splitting' refers to splitting some of the atoms in a given relation or cylindric algebra each into one or more subatoms obtaining a bigger algebra, where the number of subatoms obtained after splitting is adjusted for a certain combinatorial purpose. This number (of subatoms) can be an infinite cardinal. The idea originates with Leon Henkin. Splitting methods existing in a scattered form in the literature, possibly under different names, proved useful in obtaining (negative) results on non-atom canonicity, non-finite axiomatizability and non-first order definability for various classes of relation and cylindric algebras. In a unified framework, we give several known and new examples of each. Our framework covers Monk's splitting, Andréka's splitting, and, also, so-called blow up and blur constructions involving splitting (atoms) in finite Monk-like algebras and rainbow algebras.

preprint2014arXiv

Algebraic analysis of temporal and topological finite variable fragments, using cylindric modal algebras

We study what we call topological cylindric algebras and tense cylindric algebras defined for every ordinal $α$. The former are cylindric algebras of dimension $α$ expanded with $\sf S4$ modalities indexed by $α$. The semantics of representable topological algebras is induced by the interior operation relative to a topology defined on their bases. Tense cylindric algebras are cylindric algebras expanded by the modalities $F$(future) and $P$ (past) algebraising predicate temporal logic. We show for both tense and topological cylindric algebras of finite dimension $n>2$ that infinitely many varieties containing and including the variety of representable algebras of dimension $n$ are not atom canonical. We show that any class containing the class of completely representable algebras having a weak neat embedding property is not elementary. From these two results we draw the same conclusion on omitting types for finite variable fragments of predicate topologic and temporal logic. We show that the usual version of the omitting types theorem restricted to such fragments when the number of variables is $>2$ fails dramatically even if we considerably broaden the class of models permitted to omit a single non principal type in countable atomic theories, namely, the non-principal type consting of co atoms.

preprint2014arXiv

Algebraisable versions of predicate topological logic

Motivated by questions like: which spatial structures may be characterized by means of modal logic, what is the logic of space, how to encode in modal logic different geometric relations, topological logic provides a framework for studying the confluence of the topological semantics for $\sf S4$ modalities, based on topological spaces rather than Kripke frames. Following research initiated by Sgro, and further pursued algebraically by Georgescu, we prove an interpolation theorem and an omitting types theorem for various extensions of predicate topological logic and Chang's modal logic. Our proof is algebraic addressing expansions of cylindric algebras using interior operators and boxes, respectively. Then we proceed like is done in abstract algebraic logic by studing algebraisable extensions of both logics; obtaining a plethora of results on the amalgamation property for various subclasses of their algebraic counterparts, which are varieties. Notions like atom-canonicity and complete representations are approached for finite dimensional topological cylindric algebras. The logical consequences of our algebraic results are carefully worked out for infinitary extensions of Chang's predicate modal logic and finite versions thereof, by restricting to $n$ variables, $n$ finite, viewed as a propositional multi-dimensional modal logic, and $n$ products of bimodal whose frames are of the form $(U, U\times U, R)$ where $R$ is a pre-order, endowed with diagonal constants.

preprint2014arXiv

Amalgamation, interpolation and congruence extension properties in topological cylindric algebras

Topological cylindric algebras of dimension α, αany ordinal are cylindric algebras with dimension αexpanded with αS4 modalities. The S4 modalities in representable algebras are induced by a topology on the base of the representation of its cylindric reduct, that is not necessarily an Alexandrov topolgy. For α>2, the class of representable algebras is a variety that is not axiomatized by a finite schema, and in fact all complexity results on representations for cylindric algebras, proved by Andreka (concerning number of variables needed for axiomatizations) Hodkinson (on Sahlqvist axiomatizations and canonicity) and others, transfer to the topological addition, by implementing a very simple procedure of `discretely topologizing a cylindric algebra' Given a cylindric algebra of dimension α, one adds αmany interior identity operations, the latter algebra is representable as a topological cylindric algebra if and only if the former is; the representation induced by the discrete topology. In this paper we investigate amalgamation properties for various classes of topological cylindric algebras of all dimensions. We recover, in the topological context, all of the results proved by Andreka, Comer Madarasz, Nemeti, Pigozzi, Sain, Sayed Ahmed, Sagi, Shelah, Simon, and others for cylindric algebras and much more.

preprint2014arXiv

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

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\geq 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\geq 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 α\geq ω, for any finite k\geq 1, and for any r\in ω, there exists an atomic algebra A_r\in SNr_\alphaCA_{α+k}\sim SNr_nCA_{α+k+1}, such that Π_{r/U} A_r\in 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.

preprint2014arXiv

Dedekind completions, neat embeddings and omitting types

Let n be finite >2. We show that any class between S\Nr_n\CA_{n+3} and RCA_n is not atom canonical, and any class containing the class of completely representable algebras and contained in S_c\Nr_n\CA_{n+3} is not elementary. We show that there is no finite variable universal axiomatization of many diagonal free reducts of representable cylindric algebras of dimension n, like the varieties of representable diagonal-free cylindric algebras and Halmos' polyadic algebras (without equality). We apply our hitherto obtained algebraic results to show that the omitting types theorem fails for finite variable fragments of first order logic with and without equality, having n variables, even if we count in severely relativized models as candidates for omitting single non-principle types. Finally, we show that for many cylindric-like algebras, like diagonal free cylindric algebras and Halmos' polyadic algebras with and without equality the class of strongly representable atom structures of finite dimension >2 is not elementary.

preprint2013arXiv

A polyadic algebra of infinite dimension is completely representable if and only if it is atomic and completely additive

We prove the result in the title. We infer, that unlike cylindric algebras, there is a first order axiomatization of the class of completely representable polyadic algebras of infinite dimension, though the one we obtain is infinite; in fact uncountable, but shares a single schema, stipulating that the (uncountably many)substitution operators are completely additive. Similar results are obtained for non commutative reducts of polyadic equality algebras of infinite dimensions, where we can drop complete additivity. However, it remains unknown to us whether there are atomic polyadic algebras of infinite dimension that are not completely additive; but we strongly conjecture that there are.

preprint2013arXiv

Atom-canonicity, relativized representations and omitting types for clique guarded semantics and guarded logics

We study atom canonicity for several varieties of cylindric like algebras that contain properly the variety of representable algebras. The algebras in such varieties have relativized representations, and we thereby obtain many omitting types theorems, both negative and positive for finite variable fragments and / or modifications of first order logic. Negative results are obtained when we keep usual syntax and relativize models (so that they witness commutativity of quantifiers only locally) and positive ones are obtained when we weaken 'commutativity of quantifiers' in the syntax and relativize semantics differently. Such algebras have weak neat embedding properties, too, in the sense that they embed into neat reducts of algebras in higher dimensions possibly finite. In the second part of the paper various notions of representability originally formulated for atom structure are lifted in an obvious way to the algebra level, like weak and strong representability. Such classes of algebras (that are atomic) are characterized completely via neat embeddings. Finally, several model theoretic questions on such classes consisting of algebras having weak neat embedding properties and relativized representations, like decidability of their equational or universal theory, their finite axiomatizability if first order definable, are posed and answered.

preprint2013arXiv

Blow up and Blur constructions in Algebraic Logic

The idea in the title is to blow up a finite structure, replacing each 'colour or atom' by infinitely many, using blurs to represent the resulting term algebra, but the blurs are not enough to blur the structure of the finite structure in the complex algebra. Then, the latter cannot be representable due to a {finite- infinite} contradiction. This structure can be a finite clique in a graph or a finite relation algebra or a finite cylindric algebra. This theme gives examples of weakly representable atom structures that are not strongly representable. Many constructions existing in the literature are placed in a rigorous way in such a framework, properly defined. This is the essence too of construction of Monk like-algebras, one constructs graphs with finite colouring (finitely many blurs), converging to one with infinitely many, so that the original algebra is also blurred at the complex algebra level, and the term algebra is completey representable, yielding a representation of its completion the complex algebra. A reverse of this process exists in the literature, it builds algebras with infinite blurs converging to one with finite blurs. This idea due to Hirsch and Hodkinson, uses probabilistic methods of Erdos to construct a sequence of graphs with infinite chromatic number one that is 2 colourable. This construction, which works for both relation and cylindric algebras, further shows that the class of strongly representable atom structures is not elementary.

preprint2013arXiv

Blowing up and blurring finite Monk and rainbow algebras

We use Monk like algebras to give a new proof that the classes of strongly representable relation algebras and finite dimensional cylindric algebras of dimension >2 are not elementary. Our construction is based on relation algebras have cylindric basis, so that we obtain the result for both in one go, since they are both based on the same graph. The proof also uses Erdos' graphs. We also show using a rainbow construction that the class SNr_n\CA_{n+k} is not atom canonical, for any k\geq 4.

preprint2013arXiv

Completeness and interpolation for intuitionistic infinitary predicate logic, in connection to finitizing the class of representable Heyting polyadic algebras

We study different representation theorems for various reducts of Heyting polyadic algebras. Superamalgamation is proved for several (natural reducts) and our results are compared to the finitizability problem in classical algebraic logic dealing with cylindric and polyadic (Boolean algebras). We also prove several new neat embedding theorems, and obtain that the class of representable algebras based on (a generalized) Kripke semantics coincide with the class of algebras having the neat embedding property, that is those algebras that are subneat reducts of algebras having $ω$ extra dimensions.

preprint2013arXiv

Cylindric and polyadic algebras, new perspectives

We generalize the notion of Monk's schema in such a way to integrate finite dimensions. This allows us to lift a plathora of deep results proved for finite dimensions to the infinite dimensional case, like the solution to problem 2.12 in Henkin Monk and Tarski part one, solved by Hirsch and Hodkinson. This lifting argument was already used in a joint paper with Robin Hirsch, but in a narrower context, accepted for publication in the Journal of Symbolic Logic. We also give a general new definition of a schema for infinite dimensions covering Monk's schema and Halmos' schema. Several algebraic properties (like amalgamation) are proved for instances of systems of varieties definable by such a schema like MV algebras, reducts of Heyting polyadic algebras and Ferenczi's cylindric polyadic algebras. Finally, two serious errors in two publications in prestigeous journals are pointed out. One is fixed, the alledged result in the second is weakened.

preprint2013arXiv

Logics to which the class of neat reducts is sensitive to

Let L be a quantifier predicate logic. Let K be a class of algebras. We say that K is sensitive to L, if there is an algebra in K, that is L interpretable into an another algebra, and this latter algebra is elementary equivalent to an algebra not in K. (In particular, if L is L_{ω,ω}, this means that K is not elementary). We show that the class of neat reducts of every dimension is sensitive to quantifier free predicate logics with infinitary conjunctions; for finite dimensions, we do not need infinite conjunctions.

preprint2013arXiv

On completions, neat embeddings and omittings types, yet again

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\in \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\in ω, there exists \A\in {\sf RPEA}_n\cap \Nr_n\PEA_{n+k} such that Rd_{\sf Sc}\Cm\At\A\notin S\Nr_n\Sc_{n+k+1}. This implies that for any finite n\geq 3, for any k\geq 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.

preprint2013arXiv

On neat atom structures for cylindric like algebras

(1) Let 1\leq k\leq ω. Call an atom structure αweakly k neat representable, the term algebra is in \RCA_n\cap \Nr_n\CA_{n+k}, but the complex algebra is not representable. Call an atom structure neat if there is an atomic algebra \A, such that \At\A=α, \A\in \Nr_n\CA_ω and for every algebra $\B$ based on this atom structure there exists k\in ω$, k\geq 1, such that \B\in \Nr_n\CA_{n+k}. (2) Let k\leq ω. Call an atom structure αk complete, if there exists \A such that \At\A=αand \A\in S_c\Nr_n\CA_{n+k}. (3) Let k\leq ω. Call an atom structure $α$ k neat if there exists \A such that \At\A=α, and \A\in \Nr_n\CA_{n+k}. (4) Let K\subseteq \CA_n, and Łbe an extension of first order logic. We say that \K is well behaved w.r.t to Ł, if for any \A\in \K, A atomic, and for any any atom structure βsuch that \At\A is elementary equivalent to β, for any \B, \At\B=β, then B\in K. We investigate the existence of such structures, and the interconnections. We also present several K's and L's as in the second definition. All our results extend to Pinter's algebras and polyadic algebras with and without equality.

preprint2013arXiv

On the multi dimensional modal logic of substitutions

We prove completeness, interpolation, decidability and an omitting types theorem for certain multi dimensional modal logics where the states are not abstract entities but have an inner structure. The states will be sequences. Our approach is algebraic addressing (varieties generated by) complex algebras of Kripke semantics for such logic. Those algebras, whose elements are sets of states are common reducts of cylindric and polyadic algebras

preprint2013arXiv

Polyadic-like algebras without the amalgamation property

Usually when we have polyadic-like algebras, meaning that we have infinitary substitutions (that is substitutions moving infinitely many points) in the similarity type, then we get the superamalgamation property especially if this class of algebras happen to be a variety. This for example happens for (full) polyadic algebras, full Heyting algebras and reducts of those using only finitely many infinitary substitutions, like Sains Boolean and Heyting algebras. (The last is studied by Sayed Ahmed) . In cylindric-like algebras (like quasi-polyadic algebras) when we do not have infinitary substitutions, we do not get even the amalgamation property . In this paper, we give an example of a polyadic like variety (we have infinitary substitutions, in fact infinitely many of them) for which the amalgamation property fails.

preprint2013arXiv

Results on Polyadic Algebras

While every polyadic algebra ($\PA$) of dimension 2 is representable, we show that not every atomic polyadic algebra of dimension two is completely representable; though the class is elementary. Using higly involved constructions of Hirsch and Hodkinson we show that it is not elementary for higher dimensions a result that, to the best of our knowledge, though easily destilled from the literature, was never published. We give a uniform flexible way of constructing weak atom structures that are not strong, and we discuss the possibility of extending such result to infinite dimensions. Finally we show that for any finite $n>1$, there are two $n$ dimensional polyadic atom structures $\At_1$ and $\At_2$ that are $L_{\infty,ω}$ equivalent, and there exist atomic $\A,\B\in \PA_n$, such that $\At\A=\At_1$ and $\At\B= \At_2$, $\A\in \Nr_n\PA_ω$ and $\B\notin \Nr_n\PA_{n+1}$. This can also be done for infinite dimensions (but we omit the proof)

preprint2013arXiv

Strongly representable algebras

We give a simpler proof of a result of Hodkinson in the context of a blow and blur up construction argueing that the idea at heart is similar to that adopted by Andréka et all \cite{sayed}. The idea is to blow up a finite structure, replacing each 'colour or atom' by infinitely many, using blurs to represent the resulting term algebra, but the blurs are not enough to blur the structure of the finite structure in the complex algebra. A reverse of this process exists in the literature, it builds algebras with infinite blurs converging to one with finite blurs. This idea due to Hirsch and Hodkinson, uses probabilistic methods of Erdos to construct a sequence of graphs with infinite chromatic number one that is 2 colourable. This construction, which works for both relation and cylindric algebras, further shows that the class of strongly representable atom structures is not elementary. We will generalize such a result for any class of algebras between diagonal free algebras and polyadic algebras with and without equality, then we further discuss possibilities for the infinite dimensional case. Finally, we suggest a very plausible equivalence, and that is: If $n>2$, is finite, and $\A\in \CA_n$ is countable and atomic, then $\Cm\At\A$ is representable if and only if $\A\in \Nr_n\CA_ω$. We could prove one side.

preprint2013arXiv

Strongly representable atom structures

Using constructions of Hirsch and Hodkinson, we show that the class of strongly atom structures for various cylindric-like algebras is not elementary. This applies to diagonal free reducts and polyadic algebras with and without equality. This follows from the simple observation, that the cylindric atom structures of dimension n, constructed by Hirsch and Hodkinson, are built from algebras that can be easily expanded to polyadic equality algebras, and that such expansions are generated by elements whose dimension sets <n.

preprint2013arXiv

Strongly representable atom structures and neat embeddings

In this paper we give an alternative construction using Monk like algebras that are binary generated to show that the class of strongly representable atom structures is not elementary. The atom structures of such algebras are cylindric basis of relation algebras, both algebras are based on one graph such that both the relation and cylindric algebras are representable if and only if the chromatic number of the graph is infinite. We also relate the syntactic notion of algebras having a (complete) neat embedding property to the semantical notion of having various forms of (complete) relativized representations. Finally, we show that for n>5, the problemn as to whether a finite algebra is in the class SNr_3CA_6 is undecidable. In contrast, we show that for a finite algebra of arbitary finite dimensions that embed into extra dimensions of a another finite algebra, then this algebra have a finite relativized representation. Finally we devise what we call neat games, for such a game if \pe\ has a \ws \ on an atomic algebra \A in certain atomic game and \pa has a \ws in another atomic game, then such algebras are elementary equivalent to neat reducts, but do not have relativized (local) complete represenations. From such results, we infer that the omitting types theorem for finite variable fragments fails even if we consider clique guarded semantics. The size of cliques are determined by the number of pebbles used by \pa\.

preprint2013arXiv

The elementary closure of the class Nr_nCA_m for m\geq n+1 is not finitely axiomatizable, futhermore for any finite k\geq 1, there is A\in Nr_ωCA_{\omeg+k}that is not SNr_ωCA_{ω+k+1}

We show that for 1<n<m, the class Nr_nCA_m known to be non-elementary is pseudo elementary. When n and m are finite we use a two sorted theory, when n is finite and m infinite we use a three sorted one, and finally when both are infinite we use a four sorted defining theory. Our non finite axiomatizability result, follows from the fact that for 2<n<m, and any r\in ωthere exists a finite (Monk like) algebra C(m,n,r), such that C(m,n,r)\in Nr_nCA_m C(m,n,r)\notin SNr_nCA_{m+1}, and any non trivial ultraproduct on r of such algebras in in ElNr_nCA_m. Finally we use such algebras, to show that for infinite dimension there is an algebra A\in Nr_α\CA_{\apha+k} that is not in SNr_αCA_{α+k+1} (αan infinite ordinal).

preprint2013arXiv

There is no finite variable axiomatization for various diagonal free algebras

We show, using a ranbow construction for cylindric algebras, that for any class K between diagonal free cylindric algebras and polyadic equality algebras of finite dimension > 2, there is no finite variable universal axiomatization for the class of representable algebras. This solves an old open problem in algebraic logic, formulated by Sain and Thompson back in 1990.

preprint2013arXiv

Various interplays between relation and cylindric algebras

Using model theoretic techniques that proved that the class of $n$ neat reducts of $m$ dimensional cylindric algebras, $\Nr_n\CA_m$, is not elementary, we prove the same result for $\Ra\CA_k$, $k\geq 5$, and we show that $\Ra\CA_k\subset S_c\Ra\CA_k$ for all $k\geq 5$. Conversely, using the rainbow construction for cylindric algebra, we show that several classes of algebras, related to the class $\Nr_n\CA_m$, $n$ finite and $m$ arbitrary, are not elementary. Our results apply to many cylindric-like algebras, including Pinter's substitution algebras and Halmos' polyadic algebras with and without equality. The techniques used are essentially those used by Hirsch and Hodkinson, and later by Hirsch in \cite{hh} and \cite{r}. In fact, the main result in \cite{hh} follows from our more general construction. Finally we blow up a little the {\it blow up and blur construction} of Andréka nd Németi, showing that various constructions of weakly representable atom structures that are not strongly representable, can be formalized in our blown up, blow up and blur construction, both for relation and cylindric algebras. Two open problems are discussed, in some detail, proposing ideas. One is whether class of subneat reducts are closed under completions, the other is whether there exists a weakly representable $ω$ dimensional atom structure, that is not strongly representable. For the latter we propose a lifting argument, due to Monk, applied to what we call anti-Monk algebras (the algebras, constructed by Hirsch and Hodkinson, are atomic, and their atom structure is stongly representable.)

preprint2013arXiv

What is the spirit of the cylindric paradigm, as opposed to that of the polyadic one?

We give a categorial definition separating cylindric-like algebras from polyadic-like ones. Viewing the neat reduct operator as a functor, we show that it does not have a right adjoint in the former case, but it is strongly invertible in the second case. Several new results on amalgamation, and non finite axiomatizability are presented for both paradigms. A hitherto categorial equivalence is also given between relation algebras with quasi-projections and Nemeti's directed cylindric algebras for any dimension.