10,958 Pages

Not to be confused with the circle in Steinhaus-Moser Notation.

Friedman's circle theorem is a theorem due to Harvey Friedman that leads to a fast-growing function $$\text{Circle}(n)$$ that eventually dominates all recursive functions provably total in Peano arithmetic.

## Description

Let $$C_1, C_2, C_3, \ldots, C_n$$ be a finite sequence of non-intersecting circles in the plane, and let $$C_{[a, b]}$$ denote $$C_a \cup C_{a+1} \cup \ldots \cup C_{b-1} \cup C_{b}$$. Call $$C_1, C_2, C_3, \ldots, C_n$$ a $$k$$-good sequence if there exists $$k \le i < j \le \lfloor n/2 \rfloor$$ such that there is a homeomorphism of the plane that maps $$C_{[i,2i]}$$ into $$C_{[j,2j]}$$. The theorem states that, given a positive integer $$k$$, there exists a number $$n$$ such that all sequences $$C_1, C_2, \ldots, C_n$$ are $$k$$-good.

A homeomorphism is defined as a bijection $$f$$ such that both $$f$$ and $$f^{-1}$$ are continuous (having no jumps or gaps).

Let $$\text{Circle}(k)$$ be the largest $$n$$ such that there exists a sequence of length $$n$$ that is not $$k$$-good. It can be shown that $$\text{Circle}(1) = 5$$ and $$\text{Circle}(2) \geq 13$$. In general, $$\text{Circle}(k)$$ grows at the rate of $$f_{\varepsilon_0}(k)$$ in the fast-growing hierarchy.

## Forest interpretation

For any collection S of circles in the plane, we can naturally interpret S as a forest, with each circle corresponding to a different vertex in the forest. Root vertices will correspond to circles that are not contained in any other circles. If vertex v corresponds to a circle C, then the children of v will correspond to the circles in S that are contained in C with no intermediate circles in between. A circle $$C_1$$ will be contained in a circle $$C_2$$ if and only if the corresponding vertex $$v_1$$ is a descendent of $$v_2$$.

For any pair of collections of circles $$S_1$$ and $$S_2$$ with corresponding forests $$F_1$$ and $$F_2$$, there will be a homeomorphism of $$S_1$$ into $$S_2$$ if and only if there is an embedding of $$F_1$$ into $$F_2$$ (in other words, an isomorphism of $$F_1$$ into a subforest of $$F_2$$).

Thus, we can rephrase the definition of Circle(k) to be the largest n such that there exists a forest F with n vertices labelled 1 through n satisfying the following: Let $$F_i$$ be the subforest of $$F$$ consisting of vertices labelled i through 2i (if we deleted a vertex between any vertex and its descendant latter vertex connects to its first undeleted ancestor). Then for any $$k \le i < j \le \lfloor n/2 \rfloor$$, there does not exist an embedding of $$F_i$$ into $$F_j$$.