Topics

in

Reverse Mathematics

Mariagnese Giusto

FOUNDATIONS OF THE FORMAL SCIENCES II Bonn, November 10 − 13^{th}, 2000

⋆ Summary ⋆

⋆ Motivations and scope of Reverse Mathematics ⋆ Two examples from Combinatorics:

- Free Set Theorem

- König’s Duality Theorem ⋆ Did Cantor need Set Theory? ⋆ Atsuji and Lebesgue spaces ⋆ Limits & Projects ✓ Main Question: What set-existence axioms

are needed for “ordinary mathematics”?

✓ Language L_{2}: number and set variables. Numerical terms (using n.v., 0,1, +, ·) Basic axioms of ordered semiring for (ℕ, +, 0, 1, <) and induction axiom. Comprehension scheme.

✓ Subsystems of Z_{2}: use classical first order logic and the language of second order arithmetic L_{2}; (restricted) induction axiom, restricted comprehension or additional axioms.

⋆ RCA_{0} : Δ_{1}^{0}-comprehension and Σ_{1}^{0}-induction

⋆ WKL_{0} : RCA_{0}+WKL WKL: If T is a subtree of 2^{<ℕ} with no infinite path, then T is finite

⋆ ACA_{0} : Arithmetical comprehension

⋆ ATR_{0} : ACA_{0}+ Arith. Transf. Recursion

(Turing jump operator can be iterated along any countable well ordering starting at any set)

WKL_{0} and Hilbert’s program

✓ Gödel: impossible to reduce all infinitistic mathematics to finitistic mathematics.

Tait: Finitism identified by P RA

We can reformulate the Main Question as follows:

⋆ How much infinitistic mathematics can be developed in subsystems of Z_{2} which are Π_{1}^{0} conservative over P RA?

T_{1}, T_{2} theories, Γ set of sentences. T_{2} is Γ-conservative over T_{1} if ∀φ[(φ ∈ Γ ∧ T_{2} ⊢ φ) ⇒ T_{1} ⊢ φ].

⋆ WKL_{0} is Π_{1}^{0}-conservative over P RA

✓ All theorems provable in WKL_{0} are finitistically reducible in this sense.

Over RCA_{0}, ACA_{0} ⟺ ∀ f : ℕ → ℕ one-to-one ∃X range of f, i.e. ∀n(n ∈ X ⟷ ∃m(f(m)=n))

Over RCA_{0}, ⋆ ACA_{0} ⟺ Monotone Convergence Theorem:

(“Every bounded increasing sequence of real numbers is convergent”).

Proof of the reversal in RCA_{0}. Let f : ℕ → ℕ be one-to-one.

Let c_{n} = ∑_{i=0}^{n} 2^{−f(i)}. c_{0} < c_{1} < ⋯ < 2

By Monotone Conv.Thm, there exists c = lim c_{n}. Easy to see that for all k

∃i(f(i) = k) ⟷

∀n(|c_{n} − c| < 2^{−k} → ∃i ≤ n (f(i) = k))

Free Sets

From the joint paper Cholak-Giusto-Hirst.

✓ The model theoretic notion of “free set”.

M(A) the smallest substructure of M = (M, R_{i}, f_{j}, c_{k}) generated by A ⊆ M.

A is free for M if and only if for all A′ ⊆ A, M(A′) ∩ A = A′.

Examples

⋆ linearly independent elements in a vector space.

⋆ algebraically independent elements in a field.

⋆ [X]^{k} the set of all increasing k-tuples of elements of X.

⋆ Denote the k-tuple (x_{1}, …, x_{k}) ∈ [X]^{k} by x̄.

⋆ Free Set Theorem (F S).

Fix k and let f : [ℕ]^{k} → ℕ. Then there exists an infinite A ⊆ ℕ such that for all x̄ ∈ A,

f(x̄) ∈ A ⟶ f(x̄) ∈ {x_{1}, …, x_{k}}

F S(k) is the statement F S for a fixed k ≥ 1.

✓ “If a set A ⊆ M is free for M then, for all j, A is free for f_{j} in the sense of the Free Set Theorem.”

Theorem. F S(1) is provable in RCA_{0}.

⋆ Lower bounds on the strength of F S ⋆

Lemma. There is a computable function f : [ℕ]^{2} → ℕ such that no infinite ω-r.e. set is free.

Idea of the proof: finite injury argument. As soon as we have 2 points x and y belonging to the same set A, we define f(x, −) = y. If A is infinite there is some z > max{x, y} in A. Hence A is not free for f.

Theorem (Friedman).

(1) ACA_{0} ≠⇒ F S.

(2) F S(2) fails in an ω-model of WKL_{0}.

Proof of (2): construct f computable s.t. for any infinite set A, if A is almost recursive, then f([A]^{2}) is cofinite. Select an ω-model M of WKL_{0} s.t. ∀ X ∈ M, X is almost recursive.

⋆ n-coloring C of [X]^{k} is a function from [X]^{k} into a set of size n.

⋆ H ⊆ X is homogeneous for a n-coloring C of [X]^{k} if C is constant on [H]^{k}, i.e. all kelement subsets of H are assigned the same color by C.

⋆ RT – Ramsey’s Theorem . For all n and k, every n-coloring of [ℕ]^{k} has an infinite homogeneous set.

⋆ RT_{n}^{k} . For all n-coloring of [ℕ]^{k} there is an infinite homogeneous set.

⋆ RT_{<∞}^{k} . For all n, for all n-coloring of [ℕ]^{k} there is an infinite homogeneous set.

⋆ Upper bounds on the strength of F S⋆

Theorem (RCA_{0}).

(1) RT_{k+2}^{k+1} ⟹ F S(k).

(2) RT_{2}^{2} ⟹ F S(2).

Corollary

(1) For each k ∈ ω, ACA_{0} proves F S(k).

(2) (RCA_{0}). F S(2) does not imply ACA_{0}.

(3) F S(2) is Π_{1}^{1}-conservative over RCA_{0}+IΣ_{2}^{0}.

⋆ Questions ⋆

⋆ Does F S(2) imply WKL_{0}? ⋆ Does F S(2) imply RT_{2}^{2}? ⋆ Does F S(2) imply RT_{<∞}^{1}? ⋆ What happens in all the above questions if we replace F S(2) by F S(k), k > 2? ⋆ Does F S(k) imply ACA_{0} for k ≥ 3?

König’s Duality Theorem

bipartite graph : ordered triple G = (X, Y, E) s.t. X, Y disjoint sets, and E ⊆ {{x, y} : x ∈ X, y ∈ Y }.

vertices of G: elements of X ∪ Y.

E edges of G: elements of E.

C covering of G: a set C of vertices s.t. every edge contains a vertex in C.

M matching in G: collection of pairwise disjoint edges.

⋆ (König 1936). (KDT): For any \underline{finite} bipartite graph G, there exist a covering C of G and a matching M in G s.t. |C| = |M|.

(C, M) König covering of G: selection of one vertex from each edge of a matching M in G.

⋆ (König).

Every finite bipartite graph has a König covering. If (C, M) is a König’s covering of G then |C| = |M|.

⋆ (Podewski + Steffens 1976)

(CKDT) : Every \underline{countably infinite} bipartite graph has a König covering.

⋆ (Aharoni 1984)

Every bipartite graph has a König covering.

⋆ (Aharoni + Magidor + Shore 1992) + Simpson 1994: Over RCA_{0}, CKDT ⟺ ATR_{0}.

✓ The proof of CKDT is “complicated.”

Did Cantor need Set Theory?

Theorem (Cantor). Every countable closed set is a set of uniqueness.

Definitions in RCA_{0}

(1) 𝕋 denotes ℝ/2πℤ.

(2) A (code for a) trigonometric series ∑_{n=−∞}^{∞} c_{n}e^{inx} is a sequence S = ⟨c_{n} : n ∈ ℤ⟩, c_{n} ∈ ℂ.

(3) A countable set E ⊂ 𝕋 is called a countable set of uniqueness if for every trigonometric series S, if S converges to 0 for all x ∉ E, then c_{n} = 0 for all n ∈ ℤ.

✓ Cantor’s theorem is provable in ATR_{0}.

Key step: existence of the derived sequence

(at each step throw away the isolated points; once the sequence stabilizes you’re left with the perfect kernel).

(Hirst 1993): ATR_{0} ⟺ “every countable closed subset of a complete separable metric space has a derived sequence”

✓ Jim Humphreys, using theory of multiplication of trigonometric series, proved

Theorem (ACA_{0}). Let E ⊂ 𝕋 be countable. Then E is a countable set of uniqueness.

Corollary. Cantor’s Theorem is provable in ACA_{0}.

✓ It is possible to prove Cantor’s Theorem without using ordinals.

Cantor discovered Set Theory … by mistake!!!

⋆ Keywords – Definitions ⋆

✓ (RCA_{0}). Let X be a complete separable metric space. X is called:

(1) Lebesgue if every open covering has Lebesgue number: ∃q > 0 ∀x ∈ X B(x, q) is contained in an open set of the covering.

(2) Atsuji if every continuous function f : X → ℝ is uniformly continuous.

Known result

• In Topology:

Atsuji ⟺ Lebesgue

• In Reverse Mathematics: (joint work with A. Marcone)

[figure: Atsuji; Lebesgue; ^{RCA^{0}}; ACA_{0}?]

[figure: Atsuji; A. S. C.; Lebesgue; ^{ACA^{0}}; ^{RCA^{0}}]

A. S. C. if every sequence ⟨x_{n} : n ∈ ℕ⟩ such that

- there exists another sequence ⟨y_{n} : n ∈ ℕ⟩ such that

∗ lim_{n→∞} d(x_{n}, y_{n}) = 0

∗ x_{n} ≠ y_{n} for all n,

has an accumulation point.

✓ \underline{This} proof works in ACA_{0}.

A space is sequentially compact, if every sequence has a converging subsequence. In RCA_{0} it is provable:

(a) ACA_{0} ⟺ [0, 1] is A. S. C.

(b) sequentially compact ⇒ A. S. C.

(c) If X is perfect,

A. S. C. ⇒ sequentially compact ✓ ℕ is A. S. C. but not sequentially compact.

[figure: Atsuji; Lebesgue; Leb_{2}; ^{RCA^{0}}; ACA_{0}?; ACA_{0}?; ^{RCA^{0}}; ACA_{0}?]

X is Leb_{2} if every binary open covering has Lebesgue number.

RCA_{0} proves: WKL_{0} ⟺ [0, 1] is Leb_{2} (1) K ⊆ X is closed, if it is the complement

of a sequence of open balls in X.

(2) K ⊆ X is separably closed, if it is the closure of a sequence of points of X.

⋆ In RCA_{0} it is provable:

ACA_{0} ⟺ (sep.closed ⇒ closed)

⋆ Urysohn’s lemma (RCA_{0}) If K_{0}, K_{1} ⊆ X are disjoint closed subsets of X, then there exists f : X → ℝ continuous such that ∀i < 2 ∀x ∈ K_{i} f(x) = i.

⋆ Limits & Projects ⋆ • Language

• Set existence axioms

• Weaker base system RCA_{0}^{∗}: Σ_{0}^{0}-induction + exp. for naturals. RCA_{0} = RCA_{0}^{∗} + Σ_{1}^{0}-induction

Bibliography

[1] R. Aharoni, M. Magidor, and R. A. Shore, On the strength of König’s duality theorem for infinite bipartite graphs, Journal of Comb. Theory, Series B 54 (1992), 257–290.

[2] P. Cholak, M. Giusto, and J.L. Hirst, Free sets and reverse mathematics,to appear.

[3] H. Friedman and S. G. Simpson, Issues and problems in reverse mathematics, Cont. Math., to appear.

[4] M. Giusto, Topologia, Analisi e Reverse Mathematics, Ph.D. thesis, Univ. Torino, 1998.

[5] M. Giusto and A. Marcone, Lebesgue numbers and Atsuji spaces in subsystems of second order arithmetic, Arch. Math. Logic 37 (1998), 343–362.

[6] S.G. Simpson, Subsystems of Second Order Arithmetic, Persp. in Math Logic, Springer-Verlag, 1999.

[7] S.G. Simpson, On the strength of König’s duality theorem for countable bipartite graphs, JSL 59 (1994), 113–123.

[8] S.G. Simpson, Partial realizations of Hilbert’s program, JSL 53 (1988), 349–363.