Łukasiewicz–Moisil algebra

Łukasiewicz–Moisil algebras (LM_n algebras) were introduced in the 1940s by Grigore Moisil (initially under the name of Łukasiewicz algebras) in the hope of giving algebraic semantics for the n-valued Łukasiewicz logic. However, in 1956 Alan Rose discovered that for n ≥ 5, the Łukasiewicz–Moisil algebra does not model the Łukasiewicz logic. A faithful model for the ℵ₀-valued (infinitely-many-valued) Łukasiewicz–Tarski logic was provided by C. C. Chang's MV-algebra, introduced in 1958. For the axiomatically more complicated (finite) n-valued Łukasiewicz logics, suitable algebras were published in 1977 by Revaz Grigolia and called MV_n-algebras. MV_n-algebras are a subclass of LM_n-algebras, and the inclusion is strict for n ≥ 5. In 1982 Roberto Cignoli published some additional constraints that added to LM_n-algebras produce proper models for n-valued Łukasiewicz logic; Cignoli called his discovery proper Łukasiewicz algebras.

Moisil however, published in 1964 a logic to match his algebra (in the general n ≥ 5 case), now called Moisil logic. After coming in contact with Zadeh's fuzzy logic, in 1968 Moisil also introduced an infinitely-many-valued logic variant and its corresponding LM_θ algebras. Although the Łukasiewicz implication cannot be defined in a LM_n algebra for n ≥ 5, the Heyting implication can be, i.e. LM_n algebras are Heyting algebras; as a result, Moisil logics can also be developed (from a purely logical standpoint) in the framework of Brower's intuitionistic logic.

Definition

A LM_n algebra is a De Morgan algebra (a notion also introduced by Moisil) with n-1 additional unary, "modal" operations: ${\mathrm{\nabla }}_1,\dots ,{\mathrm{\nabla }}_{n-1}$, i.e. an algebra of signature $(A,\vee ,\wedge ,\mathrm{\neg },{\mathrm{\nabla }}_{j\in J},0,1)$ where J = { 1, 2, ... n-1 }. (Some sources denote the additional operators as $\underset{j\in J}{\overset{n}{\mathrm{\nabla }}}$ to emphasize that they depend on the order n of the algebra.) The additional unary operators ∇_j must satisfy the following axioms for all x, y ∈ A and j, k ∈ J:

1. ${\mathrm{\nabla }}_j(x\vee y)=({\mathrm{\nabla }}_{j}x)\vee ({\mathrm{\nabla }}_{j}y)$
2. ${\mathrm{\nabla }}_{j}x\vee \mathrm{\neg }{\mathrm{\nabla }}_{j}x=1$
3. ${\mathrm{\nabla }}_j({\mathrm{\nabla }}_{k}x)={\mathrm{\nabla }}_{k}x$
4. ${\mathrm{\nabla }}_j\mathrm{\neg }x=\mathrm{\neg }{\mathrm{\nabla }}_{n-j}x$
5. ${\mathrm{\nabla }}_{1}x\le {\mathrm{\nabla }}_{2}x\cdots \le {\mathrm{\nabla }}_{n-1}x$
6. if ${\mathrm{\nabla }}_{j}x={\mathrm{\nabla }}_{j}y$ for all j ∈ J, then x = y.

(The adjective "modal" is related to the [ultimately failed] program of Tarksi and Łukasiewicz to axiomatize modal logic using many-valued logic.)

Elementary properties

The duals of some of the above axioms follow as properties:

• ${\mathrm{\nabla }}_j(x\wedge y)=({\mathrm{\nabla }}_{j}x)\wedge ({\mathrm{\nabla }}_{j}y)$
• ${\mathrm{\nabla }}_{j}x\wedge \mathrm{\neg }{\mathrm{\nabla }}_{j}x=0$

Additionally: ${\mathrm{\nabla }}_{j}0=0$ and ${\mathrm{\nabla }}_{j}1=1$. In other words, the unary "modal" operations ${\mathrm{\nabla }}_j$ are lattice endomorphisms.

Examples

LM₂ algebras are the Boolean algebras. The canonical Łukasiewicz algebra ${ℒ}_n$ that Moisil had in mind were over the set $L_n=\{0,\frac{1}{n-1},\frac{2}{n-1},\mathrm{...},\frac{n-2}{n-1},1\}$ with negation $\mathrm{\neg }x=1-x$ conjunction $x\wedge y=\min \{x,y\}$ and disjunction $x\vee y=\max \{x,y\}$ and the unary "modal" operators:

${\mathrm{\nabla }}_j\left(\frac{i}{n-1}\right)=\{\begin{array}{cc}0& \text{if }i+j<n\\ 1& \text{if }i+j\ge n\end{array}i\in \{0\}\cup J,j\in J.$

If B is a Boolean algebra, then the algebra over the set B^[2] ≝ {(x, y) ∈ B×B | x ≤ y} with the lattice operations defined pointwise and with ¬(x, y) ≝ (¬y, ¬x), and with the unary "modal" operators ∇₂(x, y) ≝ (y, y) and ∇₁(x, y) = ¬∇₂¬(x, y) = (x, x) [derived by axiom 4] is a three-valued Łukasiewicz algebra.

Representation

Moisil proved that every LM_n algebra can be embedded in a direct product (of copies) of the canonical ${ℒ}_n$ algebra. As a corollary, every LM_n algebra is a subdirect product of subalgebras of ${ℒ}_n$.

The Heyting implication can be defined as:

$x\Rightarrow y\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}y\vee \underset{j\in J}{\bigwedge }(\mathrm{\neg }{\mathrm{\nabla }}_{j}x)\vee ({\mathrm{\nabla }}_{j}y)$

Antonio Monteiro showed that for every monadic Boolean algebra one can construct a trivalent Łukasiewicz algebra (by taking certain equivalence classes) and that any trivalent Łukasiewicz algebra is isomorphic to a Łukasiewicz algebra thus derived from a monadic Boolean algebra. Cignoli summarizes the importance of this result as: "Since it was shown by Halmos that monadic Boolean algebras are the algebraic counterpart of classical first order monadic calculus, Monteiro considered that the representation of three-valued Łukasiewicz algebras into monadic Boolean algebras gives a proof of the consistency of Łukasiewicz three-valued logic relative to classical logic."

Further reading

• Boicescu, V., Filipoiu, A., Georgescu, G., Rudeanu, S.: Łukasiewicz-Moisil Algebras. North-Holland, Amsterdam (1991)
• Iorgulescu, A.: Connections between MV_n-algebras and n-valued Łukasiewicz–Moisil algebras—II. Discrete Math. 202, 113–134 (1999)
• Iorgulescu, A.: Connections between MV_n-algebras and n-valued Łukasiewicz-Moisil—III. Unpublished Manuscript
• Iorgulescu, A.: Connections between MV_n-algebras and n-valued Łukasiewicz–Moisil algebras—IV. J. Univers. Comput. Sci. 6, 139–154 (2000)
• R. Cignoli, Algebras de Moisil de orden n, Ph.D. Thesis, Universidad National del Sur, Bahia Blanca, 1969
• http://projecteuclid.org/download/pdf_1/euclid.ndjfl/1093635424