Partial Ordering Relation

Definition

A relation $R$ on a set $A$ is called a partial ordering relation or partial order if it satisfies all three of the following properties:

1. Reflexive

• : For every $a \in A$, $aRa$.

2. Antisymmetric

• : For all $a, b \in A$, if $aRb$ and $bRa$, then $a = b$.

3. Transitive

• : For all $a, b, c \in A$, if $aRb$ and $bRc$, then $aRc$.

A set $A$ together with a partial order $R$ is called a partially ordered set or poset, written as $(A, R)$.

Main Content

1. First Concept: Reflexive, Antisymmetric, and Transitive Properties

Reflexive property

• Every element must be related to itself.
• This ensures that each item in the set has at least one guaranteed relationship.
• Example: For the subset relation $\subseteq$, every set is a subset of itself.

Antisymmetric property

• If one element is related to another and the reverse also holds, then the two elements must actually be the same.
• This prevents distinct elements from being mutually ordered in both directions.
• Example: If $A \subseteq B$ and $B \subseteq A$, then $A = B$.

Transitive property

• If one element is related to a second, and the second is related to a third, then the first must be related to the third.
• This property builds chains of order.
• Example: If $2\mid 4$ and $4\mid 8$, then $2\mid 8$.

2. Second Concept: Poset and Comparability

Partially ordered set (Poset)

• A set with a partial order is called a poset.
• It is the basic structure used to study partial ordering relations.
• Example: $(\mathcal{P}(S), \subseteq)$, where $\mathcal{P}(S)$ is the power set of $S$.

Comparable and incomparable elements

• Two elements $a$ and $b$ are comparable if either $aRb$ or $bRa$.
• If neither relation holds, they are incomparable.
• In partial orders, not all pairs must be comparable.
• Example: In the set of subsets of $\{1,2,3\}$, $\{1\}$ and $\{2\}$ are incomparable under $\subseteq$.

Difference from total order

• In a total order, every pair of elements is comparable.
• In a partial order, comparability is not required for all pairs.
• Example: “$\le$” on integers is a total order, but “$\subseteq$” on sets is only a partial order.

3. Third Concept: Hasse Diagram and Examples of Partial Orders

Hasse diagram

• A Hasse diagram is a simplified graphical representation of a poset.
• It shows only the essential order relations, usually omitting:
  • self-loops
  • transitive edges
• It helps visualize the structure of a partial order clearly.

Example: Divisibility relation

• On the set $\{1,2,3,6\}$, define $aRb$ if $a\mid b$.
• This is a partial order because:
  • every number divides itself,
  • if $a\mid b$ and $b\mid c$, then $a\mid c$,
  • if $a\mid b$ and $b\mid a$, then $a=b$.
• Here, 2 and 3 are incomparable because neither divides the other.

Example: Subset relation

• On $\mathcal{P}(S)$, define $A R B$ if $A \subseteq B$.
• This is one of the most common examples of a partial order.
• Some subsets may not be comparable, such as $\{1\}$ and $\{2\}$.

Diagram for the divisibility relation on $\{1,2,3,6\}$:

      6
     / \
    2   3
     \ /
      1

This diagram means:

• $1$ divides $2$, $3$, and $6$
• $2$ divides $6$
• $3$ divides $6$
• $2$ and $3$ are not comparable

Working / Process

1. Choose the set and define the relation

• Start with a set $A$.
• Define a relation $R$ that expresses the intended ordering, such as $\le$, $\subseteq$, or $\mid$.
• Make sure the relation is well-defined on the set.

2. Verify the three required properties

• Check reflexivity: every element must relate to itself.
• Check antisymmetry: mutual relation should imply equality.
• Check transitivity: ordered chains must preserve order.
• If all three are true, the relation is a partial order.

3. Analyze the structure of the poset

• Identify comparable and incomparable elements.
• Determine minimal and maximal elements if needed.
• Draw a Hasse diagram to visualize the ordering.
• Use the structure to answer questions about hierarchy, dependency, or inclusion.

Advantages / Applications

Models hierarchical structures

• Partial orders are ideal for representing systems where elements have a natural hierarchy, such as file directories, organizational charts, and course prerequisites.

Useful in mathematical reasoning

• They support proof techniques involving ordered structures, induction-like arguments, and lattice theory.
• Many algebraic and set-theoretic concepts use partial orders as their foundation.

Important in computer science and logic

• Partial orders are used in scheduling tasks with dependencies, database theory, compiler design, and theorem proving.
• They help represent dependency graphs, version control histories, and concurrency relations.

Summary

• Partial ordering relation is a relation that is reflexive, antisymmetric, and transitive.
• It forms a partially ordered set, or poset, and does not require every pair of elements to be comparable.
• It is commonly represented using Hasse diagrams and used in sets, divisibility, and hierarchical structures.
• Important terms to remember: partial order, poset, reflexive, antisymmetric, transitive, comparable, incomparable, Hasse diagram