« previous section   next section »


5.4  Upper and lower bounds

Definition 5.4.1

Let ≤ be an ordering relation in a set X and let A be a subset of X.
An element x0 ∈ X such that for every a ∈ A it holds that a ≤ x0   is an upper bound of A.

An element x1 ∈ X such that for every a ∈ A it holds  that x1 ≤ a   is a lower bound of A.

Example 5.4.1

(1) Consider an ordered set  <R, ≤ > and its subset A = {x ∈ R: 1< x < 2}. Upper bounds of the set A are the number 3 and every number greater than or equal 2.  Lower bounds of the set A are the numbers  1, 0, -1, -2, and every number less than or equal 1, for each of them is smaller than any element of the set A.

(2) Consider the set of natural numbers ordered by the relation of divisibility | and the set  B = {4,6,8}. The numbers 24, 48 and any number that divides by  4, 6 and 8 are upper bounds of the set B. Lower bounds of the set B are 1 and 2 since both 1 and 2 are divisors of 4, 6 and 8.

(3) Consider the set A of all rational numbers x such that x2are less that 2, as a subset of the set of real numbers ordered by the usual ordering. The lower bound of this set is the -square root of 2 and all less real numbers, and the upperbound is the +square root of 2 and all greater real numbers.


The following conclusion is a consequence of the above examples:

Conclusion: A subset B of an ordered set may have many different upper bounds and many different lower bounds. A lower bound (an upper bound) of B need not belong to the subset B.

Definition 5.4.2

The least upper bound (l.u.b.) or supremum of a subset A of an ordered set  <X, ≤ > is the element of X denoted sup A such that it is the least upper bound of A if it exist.

x0 = sup A iff

  1. a ≤ x0 for every a ∈ A
  2. if  b is an upper bound of A then  x0 ≤ b.

The greatest lower bound (g.l.b.) or infimum of a subset A of an ordered set  <X, ≤ > is the element of X denoted inf A such that it is the greatest lower bound of A if it exist.

x1 = inf A iff

  1. x1 ≤ a for every  a ∈ A
  2. if b is a lower bound of A then b ≤ x1.

Question 5.4.1: Let A be a subset of a partially ordered set. Is sup A  equal to the greatest element of A? 

----- See answer -----

Example 5.4.2

  1. The least upper bound of the subset A={1/n: n ∈ N>0} of the set of real numbers ordered by the relation  ≤ is 1 (1 is the greatest element of this subset). The greatest lower bound of the subset A is 0. Note that 0 does not belong to A.
  2. Consider an ordered set  <P(X), ⊆ > and two subsets A, B ∈ P(X). The following equality holds
    sup{A, B} = A ∪ B .
    Proof. Let us note that  A ∪ B is an upper bound of the set  {A, B}, since A ⊆ A ∪ B and B ⊆ A ∪ B. Let C be an arbitrary subset C ∈ P(X), such that C is also an upper bound of  {A, B}. Then, A ⊆ C and B ⊆ C, therefore by the laws of set algebra  (cf. lemma 1.3.1) we have A ∪ B ⊆ C. Hence, A ∪ B is the least upper bound of  {A, B}.
  3. Let A = {n, m} be a two-element subset of the ordered set <N, |>. Then sup{n, m} = the least common multiplicity (w skr?ie nww) liczb n i m , and inf{n, m} = the greatest common divisor (gcd) of numbers  n and m. For example sup {4, 6} = 12, and inf{4, 6} = 2; sup{12, 18} = 36, and inf{12, 18} = 6.

Question 5.4.2 Consider an ordered set <P(X), ⊆ > and two subsets  A, B ∈ P(X). Calculate the inf{A,B}.

----- See answer -----

Problem 5.4.1

Let (Xi)i ∈ I be an indexed family of subsets of an ordered set  < P(X), ⊆ >. Define the least upper bound of the family.

Answer : The generalized union of all sets of the family. Indeed,  observe that Xi ⊆ ⎩⎭ i ∈ I Xi , since the generalized union  ⎩⎭ i ∈ I Xi (c.f. 1.6) consists of all elements of all sets of the family.. Suppose that for a set B and for all i ∈ I, Xi ⊆ B and let  x ∈ ⎩⎭ i ∈ I Xi . Then there exist k ∈ I, x ∈ Xk, therefore x ∈ B. We have proved that  ⎩⎭ i ∈ I Xi ⊆ B. We conclude that the generalized union  ⎩⎭ i ∈ I Xi  is the least upper bound of the family of subsets  (Xi)i ∈I.

In an analogous way one can prove that inf (Xi)i ∈ I = ⎧⎫ i ∈ I Xi.

Definition 5.4.2

An ordered set such that for any pair of its elements there exist the least upper bound and the greatest lower bound is called a  lattice.

One example of a lattice is the ordered set shown on Figure 5.2.1. More generally, the set  <P(X), ⊆ >, where X is an arbitrary set is a lattice: for arbitrary subsets A and B of X, set-theoretical union is a least upper bound and set-theoretical intersection is a geatest lower bound.

Question 5.4.3 Consider the set of real numbers with the relation  ≤. Is it a lattice or not?

----- See answer -----


« previous section   next section »