23.2.4. General Definition of Partial Ordering

So, what is the partial ordering? If you consider a dictionary then the words in a dictionary are arranged alphabetically or we also say that the words are arranged lexicographically. There is a relationship that holds between the words regarding their arrangement. A word 'a' is related to the word 'b' in my dictionary provided 'a' appears before 'b'.

A partial ordering is a way to arrange elements where some elements may be 'less than', 'equal', or 'greater than' others. The example of a dictionary helps illustrate this idea, as words are organized in a specific sequence that establishes a clear ordering. The critical point to remember is that this organization shows how one element relates to another based on their positions.

When we say word 'a' appears before word 'b', it creates a directed relationship. So this arrangement helps manage other contexts beyond words, such as tasks, numbers, or abstract concepts.

Think of a library where books are arranged on shelves alphabetically by title. You can easily determine the position of any book relative to others. This method of organization helps everyone find information quickly and easily, just like how partial ordering helps understand relationships between elements.

The alphabetical arrangement of the words satisfies three properties: Reflexive property, Antisymmetric property, and Transitive property.

• Reflexive property: Implicitly, a word always appears before itself.
• Antisymmetric property: You cannot have two different words such that one appears before the other and vice versa.
• Transitive property: If 'b' appears after 'a', and 'c' appears after 'b', then 'c' appears after 'a'.

These three properties define the structure of a partial order:

1. Reflexive: Every element must relate to itself, which means 'a' must appear before 'a'. This is often assumed and does not require explicit demonstration.
2. Antisymmetric: If two distinct elements relate to one another in both directions, they must be the same. This prevents circular relationships where elements mutually depend on each other.
3. Transitive: This property allows us to draw connections. If one element relates to a second, and that second relates to a third, then the first element must inherently relate to the third.

Imagine a family tree. Reflexivity is like saying every person is related to themselves. Antisymmetry ensures that a child cannot have two parents unless they are the same person—two different parents cannot both be the same individual. The transitive property helps us understand family ties: if Alice is Bob's mother and Bob is Charlie's father, then it follows that Alice is Charlie's grandmother.

To define a partial ordering formally, let S be a set and R be a relation on S. The relation R is a partial ordering if it is reflexive, antisymmetric, and transitive. The pair (S, R) is called a poset (partially ordered set).

This segment establishes the formal criteria for what we consider a partial ordering. By stating that R must be reflexive, antisymmetric, and transitive, we have a clear guideline for identifying orderliness in other contexts beyond words. The notation (S, R) identifies a set S and its relationship R as a poset, signifying that we can explore the relationships among elements in a structured manner.

Consider a collection of tasks for a project. Each task can depend on another being completed first, such as writing a report before presenting it. The relationships among tasks show a partial order—tasks that are independent can be done in any order, but dependent tasks must follow a specific sequence.

Examples include:

1. The set of all positive integers with the divides relation (denoted by |).
2. The subset relation (denoted by ⊆) on the power set of a set.
3. The less than or equal to relation (≤) on the set of integers.

These examples highlight different contexts where partial orderings apply:

1. In the positive integers, for example, 2 divides 4, but not the other way around.
2. The subset relationship allows us to see how subsets relate to one another within a larger set.
3. The numerical 'less than or equal to' is familiar, indicating a clear order among integers.

Think about how some people may have different levels of experience at a job; some might be senior employees while others are interns. Their relationship in experience levels can be thought of as a partial ordering. Some employees can help train others, creating a dependency chain in tasks or projects.

Given a poset, two elements are comparable if either xRy or yRx. Conversely, they are incomparable if neither relationship holds true between them.

This chunk introduces the concept of comparing elements within the context of a partial order. If at least one direct relationship exists (one element relates to another), they are termed comparable. If no such relation is established, they are incomparable. This distinction is vital in understanding the dynamics and structure of relationships within a poset.

In a group project, imagine you and a partner are responsible for different tasks. If one task depends on the completion of another, then those tasks are comparable. But if you’re working on totally different areas of the project that do not affect one another, then those tasks are incomparable.

--