UFL Talk

Theorem: The universal theory (equivalently the quasi-equational
theory) of residuated lattices is undecidable. The same holds for any
subvariety that contains all powersets of finite monoids.

Proof: Consider the `*`-reducts of RL. The quasi-identities
that use only `*` and hold in all residuated lattices, also hold in all
subsets of residuated lattices that are closed under `*`. 

Let `bf(SG)` be the variety of all semigroups.

Any semigroup `S` can be embedded in the
`*`-reduct of some residuated lattice: 

Embed `S` in a monoid `S_e` and construct the powerset `P(S_e)`, which is
a complete residuated lattice. 

The collection of singletons is closed
under `*` and isomorphic to `S_e`.

<center>
`bf(SG) subset bf(S.Rd)_{(*)}.bf(RL) subset bf(SG)`
</center>

But the quasi-equational theory of semigroups is undecidable. Hence the same
is true for residuated lattices.

For the second part, use the result that the quasi-equational theory
of semigroups is recursively inseparable from the quasi-equational 
theory of finite semigroups. `qed`

Since `P(S_e)` is distributive, it follows that the variety of
distributive residuated lattices has an undecidable quasi-equational
theory.

But for commutative residuated lattices this argument does not
work.

Theorem (N.Galatos 2000): The local word
problem (and hence the quasi-equational theory)
for commutative distributive residuated lattices is undecidable.

More recent results by W. Blok and C.J. van Alten

<a href=ufltable.htm>Decidability Table</a>

To correct the false impression that all varieties of residuated
lattices have decidable equational theory:

Theorem: The variety of modular residuated lattices
has an undecidable equational theory.

Proof: Let `M` be a modular lattice.

Let `A=M uu {0,e,T}` where `(0<e)<x<T` for all `x in M`. 

Then `A` is still modular (in fact in the same variety as `M`)

Define `*` on
`A` by `x*0=0=0*x`, `x*e=x=e*x` and `x*y=T` if `x,y != 0,e`. 

It is easy to check that `*` is associative and residuated.

Hence the `vv,^^`-equational theory of modular residuated lattices
coincides with the equational theory of modular lattices

Since modular lattices have an undecidable equational theory
(R. Freese 1980), the same is true for modular residuated lattices.
`qed`

<center>
<a href=ufltalk2.htm>Next</a>
</center>