Relation algebras

HomePage | RecentChanges | Preferences

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

Changed: 6c6
 \wedge,1,\neg,\circ,^\cup,e\rangle$such that  \wedge,1,\neg,\circ,^{\smile},e\rangle$ such that

Changed: 9c9
 \wedge,1,\neg\rangle $is a Boolean algebra,  \wedge,1,\neg\rangle$ is a Boolean algebra,

Changed: 14,17c14,17
 x∪∪ = x and (xoy)∪ z = y∪ox∪ ∪ is join-preserving:   (x∨y)∪ z = x∪∨y∪ o is residuated:   x∪o(¬(xoy)) ≤ ¬y.
 x∪∪ = x  and  (xoy)∪ = y∪ox∪ ∪ is join-preserving:   (x∨y)∪ = x∪∨y∪ o is residuated:   x∪o(¬(xoy)) ≤ ¬y.

Removed: 19,20d18
 Remark:

Changed: 24,25c22,23
 A morphism from A to B is a function h : A→B that is a Boolean homomorphism and preserves o, ^{\cup}, e: h(xoy) = h(x)oh(y) and h(x∪) = h(x)∪ and h(e) = e.
 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.

 [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