JAIST seminar talk

<h3>
Lattice Ordered Groups and Residuated Lattices
</h3>

<h3>
Peter Jipsen
</h3>
<h3>
Vanderbilt University
</h3>
JAIST seminar talk, 21 January 2002
 
 
 
 

<img src=../../PCP/Birkhoff_Garrett_2.jpeg>
 

Garrett Birkhoff 1911 - 1996
</center>

Equational Logic is the logic of "substituting equals for equals" and is well-known
informally to anyone in high school.

In 1935 Birkhoff laid the foundations of the mathematical theory by proving that
the rules of equational logic are complete with respect to algebraic semantics.

This lead to extensive research in universal algebra.

Recall that an identity is a universal formula of the form
$s=t$, where $s,t$ are terms in some algebraic signature.

E.g. $(x\cdot y)\cdot z=x\cdot (y\cdot z)$ is the
associative identity.

A quasi-identity is a universal formula of the form
<center>
$s_1=t_1\mbox{ and }\ldots\mbox{ and }s_n=t_n\ \Rightarrow\ s_0=t_0$
</center>
where $s_i,t_i$ are terms.

E.g. $x\cdot z=y\cdot z\Rightarrow x=y$ is the quasi-identity for right-cancellativity.

Lattice-ordered groups ($l$-groups) are algebras of the form
$\m L=\<L,\vee,\wedge,\cdot, e,^{-1}\>$ such that
<blockquote>
(L)   $\<L,\vee,\wedge\>$ is a lattice, i.e., $\vee, \wedge$ are 
associative, commutative and absorbtive (for all $x,y$, $(x\vee y)\wedge x=x=(x\wedge y)
\vee x$)

$\hence$ $x\vee x=x$, $x\wedge x=x$ (Exercise 1; consider $((x\vee x)\wedge x)\vee x$)

Definition: $x\le y$ iff $x\vee y=y$ (iff $x\wedge y=x$), then $\le$ is a partial order.

(G)   $\<L,\cdot,e,^{-1}\>$ is a group, i.e., $\cdot$ is
associative, $x\cdot e=x$ and $x\cdot x^{-1}=e$

$\hence$ $e\cdot x=x$ and $x^{-1}\cdot x=e$ (Exercise 2; show $e\cdot x=e\cdot x^{-1}^{-1}=x$)

We write $x\cdot y=xy$ and apply $\cdot$ before $\vee,\wedge$. E.g. $xy\vee z=(x\cdot y)\vee z$.
We also define $x^0=e$ and $x^{n+1}=xx^n$.

(O)   $w(x\vee y)z=wxz\vee wyz$ (for all $w,x,y,z\in L$)

equivalent to $x\le y\Rightarrow xz\le yz\mbox{ and }zx\le zy$ (Exercise 3)

equivalent to $w(x\wedge y)z=wxz\wedge wyz$ (for all $w,x,y,z\in L$)

$\hence$ any $l$-group is torsion free, i.e., $x^n=e\Rightarrow x=e$ (Exercise 4)

$\hence$ any nontrivial $l$-group is infinite.
</blockquote>

Small surprise: (L), (G), (O) imply that $\m L$ is distributive: $x\wedge (y\vee z)=
(x\wedge y)\vee(x\wedge z)$. (Exercise 5; medium surprise: this is not so obvious)

Examples: $\m Z=\<\{\ldots, -1, 0, 1, \ldots\},\vee,\wedge,+,0,-\>$, where
$x\vee y=\max(x,y)$ and $x\wedge y=\min(x,y)$.

$A(\m R)=\<\{\mbox{order automorpisms of the reals}\},\vee, \wedge, \circ,
id_{\m R}, ^{-1}\>$ where the elements are onto function
$f:\m R\to\m R$ such that $x<y\Rightarrow f(x)<f(y)$, with

$(f\vee g)(x)=\max(f(x),g(x))$, $(f\wedge g)(x)=\min(f(x),g(x))$,
$(f\circ g)(x)=f(g(x))$.

Big surprise (C. Holland [1976]): every identity that fails in some
$l$-group, fails in $A(\m R)$.

This result forms the basis of the decision procedure for $l$-group identities by Holland
and McCleary [1979].

$\m{LG}=$class of all $l$-group$=\mbox{Mod}\{(\m L), (\m G), (\m O)\}$, i.e., $\m{LG}$
is an equational class.

$\hence$ (Birkhoff [1935]) $\m{LG}$ is a variety, i.e., closed under homomorphic images,
subalgebras and (cartesian) products. 

E.g. $\m Z\times\m Z\in\m{LG}$. (Exercise 6: show that $\m Z\times\m Z$ is generated
by a single element.)

$f:\m L\to\m M$ is a homomorphism if $f(x\diamond y)=f(x)\diamond f(y)$ for
$\diamond\in\{\vee,\wedge,\cdot\}$ ($\hence$ $f(e)=e$ and $f(x^{-1})=f(x)^{-1}$)

Let $\m K$ be any class of algebras of the same similarity type. 

$\m H(\m K)=\{\m M\ |\ f:\m L\to\m M\ \mbox{for some onto homomorphism}\ 
f,\mbox{ some }\m L\in \m K\}$

$\m S(\m K)=\{\m M\ |\ f:\m M\to\m L\ \mbox{for some 1-1 homomorphism}\ 
f,\mbox{ some }\m L\in \m K\}$

$\m P(\m K)=\{\prod_{i\in I}\ \m L_i\ |\ I\ \mbox{ is some set and }\
\m L_i\in \m K\mbox{ for all }i\in I\}$

Tarski [194?]: $\m{HSP}(\m K)$ is the smallest variety containing $\m K$.

E.g. $\m{LG}=\m{HSP}\{A(\m{R})\}$.

Define $\m V(\m K)=\m{HSP}(\m K)$.

Lattices of subvarieties $\m L(\m{LG})$ 

where $\m V\wedge \m W=\m V\cap\m W$ and

$\m V\vee\m W=\m{HSP}(\m V\cup\m W)$.

<a href=../../gap/lambdaRL1.html>Some subvarieties of $l$-groups, ordered by inclusion</a>

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

</center>