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 = { a₁, a₂, a₃, … },

B = { b₁, b₂, b₃, … }.

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 a_i is not yet paired with any member of B. Let j be some index such that b_j is not yet paired with any member of A and a_i can be paired with b_j consistently with the requirement that the pairing be strictly increasing. Pair a_i with b_j.

(2) Let j be the smallest index such that b_j is not yet paired with any member of A. Let i be some index such that a_i is not yet paired with any member of B and b_j can be paired with a_i consistently with the requirement that the pairing be strictly increasing. Pair b_j with a_i.

(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 a_p and a_q in A corresponding to b_p and b_q in B respectively such that a_p < a_i < a_q and b_p < b_q, we choose b_j in between b_p and b_q 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 b_j 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:

“Preaching is the expression of the moral sentiment in application to the duties of life.”
—Ralph Waldo Emerson (1803–1882)

“The human mind is capable of excitement without the application of gross and violent stimulants; and he must have a very faint perception of its beauty and dignity who does not know this.”
—William Wordsworth (1770–1850)

“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)

“I am aware that I have been on many a man’s premises, and might have been legally ordered off, but I am not aware that I have been in many men’s houses.”
—Henry David Thoreau (1817–1862)

“Analysis as an instrument of enlightenment and civilization is good, in so far as it shatters absurd convictions, acts as a solvent upon natural prejudices, and undermines authority; good, in other words, in that it sets free, refines, humanizes, makes slaves ripe for freedom. But it is bad, very bad, in so far as it stands in the way of action, cannot shape the vital forces, maims life at its roots. Analysis can be a very unappetizing affair, as much so as death.”
—Thomas Mann (1875–1955)