Problem 6 - Applied Discrete Structures

Question

We naturally order the numbers in \(A_{m}=\\{1,2, \ldots, m\\}\) with "less than or equal to," which is a partial ordering. We define an ordering, \(\preceq\) on the elements of \(A_{m} \times A_{n}\) by $$ (a, b) \preceq\left(a^{\prime}, b^{\prime}\right) \Leftrightarrow a \leq a^{\prime} \text { and } b \leq b^{\prime} $$ (a) Prove that \(\preceq\) is a partial ordering on \(A_{m} \times A_{n}\). (b) Draw the ordering diagrams for \(\preceq\) on \(A_{2} \times A_{2}, A_{2} \times A_{3},\) and \(A_{3} \times A_{3}\). (c) In general, how does one determine the least upper bound and greatest lower bound of two elements of \(A_{m} \times A_{n},(a, b)\) and \(\left(a^{\prime}, b^{\prime}\right) ?\) (d) Are there least and/or greatest elements in \(A_{m} \times A_{n} ?\)

Step-by-Step Solution

Answer

(a) \( \preceq \) is reflexive, antisymmetric, and transitive. (b) Draw Hasse diagrams. (c) LUB: \((\max(a, a'), \max(b, b'))\); GLB: \((\min(a, a'), \min(b, b'))\). (d) Least: \((1,1)\); No greatest element.

Step 1: Understanding partial ordering

A partial order is a binary relation over a set that is reflexive, antisymmetric, and transitive. For this problem, we need to show that the relation \( \preceq \) in \( A_{m} \times A_{n} \) satisfies these three properties:

Step 1(a): Prove reflexivity

A relation is reflexive if every element is related to itself. For all \( (a, b) \), \( a \leq a \) and \( b \leq b \), thus \( (a, b) \preceq (a, b) \). Hence, \( \preceq \) is reflexive.

Step 1(b): Prove antisymmetry

A relation is antisymmetric if \( (a, b) \preceq (a', b') \) and \( (a', b') \preceq (a, b) \) implies \( (a, b) = (a', b') \). If both \( a \leq a' \) and \( a' \leq a \), then \( a = a' \). Similarly, if \( b \leq b' \) and \( b' \leq b \), then \( b = b' \). Hence, \( (a, b) = (a', b') \), so \( \preceq \) is antisymmetric.

Step 1(c): Prove transitivity

A relation is transitive if \( (a, b) \preceq (a', b') \) and \( (a', b') \preceq (a'', b'') \) imply \( (a, b) \preceq (a'', b'') \). Given \( a \leq a', \) and \( a' \leq a'' \) implies \( a \leq a'' \), and \( b \leq b', \) and \( b' \leq b'' \) implies \( b \leq b'' \). Therefore, \( (a, b) \preceq (a'', b'') \), hence \( \preceq \) is transitive.

Step 2: Conclusion for part (a)

Since \( \preceq \) is reflexive, antisymmetric, and transitive, it is a partial ordering on \( A_{m} \times A_{n} \).

Step 3: Draw ordering diagrams

To draw Hasse diagrams for the sets: - **\( A_{2} \times A_{2} \):** Elements: \((1,1), (1,2), (2,1), (2,2)\).- **\( A_{2} \times A_{3} \):** Elements: \((1,1), (1,2), (1,3), (2,1), (2,2), (2,3)\).- **\( A_{3} \times A_{3} \):** Elements include coordinates from \((1,1)\) to \((3,3)\). For each, start with the smallest elements and draw edges to larger elements that don't violate the relation \( \preceq \).

Step 4: Determine least upper bound (LUB) and greatest lower bound (GLB)

For elements \((a, b)\) and \((a', b')\), the LUB is \((\max(a, a'), \max(b, b'))\) since it is the smallest element greater than or equal to both. The GLB is \((\min(a, a'), \min(b, b'))\) because it is the largest element less than or equal to both.

Step 5: Identify least and greatest elements

The element \((1, 1)\) is the least element in \( A_{m} \times A_{n} \) as it is the smallest for both coordinates, however, there is no greatest element in general, because any given element could have a larger counterpart.

Key Concepts

Reflexivity

Reflexivity is a fundamental property of partial orderings. It means that every element in the set is related to itself. Imagine reflexivity as a self-reflection in a mirror. For any given element in a set, it should always be able to "see" itself.

In mathematical terms, for the set \(A_m \times A_n\) and a relation \(\preceq\), this property is demonstrated by ensuring that

• every element \((a, b)\) in \(A_m \times A_n\) holds the relation \((a, b) \preceq (a, b)\)

Practically, it ensures elements are comparable to themselves without any contradiction. This reflexivity is evident in the properties of "less than or equal to" where \(a \leq a\) and \(b \leq b\) stand without disputation. By reflecting on these elements concerning their coordinates, reflexivity confirms that nothing has been omitted from self-comparison.

Understanding reflexivity simplifies the discovery of order within any set. It lays a basic confirmation before one can explore interactions between different peers in the realm of elements.

Antisymmetry

Antisymmetry can often be confusing because at first glance, it contradicts the natural symmetry we might expect. Unlike reflexivity, which is about self-relatedness, antisymmetry delves into interactions between pairs of elements.

Consider two elements \((a, b)\) and \((a', b')\) in the set \(A_m \times A_n\). The antisymmetric property holds when:

• If \((a, b) \preceq (a', b')\) and \((a', b') \preceq (a, b)\) simultaneously, then the only conclusion is that \((a, b) = (a', b')\)

In simpler terms, if an element can be both "less than or equal" and "greater than or equal" to another simultaneously, then they must be identical. This is akin to saying if one box can't fit inside or outside another perfectly at the same time, they must be the exact same box.

Antisymmetry ensures that there is no unintentional overlap of distinct elements in a set where each holds its unique place unless they are indeed the same. It is crucial in discriminating between relationships that might mistakenly appear equal but aren't.

Transitivity

Transitivity ties elements together, fostering a structured order across the entire set like a seamless chain of logic. In the context of partial ordering, if an element connects orderly to a second and the second orderly connects to a third, transitivity forms a direct bridge from the first to the third.

Specifically, in the set \(A_m \times A_n\), if we have elements \((a, b)\), \((a', b')\), and \((a'', b'')\), the transitive property is:

• When \((a, b) \preceq (a', b')\) and \((a', b') \preceq (a'', b'')\), then \((a, b) \preceq (a'', b'')\) is true.

This essentially means that the relation follows a consistent path; the ordering doesn’t suddenly break or jump inconsistently. Using a stepping stone analogy, if you can step from one stone to a midpoint and then to a third stone, you should be able to reach directly from the starting to the ending stone.

Transitivity establishes cohesion and continuity within a set, making it possible to navigate from any element to others logically and predictably. It maintains the integrity of order through connections and interactions among various elements.