If a relation on a set is reflexive, antisymmetric and transitive then it is called a partial ordering.
The directed graph of a partial ordering relation contains no circuit of length greater than 1.
Partial ordering is denoted as " < " with " > " denoting the inverse relation.
Poset means a partly ordered set. That is, it contains a set S and a partial ordering relation on this set. Therefore a poset can be denoted as [S,<]. This also denoted the graph of the relation < on S.
a is the immediate predecessor of b if a < b and there is no c like a < c < b. This situation is considered in a poset [S,<]. The inverse relation is called the immediate successor.
Immediate predecessor which is not reflexive, symmetric or transitive is defined on a poset, this means that it implies an underlying partial ordering.
More : Partially
ordered sets , poset
structure , posets
, posets
and lattices ,
For a and b in a poset [S,<] a least upper bound or join or sum of a and b is an element of c of S satisfying the relationship a < c and b < c. There appeares no other x in S satisfying a < x < c and b < x < c. Two elements having a unique join is denoted as ( a \/ b).
A poset whose any two elements have unique join and meet is called a lattice. A lattice is denoted as [S,\/,/\].
A lattice L = [S',+, .] is called a sublattice of another lattice L = [S,\/,/\] if S' is a subset of S and + and . are the respective restrictions of \/ and /\ to S'. (+ and . must be closed in S')
An element of a lattice L is join-irreducible if x \/ y = a means either x = a or y = a.
If all chains in a lattice are infinite then every element in the lattice can be represented as a join of a finite number of join-irreducible elements of the lattice. These lattices are of finite lengths.
In a distributive lattice of finite length, each element has a unique representation as the join of an irreduntant set of join-irreducible elements.
A
small selfquiz about this chapter
Date of Last Update: June 18, 1997