Database Reference
In-Depth Information
It is distributive if it satisfies the distributivity laws:
6.
a
∨
(b
∧
c)
=
(a
∨
b)
∧
(a
∨
c)
,
a
∧
(b
∨
c)
=
(a
∧
b)
∨
(a
∧
c)
.
A lattice
W
is
complete
if each (also infinite) subset
S
⊆
W
(or,
S
∈
P
(W)
where
P
∅∈
P
is the powerset symbol, with the empty set
(W)
) has the least upper
bound (lub, supremum) denoted by
S
∈
W
. When
S
has only two elements,
the supremum corresponds to the join operator '
'. Each finite bounded lattice
is a complete lattice. Each subset
S
has the greatest lower bound (glb, infimum)
denoted by
S
∈
W
, given as
{
a
∈
W
|∀
b
∈
S.a
≤
b
}
∨
. A complete lattice is
=
∅=
W
∈
W
and the top element
bounded and has the bottom element 0
=
∅=
W
∈
W
. An element
a
∈
W
is
compact
iff whenever
S
exists and
a
≤
S
for
S
⊆
W
then
a
≤
S
for some finite
S
⊆
W
.
W
is
compactly gen-
erated
iff every element in
W
is a supremum of compact elements. A lattice
W
is
algebraic
if it is complete and compactly generated.
A function
l
:
W
→
Y
between the posets
W,Y
is
monotone
if
a
≤
a
implies
l(a)
1
l(a
)
for all
a,a
∈
≤
W
. Such a function
l
:
W
→
Y
is said to have a right
(or upper) adjoint if there is a function
r
:
Y
→
W
in the reverse direction such
that
l(a)
≤
b
iff
a
≤
r(b)
for all
a
∈
W,b
∈
Y
. Such a situation forms a Galois
connection and will often be denoted by
l
r
. Then
l
is called a left (or lover)
adjoint of
r
.If
W,Y
are complete lattices (posets) then
l
:
W
→
Y
has a right adjoint
iff
l
preserves all joins (it is
additive
, i.e.,
l(a
0
Y
where 0
W
,
0
Y
are bottom elements in complete lattices
W
and
Y
, respectively). The
right adjoint is then
r(b)
∨
b)
=
l(a)
∨
l(b)
and
l(
0
W
)
=
=
{
c
∈
W
|
l(c)
≤
b
}
. Similarly, a monotone function
r
W
is a right adjoint (it is
multiplicative
, i.e., has a left adjoint) iff
r
preserves
all meets; the left adjoint is then
l(a)
:
Y
→
=
{
c
∈
Y
|
a
≤
r(c)
}
.
Y
on a complete lattice (poset)
W
has both the
least
fixed point (Knaster-Tarski)
μl
Each monotone function
l
:
W
→
∈
W
and
greatest
fixed point
νl
∈
W
. These
=
{
=
{
can be described explicitly as:
μl
a
∈
W
|
l(a)
≤
a
}
and
νl
a
∈
W
|
a
≤
l(a)
.
In what follows, we write
b<a
iff (
b
}
≤
a
and not
a
≤
b
) and we denote by
a
b
two unrelated elements in
W
(so that not
(a
≤
b
or
b
≤
a)
). An element in a
lattice
c
=
0isa
join-irreducible
element iff
c
=
a
∨
b
implies
c
=
a
or
c
=
b
for
∈
∈
any
a,b
W
. An element in a lattice
a
W
is an
atom
iff
a>
0 and
b
such that
a>b>
0.
A lower set (down closed) is any subset
Y
of a given poset
(W,
≤
)
such that, for
all elements
a
and
b
,if
a
Y
.
A
Heyting algebra
is a distributive bounded lattice
W
with finite meets and joins
such that for each element
a
∈
W
, the function
(
_
)
∧
a
:
W
→
W
has a right adjoint
a(
_
)
, also called an algebraic implication. An equivalent definition can be given
by considering a bonded distributive lattice such that for all
a
and
b
in
W
there
is a greatest element
c
in
W
, denoted by
ab
, such that
c
∧
a
≤
b
, i.e.,
a
b
=
{
c
∈
W
|
c
∧
a
≤
b
}
≤
b
and
b
∈
Y
then
a
∈
(relative pseudo-complement). We say that a lattice is
relatively pseudo-complemented
(r.p.c.) lattice if
ab
exists for every
a
and
b
in
W
. Thus, a Heyting algebra is, by definition, an r.p.c. lattice that has 0.
Formally, a distributive bounded lattice
(W,
,
0
,
1
)
is a Heyting algebra
iff there is a binary operation
on
W
such that for every
a,b,c
≤
,
∧
,
∨
∈
W
:
