Generalizing Silver's Theorem Part 2

In this post, I will be proving Silver’s theorem the forcing way. Recall the statement.

Theorem 1   
Suppose that E is a lightface co-analytic equivalence relation on the reals (in this case taken to be Cantor space: infinite strings of 0’s and 1’s). Then either E has countably many equivalence classes, or there is a perfect set of E-inequivalent elements.

Proof.
From here on out I will be referring to lightface analytic sets as Σ₁¹, co-analytic sets as Π₁¹, and sets which are both as Δ₁¹.

As in the topological proof, I will be using lightface analytic sets, and exploiting their properties. The first two of these properties are reasonably straightforward:

• There are only countably many Σ₁¹ sets, Π₁¹ sets, and Δ₁¹ sets.
• Disjoint Σ₁¹ sets can be separated by a Δ₁¹ set. That is whenever A and B are disjoint Σ₁¹ sets, there is a Δ₁¹ set C so that A ⊆ C and B ∩ C = ∅. This is equivalent to the reduction property for Π₁¹. For any Π₁¹ sets A and B, we can find disjoint Π₁¹ sets A′ and B′ so that A ⊆ A′, B ⊆ B′ and A ∪ B = A′ ∪ B′.

The next property will require a little bit of set-up. In descriptive set theory, we try to code everything we possibly can with real numbers. In the case of countable collections, we try to do even better, and code them by natural numbers. In particular, we can obtain a set U × ω × ℝ so that for every Π₁¹ set B, there is an n ∈ ω so that B = U ∩ ({n} × 2^ω). That is, every Π₁¹ set shows up as a vertical section of U. I am presenting these facts without proof because they are pretty standard and this post is going to be long as it is.

This proof really consists of test, the results of which provide construction principles. In words, the test is as follows: for every real x, is there a Δ₁¹ set A so that x ∈ A ⊆ [x]_E? If the answer is yes, then the fact that Δ₁¹ is countable implies that E has countably many equivalence classes. We certainly cannot have more equivalence classes than elements of Δ₁¹ in this case. So what happens if the answer is no? This is where we will use forcing to create a copy of 2^ω which consists of pairwise E-inequivalent elements.

Let Q be the collection of non-empty Σ₁¹ sets. For A,B ∈ Q, we say that A ≤ B (A extends B) iff A ⊆ B. I will refer to elements of Q as conditions. This is because they include some reals and exclude others. Intuitively, extending conditions in this partial order corresponds to filtering out reals. Now let S = {x ∈ ℝ : (∃ A ∈ Δ₁¹) [x ∈ A ⊆ [x]_E} and set W to be the complement of S. If the answer to the question is no, W is non-empty. What I want now is for W to be a Σ₁¹ set. That way I can force below W. The information that W imparts will guarantee that the forcing produces pairwise E-inequivalent reals.

Claim 1 
W is Σ₁¹.

Reason
It suffices to show that S is Π₁¹. We create a coding of the Δ₁¹ sets in order to make this computation. Let U ⊆ ω × ℝ be universal for Π₁¹. Define Π₁¹ sets V₁ and V₂ by

• V₁(⟨ n,m ⟩,x)  ⇐⇒ U(n,x) and
• V₂(⟨ n,m ⟩,x)  ⇐⇒ U(m,x).

Using the reduction property for Π₁¹, we can find disjoint Π₁¹ sets V₁′ and V₂′ so that V_i ⊆ V_i′, V₁′ ∩ V₂′ = ∅, and V₁ ∪ V₂ = V₁′ ∪ V₂′. Then ⟨ n,m ⟩ codes a Δ₁¹ set iff

(∀ y ∈ ℝ)[V1′(⟨ n,m ⟩,y) ∨ V2′(⟨ n,m ⟩,y)],

that is ⟨ n,m ⟩ finds a section of U which codes complementary Π₁¹ sets. Call the set of such codes C. C is Π₁¹. Now

x ∈ S  ⇐⇒ (∃ n,m ∈ ω)[⟨ n,m ⟩ ∈ C ∧ V1′(⟨ n,m ⟩,x) ∧ (∀ y ∈ ℝ)[¬ V2′(⟨ n,m ⟩,x) ⇒ x E y]].

This shows that S is Π₁¹.


With this knowledge of W in hand, it makes sense to speak of the conditions in Q below W. Call this poset P. I will use this poset to produce pairwise E-inequivalent reals. For the uninitiated, forcing with a poset involves three major pieces.

• Dense subsets of P(these are dense in the intuitive way; every condition can be extended to be inside the set). Topologically these correspond roughly to comeager sets.
• Generic filters for P: G is a generic filter if it is closed upwards in the ≤ order, is closed under "meets" in the sense that if p,q ∈ G, then there is an r ∈ G so that r ≤ p,q, and G has non-empty intersection with every dense subset of P.
• Names for objects which can be described by P. These are essentially collections of pairs (A,τ) where A is a condition in P and τ is another name. The construction of names is inherently recursive.

These three objects come together in a synthesis. G builds actual objects using the names as a guide: it pulls objects into a set it is building according to the conditions in G and the name that condition is tagged with. This process is recursive. In notation, the interpretation of the name τ by the generic G is written as τ_G. The dense sets are how the poset controls what G can build. The creation of clever dense sets forces G to make decisions about desired properties of the sets it constructs. If we call V our initial universe of objects, V[G] is the universe of objects which can be created from G in this way. Standard forcing theorems show that V is properly contained in V[G] and G in an element of V[G]. Syntactically, this means there are names for elements of V and for G which get interpreted appropriately for all generics G. If x ∈ V, the standard name for x is denoted ẋ.

For sentences ϕ (which are allowed to reference names) and conditions A, the notation A ⊩ ϕ means that whenever G is generic, if A ∈ G, then ϕ is true in V[G]. This symbol means that A forces ϕ. It is an important theorem in forcing that if a statement ϕ is true about V[G], then it was forced to be true by some condition in the poset. To work with the forcing in this context, I will restrict down to a countable structure M for which enough of ZFC is true for the proofs to go through. This allows for the explicit construction of generics. Actually, what I want is a little bit stronger. By first taking a sub-universe of enough of ZFC, and then taking a countable elementary substructure M, I can assume that there is an embedding ϕ:M → V which preserves all of the first order statements which come up in this proof. This small universe does not have Q or P, but M has ϕ⁻¹(P) and ϕ⁻¹(Q), which I will refer to as P and Q. As general notation, the bar will be used to denotes the ϕ-inverse of a set.
Now the poset Q I am considering has a particularly nice interplay with its generics.

Claim 2   
Suppose G is generic filter on Q. Then G gives rise to a real x_G so that x_G ∈ A iff A ∈ G.

Reason
I use cylinder sets to construct the name. For a finite string s of 0’s and 1’s, N(s) is those reals which have s as an initial segment. Consider the name ẋ = {(ṡ,A) : A ⊆ N(s)}. Then if G is a generic filter for Q over M, this name at least guarantees that ẋ_G ∈ ℝ. It suffices to show that A ⊩ ẋ ∈ A for every A ∈ P. Since A is Σ₁¹, I can write A = p[T], where T is a recursive tree on ω × ω. Then

A ⊩ ẋ ∈ A  ⇐⇒ A ⊩ (∃ y ∈ ℝ)(∀ n ∈ ω)[(ẋ|n,y|n) ∈ T].

I will first check that this does not depend on our choice of T. A could have many representations, and this computation should not depend on the representation. So Suppose T₀ and T₁ are recursive trees on ω × ω so that A = p[T₀] = p[T₁]. Suppose G is generic for P over M. I need to see that

ẋ ∈ p[T0]  ⇐⇒ ẋ ∈ p[T1].

In M, it is true that (∀ x ∈ ℝ)[x ∈ p[T₀]  ⇐⇒ x ∈ p[T₁]]. Since this is a simple enough statement (Π₂¹), Shoenfield absoluteness declares it true in M[H] as well no matter which generic H is chosen. So the forcing statement is true.

Now suppose towards a contradiction that A ⊮ẋ ∈ A. It is part of the formal definition of ⊩ that there then must be a condition B ≤ A so that B ⊩ ẋ ∉ A. Then B ⊩ ẋ ∉ B. Thus WLOG A ⊩ ẋ ∉ A. Call this element A₀. This is not quite a contradiction, but it is almost there. Write A₀ = p[T₀]. I will use A₀ to build a generic extension G so that in M[G], ẋ_G ∉ A and ẋ_G ∈ p[T₀]. In V, let {D_n : n ∈ ω} be the dense subsets of Q from M. I want to fix the first coordinate of the reals in A₀, fix a valid first coordinate for a witness that those reals are in A₀ and extend A₀ to meet D₁. Let s₀ ∈ ω and t₀⁰ ∈ ω be so that

A0′ = {x : (∃ y ∈ ℝ)[(x(0),y(0)) = (s,t00) ∧ (x,y) ∈ [T0]]} ⊆ A0.

This fixes the first digit of reals inside A₀ and the first digit of potential witness y which prove that those reals are in A₀. Let A₁ ⊆ A₀′ ∩ N(s₀) be so that A₁ ∈ D₁.

Continue this way inductively, defining A_n, T_n, s_n, t_n^m, and A_n′ for n ∈ ω and m ≤ n so that

• A_n = p[T_n],
• s_n,t_n^m ∈ ωⁿ,
• s_n ⊑ s_n+1,
• t_n^m ⊑ t_n+1^m,
• A_n′ = {x : s_n ⊑ x ∧ (∃ y^→ ∈ ∏_{m ≤ n}N(t_n^m))(∀ m ≤ n)[(x,y_m) ∈ [T_m]] },
• A_n ∈ D_n, and
• A_n ≥ A_n′ ≥ A_n+1.

We can then define a filter G by taking the ≤-upward closure of the A_n. Explicitly, define a filter G on P by

A ∈ G  ⇐⇒ (∃ n ∈ ω)[An ≤ A].

This is a generic filter for Q. By construction, ẋ_G =lim_{n → ∞}s_n. I also assumed that A₀ ⊩ ẋ ∉ A₀. Thus ẋ_G ∉ A₀. Let y = lim_{n → ∞}t_n⁰. Then (ẋ_G,y) ∈ [T₀]. So ẋ_G ∈ p[T₀] = A₀. This is a contradiction.


With this in mind, I will freely identify a real x as Q-generic (or P-generic). At this point, to meaningfully interact with the equivalence relation, I need to be working in ℝ². Unfortunately, there are two ways to lift Q and P up to ℝ². The first way is the simpler, and will be denoted Q × Q. Conditions in Q × Q are simply ordered pairs (A,B), where A,B ∈ Q. The second way is slightly more complicated. Q₂ is the version of Q defined off of ℝ². That is A ∈ Q₂ iff A ⊆ ℝ², A is Σ₁¹ and A ≠ ∅. Syntactically, this means there is a recursive tree T on ω × ω × ω so that (x,y) ∈ A iff there is a z ∈ ℝ so that (x,y,z) ∈ [T].

Let P × P be the product poset of P, and P₂ = {A ∈ Q₂ : A ≤ W × W}. Note that if G is Q₂ generic (or P₂-generic), then G defines a pair of reals (x_G,y_G). With the name (x,y) = {(ṡ,ṫ,A) : A ⊆ N(s) × N(t)}, the same proof as for one dimension shows that

(x,y)G ∈ A  ⇐⇒ A ∈ G.

Now the question is how do these two-dimensional posets interact with the one-dimensional version. The answer is quite well! I just have to define some projection operations, and then there is a smooth translation between the posets. For A ∈ Q₂, we let

πL(A) = {x ∈ ℝ : (∃ y ∈ ℝ)[(x,y) ∈ A]}  and  πR(A) = {y ∈ ℝ : (∃ x ∈ ℝ)[(x,y) ∈ A]}.

Then π_L(A),π_R(A) ∈ Q, as Σ₁¹ is closed under projections. If G is Q₂-generic, let

πL(G) = {A ∈

Q

: (∃ B ∈ G2)[πL(B) ⊆ A]},

and π_R(G) is similarly defined.

One particular nice interaction is that generic reals pass back and forth. I am proving this for Q₂ and the barred version for notational simplicity and because I can.

Claim 3 
If (x,y) is Q₂ generic, then x and y are generic for Q.

Reason
Suppose (x,y) is Q₂ generic. Let G₂ be the associated Q₂ generic. I will show that x is Q-generic, and the argument for y is symmetric. Let G = π_L(G₂). I will show that G is generic. Let D be dense for Q. Let A₂ ∈ Q₂, and set A = π_L[A₂]. Then as A ∈ Q, there is a B ≤ A in Q so that B ∈ D. Define B₂ by

B2 = (B × ℝ) ⋂ A2.

Then B₂ is Σ₁¹ and B₂ ≠ ∅. So B₂ ∈ Q₂. Note that π_L[B₂] = B ∈ D. Thus {X ∈ Q₂ : π_L[X] ∈ D} is dense in Q₂. So there is an X ∈ G so that π_L[X] ∈ D. Thus G ∩ D ≠ ∅, and so G is generic. Moreover,

x ∈ A  ⇐⇒ (x,y) ∈ A × ℝ  ⇐⇒ A × ℝ ∈ G  ⇐⇒ A ∈ G.

So G is the the generic associated to x.


Putting this all together, it finally comes out that forcing below W produces reals which are pairwise E-inequivalent.

Claim 4   
If (x,y) are P × P-generic, then (x,y) ∉ E.

Reason
BWOC suppose that (A,B) ∈ P × P are so that (A,B) ⊩_P2 ((x,y) ∈ E). Consider (A,A,B) ∈ P₂ × P. Note that A² ∩ (ℝ² − E) is in Σ₁¹ and non-empty. Thus A² ∩ (ℝ² − E) ∈ P₂. Let G₂ be P₂-generic over V so that A ∈ G₂. Let G be P-generic over V[G₂] so that B ∈ G. Then in V[G₂][G], G₂ × G defines a generic triple (x,y,z). Now

• in V[G₂], (x,y) ∉ E (as A₂ ∈ G₂),
• in V[π_L(G₂)][G], x E z (as B ∈ G, (x,z) is P × P-generic, and A × B ∈ π_L(G₂) × G) and
• in V[π_R(G₂)][G], y E z (as B ∈ G, (y,z) is P × P-generic, and A × B ∈ π_R(G₂) × G).

Thus,

in V[G2][G], [(x E z) ∧ (y E z) ∧ ((x,y) ∉ E)].

Therefore In V[G₂][G], E is not an equivalence relation. But to say E is an equivalence relation is a Π₂¹ statement. So by Shoenfield absoluteness again, in V[G₂][G], E is an equivalence relation. This is a contradiction.


Now I will build a perfect set of generics for P. To do so, I have to return to the countable sufficiently elementary submodel M. Note that by elementarity,

M ⊨ [∅ ⊩P_2 (x,y) ∉ E].

The construction is an inductive construction. I will create Σ₁¹ sets A_s for all finite strings s in such a way that incompatible strings correspond to disjoint Σ₁¹ sets and each descending sequence of A’s produces a generic. If I can follow this through, the set of such generics will be perfect and they msut also be pairwise E-inequivalent.

Let {D_n : n ∈ ω} enumerate the dense sets in P × P. Let (A₀,A₁) ∈ P₂ be so that A₀ ⊩_P ẋ(i₀) = a₀ and A₁ ⊩_P ẋ(i₀) = b₀ with a₀ ≠ b₀. In P × P there are A₀₀, A₀₁, A₁₀, A₁₁ so that A₀₀ ∩ A₀₁ = ∅ and A₁₀ ∩ A₁₁ = ∅. I can then find A′_ij ≤ A_ij so that A′_ij ∈ D₀. I simply continue in this way, defining A_s,A′_s ∈ P for s ∈ 2^<ω so that

• for all s,t ∈ 2^<ω, if s ⊑ t, then A_t ≤ A′_s,
• for all s ∈ 2^<ω, A′_s ≤ A_s,
• for all s ∈ 2^<ω, A_{s ⁀ 0} ∩ A_{s ⁀ 1} = ∅, and
• for all s ∈ 2^<ω, A′_s ∈ D_|s|−1.

The easiest way to check that this construction has worked is through the language of embeddings. Define ψ:2^ω→ ℝ by ψ(x) = ∩_n A_x|n. If x ∈ 2^ω, then the filter generated by x (A ∈ G_x  ⇐⇒ ψ(x) ∈ A) is a generic filter for P over M. In fact, if x ≠ y ∈ 2^ω, then (G_x,G_y) is P × P-generic over M. Thus in M[(G_x,G_y)], (ψ(x),ψ(y)) ∉ E. By Σ₁¹-absoluteness, it must then be true in V that (ψ(x),ψ(y)) ∉ E. This verifies the construction and finishes the proof


This version is reasonably slick, and doesn’t use the axiom of choice in ways which are incompatible with AD. However, it doesn’t actually generalize all that well. If instead of being co-analytic, the equivalence relation is merely co-κ-Suslin (a set A is κ-Suslin if it can be written as A = p[T], where T is a tree on ω × κ), the same proof will not got through as I will lose features of Σ₁¹ which made some of these complexity computations come out just so. So what’s the solution? Infinitary logic and admissible ordinals. Or, in my case, infinity Borel codes and admissible ordinals. Look for that next time.

This document was translated from L^AT_EX by H^EV^EA. (How did it work?)