Last updated Unknown

Status: Tags: #archivedCards/macm101/settheory Links: Discrete Math Relations

Partial Orders

Partial orders qualities (relation R on a set A) ?

• if it is reflexive, transitive and anti-symmetric.

Partial orders are total orders if ? Every two elements are comparable, resulting in a chain

• ex) all natural/real/positive numbers

Examples ?

• a ≤ b on the set of real numbers
• (a,b) ∈ Div if and only if a divides b

Diagram of partial orders ?

• Due to anti-symmetricity, all the elements of A are ranked with respect to the order R, that is b is ranked higher than a if (a,b) ∈ R.
• all the elements of A are ranked with to the order established by R
  • Display based on height
• Due to transivity, only need to show pairs where b is just higher than a, as there is established hierarchy

Relation of divisibility on {1,2,…,12} ? Elements a,b are said to be comparable if ;; (a,b) ∈ R or (b,a) ∈ R

Element a is minimal if ;; for any b if (b,a) ∈ R then a = b (nothing directly below locally)

Element a is maximal if ;; for any b if (a,b) ∈ R then a = b (nothing directly above locally)

Element a is called the least element if ;; for any b, (a,b) ∈ R

Element a is called the greatest element if ;; for any b, (b,a) ∈ R

Practice

Backlinks

1

list from Partial Orders AND !outgoing(Partial Orders)

References:

Created:: 2021-10-26 16:53