Łukasiewicz–Moisil algebra

From HandWiki

Łukasiewicz–Moisil algebras (LMn algebras) were introduced in the 1940s by Grigore Moisil (initially under the name of Łukasiewicz algebras[1]) 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 ℵ0-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 MVn-algebras.[2] MVn-algebras are a subclass of LMn-algebras, and the inclusion is strict for n ≥ 5.[3] In 1982 Roberto Cignoli published some additional constraints that added to LMn-algebras produce proper models for n-valued Łukasiewicz logic; Cignoli called his discovery proper Łukasiewicz algebras.[4] Moisil however, published in 1964 a logic to match his algebra (in the general n ≥ 5 case), now called Moisil logic.[2] 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.[5] Although the Łukasiewicz implication cannot be defined in a LMn algebra for n ≥ 5, the Heyting implication can be, i.e. LMn 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.[6]

Definition

A LMn algebra is a De Morgan algebra (a notion also introduced by Moisil) with n-1 additional unary, "modal" operations: [math]\displaystyle{ \nabla_1, \ldots, \nabla_{n-1} }[/math], i.e. an algebra of signature [math]\displaystyle{ (A, \vee, \wedge, \neg, \nabla_{j \in J}, 0, 1) }[/math] where J = { 1, 2, ... n-1 }. (Some sources denote the additional operators as [math]\displaystyle{ \nabla^n_{j \in J} }[/math] to emphasize that they depend on the order n of the algebra.[7]) The additional unary operators ∇j must satisfy the following axioms for all x, y ∈ A and j, k ∈ J:[3]

  1. [math]\displaystyle{ \nabla_j(x \vee y) = (\nabla_j\; x) \vee (\nabla_j\; y) }[/math]
  2. [math]\displaystyle{ \nabla_j\;x \vee \neg \nabla_j\;x = 1 }[/math]
  3. [math]\displaystyle{ \nabla_j (\nabla_k\;x) = \nabla_k\;x }[/math]
  4. [math]\displaystyle{ \nabla_j \neg x = \neg \nabla_{n-j}\;x }[/math]
  5. [math]\displaystyle{ \nabla_1\;x\leq \nabla_2\;x\cdots\leq \nabla_{n-1}\;x }[/math]
  6. if [math]\displaystyle{ \nabla_j\;x = \nabla_j\;y }[/math] 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:[3]

  • [math]\displaystyle{ \nabla_j(x \wedge y) = (\nabla_j\; x) \wedge (\nabla_j\; y) }[/math]
  • [math]\displaystyle{ \nabla_j\;x \wedge \neg \nabla_j\;x = 0 }[/math]

Additionally: [math]\displaystyle{ \nabla_j\;0 =0 }[/math] and [math]\displaystyle{ \nabla_j\;1 =1 }[/math].[3] In other words, the unary "modal" operations [math]\displaystyle{ \nabla_j }[/math] are lattice endomorphisms.[6]

Examples

LM2 algebras are the Boolean algebras. The canonical Łukasiewicz algebra [math]\displaystyle{ \mathcal{L}_n }[/math] that Moisil had in mind were over the set [math]\displaystyle{ L_{n} = \{ 0,\ \frac{1} {n-1}, \frac{2} {n-1}, ... , \frac{n-2} {n-1}\ , 1 \} }[/math] with negation [math]\displaystyle{ \neg x = 1-x }[/math] conjunction [math]\displaystyle{ x \wedge y = \min\{x, y \} }[/math] and disjunction [math]\displaystyle{ x \vee y = \max\{x, y \} }[/math] and the unary "modal" operators:

[math]\displaystyle{ \nabla_j\left(\frac{i}{n-1}\right)= \; \begin{cases} 0 & \mbox{if } i+j \lt n \\ 1 & \mbox{if } i+j \geq n \\ \end{cases} \quad i \in \{0\} \cup J,\; j \in J. }[/math]

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 ∇2(x, y) ≝ (y, y) and ∇1(x, y) = ¬∇2¬(x, y) = (x, x) [derived by axiom 4] is a three-valued Łukasiewicz algebra.[7]

Representation

Moisil proved that every LMn algebra can be embedded in a direct product (of copies) of the canonical [math]\displaystyle{ \mathcal{L}_n }[/math] algebra. As a corollary, every LMn algebra is a subdirect product of subalgebras of [math]\displaystyle{ \mathcal{L}_n }[/math].[3]

The Heyting implication can be defined as:[6]

[math]\displaystyle{ x \Rightarrow y\; \overset{\mathrm{def}}{=}\;y \vee \bigwedge_{j\in J}(\neg\nabla_j\;x) \vee (\nabla_j\;y) }[/math]

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.[7][8] 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."[7]

References

  1. ↑ Andrei Popescu, Łukasiewicz-Moisil Relation Algebras, Studia Logica, Vol. 81, No. 2 (Nov., 2005), pp. 167-189
  2. ↑ 2.0 2.1 Lavinia Corina Ciungu (2013). Non-commutative Multiple-Valued Logic Algebras. Springer. pp. vii–viii. ISBN 978-3-319-01589-7. 
  3. ↑ 3.0 3.1 3.2 3.3 3.4 Iorgulescu, A.: Connections between MVn-algebras and n-valued Łukasiewicz-Moisil algebras—I. Discrete Math. 181, 155–177 (1998) doi:10.1016/S0012-365X(97)00052-6
  4. ↑ R. Cignoli, Proper n-Valued Łukasiewicz Algebras as S-Algebras of Łukasiewicz n-Valued Propositional Calculi, Studia Logica, 41, 1982, 3–16, doi:10.1007/BF00373490
  5. ↑ Georgescu, G., Iourgulescu, A., Rudeanu, S.: "Grigore C. Moisil (1906–1973) and his School in Algebraic Logic." International Journal of Computers, Communications & Control 1, 81–99 (2006)
  6. ↑ 6.0 6.1 6.2 Georgescu, G. (2006). "N-Valued Logics and Łukasiewicz–Moisil Algebras". Axiomathes 16: 123. doi:10.1007/s10516-005-4145-6. , Theorem 3.6
  7. ↑ 7.0 7.1 7.2 7.3 Cignoli, R., "The algebras of Lukasiewicz many-valued logic - A historical overview," in S. Aguzzoli et al.(Eds.), Algebraic and Proof-theoretic Aspects of Non-classical Logics, LNAI 4460, Springer, 2007, 69-83. doi:10.1007/978-3-540-75939-3_5
  8. ↑ Monteiro, António "Sur les algèbres de Heyting symétriques." Portugaliae Mathematica 39.1–4 (1980): 1–237. Chapter 7. pp. 204-206

Further reading

  • Raymond Balbes; Philip Dwinger (1975). Distributive lattices. University of Missouri Press. Chapter IX. De Morgan Algebras and Lukasiewicz Algebras. ISBN 978-0-8262-0163-8. 
  • Boicescu, V., Filipoiu, A., Georgescu, G., Rudeanu, S.: Łukasiewicz-Moisil Algebras. North-Holland, Amsterdam (1991) ISBN 0080867898
  • Iorgulescu, A.: Connections between MVn-algebras and n-valued Łukasiewicz–Moisil algebras—II. Discrete Math. 202, 113–134 (1999) doi:10.1016/S0012-365X(98)00289-1
  • Iorgulescu, A.: Connections between MVn-algebras and n-valued Łukasiewicz-Moisil—III. Unpublished Manuscript
  • Iorgulescu, A.: Connections between MVn-algebras and n-valued Łukasiewicz–Moisil algebras—IV. J. Univers. Comput. Sci. 6, 139–154 (2000) doi:10.3217/jucs-006-01-0139
  • 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



Retrieved from "https://handwiki.org/wiki/index.php?title=Łukasiewicz–Moisil_algebra&oldid=3374465"