Lattice

  Hasse Diagram:

                    Hasse diagram is used to represent POSET in a diagrammatic way! For each subset of Hasse Diagram there may be one or more upper bounds and lower bounds.

For example consider the following Hasse diagram. For example the subset {a,b} have upper bounds b,d,e,f and lower bounds a.
The subset {b,c} have upper bounds d,e,f,g and lower bounds a.

Lattice:
                    
                             For every subset of POSET there exists many lower and upper bounds. A lattice is defined on POSET as for every subset of Hasse Diagram there must be one least upper bound and greatest lower bound.

For example consider the following diagram

The set {a,b} have least upper bound 'b' and greatest lower bound 'a'

The set { b,c} have least upper bound 'd' and greatest lower bound  'a'

The set {e,f} have least upper bound 'g' and greatest lower bound 'd'

The set {e,d} have least upper bound 'e' and greatest lower bound 'd'

Similarly the remaining subsets can be proved

Hence the given POSET is Lattice


Consider another Hasse Diagram given below.

The above diagram is not Lattice since

for example the set {b,c} does not have least upper bound.(since we cannot compare e and f)



lattice, POSET, patial ordered set, equivalence relation, compatibility relation, partially ordered relation, reflexive, transitive, symmetric relation , anti symmetric relation, symmetric relation, upper bounds, lower bounds, least upper bound greatest lower bound, GLB, LUB,  join,meet, cross product, partitions, covering 

Hasse Diagram

Partially Ordered Set (POSET): 

                                   A relation which is reflexive, anti symmetric and transitive is called POSET.

Example: >= and <= are examples of POSET

  Example:
             let A={1,2,3} and the relation R is defined on A such that R={(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)} is a partially ordered set.

R is reflexive since (1,1),(2,2),(3,3) belongs to R\

R is ant symmetric for example (1,2) belongs to R and (2,1) does not belong to R. Similarly (2,3)
belongs to R and (3,2) does not belong to R .

R is transitive since (1,2) and (2,3) belongs to R then (2,3) belongs to R

So R is Partially Ordered Set

Hasse Diagram:
                          Hasse diagram is used to represent POSET in a diagramatic way.

For two elements a and b, b is said to be immediate successor of a if and only if  there is no intermediate element between a and b.

Two elements are said to be comparable if the two elements can be compared by using less than or greater than.

If two elements are on the same level and the two elements are incomparable then the two elements are said to be incomparable

Draw the Hasse Diagram for the divisibility on the set { 1,2,3,6,8,12}

The following are the ordered pairs in divisibility set {(1,1),(2,2),(3,3),(6,6),(8,8),(12,12),(1,2),(1,3),(1,6),(1,8),(1,12),(2,6),(2,8),(2,12),(3,6),(3,12),(6,12)}

Since 1 divides 3 , 1 and 3 are on the same line and 3 divides 6, 3 and 6 are on the same line. Since the given relation is transitive 1 divides 3 and 3 divides 6 so 1 divides 6. Similarly 1 divides 12 and so on.

Lower Bound of above Hasse diagram is 1 and Upper Bound of above Hasse Diagram is 12



partially ordered set, POSET, Hasse diagram, lower boinds, upper bounds, transitive relation, anti symmetric relation, reflexive relation,  Lattice, Least Upper Bound, Greatest Lower Bound. meet, join divisibility on set. equivalence relation, compatibility relation 

Different types of Relations

                Let A be a set. Then the relation R on A is defined as subset of A*A.

for example A={1,2,3}

cross product A*A={(1,1),(1,2),(1,3).(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

 R={(1,1),(2,3),{3,0)} is a subset if A*A. So R is relation on A

Reflexive Relation:

A relation R on A is of the form {(a,a)/a belongs to A} is called reflexive relation.

A={1,2,3}

R={(1,1),(2,2),(3,3)} is reflexive relation.

R={(1,1),(2,2)} is not reflexive since (3,3) ordered pair is missing in relation R

Symmetric Relation:
                               A relation R on A is defined as if there exist (a,b) belongs to R then (b,a) belongs to R such a relation is called symmetric  relation

A={1,2,3}

R={(1,1),(1,2),(2,1),(3,1),(1,3)} is a symmetric relation

R1={(1,1),(1,2),(2,1),(3,1),(3,3)} is not a symmetric relation since (3,1) belongs to R1 but (1,3) ordered pair is missing in relation R


Transitive Relation:

    The transitive relation is defined as if (a,b)belongs to R and (b,c) belongs to R then (a,c) belongs to R

Let A={1,2,3}

R={(1,1),(1,2),(2,1),(3,1),(1,2),(3,2)} is a transitive relation.

R1={(1,1),(1,2),(2,1),(3,2)} is not transitive since (3,2) and (2,1) belongs to R but there is not ordered pair (3,1) in R1

Anti Symmetric Relation:
  A relation R on A is defined as if there exist (a,b) belongs to R then (b,a) does not belongs to R such a relation is called anti symmetric relation

A={1,2,3}

R={(1,1),(1,2),(2,1),(3,1),(1,3)} is not anti symmetric relation because for example (1,2) and (2,1) belongs to R

R1={(1,1),(1,2),,(3,1),(3,3)} is anti symmetric relation,


Note: An identity relation is reflexive, symmetric, anti symmetric and transitive

Equivalence relation:

                      A relation is said to be transitive relation if it is reflexive, symmetric and transitive.

R={(1,1),(1,2),(2,1)} is transitive relation

Partial Ordered Set(POSET):
                   A relation is said to partial ordered set if it is reflexive, anti symmetric and transitive relation .

R1={(1,1),(1,2),(2,2),(3,2)} is partial ordered set .



relations, sets, cross products, functions, identity relation , reflexive relation, symmetric relations anti symmetric relation transitive relation , poset, equivalence relation, hasse diagram, lattice, 

   

Covering and Partition

Covering

           Let S be a set and let S1,S2,,,,,,,,Sn be the subsets of S such that S1unionS2unionS3.......union Sn=S. Then S1, S2, S3....... Sn are said to be covers of S

Ex let S={1,2,3,4} and
A1={{1,2,3},{4,5}}
A2={{1,2,3},{3,5}}
A3={{1,2,3,4}}
A4={{1,2,3},{3,4,5}}

Then A1 is said to be cover of S
         A2 is not a cover of S since 4 is missing
         A3 is said to be cover of S
         A4 is said to be cover of S


Partition:
          Let S be a set and let S1,S2,,,,,,,,Sn be the disjoint  subsets of S such that                                               S1unionS2unionS3.......union Sn=S. Then S1, S2, S3....... Sn are said to be partitions of S.

Ex let S={1,2,3,4} and
A1={{1,2,3},{4,5}}
A2={{1,2,3},{3,5}}
A3={{1,2,3,4}}
A4={{1,2,3},{3,4,5}}

Then A1 is said to be cover of S
         A2 is not a cover of S since 4 is missing
         A3 is said to be cover of S
        A4 is not a partition since the given two subsets are not disjoint i.e., 3 is the common element.

Note: Every partition is a covering but not all  coverings are partitions



partition and covering, hass diagram, poset, lattice, pigeon hole principle, inclusion and exclusion principle transitive closure, compatibility relation