23.2. Introduction to Partial Ordering

In a dictionary, words are arranged alphabetically. This arrangement can be considered a relationship where a word a is related to word b if a appears before b. This alphabetical order satisfies three properties: Reflexive property, Antisymmetric property, and Transitive property.

Partial ordering refers to a way of arranging elements in a set based on a certain relation. In a dictionary, words are arranged so that if you have two words, 'a' and 'b', you can say 'a' is before 'b'. This arrangement meets three critical properties:

1. Reflexive: Every word can relate to itself, so we can say that 'a' comes before itself, even if this isn't explicitly stated.
2. Antisymmetric: If 'a' comes before 'b', then 'b' cannot come before 'a' if they are different words. For example, 'apple' cannot be before 'apple'.
3. Transitive: If 'a' is before 'b' and 'b' is before 'c', then 'a' must be before 'c'. This structure is vital to understanding how relationships establish order within sets.

Think of a relay race. If Runner A passes the baton to Runner B and Runner B passes it to Runner C, you can infer that Runner A started before Runner C. This connection of events demonstrates the concept of transitive relationships in partial ordering, where the sequence and dependencies fall into place.

The alphabetical arrangement satisfies:

1. Reflexive property: A word can always relate to itself.
2. Antisymmetric property: No two different words can have both relations simultaneously.
3. Transitive property: If word b follows word a, and word c follows word b, then word c follows word a.

Let's break down the properties of partial ordering further:

• Reflexive Property: Every element relates to itself. In our example, any word is inherently related to itself, like 'dog' relates to 'dog'.
• Antisymmetric Property: If you have two distinct elements, one cannot precede the other if they are the same. For instance, 'apple' cannot come before 'apple'. If 'apple' is before 'banana', then 'banana' cannot also be before 'apple'.
• Transitive Property: This property shows the flow of relationships. If 'apple' is before 'banana', and 'banana' is before 'cherry', then it must be true that 'apple' is before 'cherry'. This forms a chain of order based on the relationships.

Imagine a classroom line-up. If Student A is in line before Student B, and Student B is before Student C, then you naturally understand that Student A is at the front, following the rules of order implicitly set by the line-up. Each student can see they have their place in this order, reflecting the reflexive, antisymmetric, and transitive properties.

A relationship R on a set S is called a partial ordering if it is reflexive, antisymmetric, and transitive. The set S, along with R, is termed a poset (partially ordered set).

In mathematics, when we define a relationship R on a set S, if R satisfies all three properties—reflexive, antisymmetric, and transitive—we can categorize this structure as a partial ordering. When we have such a relationship on a set, the set along with this specific relation is referred to as a poset, or partially ordered set. This formal classification helps us understand the nature of elements and their relationships systematically.

Consider a project management scenario where tasks must be completed in a specific order due to dependencies. These tasks and their required sequences can be conceptualized as a poset. Task 'A' must be finished before 'B' starts; here, the relationship of dependency reflects a partial order, showing how distinct pieces of work must interact.

Consider the set of all positive integers with the relation divides, denoted by |. This relation is reflexive because every positive integer divides itself, antisymmetric because no two different positive integers can divide each other, and transitive because if a divides b and b divides c, then a divides c.

One of the simplest examples of a partial ordering is with the set of positive integers and the 'divides' relation. Here’s how it fits our definition of partial ordering:

• Reflexive: Each number divides itself, for example, 5 divides 5.
• Antisymmetric: If one number divides another, then they must be the same for them to divide each other. If 3 divides 6, then 6 cannot divide 3 unless they are equal, which they aren't.
• Transitive: If 2 divides 4 and 4 divides 8, then 2 must also divide 8. This flow showcases the transitive nature. This relationship forms a structure that is systematic and can be visualized as a partial order.

Think of a family tree where each person can be seen as a positive integer. A parent can be seen as someone who 'divides' their responsibilities and influence to their children. Each parent role relates back to themselves, meaning they inherently have a 'relationship' with their own titles and cannot share titles with others, showcasing the properties of partial ordering in familial structures.

In a poset, we often denote the relation using ≤. Note this does not imply numerical less than. Two elements are called comparable if either element ≤ the other; otherwise, they are incomparable.

In discussing posets, we can represent our relationship using a notation like ≤. Importantly, this notation does not indicate a numerical relationship; it simply signifies a relation. If you have two elements, say a and b, they’re considered comparable if:

• a ≤ b or b ≤ a, indicating a relationship between them. Conversely, if neither is true, we define them as incomparable. This understanding is crucial for recognizing the nature of order in various relational contexts.

Imagine a hierarchy in a company. The CEO can be compared to the Vice President; one role has authority over the other, making them comparable. However, the CEO and a new intern are incomparable in terms of role because their responsibilities and levels differ widely, reflecting how elements in a poset relate or don't relate to one another.

A total ordering is a special type of poset where every pair of elements in the set is comparable. That is, for any elements a and b, either a ≤ b or b ≤ a.

Understanding total ordering is pivotal in distinguishing it from partial ordering. A total ordering implies that when we take any two elements from our set, they must exhibit a definite relationship:

• Either one will come first or the other will. In contrast to partial ordering, where you might find elements that lack a clear relationship, total ordering ensures every pair is relatable in a specific manner, emphasizing a type of complete structure.

Think about students in a race. Every student finishes in a clear order: first, second, third, and so on. Here, any two students can be compared based on their finishing time. There are no instances where one student cannot be ranked against another; thus, this race exemplifies a total ordering of the students.

Partial ordering can be visually represented using Hasse diagrams, which help illustrate relationships within a poset. The diagram simplifies the depiction by omitting transitive and reflexive connections, focusing on direct relations.

Hasse diagrams serve as a powerful visualization tool for understanding posets. They graphically represent the hierarchy or arrangement of relationships in a way that is both simplified and clear. The key steps in creating a Hasse diagram include:

• Start with all the elements and their relationships (arrows) based on the defined partial ordering.
• Remove self-loops since they are implicitly understood.
• Omit transitive relationships; if one element connects to another through a third one, you do not need to illustrate that connection. Through these diagrams, the essence of the order becomes clearer.

Picture a family tree being represented graphically. Each person is a point, and direct relationships (like parent-child) are shown with lines connecting them. No need to show indirect relationships, as the direct connections present a clear overview of family relationships. This simplification helps one grasp their understanding quickly.

--