- 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.[1]
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\).
Sources[]
- ↑ H. Friedman, "Enormous integers in real life"