MV-algebra

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In abstract algebra, a branch of pure mathematics, an MV-algebra is an algebraic structure with a binary operation \oplus, a unary operation \neg, and the constant 0, satisfying certain axioms. MV-algebras are the algebraic semantics of Łukasiewicz logic; the letters MV refer to many-valued logic of Łukasiewicz. MV-algebras coincide with the class of bounded commutative BCK algebras.

Definitions[edit]

An MV-algebra is an algebraic structure \langle A, \oplus, \lnot, 0\rangle, consisting of

which satisfies the following identities:

  •  (x \oplus y) \oplus z = x \oplus (y \oplus z),
  •  x \oplus 0 = x,
  •  x \oplus y = y \oplus x,
  •  \lnot \lnot x = x,
  •  x \oplus \lnot 0 = \lnot 0, and
  •  \lnot ( \lnot x \oplus y)\oplus y = \lnot ( \lnot y \oplus x) \oplus x.

By virtue of the first three axioms, \langle A, \oplus, 0 \rangle is a commutative monoid. Being defined by identities, MV-algebras form a variety of algebras. The variety of MV-algebras is a subvariety of the variety of BL-algebras and contains all Boolean algebras.

An MV-algebra can equivalently be defined (Hájek 1998) as a prelinear commutative bounded integral residuated lattice \langle L, \wedge, \vee, \otimes, \rightarrow, 0, 1 \rangle satisfying the additional identity x \vee y = (x \rightarrow y) \rightarrow y.

Examples of MV-algebras[edit]

A simple numerical example is A=[0,1], with operations x \oplus y = \min(x+y,1) and \lnot x=1-x. In mathematical fuzzy logic, this MV-algebra is called the standard MV-algebra, as it forms the standard real-valued semantics of Łukasiewicz logic.

The trivial MV-algebra has the only element 0 and the operations defined in the only possible way, 0\oplus0=0 and \lnot0=0.

The two-element MV-algebra is actually the two-element Boolean algebra \{0,1\}, with \oplus coinciding with Boolean disjunction and \lnot with Boolean negation. In fact adding the axiom x \oplus x = x to the axioms defining an MV-algebra results in an axiomantization of Boolean algebras.

If instead the axiom added is x \oplus x \oplus x = x \oplus x, then the axioms define the MV3 algebra corresponding to the three-valued Łukasiewicz logic Ł3[citation needed]. Other finite linearly ordered MV-algebras are obtained by restricting the universe and operations of the standard MV-algebra to the set of n equidistant real numbers between 0 and 1 (both included), that is, the set \{0,1/(n-1),2/(n-1),\dots,1\}, which is closed under the operations \oplus and \lnot of the standard MV-algebra; these algebras are usually denoted MVn.

Another important example is Chang's MV-algebra, consisting just of infinitesimals (with the order type ω) and their co-infinitesimals.

Chang also constructed an MV-algebra from an arbitrary totally ordered abelian group G by fixing a positive element u and defining the segment [0, u] as { xG | 0 ≤ xu }, which becomes an MV-algebra with xy = min(u, x+y) and ¬x = ux. Furthermore, Chang showed that every linearly ordered MV-algebra is isomorphic to an MV-algebra constructed from a group in this way.

D. Mundici extended the above construction to abelian lattice-ordered groups. If G is such a group with strong (order) unit u, then the "unit interval" { xG | 0 ≤ xu } can be equipped with ¬x = ux, xy = uG (x+y), xy = 0∨G(x+yu). This construction establishes a categorical equivalence between lattice-ordered abelian groups with strong unit and MV-algebras.

Relation to Łukasiewicz logic[edit]

C. C. Chang devised MV-algebras to study many-valued logics, introduced by Jan Łukasiewicz in 1920. In particular, MV-algebras form the algebraic semantics of Łukasiewicz logic, as described below.

Given an MV-algebra A, an A-valuation is a homomorphism from the algebra of propositional formulas (in the language consisting of \oplus,\lnot, and 0) into A. Formulas mapped to 1 (or \lnot0) for all A-valuations are called A-tautologies. If the standard MV-algebra over [0,1] is employed, the set of all [0,1]-tautologies determines so-called infinite-valued Łukasiewicz logic.

Chang's (1958, 1959) completeness theorem states that any MV-algebra equation holding in the standard MV-algebra over the interval [0,1] will hold in every MV-algebra. Algebraically, this means that the standard MV-algebra generates the variety of all MV-algebras. Equivalently, Chang's completeness theorem says that MV-algebras characterize infinite-valued Łukasiewicz logic, defined as the set of [0,1]-tautologies.

The way the [0,1] MV-algebra characterizes all possible MV-algebras parallels the well-known fact that identities holding in the two-element Boolean algebra hold in all possible Boolean algebras. Moreover, MV-algebras characterize infinite-valued Łukasiewicz logic in a manner analogous to the way that Boolean algebras characterize classical bivalent logic (see Lindenbaum-Tarski algebra).

Relation to functional analysis[edit]

MV-algebras were related by D. Mundici to approximately finite-dimensional C*-algebras by establishing a bijective correspondence between all isomorphism classes of AF C*-algebras with lattice-ordered dimension group and all isomorphism classes of countable MV algebras. Some instances of this correspondence include:

Countable MV algebra AF C*-algebra
{0, 1}
{0, 1/n, ..., 1 } Mn(ℂ), i.e. n×n complex matrices
finite finite-dimensional
boolean commutative

In software[edit]

There are multiple frameworks implementing fuzzy logic (type II), and most of them implement what has been called a multi-adjoint logic. This is no more than the implementation of a MV-algebra. More information available at Multi-adjoint logic programming.

References[edit]

  • Chang, C. C. (1958) "Algebraic analysis of many-valued logics," Transactions of the American Mathematical Society 88: 476–490.
  • ------ (1959) "A new proof of the completeness of the Lukasiewicz axioms," Transactions of the American Mathematical Society 88: 74–80.
  • Cignoli, R. L. O., D'Ottaviano, I. M. L., Mundici, D. (2000) Algebraic Foundations of Many-valued Reasoning. Kluwer.
  • Di Nola A., Lettieri A. (1993) "Equational characterization of all varieties of MV-algebras," Journal of Algebra 221: 123–131.
  • Hájek, Petr (1998) Metamathematics of Fuzzy Logic. Kluwer.
  • Mundici, D.: Interpretation of AF C*-algebras in Łukasiewicz sentential calculus. J. Funct. Anal. 65, 15–63 (1986) doi:10.1016/0022-1236(86)90015-7

Further reading[edit]

  • D. Mundici (2011). Advanced Łukasiewicz calculus and MV-algebras. Springer. ISBN 978-94-007-0839-6. 

External links[edit]