Well-founded Relation - Examples

Examples

Well-founded relations which are not totally ordered include:

  • the positive integers {1, 2, 3, ...}, with the order defined by a < b if and only if a divides b and a ≠ b.
  • the set of all finite strings over a fixed alphabet, with the order defined by s < t if and only if s is a proper substring of t.
  • the set N × N of pairs of natural numbers, ordered by (n1, n2) < (m1, m2) if and only if n1 < m1 and n2 < m2.
  • the set of all regular expressions over a fixed alphabet, with the order defined by s < t if and only if s is a proper subexpression of t.
  • any class whose elements are sets, with the relation ("is an element of"). This is the axiom of regularity.
  • the nodes of any finite directed acyclic graph, with the relation R defined such that a R b if and only if there is an edge from a to b.

Examples of relations that are not well-founded include:

  • the negative integers {-1, -2, -3, …}, with the usual order, since any unbounded subset has no least element.
  • The set of strings over a finite alphabet with more than one element, under the usual (lexicographic) order, since the sequence "B" > "AB" > "AAB" > "AAAB" > … is an infinite descending chain. This relation fails to be well-founded even though the entire set has a minimum element, namely the empty string.
  • the rational numbers (or reals) under the standard ordering, since, for example, the set of positive rationals (or reals) lacks a minimum.

Read more about this topic:  Well-founded Relation

Famous quotes containing the word examples:

    “It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
    —G.C. (Georg Christoph)

    “No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
    —André Breton (1896–1966)

    “In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
    —Michel de Montaigne (1533–1592)