Back-and-forth Method - Application To Densely Ordered Sets

Application To Densely Ordered Sets

Suppose that

  • (A, ≤A) and (B, ≤B) are linearly ordered sets;
  • They are both unbounded, in other words neither A nor B has either a maximum or a minimum;
  • They are densely ordered, i.e. between any two members there is another;
  • They are countably infinite.

Fix enumerations (without repetition) of the underlying sets:

A = { a1, a2, a3, … },
B = { b1, b2, b3, … }.

Now we construct a one-to-one correspondence between A and B that is strictly increasing. Initially no member of A is paired with any member of B.

(1) Let i be the smallest index such that ai is not yet paired with any member of B. Let j be some index such that bj is not yet paired with any member of A and ai can be paired with bj consistently with the requirement that the pairing be strictly increasing. Pair ai with bj.
(2) Let j be the smallest index such that bj is not yet paired with any member of A. Let i be some index such that ai is not yet paired with any member of B and bj can be paired with ai consistently with the requirement that the pairing be strictly increasing. Pair bj with ai.
(3) Go back to step (1).

It still has to be checked that the choice required in step (1) and (2) can actually be made in accordance to the requirements. Using step (1) as an example:

If there are already ap and aq in A corresponding to bp and bq in B respectively such that ap < ai < aq and bp < bq, we choose bj in between bp and bq using density. Otherwise, we choose a suitable large or small element of B using the fact that B has neither a maximum nor a minimum. Choices made in step (2) are dually possible. Finally, the construction ends after countably many steps because A and B are countably infinite. Note that we had to use all the prerequisites.

If we iterated only step (1), rather than going back and forth, then in some cases the resulting function from A to B would fail to be surjective. In the easy case of unbounded dense totally ordered sets it is possible to avoid step 2 by choosing the element bj more carefully (by choosing j as small as possible), but this does not work for more complicated examples such as atomless Boolean algebras where steps 1 and 2 are both needed.

Read more about this topic:  Back-and-forth Method

Famous quotes containing the words application to, application, densely, ordered and/or sets:

    ““Five o’clock tea” is a phrase our “rude forefathers,” even of the last generation, would scarcely have understood, so completely is it a thing of to-day; and yet, so rapid is the March of the Mind, it has already risen into a national institution, and rivals, in its universal application to all ranks and ages, and as a specific for “all the ills that flesh is heir to,” the glorious Magna Charta.”
    —Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)

    “I conceive that the leading characteristic of the nineteenth century has been the rapid growth of the scientific spirit, the consequent application of scientific methods of investigation to all the problems with which the human mind is occupied, and the correlative rejection of traditional beliefs which have proved their incompetence to bear such investigation.”
    —Thomas Henry Huxley (1825–95)

    “I keep having the same experience and keep resisting it every time. I do not want to believe it although it is palpable: the great majority of people lacks an intellectual conscience. Indeed, it has often seemed to me as if anyone calling for an intellectual conscience were as lonely in the most densely populated cities as if he were in a desert.”
    —Friedrich Nietzsche (1844–1900)

    “The peace conference must not adjourn without the establishment of some ordered system of international government, backed by power enough to give authority to its decrees. ... Unless a league something like this results at our peace conference, we shall merely drop back into armed hostility and international anarchy. The war will have been fought in vain ...”
    —Virginia Crocheron Gildersleeve (1877–1965)

    “bars of that strange speech
    In which each sound sets out to seek each other,
    Murders its own father, marries its own mother,
    And ends as one grand transcendental vowel.”
    —Randall Jarrell (1914–1965)