# Relation algebras

HomePage | RecentChanges | Preferences

Difference (from revision 10 to current revision) (minor diff, author diff)

Changed: 14c14
 x∪∪ = x  and  (xoy)∪ z = y∪ox∪
 x∪∪ = x  and  (xoy)∪ = y∪ox∪

Changed: 16c16
 (x∨y)∪ z = x∪∨y∪
 (x∨y)∪ = x∪∨y∪

Removed: 19,20d18
 Remark:

Changed: 24c22
 A morphism from A to B is a function h : A→B that is a Boolean homomorphism and preserves o, ∪, e:
 A morphism from A to B is a function h : A → B that is a Boolean homomorphism and preserves o, ∪, e:

 [Small relation algebras]

Changed: 110,114c109,113
 [Size 2]?:   [Size 3]?:   [Size 4]?:   [Size 5]?:   [Size 6]?:
 [Size 2]?:  1 [Size 3]?:  0 [Size 4]?:  3 [Size 5]?:  0 [Size 6]?:  0

### 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.

### 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