is said to be partially ordered or a poset if there is a binary relation
"
"
defined on
such that
.
Definitions and Notation:
Reviewing, A set,
is said to be partially ordered or a poset if there is a binary relation
""
defined on
such that
For all
For all
and
For all
and
We will use the notation
to represent the pair
.
Remember a chain in a poset
to be a totally ordered subset
.
That is for any
or
.
We introduce the notation
for
the subset of chains of
We also introduce the notation
for
the Well Ordered chains
Given
, let
An element
is called an upper bound for
if
for
all
. Suppose also that
for all upper bounds
of
then
is called the least upper bound (l.u.b.). Define
lower bound and greatest lower bound
(g.l.b.) is a similar manner. We will sometimes also use the
notation,
and
.
If
is also an upper bound for
then it is called the top element of
.
Note that being the top element implies uniqueness and that it is the least
upper bound. Define the bottom element similarly.
Finally,
Let
be a given set. We also introduce the notation
for the Set of subsets of
One verifies that
is a poset . Note that any
has a least upper bound and a greatest lower bound given be set union and
intersection,
and
.
Definitions: A poset
(
)
is called a "lattice" if every pair of elements
has a l.u.b., written
and a g.l.b., written
.
Note that this implies that any finite set of elements has a g.l.b. and l.u.b.
Why?
Note that, trivially
and
A lattice is complete if every subset
has a l.u.b. and a
g.l.b.(
may be infinite!)
A lattice is distributive if
and
for all
.
A lattice is complemented if
it has a top and bottom elements
and
.
for every
there is an element
such that
and
.
Check that
is unique
in a complemented distributive lattice.
A complemented distributive lattice is called a Boolean algebra.
Examples of Boolean algebras:
The algebra of subsets of a given Set.
,under
the usual rules of logic.
n-bit binary words. ("computer logic")