N-Variables Positive Logic and Algebras of Relations

D.A.Bredikhin

The theory of algebras of relations plays an important role in modern algebraic logic. Tarski was the first to treat operations on binary relation from an algebraic point of view [1]. In the investigation of algebras of relations, one of the most important problem is to study their laws that can be expressed by equations or conditional equations (see [1-6]).

For any set Ω of operations on binary relations, denote by R{Ω} the class of algebras whose elements are binary relations and whose operations are members of Ω. Let L_{∞} be a positive first-order logic [7] and L_{n} be a restriction of L_{∞} on formulas with n individual variables. Denote by Eq_{n}{Ω} (Qeq_{n}{Ω}) the set of all equations (conditional equations) of algebras from R{Ω} that can be derived in L_{n}, and let V_{n}{Ω} (Q_{n}{Ω}) be the corresponding variety (quasivariety).

We shall consider the operations of relation product ∘, relation inverse ^{−1}, intersection ∩, union ∪, and identity relations Δ. It follows from [1] that equations and conditional equations of algebras with these operations can be expressed in L_{3}. Note that the case n = 3 is more or less trivial and we suppose that n ≥ 4.

The class R{∘,^{−1}, ∩, Δ} was introduced and studied in [3] (see also [5]).

THEOREM 1. Q_{4}{∘,^{−1}, ∩, Δ} = V_{4}{∘,^{−1}, ∩, Δ}; V_{4}{∘,^{−1}, ∩, Δ} is finitely based; an algebra (A, ·,^{−1}, ∧, e) belongs to V_{4}{∘,^{−1}, ∩, Δ} if and if and only if it satisfies the following equations: (xy)z = x(yz), (x^{−1})^{−1} = x, (xy)^{−1} = y^{−1}x^{−1}, xe = ex = x, x ∧ x = x, x ∧ y = y ∧ x, (x ∧ y) ∧ z = x ∧ (y∧ = z), (x ∧ y)^{−1} = x^{−1} ∧ y^{−1}, xy ∧ x(y ∧ z) = x(y ∧ z), x ∧ yz = x ∧ y(z ∧ x^{−1}y).

Q_{5}{∘,^{−1}, ∩, Δ} does not contain in V_{∞}{∘,^{−1}, ∩, Δ}, in particular, Q_{5}{∘,^{−1}, ∩, Δ} ≠ V_{5}{∘,^{−1}, ∩, Δ}.

THEOREM 2. Q_{4}{∘,^{−1}, ∩, ∪, Δ} = V_{4}{∘,^{−1}, ∩, ∪, Δ}; V_{4}{∘,^{−1}, ∩, ∪, Δ} is finitely based; an algebra (A, ·,^{−1}, ∧, ∨, e) belongs to V_{4}{∘,^{−1}, ∩, ∪, Δ} if and if and only if it satisfies the equations of Theorem 1 and x ∨ x = x, x ∨ y = y ∨ x, (x ∨ y) ∨ z = x ∨ (y ∨ z), x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z).

Q_{5}{∘,^{−1}, ∩, ∪, Δ} ≠ V_{5}{∘,^{−1}, ∩, ∪, Δ}.

[1] Tarski A. On the calculus of relations. J. Symbolic Logic 6(1941), no. 3, 73-89.

[2] Lyndon R.C. The representation of relation algebras, II. Ann. Math. 63(1956), no. 2, 294-307.

[3] Jónsson B. Representation of modular lattices and of relation algebras. Trans. Amer. Math. Soc. 92(1959), 449-464.

[4] Maddux R.D. The origin of relation algebras in the development and axiomatization of the calculus of relations. Studia Logica, 91(1991), 423-455.

[5] Andreka H., Bredikhin D.A. The equational theory of union-free algebras of relations. Algebra Univers. 33(1994), 516-532.

[6] Bredikhin D.A. On relations algebras with Diophantus’s operations. Reports of Russia Academy of Sciences, 360(1998), 594-595.

[7] Rasiowa H., Sikorski R. The mathematics of metamathematics. Warszawa, 1963.

Address: Saratov State Technical University, 410002 Lermontova 7-22, Saratov, Russia

E-mail: bredikhin@mail.ru