Projective Sets of Reals

and Core Models

Ralf Schindler

Institut für Formale Logik

Universität Wien

  rds@logic.univie.ac.at
http://www.logic.univie.ac.at/^{∼}rds/

Lebesgue Measurability

For A ⊂ ℝ we let μ^{⋆}(A) denote the outer measure of A.

Def. A ⊂ ℝ is called Lebesgue measurable iff: for all ϵ > 0 there is F ⊂ A closed and G ⊃ A open with μ^{⋆}(G \ F) < ϵ.

• Each open A ⊂ ℝ is Lebesgue measurable.

• The set of all subsets of ℝ which are Lebesgue measurable is a σ-algebra, i.e., it is closed w.r.t. complement, ⋃_{i∈ℕ} and ⋂_{i∈ℕ}.

Def. A ⊂ ℝ is a Borel set iff: A is contained in the smallest σ-algebra containing all open subsets of ℝ.

Theorem. Each Borel set A ⊂ ℝ is Lebesgue measurable.

Def. A ⊂ ℝ^{n} is called a projection of B ⊂ ℝ^{n+1} iff

x⃗ ∈ A ⇔ ∃y (x⃗, y) ∈ B.

Def. A ⊂ ℝ^{n} is called analytic iff: A is the projection of a Borel set (in ℝ^{n+1} ).

There are analytic sets which are not Borel. A ⊂ ℝ^{n} is a Borel set iff A and ℝ^{n} \ A are both analytic (Suslin, 17).

Theorem (Luzin, 17). Every analytic A ⊂ ℝ is Lebesgue measurable.

Projective Sets

Def.

Σ_{1}^{1} = analytic sets
Π_{n}^{1} = complements of Σ_{n}^{1}−sets
Σ_{n+1}^{1} = projections of Π_{n}^{1}−sets

_{n∈ℕ}^{⋃} Σ_{n}^{1} = _{n∈ℕ}^{⋃} Π_{n}^{1} = projective sets

Question (Luzin, 25). Are all projective sets of reals Lebesgue measurable?

The axioms of Zermelo-Fraenkel (ZF C) Extensionality: ∀u(u ∈ x ⇔ u ∈ y) ⇔ x = y Empty set: ∅ exists Pairing: for all x, y does {x, y} exist Union: for all x does ⋃ x exist Power set: for all x does P(x) exist Infinity: there is an infinite set Replacement: let Φ be a definable function (not necessarily a set!); for all x does Φ”x exist Foundation: there is no infinite chain ... ∈ x_{2} ∈ x_{1} ∈ x_{0} (i.e., the ∈ relation is well-founded)

Choice: each x can be well-ordered (i.e., there is a well-founded total order <_{x} on x)

ℝ can be well-ordered ⇒ there is a set A of reals which is not Lebesgue measurable:

For x, y ∈ [0, 1] put x ∼ y iff x − y ∈ ℚ. Let A ⊂ [0, 1] contain exactly one element from each equivalence class. (A is called a Vitali set.)

Vitali sets are at most as complicated as the well-order of ℝ defining them.

Ordinals

0 = ∅ 1 = {0} ⋮ n + 1 = {0, 1, ..., n} ⋮ ω = {0, 1, 2, ...} ω + 1 = {0, 1, 2, ..., ω} ⋮ α = {β | β < α}

For every well-ordered set (x, <_{x}) there is some ordinal α with

(α, <) ≅ (x, <_{x}).

Gödel’s Constructible Universe L_{0} = ∅ L_{α+1} = set of all subsets of L_{α} which are definable over L_{α} with parameters from L_{α} L_{λ} = ⋃_{α<λ} L_{α} for limit ordinals λ L = ⋃_{α} L_{α} Theorem (Gödel, 38). L is an inner model of ZF C. Theorem (Gödel, 38). L contains a wellorder < of ℝ which (as a subset of ℝ^{2}) is a Σ_{2}^{1}-set.

Theorem (Gödel, 38). L contains a Σ_{2}^{1}-set of reals which is not Lebesgue measurable. In particular: Con(ZF C) ⇒ Con(ZF C + there is a projective set of reals which is not Lebesgue measurable).

We let Con(Φ) ⇒ Con(Ψ) denote the fact that the consistency of Φ implies that of Ψ, i.e, that Ψ is relatively consistent with Φ.

Cardinals

Ordinals α for which there is no β < α of the same cardinality are called cardinals.

0, 1, 2, 3, ..., ω, ω_{1}, ω_{2}, ..., ω_{ω}, ..., κ = ω_{κ}, ...

Def. κ is called inaccessible iff: κ > ω, ∀α < κ 2^{α} < κ, and κ is regular.

Def. H_{κ} = all x such that for all x_{n} ∈ x_{n−1} ∈ ... ∈ x_{0} ∈ x, x_{n} is of smaller cardinality than κ.

ZF C doesn’t prove the existence of an inaccessible cardinal because H_{κ} ⊧ ZF C for any inaccessible κ (Gödel’s 2nd Incompleteness Theorem!).

Theorem (Solovay, 64). Con(ZF C + there is an inaccessible cardinal) ⇒ Con(ZF C+ all projective sets of reals are Lebesgue measurable).

Theorem (Shelah, 79). Con(ZF C+ all projective sets of reals are Lebesgue measurable) ⇒ Con(ZF C + there is an inaccessible cardinal)

(a) ZF C+ all projective sets of reals are Lebesgue measurable and

(b) ZF C+ there is an inaccessible cardinal are therefore equiconsistent theories.

Proof of Solovay’s theorem: Let V ⊧ κ is an inaccessible cardinal. Let G be Col(ω, < κ) -generic over V. Show: V [G] ⊧ all projective sets of reals are Lebesgue measurable.

Proof of Shelah’s theorem: Let V ⊧ all projective sets of reals are Lebesgue measurable. Construct Gödel’s L (in V). Show: L ⊧ ω_{1}^{V} is an inaccessible cardinal.

Projective Determinacy

Let A ⊂ [0, 1]. Consider:

\begin{matrix}I & n_{0} & & n_{2} & & ... \\ II & & n_{1} & & n_{3} & & ... \end{matrix}

Rule: n_{i} ∈ {0, 1} for all i ∈ ℕ. I wins the game G(A) iff ∑_{i=0}^{∞} \frac{n_{i}}{2^{i+1}} ∈ A. For any A do we have that at most one of the players can have a winning strategy for G(A). ℝ can be well-ordered ⇒ there is some A such that neither player has a winning strategy for G(A).

Theorem (Martin, 75). Let A ⊂ [0, 1] be a Borel set. Then either I or II has a winning strategy for G(A).

Projective Determinacy (PD): Let A ⊂ [0, 1] be a projective set. Then either I or II has a winning strategy for G(A).

Theorem (ZFC + PD, Mycielski + Swierczkowski, 64). Every projective A ⊂ ℝ is Lebesgue measurable.

The property of Baire

Def. A ⊂ ℝ has the property of Baire iff: there is some open set G such that A △ G is meager (= a countable union of nowhere dense sets).

Theorem (Luzin + Sierpinski, 23). Each analytic A ⊂ ℝ has the property of Baire.

Theorem (ZFC + PD, Mazur, 57). Each projective set A ⊂ ℝ has the property of Baire.

Uniformization.

Def. Let A ⊂ ℝ^{2}. A partial function F: ℝ → ℝ is called a uniformizing function iff: for all x: ∃y(x, y) ∈ A ⇒ (x, F (x)) ∈ A.

Projective Uniformization: Each projective A ⊂ ℝ^{2} admits a uniformizing function with a projective graph.

Theorem (ZFC + PD, Moschovakis, 71). Projective Uniformization holds.

Question (Woodin, 81): Suppose that each projective A ⊂ ℝ is Lebesgue measurable, each projective A ⊂ ℝ has the property of Baire, and Projective Uniformization holds. Does this imply that Projective Determinacy holds?

This question became known as the 12^{th} Delfino Problem. It was open for 16 years.

Def. π: V → M is called an elementary embedding iff π”V ≺ M.

Def. Let α be a cardinal. A cardinal κ is called α-strong iff for all X ∈ H_{α} there is an inner model M and some elementary embedding π: V → M such that κ is the critical point of π and X ∈ M. (Here: V = the class of all sets.)

Def. κ is a measurable cardinal iff κ is κ^{+} - strong.

There is a measurable cardinal iff: there is a σ-complete two-valued non-trivial measure on some set. (Such a measure does not exist on ℝ.)

Theorem (Steel, 97; Schindler, 00). The following theories are equiconsistent.

(A) ZF C+ each projective A ⊂ ℝ is Lebesgue measurable and has the property of Baire and Projective Uniformization holds.

(B) ZF C+ there is an infinite sequence κ_{0} < κ_{1} < κ_{2} < ... of cardinals with supremum λ such that each individual κ_{n} is λ^{+} -strong.

Corollary. The answer to Woodin’s question is “no.”

Proof of the corollary from the theorem:

Suppose that the answer were “yes,” i.e, that (A) implies P D.

Woodin: ZF C + P D implies Con(ZF C+ there is a Woodin cardinal). In particular: ZF C + P D implies Con(B). But Con(B) ⇔ Con(A). By assumption, Con(A) ⇒ Con(ZF C + P D).

We’ve shown: ZF C + P D ⇒ Con(ZF C + P D). This contradicts Gödel’s 2nd Incompleteness Theorem!

Proof of Con(B) ⇒ Con(A) (Steel):

Let V ⊧ there is an infinite sequence κ_{0} < κ_{1} < κ_{2} < ... of cardinals with supremum λ such that each individual κ_{n} is λ^{+} -strong.

Let G be Col(ω, λ)-generic over V. Then in V [G] do we have that each projective A ⊂ ℝ is Lebesgue measurable and has the property of Baire.

If V is of a special form to begin with then we even have Projective Uniformization in V [G]. More precisely: V has to be a core model.

Proof of Con(A) ⇒ Con(B) (Schindler):

Let V ⊧ each projective A ⊂ ℝ is Lebesgue measurable and has the property of Baire and Projective Uniformization holds.

It suffices to prove the following. There is an inner model W such that for some infinite sequence κ_{0} < κ_{1} < κ_{2} < ... < ω_{1}^{V}: each individual κ_{n} is ω_{1}^{V} -strong inside W.

Canonical candidate: W = L. Problem:

Theorem (Scott, 61). Gödel’s L can have no measurable cardinals.

Right candidate: W = a core model.

Core models

Core models are generalizations of L in that they may contain measurable cardinals. In fact, they contain “as many measurable cardinals as possible”.

Core models were constructed during the past 25 years by Dodd, Jensen, Koepke, Mitchell, and Steel.

For our present purpose the construction of a new family of core models was called for.

1st step of the proof of Con(A) ⇒ Con(B): construct an appropriate core model, K. K is of the form L[E] for some E. Let E be arbitrary to beigin with. L_{0}[E] = ∅ L_{α+1} [E] = set of all subsets of L_{α}[E] which are definable over L_{α}[E] with parameters from L_{α}[E] together with a predicate for E L_{λ}[E] = ⋃_{α<λ} L_{α}[E] for limit ordinals λ L[E] = ⋃_{α} L_{α}[E] Theorem. L[E] is a model of ZF C.

Which one is the right E?

E codes a carefully chosen maximal sequence (π_{α} | α ∈ OR) of elementary embeddings:

π_{α}: L[E ↾ α] → L[Ẽ] for some Ẽ.

• The existence of some such maximal sequence can only be shown under an anti large cardinal assumption; in our case we’ll need that there is no inner model with a measurable cardinal λ which is the limit of λ-strong cardinals κ < λ.

• “Carefully chosen” means that L[E] has a fine structure. This will imply that L[E] can be analyzed in great detail. Fine structure theories go back to Jensen.

K = L[E] is constructed in a couple of steps:

• Construct K^{c}, the “ω-complete” core model, a preliminary version of K

• Show, using the anti large cardinal assumption, that κ^{+K^{c}} = κ^{+} for all singular cardinals κ (“Weak Covering Lemma”)

• Isolate K as the transitive collapse of some hull which is generated inside K^{c} from some class being provided by the Weak Covering Lemma This leads to:

Theorem (Schindler, 00). Suppose that there is no inner model in which there is a measurable cardinal λ with unboundedly many λstrong cardinals κ < λ. Then the core model K = L[E] exists. If

π: K → L[Ẽ]

for some Ẽ, then E contains a code for π.

2nd step in the proof of Con(A) ⇒ Con(B): show that there is an infinite sequence κ_{0} < κ_{1} < κ_{2} < ... < ω_{1}^{V} such that each individual κ_{n} is ω_{1}^{V} -strong in K.

Central tool:

Theorem (Schindler, 97). Suppose that the core model K = L[E] exists (and P D fails). If

{κ < ω_{1}^{V} | L[E] ⊧ κ is ω_{1}^{V} −strong }

is finite then L_{ω_{1}^{V}} [E] is projective.