By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

Rigidity of the Turing degrees

Every order automorphism of the full partial order of Turing degrees (D_T, \leq_T) is the identity: \forall \pi \in \mathrm{Aut}(\mathcal{D}_T, \leq_T)\ \forall \mathbf{a} \in \mathcal{D}_T\ \pi(\mathbf{a}) = \mathbf{a}, working in ZFC with no definability or regularity hypothesis on \pi.

The Turing-degree ordering is biinterpretable without parameters with full second-order arithmetic, in the sense of [11, Definition 7.5.1].

For any Borel map F : \mathbb{R} \to 2^{\mathbb{N}} with countable fibers satisfying F(x+y) \leq_T F(x) \oplus F(y) for all x,y \in \mathbb{R}, and for every irrational t \in (0,1), there is a comeager set G_t \subseteq \mathbb{R}^2 such that for each (u,v) \in G_t there is a rational \delta \in (0,1) for which C(t) \leq_T F(u) \oplus F(u-v) \oplus F(v-u+\delta t) \oplus F(v-u+\delta(t-1)).

For an arbitrary \pi \in \mathrm{Aut}(\mathcal{D}_T, \leq_T), there is a Borel function F : \mathbb{R} \to 2^{\mathbb{N}} with countable fibers such that [F(x)]_T = \pi(d(x)) and F(x+y) \leq_T F(x) \oplus F(y) for all x,y \in \mathbb{R}.

If A, Y \subseteq \mathbb{N} with Y \not\leq_T A, then \{(u,v) \in \mathbb{R}^2 : Y \leq_T A \oplus C(u) \oplus C(v)\} is meager.

Methods

Encoding real numbers x \in \mathbb{R} as strict rational cuts C(x) = \{i : q_i < x\} \in 2^{\mathbb{N}} using a fixed effective listing (q_i)_{i \in \mathbb{N}} of \mathbb{Q}, with Turing degree d(x) = [C(x)]_T.

Source excerpts

“To distinguish ordinary real numbers from oracle sets, fix an effective listing (q_i)_{i \in \mathbb{N}} of \mathbb{Q} and put C(x) = \{i : q_i < x\}, d(x) = [C(x)]_T (x \in \mathbb{R}).” · Show in paper

Recovering an irrational parameter t \in (0,1) from four values of a Borel map F : \mathbb{R} \to 2^{\mathbb{N}} by using a bounded recurrence sn+1s_{n+1} = s_n + \delta(t - r_n) with r_n \in \{0,1\} selected by a single bit of F(u+s_n) to keep s_n confined to [b_-, b_+], and approximating t by A_N = N−1N^{-1}\sum_{n<N} r_n with error less than 1/(N\delta).

Source excerpts

“For a fixed positive rational \delta, start with a real state s_0 = 0 and repeatedly choose the increment \delta t or \delta(t - 1), recording the choice as r_n = 0 or r_n = 1, respectively. Summing these increments gives s_N = \delta(N t - \sum_{n<N} r_n).” · Show in paper

“Define s_0 = 0 and, recursively, r_n = 1 if F(u + s_n)(j) = h, 0 if F(u + s_n)(j) \neq h, sn+1s_{n+1} = s_n + \delta(t - r_n).” · Show in paper

Removing auxiliary real parameters (u,v) from a Turing-degree bound that holds on a comeager set of pairs by applying Sacks's relative category cone-avoidance principle for rational-cut oracles.

Source excerpts

“Lemma 2.3 will remove auxiliary real parameters from a degree bound that holds on a comeager set of pairs. It is the relative category cone-avoidance principle attributed to Sacks in [4, Lemma 4.1]. We include the version for rational-cut oracles that our proof requires.” · Show in paper