Problem 6 - Applied Discrete Structures

Question

Let \([L ; \vee, \wedge]\) be a lattice based on a partial ordering \(\preceq\). Prove that if \(a, b, c \in L\) (a) \(a \preceq a \vee b\). (b) \(a \wedge b \preceq a\). (c) \(b \preceq a\) and \(c \preceq a \Rightarrow b \vee c \preceq a\).

Step-by-Step Solution

Answer

(a) True by LUB definition. (b) True by GLB definition. (c) True by join properties.

Step 1: Understanding Lattice Operations

In a lattice \(L, \vee, \wedge\), the operation \(\vee\) represents the join (least upper bound), and \(\wedge\) represents the meet (greatest lower bound). These operations are derived from the partial order \(\preceq\) defined on \(L\). We will apply these definitions to prove the given parts.

Step 2: Proving Part (a): Join Property

For any elements \(a\) and \(b\) in \(L\), \(a \vee b\) is the least upper bound of \(a\) and \(b\). By definition of least upper bound, \(a \preceq a \vee b\). This is because \(a \vee b\) is the smallest element that is greater than or equal to both \(a\) and \(b\).

Step 3: Proving Part (b): Meet Property

For any elements \(a\) and \(b\) in \(L\), \(a \wedge b\) is the greatest lower bound of \(a\) and \(b\). According to the definition of greatest lower bound, \(a \wedge b \preceq a\). This is because \(a \wedge b\) is the largest element less than or equal to both \(a\) and \(b\).

Step 4: Proving Part (c): Join of Bounds

If \(b \preceq a\) and \(c \preceq a\), then both \(b\) and \(c\) are below \(a\). We need to show \(b \vee c \preceq a\). Since \(b \vee c\) is the least upper bound of \(b\) and \(c\), and both are less than \(a\), it follows from the properties of \(\vee\) that \(b \vee c \preceq a\). Thus, the join \(b \vee c\) will also be bounded by \(a\).

Key Concepts

Partial Ordering

Partial ordering is a fundamental concept in lattice theory. It refers to a binary relation over a set that is reflexive, antisymmetric, and transitive. These properties help visualize the structure of a set where not every pair of elements needs to be comparable. Here's how these properties work:

• **Reflexivity** means that every element is related to itself. If \( a \) is an element in the set, then \( a \preceq a \).
• **Antisymmetry** means that if \( a \preceq b \) and \( b \preceq a \), then \( a = b \).
• **Transitivity** means that if \( a \preceq b \) and \( b \preceq c \), then \( a \preceq c \).

In a partially ordered set (poset), not all elements must be related. This creates a structure where different subsets can have their order relations, creating a more flexible and less strict hierarchy compared to total orders.

Least Upper Bound

In lattice theory, the least upper bound (join) of two elements \( a \) and \( b \) is denoted by \( a \vee b \). This means the smallest element that is greater than or equal to both \( a \) and \( b \). Imagine placing \( a \) and \( b \) in a hierarchy where you need to find the lowest common point above them.

• **Join Property**: If we say \( a \preceq a \vee b \), it means that \( a \vee b \) is at least as large as \( a \) itself.
• **Uniqueness**: Any other common upper bound of \( a \) and \( b \) will be greater than or equal to \( a \vee b \).

The least upper bound is essential in defining how elements can be combined while respecting their comparative relationships.

Greatest Lower Bound

The greatest lower bound, also known as the meet, for two elements \( a \) and \( b \) in a lattice is denoted by \( a \wedge b \). It is the largest element that is less than or equal to both \( a \) and \( b \). This concept can be thought of as finding the closest point below both elements in the partial order.

• **Meet Property**: When we assert \( a \wedge b \preceq a \), it states that \( a \wedge b \) is no larger than \( a \).
• **Uniqueness**: Any other element common to both \( a \) and \( b \) will be less than or equal to \( a \wedge b \).

Understanding the greatest lower bound allows us to process intersecting elements within complex structures and determine the maximum overlap between elements.