Dmytro Taranovsky

June 25, 2004

Slightly Modified: February 20, 2005

**Perfect Subset Property for co-analytic sets in ZF\P**

**Abstract:** We
prove that second order arithmetic plus every uncountable co-analytic
set has a perfect subset is equiconsistent with ZFC.

**Introduction:**
The question of whether every uncountable co-analytic set has a
perfect subset (in other words, whether every co-analytic set has
perfect subset property) has been an important problem in classical
descriptive set theory. Eventually, the
question has been shown undecidable in ZFC and a positive answer
equiconsistent with the existence of an inaccessible cardinal.
Nevertheless, based on strong set existence axioms (**Σ _{1}^{1}**
determinacy would suffice), a consensus has emerged that every
uncountable co-analytic set has a perfect subset.

In ZFC, perfect subset property for co-analytic sets is
equivalent to the claim that ω_{1 }
is inaccessible to the reals, that is ω_{1}
in V is inaccessible in L(r) for every real number r (which implies
that ω_{1} is inaccessible
in the constructible universe L). Conversely, given a model of ZFC
with an inaccessible cardinal κ, by
using forcing, specifically Levy collapse, we can collapse all
cardinals below κ to ω
to produce a model of ZFC + ω_{1}^{
}is inaccessible to the reals.

Second order arithmetic is the standard theory about integers and sets of
integers. It consists of basic facts about integers, induction axiom
**(**0∈X and ∀n (n ∈ X → n+1 ∈ X) implies every natural
number I ∈ X**)**, and comprehension
axiom schema, which is the universal closure of ∃X ∀n (x∈X ↔
φ(n)) for every formula φ with
parameters. Simpson's book [1] explains how to formalize and prove
much of mathematics, including descriptive set theory and
theory of constructible sets in (weak subsystems of) second order
arithmetic. The membership relation for co-analytic sets is
formalized by a Π_{1}^{1}
formula with parameters. A perfect set is the set of all paths
through a perfect tree, and can be coded by such perfect tree. A
formula with one free real number variable defines an uncountable set
of reals if there is no real number that enumerates all of the real
numbers that satisfy the formula.

Second order arithmetic is inter-interpretable ZF\P + "every set is
countable" and hence equiconsistent with ZF minus power-set.
For convenience, we will work in ZF\P. A reference to an uncountable
set in ZF\P should be interpreted as a reference to a corresponding
code.

**Foundational Significance:** The proof illustrates that as far as ZFC "knows",
the class of all ordinals Ord is inaccessible: The proof uses Ord in
place of an inaccessible cardinal in the Levy collapse. More
importantly, the results contribute to the program of proving
consistency and existence of well-behaved models of higher set theory
from natural and intuitively true statements about integers and real
numbers. A number of philosophers believe that the notion of an
arbitrary set of real numbers is inherently vague or that uncountable
sets exist only as syntactical constructs. At any rate, there is a
greater doubt about higher set theory than about integers and real
numbers, and it is important to place the study of higher set theory
on a firm foundation.

**Further Areas Study:**
A model obtained by Col(ω, <Ord)
should have every projective set measurable, have Baire property, and
perfect subset property, but verifying this requires checking that
the usual proof can be modified to work for class forcing.
Restrictions of Separation and Replacement to Σ^{n}_{ZF}
formulas should correspond to corresponding restrictions in ZFC\P +
(proper formalization of) every uncountable co-analytic set has a
perfect subset. A more ambitious project toward establishing
consistency of higher infinities would be to show inside second order
arithmetic that

**Σ ^{1}_{n+1}**
determinacy is equivalent to "M

**Theorem:** ZF\P +
"every co-analytic set/class has perfect subset property"
is equiconsistent with ZFC.

**Proof:** Perfect subset property for co-analytic sets is equivalent to "for every
real number r, the set of real numbers constructible from r is
countable". The only uses of uncountable sets in the standard
proof are routine manipulations of projective sets, so the proof goes
through (with syntactic modifications) inside ZF\P.

Consider a model M of
ZF\P. The notions in this paragraph are assumed to be relativized to
M. The constructible sets under the membership relation form a model
L of ZFC\P. Suppose that every set is countable and perfect subset
property holds for co-analytic sets. We show that L satisfies ZFC by
showing that if α is a (countable)
ordinal, then L satisfies the existence of the power-set of α.
Let r be a real number coding a bijection between α
and ω. The set of real numbers in
L(r) is countable, so the set of subsets of α
in L(r)^{M} and hence in L^{M} is countable
in M. Therefore, there is an ordinal β
such that L_{β} contains all
constructible subsets of α, so L_{β
+1} and hence L contains the constructible power set of
α.

For the other direction, let M be a (countable) model of ZFC. Let G=Col(ω,
<Ord), which is the product of generic collapses Col(ω,
κ) for every infinite regular cardinal
κ. Since the forcing is class
forcing, the generic extension M[G] does not have to satisfy ZFC;
however, G is sufficiently tame for M[G] to satisfy ZFC\P. Because
all uncountable cardinals are collapsed, in M[G], every set is
countable. Let r be a real number in M[G]. Let g be a sufficiently
long initial segment of G--sufficiently long for M[g] to contain r.
Since M[g] satisfies ZFC, ω_{1}^{L(r)}
exists in M[g]. By absoluteness, the same ordinal is ω_{1}^{L(r)}
in M[G], so the set of all reals constructible from r is countable in
M[G]. Thus, in M[G] co-analytic sets satisfy perfect subset
property.

REFERENCE

[1] Simpson, Stephen.
*Subsystems of Second Order Arithmetic*. Springer-Verlag: New
York, 1999.