[Home]Relation algebras

HomePage | RecentChanges | Preferences

Abbreviation: RA

Definition

A relation algebra is a structure A = (A,∨,0, ∧,1,¬,o,,e) such that

(A,∨,0, ∧,1,¬) is a Boolean algebra,
(A,o,e) is a monoid,
o is join-preserving:   (xy)oz = (xoz)∨(yoz)
is an involution:   x = x  and  (xoy) = yox
is join-preserving:   (xy) = xy
o is residuated:   xo(¬(xoy)) ≤ ¬y.

Morphisms

Let A and B be relation algebras. A morphism from A to B is a function h : A → B that is a Boolean homomorphism and preserves o, , e: h(xoy) = h(x)oh(y)  and  h(x) = h(x)  and  h(e) = e.

Some results

Examples

Properties

Classtype variety
Equational theory undecidable
Quasiequational theory undecidable
First-order theory undecidable
Locally finite no
Residual size unbounded
Congruence distributive yes
Congruence modular yes
Congruence n-permutable yes, n = 2
Congruence regular yes
Congruence uniform yes
Congruence extension property yes
Definable principal congruences yes
Equationally definable principal congruences yes
[Discriminator variety]? yes
Amalgamation property no
Strong amalgamation property no
Epimorphisms are surjective no

Finite members

[Small relation algebras]
[Size 1]?:  1
[Size 2]?:  1
[Size 3]?:  0
[Size 4]?:  3
[Size 5]?:  0
[Size 6]?:  0

Subclasses

[n-dimensional relation algebras]?
[Representable relation algebras]?
[Commutative relation algebras]?
[Square-increasing relation algebras]?

Superclasses

Sequential algebras
[Semiassociative relation algebras]?


HomePage | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited May 18, 2003 10:33 am (diff)
Search: