59 results on '"Ahmed, Tarek Sayed"'
Search Results
2. Geometrical representation theorems for cylindric-type algebras
- Author
-
Khaled, Mohamed and Ahmed, Tarek Sayed
- Subjects
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Computer Science::Logic in Computer Science ,FOS: Mathematics ,Cylindric algebras, representability, games and networks ,Mathematics - Logic ,Logic (math.LO) ,Primary 03G15, Secondary 03G25, 03B45 - Abstract
In this paper, we give new proofs of the celebrated Andréka-Resek-Thompson representability results of certain axiomatized cylindric-like algebras. Such representability results provide completeness theorems for variants of first order logic, that can also be viewed as multi-modal logics. The proofs herein are combinatorial and we also use some techniques from game theory.Mathematics Subject Classification (2010): Primary 03G15; Secondary 03G25, 03B45.Keywords: Cylindric algebras, representability, games and networks
- Published
- 2020
3. Space and time via Topological and Tense cylindric algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
Let $\alpha$ be an arbritary ordinal, and $2, Comment: arXiv admin note: text overlap with arXiv:1912.12114, arXiv:1408.3282, arXiv:1608.03513
- Published
- 2020
- Full Text
- View/download PDF
4. Completely representable neat reducts
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
For an ordinal $\alpha$, $\sf PEA_{\alpha}$ denotes the class of polyadic equality algebras of dimension $\alpha$. We show that for several classes of algebras that are reducts of $\PEA_{\omega}$ whose signature contains all substitutions and finite cylindrifiers, if $\B$ is in such a class, and $\B$ is atomic, then for all $n, Comment: arXiv admin note: substantial text overlap with arXiv:1504.05947, arXiv:1912.12114, arXiv:1912.12182, arXiv:1408.3282
- Published
- 2020
- Full Text
- View/download PDF
5. An infinite stratum of representability; some cylindric algebras are more representable than others
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
Let $2, Comment: arXiv admin note: substantial text overlap with arXiv:1912.12114, arXiv:1912.12182, arXiv:1408.3282, arXiv:1504.05947, arXiv:1608.03513
- Published
- 2020
- Full Text
- View/download PDF
6. A universal approach to Omitting types for various multimodal and quantifier logics
- Author
-
Ahmed, Tarek Sayed
- Subjects
Computer Science::Logic in Computer Science ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We intend to investigate the metalogical property of 'omitting types' for a wide variety of quantifier logics (that can also be seen as multimodal logics upon identifying existential quantifiers with modalities syntactically and semantically) exhibiting the essence of its abstract algebraic facet, namely, atom-canonicity, the last reflecting a well known persistence propery in modal logic. In the spirit of 'universal logic ', with this algebraic abstraction at hand, the omitting types theorem OTT will be studied for various reducts extensions and variants (possibly allowing formulas of infinite length) of first order logic. Our investigatons are algebraic, addressing (non) atom canoicity of varieties of algebra of relations. In the course of our investigations, both negative and positive results will be presented. For example, we show that for any countable theory $L_n$ theory $T$ that has quantifier elimination $< 2^{\omega}$ many non-principal complete types can be omitted. Furthermore, the maximality (completeness) condition, if eliminated, leads to an independent statement from $\sf ZFC$ implied by Martin's axiom. $\sf OTT$s are approached for other algebraizable (in the classical Blok-Pigozzi sense) reformulations or/ and versions of $L_{\omega \omega}$; they are shown to hold for some and fail for others. We use basic graph theory, finite combinatorics, combinatorial game theory orchestrated by algebraic logic., Comment: arXiv admin note: text overlap with arXiv:1608.03513, arXiv:1504.05947, arXiv:1408.3282
- Published
- 2019
7. Hilbert's tenth problem, G\'odel's incompleteness, Halting problem, a unifying perspective
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics - Logic - Abstract
We formulate a property $P$ on a class of relations on the natural numbers, and formulate a general theorem on $P$, from which we get as corollaries the insolvability of Hilbert's tenth problem, G\"odel's incompleteness theorem, and Turing's halting problem. By slightly strengthening the property $P$, we get Tarski's definability theorem, namely that truth is not first order definable. The property $P$ together with a "Cantor's diagonalization" process emphasizes that all the above theorems are a variation on a theme, that of self reference and diagonalization combined. We relate our results to self referential paradoxes, including a formalisation of the Liar paradox, and fixed point theorems. We also discuss the property $P$ for arbitrary rings. We give a survey on Hilbert's tenth problem for quadratic rings and for the rationals pointing the way to ongoing research in main stream mathematics involving recursion theory, definability in model theory, algebraic geometry and number theory.
- Published
- 2018
8. Hilbert's tenth problem, G��del's incompleteness, Halting problem, a unifying perspective
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Logic (math.LO) - Abstract
We formulate a property $P$ on a class of relations on the natural numbers, and formulate a general theorem on $P$, from which we get as corollaries the insolvability of Hilbert's tenth problem, G��del's incompleteness theorem, and Turing's halting problem. By slightly strengthening the property $P$, we get Tarski's definability theorem, namely that truth is not first order definable. The property $P$ together with a "Cantor's diagonalization" process emphasizes that all the above theorems are a variation on a theme, that of self reference and diagonalization combined. We relate our results to self referential paradoxes, including a formalisation of the Liar paradox, and fixed point theorems. We also discuss the property $P$ for arbitrary rings. We give a survey on Hilbert's tenth problem for quadratic rings and for the rationals pointing the way to ongoing research in main stream mathematics involving recursion theory, definability in model theory, algebraic geometry and number theory.
- Published
- 2018
- Full Text
- View/download PDF
9. Atom-canonicity in algebraic logic in connection to omitting types in modal fragments of L_{\omega, \omega}
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,Mathematics - Logic - Abstract
Fix 2n, 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_{\omega, \omega}, looked upon as a special case of OTT for L_{\omega, \omega}, 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, Comment: arXiv admin note: substantial text overlap with arXiv:1504.05947
- Published
- 2016
10. Atom-canonicity in algebraic logic in connection to omitting types in modal fragments of L_{��, ��}
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Logic (math.LO) - Abstract
Fix 2n, 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, arXiv admin note: substantial text overlap with arXiv:1504.05947
- Published
- 2016
- Full Text
- View/download PDF
11. Finite relation algebras and omitting types in modal fragments of first order logic
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
Let 2, Comment: arXiv admin note: text overlap with arXiv:1408.3282, arXiv:1502.07701
- Published
- 2015
12. A solution to the finitizability problem for quantifier logics with equality
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We consider countable so-called rich subsemigroups of (\omega\omega,\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 \omega-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 \omega-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.
- Published
- 2015
13. A brief history of algebraic logic from neat embeddings to rainbow constructions
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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.
- Published
- 2015
- Full Text
- View/download PDF
14. Splitting methods in algebraic logic: Proving results on non-atom-canonicity, non-finite axiomatizability and non-first oder definability for cylindric and relation algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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\'eka's splitting, and, also, so-called blow up and blur constructions involving splitting (atoms) in finite Monk-like algebras and rainbow algebras., Comment: arXiv admin note: substantial text overlap with arXiv:1502.07701, arXiv:1408.3282
- Published
- 2015
- Full Text
- View/download PDF
15. Problems on neat embeddings solved by rainbow constructions and Monk algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Mathematics::General Mathematics ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
This paper is a survey of recent results and methods in (Tarskian) algebraic logic. We focus on cylindric algebras. Fix 2, Comment: arXiv admin note: substantial text overlap with arXiv:1408.3282
- Published
- 2015
- Full Text
- View/download PDF
16. Amalgamation, interpolation and congruence extension properties in topological cylindric algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
Topological cylindric algebras of dimension \alpha, \alpha any ordinal are cylindric algebras with dimension \alpha expanded with \alpha 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 \alpha>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 \alpha, one adds \alpha 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.
- Published
- 2014
17. Dedekind completions, neat embeddings and omitting types
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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., arXiv admin note: substantial text overlap with arXiv:1308.6165, arXiv:1307.1016, arXiv:1307.4298, arXiv:1309.0681
- Published
- 2014
18. Algebraisable versions of predicate topological logic
- Author
-
Ahmed, Tarek Sayed
- Subjects
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Computer Science::Logic in Computer Science ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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.
- Published
- 2014
- Full Text
- View/download PDF
19. Algebraic analysis of temporal and topological finite variable fragments, using cylindric modal algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We study what we call topological cylindric algebras and tense cylindric algebras defined for every ordinal $\alpha$. The former are cylindric algebras of dimension $\alpha$ expanded with $\sf S4$ modalities indexed by $\alpha$. 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., Comment: arXiv admin note: substantial text overlap with arXiv:1308.6165, arXiv:1307.1016, arXiv:1309.0681, arXiv:1307.4298, arXiv:1401.1103, arXiv:1401.1156
- Published
- 2014
- Full Text
- View/download PDF
20. Atom-canonicity and complete representations for cylindric-like algebras, and omitting types for the clque guarded fragment of first order logic
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - 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\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 \alpha\geq \omega, for any finite k\geq 1, and for any r\in \omega, there exists an atomic algebra A_r\in SNr_\alphaCA_{\alpha+k}\sim SNr_nCA_{\alpha+k+1}, such that \Pi_{r/U} A_r\in RCA_{\alpha} where U is any non--principal ultrafilter on \omega. 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., Comment: arXiv admin note: text overlap with arXiv:1308.6165, arXiv:1307.1016
- Published
- 2014
- Full Text
- View/download PDF
21. Strongly representable atom structures and neat embeddings
- Author
-
Ahmed, Tarek Sayed and Khaled, Mohammed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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\., arXiv admin note: text overlap with arXiv:1302.1368, arXiv:1304.1149, arXiv:1305.4570, arXiv:1307.1016
- Published
- 2013
22. For finite n\geq 3, and k\geq 4, the variety SNr_n\CA_{n+k} is not atom canonical
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We show that there exists an atomic representable polyadic equality algebra of finite dimension n\geq 3, such that the cylindric reduct of its completion is not in SNr_n\CA_{n+4}, hence the result in the title. This solves an open problem in algebraic logic, though the values for k=n+1, n+2, n+3, is still, to the best of our knowlege unknown., arXiv admin note: text overlap with arXiv:1305.4570, arXiv:1302.1368, arXiv:1305.5269, arXiv:1304.0785
- Published
- 2013
23. A polyadic algebra of infinite dimension is completely representable if and only if it is atomic and completely additive
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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., Submitted to the Journal of Symbolic Logic. arXiv admin note: substantial text overlap with arXiv:1301.5850
- Published
- 2013
24. Blowing up and blurring finite Monk and rainbow algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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.
- Published
- 2013
25. Various interplays between relation and cylindric algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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\'eka nd N\'emeti, 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 $\omega$ 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.), Comment: arXiv admin note: substantial text overlap with arXiv:1304.5152, arXiv:1304.0785, arXiv:1304.1149, arXiv:1305.4570, arXiv:1305.5151
- Published
- 2013
26. Strongly representable algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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\'eka 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_{\omega}$. We could prove one side., Comment: arXiv admin note: substantial text overlap with arXiv:1304.1149
- Published
- 2013
27. On atomicity of free algebras in Boolean algebras with operators, and a new result on Pinter's free algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We give some general theorems on free algebras of varieties of Boolean algebras with operators; a hitherto new result is obtained for Pinter's substitution algebras. For n\geq 3, and m>1, there is a generating set of the free algebra freely generated by m elements, which is not a free set of generators., arXiv admin note: substantial text overlap with arXiv:1304.1148, arXiv:1302.3043
- Published
- 2013
28. On completions of algebras in SNr_nCA_{n+k}, n\geq 3, k\geq 1
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We give a sufficient condition that implies that SNr_nCA_{n+k}, n\geq 3, k\geq 3 (both finite)is not closed under completions. We compare this condition to existing results in literature.
- Published
- 2013
29. Logics to which the class of neat reducts is sensitive to
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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_{\omega,\omega}, 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.
- Published
- 2013
30. Results on Polyadic Algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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,\omega}$ 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_{\omega}$ and $\B\notin \Nr_n\PA_{n+1}$. This can also be done for infinite dimensions (but we omit the proof), Comment: arXiv admin note: text overlap with arXiv:1304.1149
- Published
- 2013
31. On some open problems in Algebraic logic
- Author
-
Ahmed, Tarek Sayed
- Subjects
Computer Science::Logic in Computer Science ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
Several open problems in algebraic logic are solved., Comment: arXiv admin note: text overlap with arXiv:1302.1368, arXiv:1303.7386, arXiv:1301.5850, arXiv:1304.0619, arXiv:1304.0785, arXiv:1304.0883
- Published
- 2013
32. An instance of Vaught's conjecture using algebraic logic
- Author
-
Assem, Mohammed and Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics::General Topology ,Mathematics - Logic ,Logic (math.LO) - Abstract
Let \phi be a first order formula and M be a countable model. \phi^M denotes the set of all assignments that satisfy \phi in M. Let M, N be countable models. A formula \phi distinguishes these models if |\phi^M|\neq |\phi^N|. We show that the number of distinguishable countable models for a complete countable first order theory, satisfies the Glimm Effross dichotomy, hence also Vaught's conjecture. The proof in the presence of equality is fairly easy, though we need infinite conjunctions to implement it and somewhat heavy theorems from descriptive set theory. However, the case without equality seems to be much more difficult (because we cannot count without equality) and in this case algebraic logic comes to our rescue via the representation theory of locally finite quasi polyadic algebras. We show that the equivalence relation induced by such (indistinguishable) models is a Borel subset of the product of the Stone Polish space (consisting of ultarfilters corresponding to models) with itself. We also formuate and prove a Vaught's theorem for certian infinitary extensions of first order logic via the representation theory of dimension complemented algebras. In all case we also count the number of non isomorphic models omitting < covK many non isolated types (the latter is the least cardinal such that the Baire Category theorem fails and also the largest cardinal such tha Martin's axiom restrcited to countable Boolean algebra hold.) In such cases, for locally finite algebras and dimension complemented ones we obtain the same number of non-ismorphic distinguishable models., Comment: arXiv admin note: text overlap with arXiv:1304.0619
- Published
- 2013
33. Free algebras, amalgamation, and a theorem of Vaught for many valued logics
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We investigate atomicity of free algebras and various forms of amalgamation for BL and MV algebras, and also Heyting algebras, though the latter algebras may not be linearly ordered, so strictly speaking their corresponding intuitionistic logic does not belong to many valued logic. Generalizing results of Comer proved in the classical first order case; working out a sheaf duality on the Zarski topology defined on the prime spectrum of such algebras, we infer several definability theorems, and obtain a representation theorem for theories as continuous sections of Sheaves. We also prove an omitting types theorem for fuzzy logic, and formulate and prove several of its consequences (in classical model theory) adapted to our case; that has to do with existence and uniqueness of prime and atomic models., arXiv admin note: substantial text overlap with arXiv:1304.0707, arXiv:1304.0612, arXiv:1304.0760, arXiv:1302.3043
- Published
- 2013
34. Characterizing amalgmation bases for relation, cylindric and polyadic algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We characterize completey (give a necessary and suffcient condition using special neat embeddings)for a relation algebra to belong to the amalgamation, strong amalgamation, and superamalgamation base of the class of representable algebras. We do the same for cylindric and polyadic algebras for all dimensions >1, infinite included. Finally, we show that we can expand our algebras by finitely many natural operations, that force the newly expanded algebras to have various forms of amalgamation properties, like quasi-projections and directed cylindrifiers., arXiv admin note: text overlap with arXiv:1303.7386
- Published
- 2013
35. Interpolation in many valued predicate logics using algebraic logic
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
Using polyadic MV algebras, we show that many predicate many valued logics have the interpolation property., 49 pages. arXiv admin note: text overlap with arXiv:1304.0707
- Published
- 2013
36. The superamalgamation property for reducts of Heyting polyadic algebras with and without equality
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We show that several reducts of Heyting polyadic algebras of infinite dimension, with and without equality enjoy various amalgamation properties. In the equality free case we obtain superamalgamation, but when we have equality we obtain a weaker interpolation property, for the corresponding infinitary intuitionistic logic with equality., 58 pages
- Published
- 2013
37. On complete representability of Pinter's algebras and related structures
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Mathematics - K-Theory and Homology ,FOS: Mathematics ,K-Theory and Homology (math.KT) ,Mathematics - Logic ,Logic (math.LO) - Abstract
We answer an implicit question of Ian Hodkinson's. We show that atomic Pinters algebras may not be completely representable, however the class of completely representable Pinters algebras is elementary and finitely axiomatizable. We obtain analagous results for infinite dimensions (replacing finite axiomatizability by finite schema axiomatizability). We show that the class of subdirect products of set algebras is a canonical variety that is locally finite only for finite dimensions, and has the superamalgamation property; the latter for all dimensions. However, the algebras we deal with are expansions of Pinter algebras with substitutions corresponding to tranpositions. It is true that this makes the a lot of the problems addressed harder, but this is an acet, not a liability. Futhermore, the results for Pinter's algebras readily follow by just discarding the substitution operations corresponding to transpostions. Finally, we show that the multi-dimensional modal logic corresponding to finite dimensional algebras have an $NP$-complete satisfiability problem., arXiv admin note: substantial text overlap with arXiv:1302.3043
- Published
- 2013
38. Cylindric polyadic algebras have the superamalgamation
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,FOS: Mathematics ,Condensed Matter::Strongly Correlated Electrons ,Mathematics - Logic ,Logic (math.LO) - Abstract
We show that cylindric polyadic algebras introduced by Ferenczi has the superamalgmation property. We give two proofs. One is a Henkin construction, and the other is inspired by duality theory in modal logic between finite zig zag products of Kripke frames and their complex algebras., arXiv admin note: substantial text overlap with arXiv:1303.7386
- Published
- 2013
39. What is the spirit of the cylindric paradigm, as opposed to that of the polyadic one?
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Mathematics::Category Theory ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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., 88 pages. arXiv admin note: text overlap with arXiv:1302.0365
- Published
- 2013
40. On the multi dimensional modal logic of substitutions
- Author
-
Ahmed, Tarek Sayed and Assem, Mohammad
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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
- Published
- 2013
41. On the finitizability problem in algebraic logic; recent results
- Author
-
Ahmed, Tarek Sayed
- Subjects
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
This is a survey article in algebraic logic, where we take a magical tour from old concepts due to Henkin, Monk and Tarski like neat embeddings, to modern views and perspectives, culminating in the use of Erdos graphs in settling important questions in algebraic logic.
- Published
- 2013
42. The class of infinite dimensional quasipolaydic equality algebras is not finitely axiomatizable over its diagonal free reducts
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We show that the class of infinite dimensional quasipolaydic equality algebras is not finitely axiomatizable over its diagonal free reducts
- Published
- 2013
43. Atomic polyadic algebras of infinite dimension are completely representable
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Physics::Atomic Physics ,Mathematics - Logic ,Physics::Chemical Physics ,Logic (math.LO) ,Computer Science::Numerical Analysis ,Computer Science::Formal Languages and Automata Theory - Abstract
We show that atomic polyadic algebras of infinite dimensions are completely representable
- Published
- 2013
44. Amalgmation in Boolean algebras with operators
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Computer Science::Computational Complexity ,Logic (math.LO) - Abstract
We study various forms of amalgamation for Boolean algebras with operations. We will also have the occasion to weaken the Boolean structure dealing with MV and BL algebras with operators., Comment: arXiv admin note: substantial text overlap with arXiv:1302.3043, arXiv:1303.7386, arXiv:1304.0612, arXiv:1304.1148
- Published
- 2013
- Full Text
- View/download PDF
45. Quasi-projective relation algebras and directed cylindric algebras are categorially equivalent
- Author
-
Ahmed, Tarek Sayed
- Subjects
FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
We show that quasi-projective relation algebras and directed cylindric algebras are equivalent categorialy. We work out a Godels second incompleteness theorem for finite varibale fragments of first order logic. We show that distinct set theories (like one with CH, and another with its negation) give rise to equationally distinct simple directed cylindric algebras. This correspondance was worked out for quasi projective relation algebras (with a distinguished element corresponding to membership relation). The idea of the proof is that the Sagi representation of directed cylindric algebras preserve well-foundnes. Finally, using that the functor defined preserves order, we show that the class of directed cylindric algebras have the superamalgmation property., Comment: arXiv admin note: substantial text overlap with arXiv:1303.7386, arXiv:1304.0712; and overlap with arXiv:math/0508572 by other author without attribution
- Published
- 2013
- Full Text
- View/download PDF
46. Strongly representable atom structures
- Author
-
Ahmed, Tarek Sayed and Khalifa, Mohamed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
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
- Published
- 2013
- Full Text
- View/download PDF
47. Cylindric and polyadic algebras, new perspectives
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) ,Computer Science::Digital Libraries - Abstract
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., Comment: arXiv admin note: substantial text overlap with arXiv:1303.7386, arXiv:1308.6165, arXiv:1307.1016, arXiv:1304.0761
- Published
- 2013
- Full Text
- View/download PDF
48. On neat atom structures for cylindric like algebras
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) - Abstract
(1) Let 1\leq k\leq \omega. Call an atom structure \alpha 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=\alpha, \A\in \Nr_n\CA_{\omega} and for every algebra $\B$ based on this atom structure there exists k\in \omega$, k\geq 1, such that \B\in \Nr_n\CA_{n+k}. (2) Let k\leq \omega. Call an atom structure \alpha k complete, if there exists \A such that \At\A=\alpha and \A\in S_c\Nr_n\CA_{n+k}. (3) Let k\leq \omega. Call an atom structure $\alpha$ k neat if there exists \A such that \At\A=\alpha, and \A\in \Nr_n\CA_{n+k}. (4) Let K\subseteq \CA_n, and \L be an extension of first order logic. We say that \K is well behaved w.r.t to \L, if for any \A\in \K, A atomic, and for any any atom structure \beta such that \At\A is elementary equivalent to \beta, for any \B, \At\B=\beta, 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., Comment: arXiv admin note: substantial text overlap with arXiv:1305.4532
- Published
- 2013
- Full Text
- View/download PDF
49. Polyadic-like algebras without the amalgamation property
- Author
-
Ahmed, Tarek Sayed
- Subjects
Mathematics::Logic ,Computer Science::Logic in Computer Science ,FOS: Mathematics ,Mathematics - Logic ,Logic (math.LO) ,Computer Science::Formal Languages and Automata Theory - Abstract
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., Comment: arXiv admin note: text overlap with arXiv:1303.7386
- Published
- 2013
- Full Text
- View/download PDF
50. Neat atom structures
- Author
-
Ahmed, Tarek Sayed
- Subjects
Condensed Matter::Quantum Gases ,Mathematics::Logic ,Physics::Space Physics ,Physics::Atomic and Molecular Clusters ,FOS: Mathematics ,Mathematics - Logic ,Physics::Atomic Physics ,Logic (math.LO) - Abstract
An atom structure is neat if there an algebra based on this atom structure in Nr_nCA_{\omega}. We show that this class is not elementary, Comment: arXiv admin note: text overlap with arXiv:1302.1368
- Published
- 2013
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.