MV-Algebras and Many-Valued Logic

Introduction

This is the third article of the Boolean system in Part V, and it occupies the algebra slot of that system for the many-valued reading of the domain. The system is still propositional, but its truth values are no longer the two points of $\mathbf{2}$: the two-element algebra is replaced by the unit interval $[0,1]$, and the classical connectives are replaced by the operations of Łukasiewicz logic. The algebras that arise are the MV-algebras of Chang, and they stand to the standard interval $[0,1]$ exactly as the Boolean algebras stand to $\mathbf{2}$.

The boundary against the general theory is deliberate. Lattices, distributivity and residuation are the subject of Order Theory and Lattices and of Heyting Algebras and Intuitionistic Logic, and are used here rather than re-derived. The logic is not the intuitionistic one: by Heyting Algebras and Intuitionistic Logic, no finite set of finite Heyting algebras characterises the intuitionistic calculus, whereas the MV-algebra $[0,1]$ is a single algebra whose variety is generated by it, and it is continuously rather than finitely valued. The topological and pointfree generalisations are the subject, and the non-distributive generalisation is not covered here.

The corpus's default base is the commutative ring; this article replaces it by an MV-algebra, as the Boolean system replaces it by a Boolean algebra. No field, no characteristic hypothesis and no invertibility of $2$ is used. The one place where an additive group appears is Mundici's theorem, and there the group is a lattice-ordered abelian group, which is torsion-free.

Throughout, an MV-algebra is written $(A, \oplus, \neg, 0)$, its order is $\leq$, and its top is $1 = \neg 0$. The lattice operations are written $\wedge$ and $\vee$ and are distinct from $\oplus$ and the derived product $\odot$; this distinction is the single most common error in the subject. The unit interval with the Łukasiewicz operations is written $[0,1]_{\mathrm{L}}$ when the operations need to be emphasised, and the chain with $n+1$ elements is $\mathrm{L}_n$.

MV-Algebras

The Axioms

Definition. An MV-algebra is a set $A$ with a binary operation $\oplus$, a unary operation $\neg$ and an element $0$, satisfying

$$ \text{(MV1)}\quad \alpha \oplus \beta = \beta \oplus \alpha, \qquad \text{(MV2)}\quad (\alpha \oplus \beta) \oplus \gamma = \alpha \oplus (\beta \oplus \gamma), $$

$$ \text{(MV3)}\quad \alpha \oplus 0 = \alpha, \qquad \text{(MV4)}\quad \neg \neg \alpha = \alpha, \qquad \text{(MV5)}\quad \alpha \oplus \neg 0 = \neg 0, $$

$$ \text{(MV6)}\quad \neg(\neg \alpha \oplus \beta) \oplus \beta = \neg(\neg \beta \oplus \alpha) \oplus \alpha . $$

One writes $1 = \neg 0$, and defines the product and the residuum by

$$ \alpha \odot \beta = \neg(\neg \alpha \oplus \neg \beta), \qquad \alpha \to \beta = \neg \alpha \oplus \beta . $$

A homomorphism of MV-algebras is a map preserving $\oplus$, $\neg$ and $0$; it then preserves $1$, $\odot$ and $\to$ as well. A subalgebra is a subset closed under $\oplus$ and $\neg$ and containing $0$.

The axioms (MV1)–(MV4) say that $(A, \oplus, 0)$ is a commutative monoid and that $\neg$ is an involution; (MV5) makes $1$ absorbing for $\oplus$; and (MV6) is the axiom that forces the order to be a lattice order and the operation to be the Łukasiewicz one on each chain. The definition is equational, so the MV-algebras form a variety in the sense of universal algebra.

The Order and the Lattice Operations

Definition. On an MV-algebra $A$ define

$$ \alpha \leq \beta \iff \alpha \odot \neg \beta = 0 \iff \alpha \to \beta = 1 . $$

Theorem. The relation $\leq$ is a partial order with least element $0$ and greatest element $1$, and the operations

$$ \alpha \wedge \beta = \alpha \odot (\alpha \to \beta), \qquad \alpha \vee \beta = (\alpha \to \beta) \to \beta $$

are the meet and the join for it. Under these operations $A$ is a distributive lattice, and $\neg$ is an order-reversing involution with $\neg 0 = 1$, $\neg 1 = 0$. The monoid operation is monotone: $\alpha \leq \beta$ implies $\alpha \oplus \gamma \leq \beta \oplus \gamma$ and $\alpha \odot \gamma \leq \beta \odot \gamma$.

Proof. The relation is reflexive because $\alpha \odot \neg \alpha = \neg(\alpha \oplus \neg \alpha)$ and $\alpha \oplus \neg \alpha = 1$ by (MV5) with $\alpha$ and $\neg \alpha$; it is antisymmetric and transitive by the standard computations from (MV6), which is precisely the axiom that makes $\alpha \odot \neg \beta$ a residuated pairing and yields the lattice laws. Monotonicity of $\oplus$ and $\odot$ is immediate from the definition of $\leq$ and the associativity of $\oplus$. The distributivity is the standard theorem of Chang; the lattice of an MV-algebra is distributive and is a sublattice of a product of chains. The full verification is Chang's and is quoted.

Theorem. In an MV-algebra, for all $\alpha, \beta$:

$$ \alpha \oplus \neg \alpha = 1, \qquad \alpha \odot \neg \alpha = 0, \qquad \alpha \oplus 1 = 1, \qquad \alpha \odot 0 = 0, \qquad \alpha \oplus \beta = \neg(\neg \alpha \odot \neg \beta), $$

and the order is characterised by $\alpha \leq \beta \iff \neg \beta \leq \neg \alpha$.

Proof. The first two are the standard identities $\alpha \oplus \neg \alpha = 1$ and $\alpha \odot \neg \alpha = 0$, derived from (MV4)–(MV6) by Chang. The third is (MV5). The fourth is the negation of the third. The fifth is (MV4) applied to the definition of $\odot$. The last is the order-reversing property of the involution $\neg$, which follows from $\alpha \odot \neg \beta = \neg(\neg \alpha \oplus \beta)$.

Remark. The identities $\alpha \oplus \neg \alpha = 1$ and $\alpha \odot \neg \alpha = 0$ do not make $\neg$ a Boolean complement: the complement of a Boolean algebra complements with respect to the lattice operations, so that $\alpha \vee \neg \alpha = 1$ and $\alpha \wedge \neg \alpha = 0$; here the identities are stated for $\oplus$ and $\odot$, which are not the join and the meet. In the standard algebra $[0,1]_{\mathrm{L}}$ one has $\alpha \vee \neg \alpha = \max(\alpha, 1-\alpha)$, which equals $1$ only for $\alpha \in \{0,1\}$, and $\alpha \wedge \neg \alpha = \min(\alpha,1-\alpha) = 0$ only for the same two points. The lattice of an MV-algebra is distributive and complemented only when the algebra is Boolean.

Elementary Identities

The following identities are used constantly and are collected here.

Theorem. In an MV-algebra, for all $\alpha, \beta, \gamma$:

$$ \alpha \to \beta = \neg \beta \to \neg \alpha, \qquad (\alpha \to \beta) \to (\alpha \to \gamma) = (\alpha \wedge \beta) \to \gamma, $$

$$ \alpha \to (\beta \to \gamma) = (\alpha \odot \beta) \to \gamma, \qquad \alpha \to \beta = 1 \iff \alpha \leq \beta, $$

and the residuation law

$$ \gamma \leq \alpha \to \beta \iff \alpha \odot \gamma \leq \beta $$

holds.

Proof. Since $\alpha \to \beta = \neg \alpha \oplus \beta$ and $\neg \beta \to \neg \alpha = \neg\neg \beta \oplus \neg \alpha = \beta \oplus \neg \alpha$, the first identity is the commutativity of $\oplus$. The second and the third express the fact that $\odot$ is left adjoint to $\to$; they are the standard consequences of (MV6), verified directly from the axioms in Chang's original paper. The equivalence $\alpha \to \beta = 1 \iff \alpha \leq \beta$ is the definition of the order, and the residuation law is its residuated form.

Example (the standard algebra). On the unit interval $[0,1]$ put

$$ \alpha \oplus \beta = \min(1, \alpha + \beta), \qquad \neg \alpha = 1 - \alpha, \qquad 0 = 0 . $$

Then $1 = 1$, $\alpha \odot \beta = \max(0, \alpha + \beta - 1)$, and $\alpha \to \beta = \min(1, 1 - \alpha + \beta)$; the order of the MV-algebra is the usual order of $[0,1]$, and the lattice operations are $\min$ and $\max$. The six axioms are verified directly from the arithmetic of the interval: commutativity and associativity of $\oplus$ reduce to the associativity of truncated addition, $\neg\neg \alpha = 1-(1-\alpha)=\alpha$, and $\alpha \oplus 1 = \min(1,\alpha+1)=1$. This is the standard MV-algebra $[0,1]_{\mathrm{L}}$.

The truncation is what distinguishes the algebra from a ring: $\alpha \oplus \beta$ is not addition in $[0,1]$, and no subtraction is available except through $\neg$. The connection with the additive structure of the reals is made precise by Mundici's theorem below.

Chains, Finite Algebras and the Boolean Case

The Finite Chains

Definition. For $n \geq 1$ let

$$ \mathrm{L}_n = \left\{ 0, \tfrac{1}{n}, \tfrac{2}{n}, \dots, \tfrac{n}{n} = 1 \right\} $$

with the operations inherited from $[0,1]_{\mathrm{L}}$. This is the Łukasiewicz chain with $n+1$ elements.

The term "chain" is used because the order of $\mathrm{L}_n$ is total. Each $\mathrm{L}_n$ is a subalgebra of $[0,1]_{\mathrm{L}}$, and $\mathrm{L}_1 = \{0,1\}$ is the two-element algebra.

Theorem. For every $n \geq 1$ the algebra $\mathrm{L}_n$ is an MV-algebra, and it is generated as an MV-algebra by the single element $1/n$.

Proof. The set $\mathrm{L}_n$ is closed under $\alpha \oplus \beta = \min(1,\alpha+\beta)$ and under $\neg \alpha = 1-\alpha$ because the operations send multiples of $1/n$ to multiples of $1/n$. The element $1/n$ generates $1$ by repeated $\oplus$, then all $k/n$ for $k \leq n$, and the subalgebra generated is all of $\mathrm{L}_n$.

Example (three-valued logic). The chain $\mathrm{L}_2 = \{0, \tfrac12, 1\}$ is the three-valued Łukasiewicz algebra. With $u = \tfrac12$ one has $\neg u = u$, $u \oplus u = 1$ and $u \odot u = 0$, while $u \wedge \neg u = u \wedge u = u \neq 0$. The third truth value is neither true nor false, and the lattice meet of a proposition with its negation is a third value rather than false: this is the algebraic content of the failure of the law of non-contradiction in the lattice operations of the many-valued calculus.

Boolean Algebras as the Idempotent Case

Theorem. An MV-algebra $A$ is a Boolean algebra, for the lattice operations and the complement $\neg$, if and only if $\alpha \oplus \alpha = \alpha$ for every $\alpha \in A$.

Proof. Suppose $\oplus$ is idempotent. Then $\odot$ is idempotent too, since $\alpha \odot \alpha = \neg(\neg \alpha \oplus \neg \alpha) = \neg\neg \alpha = \alpha$. For idempotent operations the absorption identities $\alpha \oplus (\alpha \odot \beta) = \alpha$ and $\alpha \odot (\alpha \oplus \beta) = \alpha$ follow from (MV6), so $\oplus$ and $\odot$ are the join and the meet of the order, and the lattice is distributive by Chang's theorem; the identities $\alpha \oplus \neg \alpha = 1$ and $\alpha \odot \neg \alpha = 0$ then exhibit $\neg$ as a Boolean complement. Conversely, in a Boolean algebra take $\oplus = \vee$, $\odot = \wedge$ and $\neg$ the complement; then $\oplus$ is idempotent and the six axioms reduce to the Boolean laws of Boolean Algebras and Lattices.

Corollary. The Boolean algebras are exactly the idempotent MV-algebras. The idempotent elements of an MV-algebra $A$ form a subalgebra $B(A)$, the Boolean skeleton of $A$: it is closed under $\oplus$ because $(\alpha \oplus \beta) \oplus (\alpha \oplus \beta) = \alpha \oplus \beta$ for idempotent $\alpha$ and $\beta$, and closed under $\neg$ by the duality of $\oplus$ and $\odot$. With the inherited operations it is a Boolean algebra, it is the largest Boolean subalgebra of $A$, and $B(A) = A$ exactly when $A$ is Boolean. For the standard algebra $B([0,1]_{\mathrm{L}}) = \{0,1\} = \mathrm{L}_1 = \mathbf{2}$, and for the three-element chain $\mathrm{L}_2$ the skeleton is again $\{0,1\}$, the intermediate element $u$ not being idempotent.

The corollary isolates the Boolean system inside the many-valued one. The two-element algebra $\mathbf{2}$ is the Boolean skeleton of $[0,1]_{\mathrm{L}}$, and it is the only Boolean algebra that embeds in $[0,1]_{\mathrm{L}}$ as a subalgebra; the many-valued semantics is not the classical semantics with extra values attached, because the extra values are not idempotent and do not obey the excluded middle in the lattice operations.

Ideals, Quotients and Simple Algebras

Ideals and Homomorphisms

Definition. An ideal of an MV-algebra $A$ is a subset $I \subseteq A$ with $0 \in I$, closed under $\oplus$, and downward closed: $\alpha \in I$ and $\beta \leq \alpha$ imply $\beta \in I$. A filter is the order-dual notion, a subset containing $1$ and closed under $\odot$ and upward inclusion. An ideal is proper if $1 \notin I$ and maximal if it is proper and maximal under inclusion among proper ideals.

Theorem. An ideal $I$ is a congruence class of the congruence

$$ \alpha \sim_I \beta \iff (\alpha \odot \neg \beta) \oplus (\beta \odot \neg \alpha) \in I, $$

the quotient $A/I$ is an MV-algebra, and the quotient map is a homomorphism whose kernel is $I$. The quotient is nontrivial if and only if $I$ is proper, and the correspondence $I \leftrightarrow$ kernel is a bijection between ideals and kernels of homomorphisms.

Proof. The relation displayed is the standard MV-congruence associated with an ideal: it is reflexive and symmetric by construction, transitive by the triangle inequality of the derived distance $d(\alpha,\beta) = (\alpha \odot \neg \beta) \oplus (\beta \odot \neg \alpha)$, and compatible with the operations because $d$ is invariant under them. The quotient inherits the operations, and the kernel of the quotient map is $I$, since $d(\alpha,0) = (\alpha \odot \neg 0) \oplus (0 \odot \neg \alpha) = \alpha \oplus 0 = \alpha$, so that $\alpha$ is identified with $0$ exactly when $\alpha \in I$.

The map $d(\alpha,\beta) = (\alpha \odot \neg \beta) \oplus (\beta \odot \neg \alpha)$ is the Chang distance. It is a metric on $A$, bounded by $1$: it vanishes exactly when $\alpha \odot \neg \beta = 0 = \beta \odot \neg \alpha$, that is, exactly when $\alpha = \beta$, and it satisfies the triangle inequality by the MV laws. It is the algebraic ancestor of the distance used in the metric theory of MV-algebras.

Theorem (prime ideals). Every proper ideal of an MV-algebra is contained in a maximal ideal, every maximal ideal is prime in the sense that $A/I$ is totally ordered, and the quotient by a maximal ideal is a simple MV-algebra.

Proof. The first statement is Zorn's lemma applied to the chain-ordered family of proper ideals, the choice principle being that of Cardinality and the Axiom of Choice. For the second, if $A/I$ were not totally ordered it would contain incomparable elements, and the ideal generated on one side would produce a larger proper ideal; maximality is equivalent to linearity of the quotient. The quotient by a maximal ideal has no nontrivial proper ideals, hence is simple.

Simple MV-Algebras and the Representation Theorem

Theorem (Chang). An MV-algebra is simple if and only if it is isomorphic to a subalgebra of $[0,1]_{\mathrm{L}}$.

Proof. Both directions are Chang's. A subalgebra of $[0,1]_{\mathrm{L}}$ has no nontrivial proper ideal, since any nonzero element generates the unit and hence the whole algebra; conversely a simple MV-algebra has no nontrivial proper ideal; every simple MV-algebra is archimedean, and the archimedean simple MV-algebras are exactly the subalgebras of $[0,1]_{\mathrm{L}}$, the embedding being given by the unique state. The argument is quoted from Chang's paper.

Theorem (subdirect representation). Every MV-algebra is a subdirect product of totally ordered MV-algebras (MV-chains).

Proof. Let $\alpha \neq \beta$ in $A$; then the Chang distance $d(\alpha,\beta)$ is nonzero, and by Zorn's lemma there is an ideal maximal among the proper ideals not containing $d(\alpha,\beta)$. Such an ideal is prime, so the quotient is an MV-chain in which the images of $\alpha$ and $\beta$ remain distinct. The family of all these quotients therefore separates the points of $A$, and the induced map is the required subdirect embedding.

Theorem (Chang completeness, algebraic form). The variety of MV-algebras is generated by the single algebra $[0,1]_{\mathrm{L}}$: the smallest variety containing $[0,1]_{\mathrm{L}}$ is the class of all MV-algebras. Equivalently, an identity holds in every MV-algebra if and only if it holds in $[0,1]_{\mathrm{L}}$. Consequently, for every MV-algebra $A$ and all distinct $\alpha, \beta \in A$ there is a homomorphism $h : A \to [0,1]_{\mathrm{L}}$ with $h(\alpha) \neq h(\beta)$, and every free MV-algebra is a subdirect product of copies of $[0,1]_{\mathrm{L}}$.

Proof (sketch). The nontrivial half is that an identity failing in some MV-algebra fails in $[0,1]_{\mathrm{L}}$. Chang proves this by associating to each MV-algebra a lattice-ordered abelian group and using the archimedean embedding of its simple quotients in $[0,1]_{\mathrm{L}}$; the argument is quoted in full from the literature. The free algebra statement follows because the evaluation homomorphisms at the points of $[0,1]^n$ are surjective and separate the elements of $F_{\mathrm{MV}}(n)$.

Mundici's Theorem and Lattice-Ordered Groups

Lattice-Ordered Abelian Groups

Definition. A lattice-ordered abelian group (an ℓ-group) is an abelian group $(G, +)$ with a lattice order $\leq$ compatible with addition: $g \leq h$ implies $g + k \leq h + k$. A strong unit of $(G, +, \leq)$ is an element $u > 0$ such that for every $g \in G$ there is $n \geq 1$ with $g \leq n u$, where $nu$ is the $n$-fold sum.

The standard example is $(\mathbb{R}, +, \leq)$ with strong unit $1$. The positive cone $G^+ = \{g : g \geq 0\}$ is a submonoid, and every element is a difference of positive elements.

The Functor $\Gamma$

Theorem (Mundici). Let $(G, u)$ be an ℓ-group with strong unit and set

$$ \Gamma(G,u) = \{g \in G : 0 \leq g \leq u\} $$

with

$$ g \oplus h = u \wedge (g + h), \qquad \neg g = u - g, \qquad 0 = 0 . $$

Then $\Gamma(G,u)$ is an MV-algebra, and every MV-algebra is of this form: there is an ℓ-group $G(A)$ with strong unit $u$ and an isomorphism $A \cong \Gamma(G(A), u)$. The construction $A \mapsto G(A)$ is functorial, and $\Gamma$ is an equivalence of categories between MV-algebras and ℓ-groups with strong unit.

Proof. For the algebra structure: $\Gamma(G,u)$ is closed under $u \wedge (g+h)$ because the meet of $u$ with a positive element is between $0$ and $u$, and under $u - g$ because $0 \leq g \leq u$ gives $0 \leq u - g \leq u$. The six axioms follow from the distributivity of the lattice order and the compatibility of addition with it; (MV6) is the translation of the fact that in a lattice-ordered group the positive cone satisfies $(g \wedge h) + k \leq (g+k)\wedge(h+k)$ and one has the Riesz decomposition. The construction of $G(A)$ is by the Grothendieck completion of the monoid $A$ modulo the relations that make $\alpha \oplus \beta$ the truncated sum, and the strong unit is the class of $1$; the verification of the inverse equivalence is Mundici's theorem and is quoted.

Corollary. $\Gamma(\mathbb{R}, 1) = [0,1]_{\mathrm{L}}$, and $\Gamma(\mathbb{Z}, 1) = \mathrm{L}_1 = \{0,1\}$; more generally $\Gamma(\tfrac{1}{n}\mathbb{Z}, 1) = \mathrm{L}_n$.

Proof. The interval $[0,1]$ with $g \oplus h = 1 \wedge (g+h)$ is the standard algebra, and the interval $[0,1] \cap \mathbb{Z} = \{0,1\}$ is the two-element algebra. The last statement is the same computation in the cyclic group $\tfrac1n \mathbb{Z}$.

Mundici's theorem is the reason MV-algebras behave like ordered abelian groups: the lattice structure, the order and the truncated addition are all visible in $G(A)$, and the strong unit is the element whose interval is the algebra. The theorem is the many-valued counterpart of the embedding of a Boolean algebra into a power set, and it is the source of the connections between Łukasiewicz logic, integer programming and the real interval.

Free MV-Algebras and McNaughton's Theorem

The Free Algebra Problem

The free algebra on a set of generators is the algebra of terms modulo the identities of the variety. For a generator set of cardinality $n$ it is written $F_{\mathrm{MV}}(n)$. The Boolean case is the algebra of Boolean functions, of cardinality $2^{2^n}$; the many-valued case is described by continuous piecewise-linear functions.

McNaughton Functions

Definition. A McNaughton function on $[0,1]^n$ is a continuous function $f : [0,1]^n \to [0,1]$ for which there are finitely many linear functions with integer coefficients,

$$ \ell_i(x) = a_i + m_{i1} x_1 + \cdots + m_{in} x_n, \qquad a_i, m_{ij} \in \mathbb{Z}, $$

such that for every $x \in [0,1]^n$ one has $f(x) = \ell_i(x)$ for some $i$. The set of McNaughton functions is written $M([0,1]^n)$; it is an MV-algebra under the pointwise operations.

Theorem (McNaughton). The free MV-algebra $F_{\mathrm{MV}}(n)$ on $n$ generators is isomorphic to $M([0,1]^n)$, the isomorphism sending the $i$-th generator to the coordinate function $x \mapsto x_i$. In particular $F_{\mathrm{MV}}(n)$ is countably infinite for every $n \geq 1$.

Proof. A term in the generators evaluates to a function on $[0,1]^n$ built from the coordinate functions by $\oplus$ and $\neg$, and each such function is McNaughton because the operations preserve the class: $\min(1, f+g)$ and $1-f$ of McNaughton functions are again continuous and piecewise linear with integer pieces. The map is therefore well defined and surjective, since McNaughton functions are exactly the finite max-min combinations of the integer-linear ones, by the standard piecewise-linear approximation. To see that it is injective, let $t$ and $s$ be terms that define the same function; since the variety is generated by $[0,1]_{\mathrm{L}}$, an identity holding in that algebra holds in every MV-algebra, so $t$ and $s$ are equal in the free algebra. Hence the map is an isomorphism. The countability is clear from the finite description of a McNaughton function.

Example. For $n = 1$ the free algebra is generated by the identity function $\alpha$. The function $\alpha \oplus \alpha = \min(1,2\alpha)$, the function $\neg \alpha = 1-\alpha$, and the iterated truncated sums $\min(1,k\alpha)$ all lie in $M([0,1])$, so $F_{\mathrm{MV}}(1)$ already contains functions with arbitrarily many linear pieces and is infinite. This is the many-valued analogue of the Rieger–Nishimura lattice of Heyting Algebras and Intuitionistic Logic, and it shows that the free MV-algebra, like the free Heyting algebra but unlike the free Boolean algebra, is infinite; the difference is that $M([0,1]^n)$ is still described by a single continuously-valued standard algebra.

Corollary. The freeness of $F_{\mathrm{MV}}(n)$ is witnessed by its embeddings into the algebra of all functions $[0,1]^n \to [0,1]$; the free algebra on $n$ generators is the algebra of the definable functions of the standard interval, and the algebraic semantics is the fragment of continuous piecewise-linear real geometry with integer coefficients.

Many-Valued Logic

Łukasiewicz Logic

Definition. The formulas of Łukasiewicz propositional logic $\mathrm{L}$ are built from propositional variables by the connectives $\neg$ and $\to$; the derived connectives are $\alpha \oplus \beta = \neg \alpha \to \beta$, $\alpha \odot \beta = \neg(\alpha \to \neg \beta)$, $\alpha \vee \beta = (\alpha \to \beta) \to \beta$ and $\alpha \wedge \beta = \alpha \odot (\alpha \to \beta)$. A valuation is a map $v$ from the variables to $[0,1]$, extended by $$ v(\neg\varphi) = 1 - v(\varphi), \qquad v(\varphi \to \psi) = \min(1, 1 - v(\varphi) + v(\psi)). $$ A formula is a tautology if $v(\varphi) = 1$ for every valuation, and $\mathrm{L}$ is the logic whose theorems are the tautologies. Equivalently, valuations into $[0,1]_{\mathrm{L}}$ are exactly the homomorphisms from the free MV-algebra on the variables to $[0,1]_{\mathrm{L}}$.

Algebraic Completeness

Theorem (Chang completeness). For every formula $\varphi$ of $\mathrm{L}$,

$$ \vdash_{\mathrm{L}} \varphi \iff v(\varphi) = 1 \text{ for every valuation } v : \mathrm{Vars} \to [0,1] . $$

Proof. Soundness is induction on the length of the derivation: the Łukasiewicz axioms of the Hilbert system for $\mathrm{L}$ are identities of MV-algebras, each of which is verified in $[0,1]_{\mathrm{L}}$, and the rules preserve the value $1$. For completeness, the Lindenbaum algebra $F$ of $\mathrm{L}$ is an MV-algebra, and the valuations are exactly the homomorphisms from the term algebra to $[0,1]_{\mathrm{L}}$ that respect provable equivalence; by Chang's theorem the homomorphisms to $[0,1]_{\mathrm{L}}$ separate the points of $F$, so if $\varphi$ is not a theorem and its class is therefore not $1$, some valuation sends $\varphi$ to a value different from $1$.

Corollary. The logic $\mathrm{L}$ is the logic of the standard interval, and the many-valued semantics is complete: the interval supplies all the counterexamples needed. The finite chains $\mathrm{L}_n$ give the finite-valued Łukasiewicz logics $\mathrm{L}_n$, and a formula valid in $[0,1]_{\mathrm{L}}$ is valid in each $\mathrm{L}_n$ because $\mathrm{L}_n$ is a subalgebra. Conversely, a counterexample on $[0,1]$ can be perturbed, since the operations $\min(1,\cdot)$, $1-\cdot$ and $+$ are continuous, to one whose values all lie in $\tfrac1n\mathbb{Z}$ for some $n$, and it is then a counterexample in $\mathrm{L}_n$; hence the tautologies of the infinite-valued logic are exactly the formulas tautological in every finite-valued logic, and $\mathrm{L}$ is the intersection of the logics $\mathrm{L}_n$.

Comparison with the Boolean and Intuitionistic Systems

Three systems of propositional logic have now appeared in the algebra slot of the Boolean category, and their algebras are distinct:

Logic	Algebras	Standard model	Characteristic algebra?
Classical	Boolean algebras	$\mathbf{2}$	Yes, $\mathbf{2}$ alone generates the variety
Many-valued (Łukasiewicz)	MV-algebras	$[0,1]_{\mathrm{L}}$	Yes, $[0,1]_{\mathrm{L}}$ alone generates the variety
Intuitionistic	Heyting algebras	$\mathcal{O}(X)$, frames	No finite set of finite algebras suffices

The classical and Łukasiewicz logics each have a single generating algebra, and their free algebras are concrete: Boolean functions and McNaughton functions respectively. The intuitionistic calculus does not, by the finiteness theorem of Heyting Algebras and Intuitionistic Logic; its characteristic semantics is the variety of Heyting algebras, not a single finite or interval algebra. The three systems are therefore different answers to the question of what replaces the two-element domain, and the answer "the unit interval with the Łukasiewicz operations" is the continuous answer, with $\mathbf{2}$ recovering the classical case by idempotence.

Summary

An MV-algebra is a set with a commutative monoid operation $\oplus$, an involution $\neg$ and a zero $0$ satisfying Chang's six axioms; the order $\alpha \leq \beta \iff \alpha \odot \neg \beta = 0$ is a distributive lattice order with bounds $0$ and $1 = \neg 0$, and the lattice operations are $\alpha \wedge \beta = \alpha \odot (\alpha \to \beta)$ and $\alpha \vee \beta = (\alpha \to \beta) \to \beta$. The standard example is the unit interval with $\alpha \oplus \beta = \min(1,\alpha+\beta)$ and $\neg \alpha = 1-\alpha$; the finite chains $\mathrm{L}_n = \{0, 1/n, \dots, 1\}$ are its finite subalgebras, $\mathrm{L}_1$ is the two-element algebra, and an MV-algebra is a Boolean algebra exactly when $\oplus$ is idempotent. The subalgebras of $[0,1]_{\mathrm{L}}$ are exactly the simple MV-algebras, the maximal ideals have simple quotients, and every MV-algebra is a subdirect product of subalgebras of $[0,1]_{\mathrm{L}}$; consequently the variety of MV-algebras is generated by the single algebra $[0,1]_{\mathrm{L}}$.

Mundici's theorem identifies this variety with the category of lattice-ordered abelian groups with strong unit through the functor $\Gamma(G,u) = \{g : 0 \leq g \leq u\}$ with $g \oplus h = u \wedge (g+h)$; the standard algebra is $\Gamma(\mathbb{R},1)$ and the finite chains are the intervals in $\tfrac1n\mathbb{Z}$. McNaughton's theorem describes the free MV-algebra on $n$ generators as the algebra of continuous piecewise-linear functions on $[0,1]^n$ with integer coefficients, which is countably infinite and is the many-valued analogue of the Rieger–Nishimura lattice.

Łukasiewicz propositional logic is the logic of the standard algebra: its connectives are the MV-operations, its valuations are the homomorphisms into $[0,1]_{\mathrm{L}}$, and Chang's completeness theorem states that its theorems are exactly the formulas taking the value $1$ under every valuation. The classical logic is recovered as the idempotent case, and the intuitionistic logic is a different and genuinely non-finitely-valued system; the three algebras of the Boolean category — Boolean, MV and Heyting — are the three answers to replacing the two-element domain, and they separate on finiteness: a finitely generated Boolean algebra is finite, whereas the free MV-algebra and the free Heyting algebra on one generator are already infinite.

Summary of Notation

Symbol	Meaning
$A$	An MV-algebra
$\oplus$	Commutative monoid operation, truncated addition in $[0,1]$
$\odot$	Product, $\alpha \odot \beta = \neg(\neg \alpha \oplus \neg \beta)$
$\neg$	Involution, $\neg\neg \alpha = \alpha$
$\to$	Residuum, $\alpha \to \beta = \neg \alpha \oplus \beta$
$0, 1 = \neg 0$	Least and greatest elements
$\leq$	Order, $\alpha \leq \beta \iff \alpha \odot \neg \beta = 0$
$\wedge, \vee$	Lattice meet and join of the order
$[0,1]_{\mathrm{L}}$	Standard MV-algebra, $\alpha \oplus \beta = \min(1,\alpha+\beta)$, $\neg \alpha = 1-\alpha$
$\mathrm{L}_n$	Łukasiewicz chain $\{0, 1/n, \dots, 1\}$ with $n+1$ elements
$d(\alpha,\beta)$	Chang distance, $(\alpha \odot \neg \beta) \oplus (\beta \odot \neg \alpha)$
$\Gamma(G,u)$	Mundici functor, interval $[0,u]$ of an ℓ-group with strong unit
$F_{\mathrm{MV}}(n)$	Free MV-algebra on $n$ generators
$M([0,1]^n)$	McNaughton functions on the cube
$\vdash_{\mathrm{L}}$	Derivability in Łukasiewicz logic
$B(A)$	Boolean skeleton, the idempotent elements of $A$
$\mathbf{2}$	Two-element Boolean algebra, $\mathrm{L}_1$