Weakly representable but not representable relation algebras

We prove the existence of non-representable relation algebras the union and complementation free reducts of which can be represented, i.e. which are weakly representable. This answers Problem 3 in Jónsson [4], and has consequences concerning the complexity of the equational theory of representable relation algebras.Presented by B. Jonsson.Research supported by Hungarian National Foundation for Scientific Research grants No. 1911 and No. T7255.     

Weakly representable relation algebras form a variety

We prove that the class of weakly representable relation algebras is closed under homomorphic images, hence it is a variety. As a corollary we classify the subdirectly irreducible algebras in this class. Received April 3, 2007; accepted in final form February 7, 2008.     

A note on substitutions in representable cylindric algebras

We show that it is impossible to define a substitution operator for arbitrary representable cylindric algebras that agrees in its basic properties with the notion of substitutions introduced for dimension complemented algebras (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Weakly representable atom structures that are not strongly representable,with an application to first order logic

Letn > 2. A weakly representable relation algebra that is not strongly representable is constructed. It is proved that the set of all n by n basic matrices 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. An application to first order logic is given. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The subvariety lattice for representable idempotent commutative residuated lattices

RICRL denotes the variety of commutative residuated lattices which have an idempotent monoid operation and are representable in the sense that they are subdirect products of linearly ordered algebras. It is shown that the subvariety lattice of RICRL is countable, despite its complexity and in contrast to several varieties of closely related algebras.     

On the complexity of axiomatizations of the class of representable quasi‐polyadic equality algebras

Using games, as introduced by Hirsch and Hodkinson in algebraic logic, we give a recursive axiomatization of the class RQPEA _α of representable quasi‐polyadic equality algebras of any dimension α. Following Sain and Thompson in modifying Andréka’s methods of splitting, to adapt the quasi‐polyadic equality case, we show that if Σ is a set of equations axiomatizing RPEA _n for $2< n <\omegaUsing games, as introduced by Hirsch and Hodkinson in algebraic logic, we give a recursive axiomatization of the class RQPEA _α of representable quasi‐polyadic equality algebras of any dimension α. Following Sain and Thompson in modifying Andréka’s methods of splitting, to adapt the quasi‐polyadic equality case, we show that if Σ is a set of equations axiomatizing RPEA _n for $2< n <\omega$ and $l< n,$ $k < n$, k′ < ω are natural numbers, then Σ contains infinitely equations in which ? occurs, one of + or · occurs, a diagonal or a permutation with index l occurs, more than k cylindrifications and more than k′ variables occur. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Axiomatizability of reducts of algebras of relations

In this paper, we prove that any subreduct of the class of representable relation algebras whose similarity type includes intersection, relation composition and converse is a non-finitely axiomatizable quasivariety and that its equational theory is not finitely based. We show the same result for subreducts of the class of representable cylindric algebras of dimension at least three whose similarity types include intersection and cylindrifications. A similar result is proved for subreducts of the class of representable sequential algebras. Received October 7, 1998; accepted in final form September 10, 1999.     

Strongly representable atom structures of relation algebras

A relation algebra atom structure is said to be strongly representable if all atomic relation algebras with that atom structure are representable. This is equivalent to saying that the complex algebra is a representable relation algebra. We show that the class of all strongly representable relation algebra atom structures is not closed under ultraproducts and is therefore not elementary. This answers a question of Maddux (1982).

Our proof is based on the following construction. From an arbitrary undirected, loop-free graph , we construct a relation algebra atom structure and prove, for infinite , that is strongly representable if and only if the chromatic number of is infinite. A construction of Erdös shows that there are graphs () with infinite chromatic number, with a non-principal ultraproduct whose chromatic number is just two. It follows that is strongly representable (each ) but is not.

     

Bifunctional-elementary relation algebras

A relation algebra is bifunctional-elementary if it is atomic and for any atom a, the element a;1;a is the join of at most two atoms, and one of these atoms is bifunctional (an element x is bifunctional if ’). We show that bifunctional-elementary relation algebras are representable. Our proof combines the representation theorems for: pair-dense relation algebras given by R. Maddux; relation algebras generated by equivalence elements provided corresponding relativizations are representable by S. Givant; and strong-elementary relation algebras dealt with in our earlier work. It turns out that atomic pair-dense relation algebras are bifunctional elementary, showing that our theorem generalizes the representation theorem of atomic pair-dense relation algebras. The problem is still open whether the related classes of rather elementary, functional-elementary, and strong functional-elementary relation algebras are representable. Received July 15, 2007; accepted in final form March 17, 2008.     

Axiomatization of identity-free equations valid in relation algebras

A finite axiom set for the identity-free equations valid in relation algebras is given. This is a simplification of the one given by Jónsson, and confirms a conjecture of Tarski. An axiom set for the identity-free equations valid in the representable relation algebras is given, too. We show that in the class of representable relation algebras, both the operation of taking converse and the identity constant are finitely axiomatizable (over the rest of the operations).Dedicated to the memory of Alan DayPresented by J. Sichler.     

Comparing decision problem for various paradigms of algebraic logic

We show that in many cases the decision problems for varieties of cylindric algebras are much harder than those for the corresponding relation algebra reducts. We also give examples of varieties of cylindric and relation algebras which are algorithmically more complicated than the subvarieties of their representable algebras.     

Necessary subalgebras of simple nonintegral semiassociative relation algebras

There are six finite nonintegral representable relation algebras such that every nonintegral simple semiassociative relation algebra has a nontrivial subalgebra isomorphic to one of those six.Presented by Bjarni Jónsson.     

Type 1 representable lattices of dimension at most 4

We prove that every lattice of length (formerly, dimension) at most 4, representable by commuting equivalence relations, is also representable by subgroups of an Abelian group.     

On the equational complexity of RRA

We prove that the equational complexity function for the variety of representable relation algebras is bounded below by a log-log function.     

Boolean products of R0‐algebras

In this paper, the (weak) Boolean representation of R₀‐algebras are investigated. In particular, we show that directly indecomposable R₀‐algebras are equivalent to local R₀‐algebras and any nontrivial R₀‐algebra is representable as a weak Boolean product of local R₀‐algebras (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Varieties minimal over representable varieties of lattice-ordered groups

Weinberg showed that the variety of abelian lattice-ordered groups is the minimal nontrivial variety in the lattice of varieties of lattice-ordered groups. Scrimger showed that the abelian variety of lattice-ordered groups has countably infinitely many nonrepresentable covering varieties, and it is now known that his varieties are the only nonrepresentable covers of the abelian variety.

In this paper, a variation of the method used to construct the Scrimger varieties is developed that is shown to produce every nonrepresentable cover of any representable variety. Using this variation, all nonrepresentable covers of any weakly abelian l-variety are specifically identified, as are the nonrepresentable covers of any l-metabelian representable l-variety. In both instances, such il-varieties have only countably infinitely many such covers.

Any nonrepresentable cover of a representable il-variety is shown to be a subvariety of a quasi-representable il-variety as defined by Reilly. The class of these quasi-representable l-varieties is shown to contain the well-known L_n l-varieties and to generalize many of their properties.     

Relativized relation algebras

Relativization is one of the central topics in the study of algebras of relations (i.e. relation and cylindric algebras). Relativized representable relation algebras behave much nicer than the original class RAA: for instance, one obtains finite axiomatizability, decidability and amalgamation by relativization. The properties of the class obtained by relativizing RRA depend on the kind of element with which the algebras are relativized. We give a systematic account of all interesting choices of relativizing RRA, and show that relativizing with transitive elements forms the borderline where all above mentioned three properties switch from negative to positive. Received January 24, 1993; accepted in final form October 7, 1998.     

On the definition and the representability of quasi‐polyadic equality algebras

We show that the usual axiom system of quasi polyadic equality algebras is strongly redundant. Then, so called non‐commutative quasi‐polyadic equality algebras are introduced (), in which, among others, the commutativity of cylindrifications is dropped. As is known, quasi‐polyadic equality algebras are not representable in the classical sense, but we prove that algebras in are representable by quasi‐polyadic relativized set algebras, or more exactly by algebras in .     

Linearly representable codes over chain rings

In this paper, we consider linear codes over finite chain rings. We present a general mapping which produces codes over smaller alphabets. Under special conditions, these codes are linear over a finite field. We introduce the notion of a linearly representable code and prove that certain MacDonald codes are linearly representable. Finally, we give examples for good linear codes over finite fields obtained from special multisets in projective Hjelmslev planes.