A model of second-order arithmetic satisfying AC but not DC

This is a talk at the Journées sur les Arithmétiques Faibles 2019 Conference, CUNY Graduate Center, May 28-30, 2019.
Slides

Abstract: Models of second-order arithmetic have two kinds of objects: numbers and sets of numbers, which we think of as the reals. A second-order arithmetic axiom system specifies general existence rules for real numbers. If a result from, say, analysis can be proved in some such system, then we have a bound on the kind of reals that must exist in order for it to hold. Indeed, most classical results in analysis don't just follows from, but are actually equivalent (over a weak base system) to one of a short list of main second-order arithmetic systems.

One of the strongest second-order arithmetic systems is full second-order arithmetic Z2 which asserts that every second-order formula (with any number of set quantifiers) defines a set. We can augment Z2 with choice principles such as the choice scheme and the dependent choice scheme. The Σ1n-choice scheme asserts for every Σ1n-formula φ(n,X) that if for every n, there is a set X witnessing φ(n,X), then there is a single set Z whose n-th slice Zn is a witness for φ(n,X). The Σ1n-dependent choice scheme asserts that every Σ1n-relation φ(X,Y) without terminal nodes has an infinite branch: there is a set Z such that φ(Zn,Zn+1) holds for all n. The system Z2 proves the Σ12-choice scheme and the Σ12-dependent choice scheme. The independence of Π12-choice scheme from Z2 follows by taking a model of Z2 whose sets are the reals of the Feferman-Levy model of ZF in which every Ln is countable and Lω is the first uncountable cardinal.

We construct a model of ZF+ACω whose reals give a model of Z2 together with the full choice scheme in which Π12-dependent choice fails. This result was first proved by Kanovei in 1979 and published in Russian. It was rediscovered by Sy Friedman and myself with a slightly simplified proof.