In mathematical logic

Mathematical logic

Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

, especially set theory

Set theory

Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

 and model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

, the back-and-forth method is a method for showing isomorphism

Isomorphism

In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

 between countably 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 between linear orders is simply a strictly increasing bijection
  Bijection
  A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
  
  . This result implies, for example, that there exists a strictly increasing bijection between the set of all rational number
  Rational number
  In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
  
  s and the set of all real
  Real number
  In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
  
   algebraic number
  Algebraic number
  In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients. Numbers such as π that are not algebraic are said to be transcendental; almost all real numbers are transcendental...
  
  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 models of a theory are isomorphic.

• It can be used to prove that the Erdős–Rényi model
  Erdos–Rényi model
  In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
  
   of random graph
  Random graph
  In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
  
  s, when applied to countably infinite graphs, always produces a unique graph, the Rado graph
  Rado graph
  In the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique countable graph R such that for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an...
  
  .

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.

History

According to Hodges (1993):

Back-and-forth methods are often ascribed to Cantor

Georg Cantor

Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...

, Bertrand Russell

Bertrand Russell

Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...

 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 by Roland Fraïssé

Roland Fraïssé

Roland Fraïssé was a French mathematical logician. He received his doctoral degree from the University of Paris in 1953. In his thesis, Fraïssé used the back-and-forth method to determine whether two model-theoretic structures were elementarily equivalent...

 in model theory

Model theory

In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

.

See also: Ehrenfeucht–Fraïssé game

Ehrenfeucht–Fraïssé game

In the mathematical discipline of model theory, the Ehrenfeucht–Fraïssé game is a technique for determining whether two structures...

.