×

Weakly representable atom structures that are not strongly representable, with an application to first order logic. (English) Zbl 1141.03031

The author presents some known results but with a new construction.
Let \(n>2\). By \(\text{CA}_{n}\) is denoted the class of cylindric algebras of dimension \(n\), and by RA the class of relation algebras.
Let \(\mathcal{B}=(B,T_{k},E_{kl})_{k,l<\alpha}\) be any structure with \(T_{k}\subseteq B\times B\) and \(E_{kl}\subseteq B\) for all \(k,l<\alpha\). The complex algebra of \(\mathcal{B}\) is \(\mathcal{C}m\mathcal{B}=(\mathcal{P}(B), \cup,\setminus, T_{k}^{*},E_{kl})_{k,l<\alpha}\), where \((\mathcal{P}(B), \cup,\setminus)\) is the Boolean algebra of all subsets of \(B\) and \(T_{k}^{*}(X)=\{y:(\exists x\in X)((x,y)\in T_{k})\}\). \(\mathcal{B}\) is a cylindric algebra atom structure of dimension \(\alpha\) if \(\mathcal{C}m\mathcal{B}\) is a \(\text{CA}_{\alpha}\). \(\mathcal{B}\) is strongly representable if \(\mathcal{C}m\mathcal{B}\) is a representable cylindric algebra.
Let \(\mathcal{B}=(B,I,^{\smile},C)\) be any structure such that \(C\subseteq B\times B\times B\), \(^{\smile}\) is a function from \(B\) to \(B\) and \(I\subseteq B\). The complex algebra of \(\mathcal{B}\) is \(\mathcal{C}m\mathcal{B}=(\mathcal{P}(B), \cup,\setminus,I,^{\smile}, C^{*})\), where \(C^{*}(X,Y)=\{z: (\exists x\in X)(\exists y\in Y)((x,y,z)\in C)\}\) and \(\overset\smile X=\{\overset\smile x: x\in X \}\). \(\mathcal{B}\) is a relation algebra atom structure if \(\mathcal{C}m\mathcal{B}\) is a relation algebra. \(\mathcal{B}\) is strongly representable if \(\mathcal{C}m\mathcal{B}\) is a representable relation algebra. \(\mathcal{B}\) is weakly representable if \(\mathcal{T}m\mathcal{B}\) (the term algebra – the subalgebra of \(\mathcal{C}m\mathcal{B}\) generated by singletons) is representable. If \(\mathcal{B}\) is strongly representable, then it is weakly representable, but the converse fails.
If \(\mathcal{A}=(A,+,-,0,1,1',^{\smile},;)\) is an atomic relation algebra, we consider \(M_{n}\) \((n\leq 2)\) the set of all \(n\) by \(n\) matrices of atoms in \(\mathcal{A}\) which satisfy the following conditions: \(m_{kk}\leq 1', m_{ij}=m_{ji},m_{ij}\leq m_{jk};m_{ki}\) for all \(i,j,k<n\). The matrices in \(M_{n}\) are called basic matrices.
The main result of this paper is the construction of a weakly representable relation algebra that is not strongly representable: it is proved that the set of all \(n\) by \(n\) basic matrices (\(n\leq 2\)) forms a cylindric basis that is also a weakly but not a strongly representable atom structure. This gives an example of a binary generated atomic representable cylindric algebra with no complete representation. Finally, the author gives an application to first-order logic.

MSC:

03G15 Cylindric and polyadic algebras; relation algebras
03B10 Classical first-order logic
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , Algebraic Logic (North-Holland, 1991).
[2] , and , Omitting types for finite variable fragments and complete representations for algebras. To appear in the Journal of Symbolic Logic. · Zbl 1143.03035
[3] Andréka, J. Philosophical Logic 27 pp 217– (1998)
[4] Andréka, Bull. Symbolic Logic 5 pp 88– (1999)
[5] Non-finite axiomatizability results in algebraic logic. J. Symbolic Logic 57, 832–843 (1992). · Zbl 0772.03032
[6] and , Model Theory (North-Holland, 1994).
[7] , and , Cylindric Algebras, Part I (North-Holland, 1971).
[8] , and , Cylindric Algebras, Part II (North-Holland, 1985).
[9] Hirsch, J. Symbolic Logic 62 pp 816– (1997)
[10] Hirsch, Proc. Amer. Math. Soc. 130 pp 1819– (2002)
[11] and , Relation Algebras by Games. Studies in Logic and the Foundations of Mathematics 147 (Elsevier, 2002).
[12] Hodkinson, Annals Pure Appl. Logic 89 pp 117– (1997)
[13] Introductory course on relation algebras. In [1], pp. 361–392. · Zbl 0749.03048
[14] Sayed Ahmed, Studia Logica 72 pp 1– (2002)
[15] Sayed Ahmed, Bull. Section of Logic 32 pp 117– (2003)
[16] Sayed Ahmed, Logic J. IGPL 15 pp 41– (2007)
[17] Venema, Algebra Universalis 38 pp 185– (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.