CSCE 222 Lecture 16

From Notes
Jump to navigation Jump to search

« previous | Wednesday, March 2, 2011 | next »


Partial Orderings

These relations must work for all comparable numbers

Antisymmetry

Relation R on a set A is called antisymmetric iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_aR_b} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_bR_a} implies that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=b}

Examples:

  • ≤ operator on integers is antisymmetric
  • = operator on integers is antisymmetric

Partial Order

Relation R on S is a partial order iff it is reflexive, antisymmetric, and transitive.

Examples:

  • ≤ operator on integers is a partial order
  • ⊆ operator on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(S)} is a partial order

Comparability

We call two elements Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} of a partially ordered set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S,\le)} comparable iff a ≤ b or b ≤ a

Examples:

  • The set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (P(\mathbb{Z}), \subseteq)} contains {1, 2} and {1, 3}, but they are not subsets of each other, so they are incomparable.
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{N}, |)} (a "divides" b implies b mod a = 0) is:
    • reflexive (every number divides itself)
    • transitive (if a is a factor of b and b is a factor of c, then a is a factor of c)
    • antisymmetric (if a divides b and b divides a, then a and b must be equal)
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbb{Z}, |)} is not a partial order since it is not antisymmetric (1 divides −1 and −1 divides 1, but 1 ≠ −1)


Hasse Diagrams

Sample Hasse diagram for partial order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\{2,4,5,10,12,20,25\}, |\})}

A set of lines connecting all numbers that satisfy a partial order relations:

  • Remove all self/reflexive satisfying loops
  • Any upward-chained connecting lines imply transitivity
  • All edges "point" upward

Maximal/Minimal

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S, \le)} be a partially ordered set.

A number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \in S} is called maximal iff it is the largest element.

A number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in S} is called minimal iff it is the smallest element.

Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\{2,4,5,10,12,20,25\}, |)} : in a Hasse diagram (see image at right), 12, 20, 25 are maximal elemets; 2, 5 are minimal.

Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_222_Lecture_16&oldid=1213"