[figure]

Coding in R_{m} and E

André Nies, The University of Chicago

[figure]

Outline

R_{m}: upper semilattice of computably enumerable many-one degrees E: c.e. sets under inclusion

Theorem 1 (N ’92) Th(ℕ, +, ×) can be interpreted in Th(R_{m})

Theorem 2 (Harrington ’94) Th(ℕ, +, ×) can be interpreted in Th(E)

[figure]

Coding

A is coded in B if, with an appropriate scheme of formulas in language of B, an isomorphic copy of A is defined in B. Examples:

• ℚ is coded in ℤ, where the formulas are given by the usual quotient field construction.

• The finite distributive lattices are (uniformly) coded in R_{m}:

∀L ∃a ∈ R_{m} L ≅ [0, a]_{R_{m}}.

Call a a parameter.

[figure]

A path of investigation

The following was done for A = D_{T} (≤ ∅′) and A = R_{T}.

1. Study Th(A)

(a) Th(A) undecidable

(b) Th(ℕ, +, ×) ≤_{m} Th(A)

2. Study A as a structure

(a) DY results + restrictions on automorphisms

(b) Code ℕ without parameters

(c) Biinterpretability of A, ℕ (possibly with parameters) ?

[figure]

Biinterpretability with parameters

“For some list of constants \overline{a} ∈ A, A, \overline{a} is model theoretically equivalent to ℕ”

• M coded copy of ℕ (called a standard model)

• F : A ↦ M 1-1

• everything definable with params \overline{a}

Consequences

• Automorphisms determined by what they do to \overline{a}. BUT: R_{m}, E have uncountably many !

• R has arithmetical index set ⇒ R parameter definable BUT: This is false for R_{m}, E !

[figure]

Interpreting Th(ℕ, +, ×) for R_{m}, E

The basic idea behind both proofs is still the idea which underlies biinterpretability: Arithmetical definability ⇒ definability (with parameters) in the structure More precisely:

• Prove uniform definability of relations (of a certain type) which have an Σ_{k}^{0} index set

• Do this by induction over k

Such a result is called an arithmetical definability lemma (ADL)

[figure]

How to interpret Th(ℕ, +, ×)

a) Obtain a scheme

φnum(x; \overline{p}), φ_{+}(x, y, z; \overline{p}), φ_{×}(x, y, z; \overline{p})

such that for some special list \overline{p}, a (called standard model) is coded

b) recognize by a f.o.-formula ψ(\overline{p}) whether arbitrary parameters code a standard model

A sufficiently strong ADL may be used for both (a) and (b)

[figure]

The ADL for R_{m}

Lemma 1 For each k ≥ 3, the class of n -ary relation which have a Σ_{k}^{0} index set and are included in [0, e]^{n} for some e < 1 is uniformly definable. In fact there is a fmla φ_{k}(x_{1}, …, x_{n}; e, b) such that, as b varies,

{x_{1}, …, x_{n} : R_{m} ⊧ φ_{k}(x_{1}, …, x_{n}; e, b)}

includes all such relations (and more).

[figure]

Coding a standard model

• Pick any e < 1 such that [0, e] is infinite.

• Since “W_{i} ≢_{m} W_{j}” is ≤_{T} ∅^{(3)}, we can define an h ≤_{T} ∅^{(3)} such that the sequence

a_{n} = deg_{m}(W_{h(n)}

consist of pairwise distinct degrees ≤ e.

• The set {a_{i} : i ∈ ω}, and addition and multiplication (viewed as ternary relations on this set) have Σ_{4}^{0} index sets. So using the ADL can define this standard model with params b_{M}, b_{+}, b_{×}.

[figure]

Recognizing standardness

Consider any list \overline{p} (including an upper bound on elements e). Can require in a f.-o.-way that e < 1 and

• the scheme introduced above codes with \overline{p} a model M = (M, +, ×) of basic arithmetic such that M ⊆ [0, e]

• M is standard.

The standard part S of any such M has a Σ_{c}^{0} index set (fixed c): deg_{m}(W_{e}) ∈ S ⇔ can pass by finitely many applications of the successor function of M from 0^{M} to deg_{m}(W_{e}).

[figure]

So by the uniformity of the ADL (Σ_{c}^{0}- case), can express that M is standard: “each subset of M defined by the formula for Σ_{c}^{0}-sets which contains 0^{M} and is closed under successor equals M.”

[figure]

Proving the ADL for R_{m}

Induction start: k = 3 Reduce it to the following: if (d_{i}) is a u.c.e. sequence of incomplete m-degrees, then can uniformly define {d_{i} : i ∈ ω}. Do this by putting an antichain of strong minimal covers (c_{i}) on top of the d_{i}. If [0, e) is the ideal generated by the c_{i}, then

{d_{i}} = maximal elts < e with s.m.c.

Induction step: k ⇒ k + 1 View a relation S with Π_{4}^{0} index set as a uniform intersection of Σ_{3}^{0} relations.

[figure]

The ADL for E

A c.e. non recursive set

• B(A)= the Boolean algebra of components of r.e. splittings of A

• R(A) = the ideal of B(A) consisting of the recursive subsets of A.

• An ideal I of B(A) is k-acceptable if R(A) ⊆ I, and {e : W_{e} ∈ I} is Σ_{k}^{0}.

For instance, R(A) is 3-acceptable.

[figure]

The Ideal Definability Lemma

Lemma 2 (Harrington) Let k ≥ 3 be odd. Then the k-acceptable ideals of B(A) can be uniformly defined with parameters. In fact there is a fmla φ_{k}(X; A, \overline{C}) such that for varying \overline{C},

\{X : E ⊧ φ_{n}(X; A, \overline{C})\}

ranges over the k− acceptable ideals, and nothing else.

[figure]

Proving the ADL for E

Induction start: k = 3

φ_{3}(X; A, C) ≡ X ⊏ A∧(∃R ⊆ A rec )X ⊆ C ∪R.

Show that for each 3-acceptable I there is a C_{I} Induction step: k ⇒ k + 2. There is a C ⊆ A such that we can reduce the problem of defining a k + 2- acceptable ideal of B(A) to defining a k-acceptable of B(C).

[figure]

Interpreting Th(ℕ, +, ×) in Th(E)

Uses the same background: e.g. standard part of coded M has an arithmetical index set. But, it is harder. For instance, to code some standard model M with a special list,

• work with a hh-simple A such that L^{∗}(A) has ∞ many atoms.

• elements of M are atoms in B(A)/I , for some 7- acceptable I

• define +, × by further ideals, using the interaction of L^{∗}(A) and B(A)

The currently best coding gives undecidability of Σ_{6}^{0}-Th(E^{∗}, ∨, ∧) [N ta]