Weak systems of determinacy and arithmetical quasi-inductive definitions

Philip Welch University of Bristol

Barcelona, June 10, 2004

(Paper & slides - of the same title - available at www.bris.ac.uk/˜ mapdw)

Arithmetic operators

We consider arithmetic definitions of operators. Definition 1 An operator Γ : P(ℕ) → P(ℕ) is an arithmetic operator if “n ∈ Γ(X)” is an arithmetic relationship over

ℕ = ⟨ℕ, +, ×, 0,′ , …, X⟩ (by a formula in an appropriate language with a symbol Ẋ). Thus:

Γ(X) = { n | ⟨ℕ, +, ×, 0,′ , …, X⟩ ⊧ φ[n, X] }.

Define the following iterates: Γ_{0}(X) = X; Γ_{α+1}(X) = Γ(Γ_{α}(X)); Γ_{λ}(X) =?

Monotone Operators

Definition 2 Γ is monotone iff ∀X ⊆ Y Γ(X) ⊆ Γ(Y)

In this case we set:

Γ_{λ}(X) = ⋃_{α<λ} Γ_{α}(X)

Clearly Γ monotone implies there will be fixed points:

Definition 3 We say that Γ reaches a fixed point on X, if there is α so that Γ_{α}(X) = Γ_{α+1}(X); and if so we call Γ_{∞}(X) = Γ_{α}(X) the least fixed point (over X).

Clearly α will be countable.

Definition 4 We say X is arithmetically inductive if for some monotone arithmetical operator Γ : P(ℕ × ℕ) → P(ℕ × ℕ) there is m_{0} so that

X = {n | (n, m_{0}) ∈ Γ_{∞}(∅)}

Theorem 1 (Spector, Gandy, Moschovakis) The inductive sets over ℕ are precisely the Π_{1}^{1} sets.

Arithmetical quasi-inductive definitions.

Let Γ : P(ℕ) → P(ℕ) be an arithmetic operator. Define iterates as before except for limits λ:

Γ_{λ}(X) = lim inf_{α→λ} Γ_{α}(X) = ∪_{α<λ} ∩_{λ>β>α} Γ_{β}(X).

Any such operator has a least countable ζ = ζ(Γ) with Γ_{ζ}(∅) = Γ_{On}(∅).

Definition 5 Y ⊆ ω is arithmetically quasi-inductive if for some such Γ, Y is (1-1) reducible to Γ_{On}(∅).

Examples

• H.Field “Revenge-immune Solution to the Semantic Paradoxes”, J.Philosophical Logic, April 2003.

• J.Hamkins & A.Lewis “Infinite Time Turing Machines, JSL 2002.

• H.Herzberger “Notes on Naive Semantics”

• S. Kreutzer Partial fixed point logic on infinite structures, Annual Conference of the European Association for Computer Science Logic (CSL), 2002, Lecture Notes in Computer Science, 2471.

Proposition 1 (Burgess) (i) A set Y is arithmetical quasi-inductive iff Y ∈ Σ_{2}(L_{ζ}). (ii) ζ is the least Σ_{2}-extendible ordinal; that is the least ζ so that there is a Σ > ζ with L_{ζ} ≺_{Σ_{2}} L_{Σ}.

Proposition 2 There is a recursive operator Γ with ζ(Γ) = ζ.

Some quasi-inductive definitions may reach a fixed point.

Definition 3 We say that Γ reaches a fixed point on X, if there is α so that Γ_{α}(X) = Γ_{α+1}(X); and if so we call Γ_{α}(X) the fixed point.

Definition 4 A repeat pair (ζ(Γ, X), Σ(Γ, X)) is a pair of ordinals so that Γ_{ζ}(X) = Γ_{Σ}(X). If an arithmetic operator Γ acting on X has a repeat pair, we say that Γ converges (with input X).

Definition 5 (i) AQI is the sentence:

“For every arithmetic operator Γ, for every X ⊆ ω, there is a wellordering W with a repeat pair (ζ(Γ, X), Σ(Γ, X)) in Field(W)”.

(ii) If an arithmetic operator Γ acting on X has a repeat pair, we say that Γ converges (with input X).

A certain amount of set theory (or analysis) is needed to show that every operator converges.

Question: How strong in terms of analysis is AQI?

A (set-theoretical) answer using Prop. 1, this is thus: Lemma 6 KP ⊢ AQI ⟷ ∀X ⊆ ω ∃ξ, σ(L_{ξ}[X] ≺_{Σ_{2}} L_{σ}[X]).

A slide for Proof Theorists

Recall: The strength of Π_{2}^{1}-CA_{0} by work of Rathjen is tied up with analysing chains of finite length L_{κ_{n}} ≺_{Σ_{1}} L_{κ_{n+1}}.

• The first level L_{α} which is an infinite tower of such models, is the first whose reals form a β-model of Π_{2}^{1}-CA_{0}. Equivalently , it is the least α so that L_{α} ⊧ Σ_{1}-Separation.

The same occurs for Π_{3}^{1}-CA_{0}:

•The first L_{γ} whose reals form a β-model of Π_{3}^{1}-CA_{0} is the union of an infinite tower of models L_{ζ_{n}} ≺_{Σ_{2}} L_{ζ_{n+1}}. Equivalently, it is the least α so that L_{γ} ⊧ Σ_{2}-Separation.

Moral: if anyone is to analyse Π_{3}^{1}-CA_{0}, they will have to analyse AQI along the way.

Games of perfect information

Theorem 2 (Martin) ZF C proves that all Borel games are determined. Theorem 3 (H. Friedman) Weaker theories (e.g. of analysis) cannot prove Det(Borel). In fact Σ_{4}^{0}-Determinacy requires ZF C^{−}.

Determinacy and Inductive Definitions

Theorem 4 Any Σ_{1}^{0}-game has a monotone Π_{1}^{1}-inductive strategy (if I wins), in fact a strategy σ ∈ L_{ω_{1}^{ck}}; if II wins, then a strategy can be found Π_{1}(L_{ω_{1}^{ck}}).

Theorem 5 (Solovay) Any Σ_{2}^{0}-game has a monotone Σ_{1}^{1}- inductive strategy (if I wins), i.e. a strategy σ ∈ L_{σ_{1}^{1}}; if II wins, then a strategy can be found in L_{(σ_{1}^{1})^{+}}.

A slide for Reverse Mathematicians

Theorem 6 (Steel) Over RCA_{0} the following are equivalent:

(i) arithmetical transfinite recursion; (ii)Det(Σ_{1}^{0}); (iii)Det(Δ_{1}^{0})

Theorem 7 (Tanaka) Over RCA_{0} the following are equivalent:

(i) Σ_{1}^{1}-MI; (ii)Det(Σ_{2}^{0})

The strength of AQI

We locate winning strategies for various Σ_{3}^{0}-games in the L-hierarchy in order to prove the following:

Theorem 8 KP +Σ_{2}-Separation ⊢ ∃ a β-model of Δ_{3}^{1}-CA_{0} + Σ_{3}^{0}-Determinacy .

Alternatively: Π_{3}^{1}-CA_{0} ⊢ there is a β-model of Δ_{3}^{1}-CA_{0} + Σ_{3}^{0}-Determinacy .

The implication is not reversible.

Theorem 9 KP +Δ_{2}-Comprehension +Σ_{2}-Collection +AQI ⊬Σ_{3}^{0}-Determinacy .

Alternatively: Theorem 10 Δ_{3}^{1}-CA_{0} + AQI ⊬Σ_{3}^{0}-Determinacy . In short: in descending order of strength are: Π_{3}^{1}-CA_{0} >> Δ_{3}^{1}-CA_{0} + Σ_{3}^{0}-Determinacy >>

>> Δ_{3}^{1}-CA_{0}+AQI >> Δ_{3}^{1}- CA_{0}.

Proof: Let δ be least so that L_{δ} ⊧ Σ_{2} -KP +AQI. We show L_{δ} |̸=Σ_{3}^{0}-Determinacy . (Note that the latter is itself a Σ_{1}^{KP} sentence.) Let Ψ = Σ_{1}-T h(L_{δ}). For ψ ∈ Ψ, let α_{ψ} be least so that L_{α} ⊧ KP + ψ. One shows that for each such ψ there is a Π_{3}^{0} game, G_{ψ}, without a winning strategy in L_{α_{ψ}}. Fix such a ψ ∈ Ψ. I plays m_{0,}m_{1,} …, m_{i} x = (m_{0,}m_{1,} …, m_{i}, …) II plays n_{0,}n_{1,} …, n_{i} y = (n_{0,}n_{1,} …, n_{i}, …) Rules for I. Let T be the theory KP +V = L + ψ. x must be a code for the complete Σ_{1} ∪ Π_{1}-theory of an ω-model of T +“there is no set model of T ”.

Approximate Rules for II. In effect she tries to build an r_{n+1} <_{M} r_{n}- descending chain through the ordinals that I defines using Σ_{1}-terms. At any move she may “pass” by playing n_{k} = 0, or she can pick out one of the terms I has previously played as defining an ordinal, which is <_{M} below her previous choice.

II wins if both players obey their rules, and infinitely often II does not pass.

Lemma 7 I has a winning strategy.

(Play A_{α_{ψ}} =_{df} the true Σ_{1} theory of L_{α_{ψ}}).

Lemma 8 Let σ be any winning strategy for I in G_{ψ}. Then A_{α_{ψ}} ≤_{T} σ.

As A =_{df} A_{α_{ψ}} ∉ L_{α_{ψ}} this implies σ ∉ L_{α_{ψ}} for any such σ as we required.

The key lemma says the only way I can win is by playing the truth.

Lemma 9 Let σ be any strategy for I. If at any stage I asserts “ m_{k} = τ \frac{∈}{∉}A”, whilst in fact τ \frac{∉}{∈}A then II can win.

We have to describe how II can win in this latter case. This amounts to showing how, under our “smallness” assumption about δ, the L-hierarchy up to δ is sufficiently simple, and consequently for any code x of an ω-model of the theory of one of its levels L_{α}, if the model is illfounded, then recursively in x and A_{α} the standard Σ_{1} code of L_{α} we can pick out a descending chain through the ordinals named by Σ_{1}-Skolem terms in that theory x.

Suppose I plays an untruth. Then II knows M will be illfounded.

Suppose I says “τ_{0} is a Σ_{1} truth of M as first witnessed at stage a_{0} + 1 = t_{l}” (where ⟨t_{i}|i < ω⟩ enumerates all Σ_{1}-terms), and II sees τ_{0} ∉ A.

Then II could put r_{0} = t_{l} at the head of her putative descending chain. She then waits until I says “τ_{1} is a Σ_{1} truth of M as first witnessed at stage a_{1} = t_{p} ∧ t_{p} < t_{l} ”, and II sees τ_{1} ∉ A. II could then set r_{1} = t_{p} < r_{0}.

However this will not work: I could force II down into a stretch of the M-ordinals of the form [b, b + β) where β = β_{M} =_{df} On^{M} ∩ W F P (M). II is stuck: there may be no new Σ_{1}-M-truths becoming true in the interval (β, b).

Suppose I plays an untruth. Then II knows M will be illfounded. Suppose II somehow knew what β_{M} was going to be.

• She waits for an r_{0} = t_{l} as before. For γ ∈ On let T^{γ} =_{df} Σ_{2}-T h(L_{γ}).

• Now she waits until I says: “τ_{1} ∈ T^{r_{0}}” but II sees that τ_{1} ∉ T^{β}. Claim: (For some such t_{l}) There is such a τ_{1}. (Using leastness of δ.) She continues to wait until I says: “t_{l} is the least ordinal so that ∀c ∈ (t_{l}, r_{0}]L_{c} ⊧ τ_{1}”

• She then sets r_{1} = t_{l} < r_{0}.

• Note r_{1} ∉ W F P (M), for otherwise τ_{1} ∈ T^{β}.

She continues to wait until I says: “t_{p} is the least ordinal so that ∀c ∈ (t_{p}, r_{1}]L_{c} ⊧ τ_{2} where τ_{2} ∈ T^{r_{1}}” but II knows that τ_{2} ∉ T^{β}. She then sets r_{2} = t_{p} < r_{1}. Etc.

However this tactic can also fail: I may force II down into W F P (M) by playing so that II sets r_{n} = t_{l} say, but we have (L_{a} ≺_{Σ_{2}} L_{r_{n}})_{M} and a ∈ β. Then (T^{r_{n}})_{M} = T^{a} ∈ L_{β}.

Let ⟨β_{i}|i < ω⟩ enumerate the admissibles ≤ α_{ψ}. The correct Rules for II involve expressing ℕ = ⊕_{i,u}A_{i,u} with each A_{i,u} infinite, and in rounds k with k ∈ A_{i,u} she plays with the working assumption that β_{M} = β_{i}, and building putative chains r_{n+1}^{i} <^{M} r_{n}^{i} <^{M} … <^{M} r_{0}^{i} = t_{u}. II then wins iff “∃i, u({n_{k}|k ∈ A_{i,u} ∧ n_{k} ≠ 0} is infinite).” This is a Σ_{3}^{0} condition for II.