Free Sets and Reverse Mathematics

Mariagnese Giusto

In this talk we present some results – obtained in collaboration with Prof. P. Cholak and Prof. J.L. Hirst– related to Ramsey’s theorem and the free set theorem in the context of Reverse Mathematics. A posting of H. Friedman in the FOM email list sparked our interest in this topic.

The purpose of Reverse Mathematics is to study the role of set existence axioms, trying to establish the weakest subsystem of second order arithmetic in which a theorem of ordinary mathematics can be proved. The basic reference is Simpson’s recent monograph.

The Free Set Theorem (F S) reads as follows: “Let f : ℕ^{k} → ℕ. There exists a free set for f, i.e. an infinite A ⊆ ℕ such that for all x_{1}, …, x_{k} ∈ A, if f(x_{1}, …, x_{k}) ∈ A then f(x_{1}, …, x_{k}) ∈ {x_{1}, …, x_{k}}.” For k ≥ 1, we use F S(k) to denote the statement F S restricted to a particular value of k.

We recall that Ramsey theorem (RT_{k}^{n}) reads as follows: “For all k-coloring of [ℕ]^{n} there is an infinite homogeneous set”.

The most relevant result we found is that Ramsey’s theorem for pairs and two colors (RT_{2}^{2}) implies the free set theorem for pairs (F S(2)). This result provides some interesting corollaries: “F S(2) is Π_{1}^{1}-conservative over RCA_{0} + IΣ_{2}” and “every computable f : ℕ^{2} → ℕ has a low_{2} free set”.

Address: University of Torino, Postal address: Via Loreto Vecchia 9/10/A - 17100 Savona -Italy

E-mail: giusto@dm.unito.it, mariagnese@savonaonline.it