Relation algebras

HomePage | RecentChanges | Preferences

Difference (from prior major revision) (no other diffs)

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:

Added: 108a107

[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

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: (x∨y)oz = (xoz)∨(yoz)
^∪ is an involution: x^∪^∪ = x and (xoy)^∪ = y^∪ox^∪
^∪ is join-preserving: (x∨y)^∪ = x^∪∨y^∪
o is residuated: x^∪o(¬(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]?