# Back-and-forth method

In

mathematical logic , especiallyset theory andmodel theory , the**back-and-forth method**is a method for showingisomorphism betweencountably infinite structures satisfying specified conditions. In particular:* 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 betweenlinear order s is simply a strictly increasingbijection . This result implies, for example, that there exists a strictly increasing bijection between the set of allrational number s and the set of all realalgebraic number s.* 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 model s of a theory are isomorphic.**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"

_{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.**History**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."While the theorem on countable densely ordered sets is due to Cantor (1895), the back-and-forth method with which it is now proved was developed by Huntington (1904) and Hausdorff (1914). Later it was applied in other situations, most notably byRoland Fraïssé inmodel theory .See also:

Ehrenfeucht–Fraïssé game .**References***

*

*

*

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Back and Forth (disambiguation)**— Back and Forth may refer to:*Back and forth, a method of showing isomorphism between countably infinite structures satisfying specified conditions. * Back and Forth , the self published debut album of Skinny Puppy, released in 1984 * Back and… … Wikipedia**Forth (programming language)**— infobox programming language name = Forth paradigm = Procedural, stack oriented year = 1970s designer = Charles H. Moore typing = typeless dialects = colorForth, Open Firmware implementations = Forth, Inc., GNU Forth, MPE influenced by =… … Wikipedia**Method ringing**— (also known as scientific ringing) is a form of change ringing (the practice of ringing a series of mathematical permutations on tuned bells, rather than a melody). In method ringing, the ringers are guided from permutation to permutation by… … Wikipedia**Method of loci**— The method of loci (plural of Latin locus for place or location), also called the memory palace, is a mnemonic device introduced in ancient Roman rhetorical treatises (in the anonymous Rhetorica ad Herennium, Cicero s De Oratore, and Quintilian s … Wikipedia**Scientific method**— … Wikipedia**Linguistics and the Book of Mormon**— Part of a series on The Book of Mormon … Wikipedia**Eye Movement Desensitization and Reprocessing**— (EMDR) is a form of psychotherapy that was developed to resolve symptoms resulting from disturbing and unresolved life experiences. It uses a structured approach to address past, present, and future aspects of disturbing memories. The approach… … Wikipedia**List of Doctor Who universe creatures and aliens**— This is a list of fictional creatures and aliens from the universe of the long running BBC science fiction television series Doctor Who, including Torchwood, The Sarah Jane Adventures and K 9. It covers alien races and other fictional creatures,… … Wikipedia**Bates method**— Alternative medicine / fringe therapies William Bates and his assistant. Claims The need for eyeglasses can be reversed by relaxation. Related fields Ophthalmo … Wikipedia**List of Torchwood monsters and aliens**— This is a list of monsters and aliens from the television series Torchwood .AAbaddonDoctorwhocharacter name=Abaddon series=Torchwood affiliation=Bilis Manger The Beast The Light race=Demon planet=Earth era=Before the dawn of time start= End of… … Wikipedia