Added to Favorites

Related Searches

In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular:## Application to densely ordered sets

## History

## References

- It can be used to prove that any two countably infinite densely ordered sets (i.e., linearly ordered in such a way that between any two members there is another) without endpoints are isomorphic. An isomorphism between linear orders is simply a strictly increasing bijection. This result implies, for example, that there exists a strictly increasing bijection between the set of all rational numbers and the set of all real algebraic numbers.
- It can be used to prove that any two countably infinite atomless Boolean algebras are isomorphic to each other.
- It can be used to prove that any two equivalent countable atomic models of a theory are isomorphic.

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
_{1}, a_{2}, a_{3}, … },

- B = { b
_{1}, b_{2}, b_{3}, … }.

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.

According to Hodges (1993):

- Back-and-forth methods are often ascribed to Cantor, Bertrand Russell and C. H. Langford […], but there is no evidence to support any of these attributions.

See also: Ehrenfeucht–Fraïssé game.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday July 23, 2008 at 19:40:32 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday July 23, 2008 at 19:40:32 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.