Partial Order Relations in Discrete Mathematics: Reflexivity, Antisymmetry, and Transitivity

Learn about partial order relations, a type of relation on a set that is reflexive, antisymmetric, and transitive. This guide defines partial orders, explains their properties, and provides examples to illustrate these concepts.

Partial Order Relations in Discrete Mathematics

What is a Partial Order Relation?

A partial order relation on a set A is a relation that's reflexive, antisymmetric, and transitive. This means it defines a type of ordering between some (but not necessarily all) pairs of elements in the set. It's called "partial" because not every pair of elements needs to be comparable (ordered).

Properties of a Partial Order Relation

  1. Reflexive: Every element is related to itself (aRa for all a ∈ A).
  2. Antisymmetric: If aRb and bRa, then a = b.
  3. Transitive: If aRb and bRc, then aRc.

Examples of Partial Order Relations

Example 1: Greater Than or Equal To

Show that the relation (x, y) ∈ R if x ≥ y is a partial order relation on the set of positive integers.

(The solution showing that this relation is reflexive, antisymmetric, and transitive would be included here.)

Example 2: Divisibility

Show that the "divides" relation on the set of natural numbers (ℕ) is a partial order relation.

(The solution demonstrating reflexivity, antisymmetry, and transitivity for the divisibility relation would be included here.)

Example 3: Set Inclusion

Set inclusion (⊆) is a partial order on any collection of sets.

(The explanation showing that set inclusion satisfies reflexivity, antisymmetry, and transitivity would be included here.)

Elements in a Poset

  • Maximal Element: An element 'a' such that there is no element 'c' with a ≤ c.
  • Minimal Element: An element 'b' such that there is no element 'c' with c ≤ b.

(Note: A poset can have more than one maximal or minimal element.)

Comparable and Non-Comparable Elements

In a poset, two elements are:

  • Comparable: If one is less than or equal to the other (a ≤ b or b ≤ a).
  • Non-comparable: If neither is less than or equal to the other.

(An example showing comparable and non-comparable elements in a specific poset, like the divisors of 30 ordered by divisibility, would be included here.)

Linearly Ordered Sets (Totally Ordered Sets)

A linearly ordered set (or totally ordered set) is a poset where every pair of elements is comparable.

n-Ary Relations

An n-ary relation is a set of ordered n-tuples. A ternary relation is a 3-ary relation.

Partial Order Sets (Posets)

A poset is a set A with a partial order relation R on A, denoted (A, R).

Total Order Relations

A total order relation on a set A is a relation where every pair of distinct elements is comparable (either aRb or bRa).

(An example showing that the '<' (less than) relation on positive integers is a total order relation but not a partial order relation would be included here. The explanation should include why it is not reflexive.)

Equivalence Classes

Given an equivalence relation R on a set A, the equivalence class of an element 'a' is the set of all elements in A that are related to 'a'.

(An example demonstrating how to find equivalence classes is provided in the original text and should be included here.)

Circular Relations

A binary relation R on a set A is circular if (a, b) ∈ R and (b, c) ∈ R implies (c, a) ∈ R.

(An example showing that an equivalence relation is circular is given in the original text and should be included here.)

Compatible Relations

A compatible relation is a binary relation that is both reflexive and symmetric.

Conclusion

Partial order relations and related concepts provide valuable tools for understanding order and structure within sets.