Problem 7 - Applied Abstract Algebra

Question

More generally, prove that in a lattice \((L, \leq)\) every finite nonempty subset \(S\) has a least upper bound and a greatest lower bound.

Step-by-Step Solution

Answer

To prove that every finite nonempty subset \(S\) in a lattice \((L, \leq)\) has a least upper bound (lub) and greatest lower bound (glb): First, understand what lattices, lub, and glb are. Then, take two arbitrary elements 'a' and 'b' in \(S\), and prove that they have a lub and glb. Next, extend this proof for all elements in the set using mathematical induction. Thus, every finite nonempty subset \(S\) in a lattice \((L, \leq)\) has a lub and a glb.

Step 1: Understanding Lattices

A lattice \((L, \leq)\) is a partially ordered set (poset) in which any two elements have a greatest lower bound (glb) and least upper bound (lub). The glb is the greatest element that is less than or equal to all elements in the set. The lub is the smallest element that is greater than or equal to all elements in the set.

Step 2: Proof of Least Upper Bound and Greatest Lower Bound

To prove the existence of lub and glb, a common strategy is to take two arbitrary elements 'a' and 'b' from the set \(S\). Due to the nature of a lattice, these two elements will have a lub and a glb within the set. Prove this by first assuming otherwise, and then showing that this leads to a contradiction, which demonstrates the existence of a lub and glb for 'a' and 'b'.

Step 3: Extending to all elements in the set

Approach the entire proof using mathematical induction for more than two elements. After proving the base case for two elements, assume that the statement holds for \(n\) elements. Consider adding one more element to the set, and prove that the new set still has a lub and glb, based on the induction hypothesis and the pairwise lub and glb existence already proven in Step 2.

Key Concepts

Partially Ordered Set

A partially ordered set, or simply a poset, is a set equipped with a relation that dictates how elements compare with each other. In a poset, not all elements need to be comparable, which is different from a totally ordered set where every two elements are comparable. The relation, often denoted as \(\leq\), must satisfy three key properties:

• Reflexivity: Every element is comparable to itself, meaning for any element \(a\), \(a \leq a\).
• Antisymmetry: If one element is comparable to another in both directions, they must be equal, i.e., if \(a \leq b\) and \(b \leq a\), then \(a = b\).
• Transitivity: If one element is comparable to a second, which is comparable to a third, the first and third elements are also comparable, i.e., if \(a \leq b\) and \(b \leq c\), then \(a \leq c\).

This structure is foundational in lattice theory because it helps establish a framework where concepts like least upper bounds and greatest lower bounds are defined.

Least Upper Bound

The least upper bound, sometimes referred to as the supremum, is an important concept in lattice theory. Given a set \(S\), an upper bound is an element that is greater than or equal to every element in \(S\). The least upper bound (lub) is the smallest such element, ensuring that no other upper bound is lesser than it. The significance of the least upper bound lies in its ability to act as a universal constraint within a subset.

• Properties of lub: If \(u\) is a least upper bound of \(S\), then for every element \(s\) in \(S\), \(s \leq u\).
• There is no other element \(u'\) such that \(u' \lt u\) and \(u'\) is an upper bound for \(S\).

In a lattice, every pair of elements is guaranteed to have a least upper bound. This means, for finite non-empty subsets of a lattice, a lub always exists, allowing us to tackle a range of problems using this structure.

Greatest Lower Bound

The greatest lower bound, also known as the infimum, mirrors the least upper bound but works in the reverse ordering direction. For a set \(S\), a lower bound is an element that is less than or equal to every element in the set. The greatest lower bound (glb) is the largest among all lower bounds, which means no other lower bound is greater.

• Properties of glb: If \(v\) is a greatest lower bound of \(S\), then for every element \(s\) in \(S\), \(v \leq s\).
• There is no other element \(v'\) such that \(v \gt v'\) and \(v'\) is a lower bound for \(S\).

Like the least upper bound, every pair of elements in a lattice also has a greatest lower bound. This ensures that finite non-empty subsets can always be coordinated to find their glb, simplifying proofs and solutions among complex element arrangements in a lattice.

Mathematical Induction

Mathematical induction is a powerful proof technique often used to establish the truth of an infinite sequence of statements. It is particularly useful in demonstrating properties of lattices involving any number of elements. The process involves two key steps:

• Base Case: Verify that the statement holds for an initial element, often times the smallest or a straightforward case like two elements in a lattice.
• Inductive Step: Assume the statement is true for a generic case of \(n\) elements. Then demonstrate it also holds for \(n + 1\) elements by introducing another element and leveraging the previous truths.

Induction allows us to extend conclusions about pairs to conclusions about entire sets. In lattice theory, it's often used to prove that properties like having a least upper bound and greatest lower bound apply not only to two elements but to any finite subset of the lattice. This makes it an indispensable tool for mathematicians working with ordered sets.