Jordan curve theorem

In

The Jordan curve theorem is named after the mathematician Camille Jordan (1838–1922), who published its first claimed proof in 1887.^[1][2] For decades, mathematicians generally thought that this proof was flawed and that the first rigorous proof was carried out by Oswald Veblen. However, this notion has been overturned by Thomas C. Hales and others.^[3]

Definitions and the statement of the Jordan theorem

A Jordan curve or a simple closed curve in the plane R² is the

The Jordan curve theorem can be proved from the Brouwer fixed point theorem (in 2 dimensions),^[4] and the Brouwer fixed point theorem can be proved from the Hex theorem: "every game of Hex has at least one winner", from which we obtain a logical implication: Hex theorem implies Brouwer fixed point theorem, which implies Jordan curve theorem.^[5]

It is clear that Jordan curve theorem implies the "strong Hex theorem": "every game of Hex ends with exactly one winner, with no possibility of both sides losing or both sides winning", thus the Jordan curve theorem is equivalent to the strong Hex theorem, which is a purely discrete theorem.

The Brouwer fixed point theorem, by being sandwiched between the two equivalent theorems, is also equivalent to both.^[6]

In reverse mathematics, and computer-formalized mathematics, the Jordan curve theorem is commonly proved by first converting it to an equivalent discrete version similar to the strong Hex theorem, then proving the discrete version.^[7]

Application to image processing

In image processing, a binary picture is a discrete square grid of 0 and 1, or equivalently, a compact subset of ${\displaystyle \mathbb {Z} ^{2}}$. Topological invariants on ${\displaystyle \mathbb {R} ^{2}}$, such as number of components, might fail to be well-defined for ${\displaystyle \mathbb {Z} ^{2}}$ if ${\displaystyle \mathbb {Z} ^{2}}$ does not have an appropriately defined graph structure.

There are two obvious graph structures on ${\displaystyle \mathbb {Z} ^{2}}$:

• the "4-neighbor square grid", where each vertex ${\displaystyle (x,y)}$ is connected with ${\displaystyle (x+1,y),(x-1,y),(x,y+1),(x,y-1)}$.
• the "8-neighbor square grid", where each vertex ${\displaystyle (x,y)}$ is connected with ${\displaystyle (x',y')}$ iff ${\displaystyle |x-x'|\leq 1,|y-y'|\leq 1}$, and ${\displaystyle (x,y)\neq (x',y')}$.

Both graph structures fail to satisfy the strong Hex theorem. The 4-neighbor square grid allows a no-winner situation, and the 8-neighbor square grid allows a two-winner situation. Consequently, connectedness properties in ${\displaystyle \mathbb {R} ^{2}}$, such as the Jordan curve theorem, do not generalize to ${\displaystyle \mathbb {Z} ^{2}}$ under either graph structure.

If the "6-neighbor square grid" structure is imposed on ${\displaystyle \mathbb {Z} ^{2}}$, then it is the hexagonal grid, and thus satisfies the strong Hex theorem, allowing the Jordan curve theorem to generalize. For this reason, when computing connected components in a binary image, the 6-neighbor square grid is generally used.^[8]

Steinhaus chessboard theorem

The Steinhaus chessboard theorem in some sense shows that the 4-neighbor grid and the 8-neighbor grid "together" implies the Jordan curve theorem, and the 6-neighbor grid is a precise interpolation between them.^[9][10]

The theorem states that: suppose you put bombs on some squares on a ${\displaystyle n\times n}$ chessboard, so that a king cannot move from the bottom side to the top side without stepping on a bomb, then a rook can move from the left side to the right side stepping only on bombs.

History and further proofs

The statement of the Jordan curve theorem may seem obvious at first, but it is a rather difficult theorem to prove. Bernard Bolzano was the first to formulate a precise conjecture, observing that it was not a self-evident statement, but that it required a proof.^[11] It is easy to establish this result for

The first proof of this theorem was given by Camille Jordan in his lectures on real analysis, and was published in his book Cours d'analyse de l'École Polytechnique.^[1] There is some controversy about whether Jordan's proof was complete: the majority of commenters on it have claimed that the first complete proof was given later by Oswald Veblen, who said the following about Jordan's proof:

His proof, however, is unsatisfactory to many mathematicians. It assumes the theorem without proof in the important special case of a simple polygon, and of the argument from that point on, one must admit at least that all details are not given.^[12]

However, Thomas C. Hales wrote:

Nearly every modern citation that I have found agrees that the first correct proof is due to Veblen... In view of the heavy criticism of Jordan’s proof, I was surprised when I sat down to read his proof to find nothing objectionable about it. Since then, I have contacted a number of the authors who have criticized Jordan, and each case the author has admitted to having no direct knowledge of an error in Jordan’s proof.^[13]

Hales also pointed out that the special case of simple polygons is not only an easy exercise, but was not really used by Jordan anyway, and quoted Michael Reeken as saying:

Jordan’s proof is essentially correct... Jordan’s proof does not present the details in a satisfactory way. But the idea is right, and with some polishing the proof would be impeccable.^[14]

Earlier, Jordan's proof and another early proof by Charles Jean de la Vallée Poussin had already been critically analyzed and completed by Schoenflies (1924).^[15]

Due to the importance of the Jordan curve theorem in

• Elementary proofs were presented by Filippov (1950) and Tverberg (1980).
• A proof using
  non-standard analysis by Narens (1971)
  .
• A proof using constructive mathematics by Gordon O. Berg, W. Julian, and R. Mines et al. (1975).
• A proof using the
  Brouwer fixed point theorem by Maehara (1984)
  .
• A proof using non-planarity of the complete bipartite graph K_3,3 was given by Thomassen (1992).

The root of the difficulty is explained in Tverberg (1980) as follows. It is relatively simple to prove that the Jordan curve theorem holds for every Jordan polygon (Lemma 1), and every Jordan curve can be approximated arbitrarily well by a Jordan polygon (Lemma 2). A Jordan polygon is a polygonal chain, the boundary of a bounded connected open set, call it the open polygon, and its closure, the closed polygon. Consider the diameter ${\displaystyle \delta }$ of the largest disk contained in the closed polygon. Evidently, ${\displaystyle \delta }$ is positive. Using a sequence of Jordan polygons (that converge to the given Jordan curve) we have a sequence ${\displaystyle \delta _{1},\delta _{2},\dots }$ presumably converging to a positive number, the diameter ${\displaystyle \delta }$ of the largest disk contained in the

${\displaystyle \delta _{1},\delta _{2},\dots }$

The first

${\displaystyle {\mathsf {RCA}}_{0}}$

Application

In computational geometry, the Jordan curve theorem can be used for testing whether a point lies inside or outside a simple polygon.^[16][17][18]

From a given point, trace a

• Denjoy–Riesz theorem, a description of certain sets of points in the plane that can be subsets of Jordan curves
• Lakes of Wada
• Quasi-Fuchsian group, a mathematical group that preserves a Jordan curve

Notes