Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Iterating through an infinite ordered set

  1. Sep 23, 2009 #1
    If we want to do a specific operation for each element in a set in specific order, is there some limitations for that?

    Here is an example that seems to lead a bit strange conclusion:

    Let S be an infinite totally ordered set without maximal element and A an empty set to begin with.

    For each element x in S, do the following operation:
    If set A contains element larger than x, do nothing.
    Else, select y > x and add it into A.
    Do these operations in descending order, i.e. if x < y, process y before processing x.

    Now it seems that each iteration for x makes sure that A will contain an element larger than x, yet no iteration will actually add anything to A: For each x being iterated, some y > x must have been iterated earlier, resulting that there already must be element larger than x in A. ?
  2. jcsd
  3. Sep 23, 2009 #2
    Right - it seems that the machine will be caught in an infinite loop looking for the largest element.
  4. Sep 23, 2009 #3
    For "step-by-step" operations of this kind, the usual requirement on the ordered set would be "well ordered" (or in your case, reverse well ordered).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook