{"id":3028,"date":"2025-06-07T15:05:09","date_gmt":"2025-06-07T15:05:09","guid":{"rendered":"https:\/\/diznr.com\/?p=3028"},"modified":"2025-06-07T15:05:09","modified_gmt":"2025-06-07T15:05:09","slug":"day-03part-08-discrete-mathematics-for-gate-concept-of-least-upper-bound-and-greatest-bound-lower","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/day-03part-08-discrete-mathematics-for-gate-concept-of-least-upper-bound-and-greatest-bound-lower\/","title":{"rendered":"Day 03Part 08-Discrete mathematics for gate- Concept of Least upper bound and greatest lower bound."},"content":{"rendered":"

Day 03Part 08-Discrete mathematics for gate- Concept of Least upper bound and greatest lower bound.<\/p>\n

[fvplayer id=”223″]<\/p>\n

Least Upper Bound (LUB) and Greatest Lower Bound (GLB) – Discrete Mathematics (GATE)<\/strong><\/h3>\n

The concepts of Least Upper Bound (LUB)<\/strong> and Greatest Lower Bound (GLB)<\/strong> are essential in partially ordered sets (posets)<\/strong> in Discrete Mathematics<\/strong>. These are also known as Supremum (sup)<\/strong> and Infimum (inf)<\/strong>, respectively.<\/p>\n

1. Partial Order & Lattice Basics<\/strong><\/h3>\n

A poset (Partially Ordered Set)<\/strong> is a set SS<\/span>S<\/span><\/span><\/span><\/span> with a relation \u2264\\leq<\/span>\u2264<\/span><\/span><\/span><\/span> that satisfies:
Reflexivity<\/strong>: a\u2264aa \\leq a<\/span>a<\/span>\u2264<\/span><\/span>a<\/span><\/span><\/span><\/span>
Antisymmetry<\/strong>: If a\u2264ba \\leq b<\/span>a<\/span>\u2264<\/span><\/span>b<\/span><\/span><\/span><\/span> and b\u2264ab \\leq a<\/span>b<\/span>\u2264<\/span><\/span>a<\/span><\/span><\/span><\/span>, then a=ba = b<\/span>a<\/span>=<\/span><\/span>b<\/span><\/span><\/span><\/span>.
Transitivity<\/strong>: If a\u2264ba \\leq b<\/span>a<\/span>\u2264<\/span><\/span>b<\/span><\/span><\/span><\/span> and b\u2264cb \\leq c<\/span>b<\/span>\u2264<\/span><\/span>c<\/span><\/span><\/span><\/span>, then a\u2264ca \\leq c<\/span>a<\/span>\u2264<\/span><\/span>c<\/span><\/span><\/span><\/span>.<\/p>\n

If every pair of elements in SS<\/span>S<\/span><\/span><\/span><\/span> has a Least Upper Bound (LUB)<\/strong> and Greatest Lower Bound (GLB)<\/strong>, then SS<\/span>S<\/span><\/span><\/span><\/span> forms a lattice<\/strong>.<\/p>\n

2. Least Upper Bound (LUB) \/ Supremum (sup)<\/strong><\/h3>\n

The Least Upper Bound (LUB)<\/strong> of a subset AA<\/span>A<\/span><\/span><\/span><\/span> of a poset (S,\u2264)(S, \\leq)<\/span>(<\/span>S<\/span>,<\/span>\u2264<\/span><\/span>)<\/span><\/span><\/span><\/span> is the smallest element in SS<\/span>S<\/span><\/span><\/span><\/span> that is greater than or equal to all elements of AA<\/span>A<\/span><\/span><\/span><\/span><\/strong>.<\/p>\n

Mathematically, an element uu<\/span>u<\/span><\/span><\/span><\/span> is LUB (sup) of AA<\/span>A<\/span><\/span><\/span><\/span> if:<\/strong><\/p>\n

    \n
  1. uu<\/span>u<\/span><\/span><\/span><\/span> is an upper bound<\/strong> of AA<\/span>A<\/span><\/span><\/span><\/span> (\u2200a\u2208A,a\u2264u\\forall a \\in A, a \\leq u<\/span>\u2200<\/span>a<\/span>\u2208<\/span><\/span>A<\/span>,<\/span>a<\/span>\u2264<\/span><\/span>u<\/span><\/span><\/span><\/span>).<\/li>\n
  2. uu<\/span>u<\/span><\/span><\/span><\/span> is the smallest such element<\/strong>, meaning if vv<\/span>v<\/span><\/span><\/span><\/span> is another upper bound, then u\u2264vu \\leq v<\/span>u<\/span>\u2264<\/span><\/span>v<\/span><\/span><\/span><\/span>.<\/li>\n<\/ol>\n

    Example:<\/strong>
    Consider A={2,4,5}A = \\{ 2, 4, 5 \\}<\/span>A<\/span>=<\/span><\/span>{<\/span>2<\/span>,<\/span>4<\/span>,<\/span>5<\/span>}<\/span><\/span><\/span><\/span> in the poset (S,\u2264)(S, \\leq)<\/span>(<\/span>S<\/span>,<\/span>\u2264<\/span><\/span>)<\/span><\/span><\/span><\/span> where S={1,2,3,4,5,6}S = \\{1, 2, 3, 4, 5, 6\\}<\/span>S<\/span>=<\/span><\/span>{<\/span>1<\/span>,<\/span>2<\/span>,<\/span>3<\/span>,<\/span>4<\/span>,<\/span>5<\/span>,<\/span>6<\/span>}<\/span><\/span><\/span><\/span>.
    \u2714 Upper bounds of AA<\/span>A<\/span><\/span><\/span><\/span> in SS<\/span>S<\/span><\/span><\/span><\/span><\/strong>: {5, 6}
    \u2714 Least Upper Bound (LUB)<\/strong>: 5 (because it is the smallest upper bound)<\/strong><\/p>\n

    3. Greatest Lower Bound (GLB) \/ Infimum (inf)<\/strong><\/h3>\n

    The Greatest Lower Bound (GLB)<\/strong> of a subset AA<\/span>A<\/span><\/span><\/span><\/span> of a poset (S,\u2264)(S, \\leq)<\/span>(<\/span>S<\/span>,<\/span>\u2264<\/span><\/span>)<\/span><\/span><\/span><\/span> is the largest element in SS<\/span>S<\/span><\/span><\/span><\/span> that is less than or equal to all elements of AA<\/span>A<\/span><\/span><\/span><\/span><\/strong>.<\/p>\n

    Mathematically, an element gg<\/span>g<\/span><\/span><\/span><\/span> is GLB (inf) of AA<\/span>A<\/span><\/span><\/span><\/span> if:<\/strong><\/p>\n

      \n
    1. gg<\/span>g<\/span><\/span><\/span><\/span> is a lower bound<\/strong> of AA<\/span>A<\/span><\/span><\/span><\/span> (\u2200a\u2208A,g\u2264a\\forall a \\in A, g \\leq a<\/span>\u2200<\/span>a<\/span>\u2208<\/span><\/span>A<\/span>,<\/span>g<\/span>\u2264<\/span><\/span>a<\/span><\/span><\/span><\/span>).<\/li>\n
    2. gg<\/span>g<\/span><\/span><\/span><\/span> is the largest such element<\/strong>, meaning if hh<\/span>h<\/span><\/span><\/span><\/span> is another lower bound, then h\u2264gh \\leq g<\/span>h<\/span>\u2264<\/span><\/span>g<\/span><\/span><\/span><\/span>.<\/li>\n<\/ol>\n

      Example:<\/strong>
      Consider A={2,4,5}A = \\{ 2, 4, 5 \\}<\/span>A<\/span>=<\/span><\/span>{<\/span>2<\/span>,<\/span>4<\/span>,<\/span>5<\/span>}<\/span><\/span><\/span><\/span> in the poset (S,\u2264)(S, \\leq)<\/span>(<\/span>S<\/span>,<\/span>\u2264<\/span><\/span>)<\/span><\/span><\/span><\/span> where S={1,2,3,4,5,6}S = \\{1, 2, 3, 4, 5, 6\\}<\/span>S<\/span>=<\/span><\/span>{<\/span>1<\/span>,<\/span>2<\/span>,<\/span>3<\/span>,<\/span>4<\/span>,<\/span>5<\/span>,<\/span>6<\/span>}<\/span><\/span><\/span><\/span>.
      Lower bounds of AA<\/span>A<\/span><\/span><\/span><\/span> in SS<\/span>S<\/span><\/span><\/span><\/span><\/strong>: {1, 2}
      Greatest Lower Bound (GLB)<\/strong>: 2 (because it is the largest lower bound)<\/strong><\/p>\n

      4. Graphical Representation in Hasse Diagram<\/strong><\/h3>\n

      In a Hasse Diagram<\/strong>,<\/p>\n