Infinite Combinatorics, Definability, and Forcing
David Schrittesser
University of Copenhagen (Denmark)

RIMS Workshop on

Infinite Combinatorics and Forcing Theory

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

1 / 25

Discrete sets
Let R be a binary relation on a set X .

Definition
We say a set A ⊆ X is discrete (w.r.t. R) ⇐⇒ no two distinct
elements x, y of A are R-related.

Definition
We call such a set maximal discrete (w.r.t. R; short R-m.d.) if it is nota proper subset of any discrete set.
A is maximal discrete iff A is discrete and for any x ∈ X \ A(∃a ∈ A) (a R x) ∨ (x R a)

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

2 / 25

Discrete sets (non-binary)
Let X be a set and R ⊆ X <ω .

Definition
We say a set A ⊆ X is discrete (w.r.t. R) ⇐⇒ A<ω ∩ R = ∅.
The notion of maximal discrete set is defined as before.
A is maximal discrete iff A is discrete and for any x ∈ X \ A(∃y0 , . . . , yn ∈ A ∪ {x}) (y0 , . . . , yn ) ∈ R.
While maximal discrete sets always exist (under AC), one can study
under which circumstances they can be definable.
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

3 / 25

Examples
There are many interesting examples where X is an effective Polishspace and R is Borel:
BinaryTransversals for equivalence relations
mad families
maximal eventually different families
maximal orthogonal families of measures
Higher arity
Hamel basis of R over Q
Cofinitary groups. . . and many more.
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

4 / 25

Example 1: mad families
Let X = [ω]ω .

Define R ⊆ X 2 as follows: For x, y ∈ X ,x R y ⇐⇒ x ∩ y is infinite.

A mad family is an infinite maximal discrete set w.r.t. R.

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

5 / 25

Some facts about mad families
1

There is no analytic mad family (Mathias, 1968).
There is a (lightface) Π11 mad family in L (A. R. Miller, 1987).
I If there is a Σ1 mad family, there is a Π1 mad family (Törnquist,122013).
II

2

3

One can find mad families which remain mad after forcing (forvarious forcings; many authors).
I In particular, the existence of a Π1 mad family is consistent with1
arbitrary values for 2ω .
I

One can force that there are no definable mad families:Mathias, ca. 1969: from a Mahlo,
Törnquist, 2015: from an inaccessible (no mad families in Solovay’smodel),I Horowitz-Shelah, 2016: from ZFC.

II

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

6 / 25

“there is no projective R-m.d. family” is equiconsistent with ZFC inseveral other cases, as well:maximal eventually different families of functions(Brendle-Khomskii, unpublished)maximal orthogonal families of measures (Fischer-Törnquist,2010); This is because the same holds for “every projective set
has the Baire property”
Example 2
The statement that there are no definable R-m.d. sets can have large
cardinal strength:

Theorem (Horowitz-Shelah, 2016)
There is a Borel binary relation R on 2ω (in fact, a graph relation) suchthat “there is no projective R-m.d. set” is equiconsistent with theexistence of an inaccessible cardinal.
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

7 / 25

Example 3
Let X = ω ω and for f , g ∈ X letf R g ⇐⇒ {n | f (n) = g(n)} is infinite.
A (maximal) discrete set w.r.t. R is a (maximal) eventually differentfamily.

Theorem (Horowitz-Shelah, 2016)(ZF) There is a Borel maximal eventually different family.
Such a family remains m.d. in any larger universe.

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

8 / 25

Example 4: Orthogonality of measures
Let P(2ω ) be the set of Borel probability measures on 2ω .
Two measures µ, ν ∈ P(2ω ) are said to be orthogonal, writtenµ⊥ν
exactly if: there is a Borel set A ⊆ 2ω such thatµ(A) = 1andν(A) = 0.
Note that P(2ω ) is an effective Polish space.

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

9 / 25

History of maximal orthogonal families
Question (Mauldin, circa 1980)
Can a mof in P(2ω ) be analytic?
The answer turned out to be ‘no’:

Theorem (Preiss-Rataj, 1985)
There is no analytic mof in P(2ω ).
This is optimal, in a sense:

Theorem (Fischer-Törnqust, 2009)
In L, there is a Π11 mof in P(2ω ).
In fact:

TheoremIf there is a Σ12 mof in P(2ω ), there is a Π11 mof.
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201610 / 25

Mofs and forcing
Mofs are fragile creatures:

Facts
12Adding any real destroys maximality of mofs from thegroundmodel (observed by Ben Miller; not restricted to forcingextensions)
If there is a Cohen real over L, there are no Σ12 mofs in P(2ω )(F-T, 2009)3

The same holds if there is a random real over L(Fischer-Friedman-Törnquist, 2010).

4

The same holds if there is a Mathias real over L (S-Törnquist,2015).

Question (F-T, 2009)
If there is a Π11 mof, does it follow that P(ω) ⊆ L?
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201611 / 25Π11 mofs in extensions of L
Theorem (S-Törnquist, 2015)
If s is Sacks over L there is a (lightface!) Π11 mof in L[s].

Theorem (S 2016)
The statement ‘there is a Π11 mof ’ is consistent with 2ω = ω2 .
In fact :Theorem (S 2016)
Let R be a binary Σ11 relation on an effective Polish space X . If s̄ isgeneric for iterated Sacks forcing over L, there is a (lightface) ∆12
maximal R-discrete set in L[s̄].

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201612 / 25

Here is the main idea of the proof in the case of adding a single Sacks
real.
Assume R is symmetric (otherwise, look at R ∪ R −1 ).
Of course Sacks forcing S is the set of perfect trees p ⊆ 2<ω , orderedby inclusion and [p] is the set of branches through p.
We need the following theorem of Galvin:

Theorem (Galvin’s Theorem)
Let p ∈ S andc : [p]2 → {0, 1}

be symmetric and Baire measurable.
Then there is q ∈ S, q ≤ p such that c is constant on[q]2 \ diag

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201613 / 25

The m.d. set will be a union of ω1 -many perfect sets:
For some for sequence of perfect sets hPξ | ξ < ω1 i ∈ L, our m.d. set isjust[L[s]P¯ξ .
ξ<ω1We construct this sequence by induction: Say we havehPν | ν < ξi ∈ L, and say we have p ∈ S and a S-name which are
candidates forp ẋ is not in our family.
SSo assume that p (∀y ∈ ν<ξ P¯ν )¬(ẋ R y ).
We can also assume ẋ is given by a continuous function f : 2ω → X :pẋ = f (sĠ ).

It is easy to thin out p so that(∀x ∈ f 00 [p])(∀y ∈[Pν )¬(x R y ).

ν<ξSchrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201614 / 25

Further thin out such that either:1

f 00 [p] is R-discrete2

f 00 [p] is R-complete, i.e. (∀x, y ∈ f 00 [p]) x R y .

In the first case, let Pξ = f 00 [p]. Aspẋ = f (sĠ ) ∈ P¯ξ

we have dealt with this candidate.
In the second case, let Pξ = {f (z)}, where z is the left-most branchthrough p. By Shoenfield absolutenesspẋ = f (sĠ ) R f (z),so we have again dealt with this candidate.
SIn either case, ν≤ξ Pν is discrete. By Π11 absoluteness, this will holdSL[s]forP¯ξas well.
ξ<ω1As there are only ω1 -many pairs (ẋ, p) as above, we can ensure
maximality.
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201615 / 25

A basis for R over Q
Let X = R and let R be the set of finite tuples from X which are linearly
dependent over Q.

A more involved proof but using similar ideas as in the previous sketch(including a generalization of Galvin’s theorem to k -tuples due toBlass) gives us:Theorem (S 2016)
If s is a Sacks real over L, there is a Π11 basis for R over Q in L[s].

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201616 / 25

What is Galvin’s Theorem for iterated Sacks forcing?
Let P̄ be iterated Sacks forcing and p̄ ∈ P. What is [p̄]?
Provided we can define [p̄]. . .

Question:Is there for every p̄ ∈ P and everyc : [p̄]2 → {0, 1}
which is symmetric and nice, some q̄ ∈ P, q̄ ≤ p̄ such that c isconstant on [q̄]2 \ diag?
What do I mean by nice?
Answer is ‘yes’ for c which is continuous on [p̄]2 \ diag
(Geschke-Kojman-Kubiś-Schipperus)
perhaps Baire measurable. . . ?
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201617 / 25

For a dense set of p̄ ∈ P we have:
0 There is F0 : [p̄(0)] → PERFECT TREES and σ1 ∈ supp(p̄) such thatp̄p̄(σ1 ) = F0 (s̄Ġ (0))

1 There is a continuous function F1 and σ2 ∈ supp(p̄) such that(letting σ0 = 0)p̄ p̄(σ2 ) = F1 (s̄Ġ  σ2 )ω And so on: There exists sequences F0 , . . . , Fk , . . . and
σ0 , . . . , σk , . . . with σ0 = 0 such that the analogous holds for eachk ∈ ω and{σk | k ∈ ω} = supp(p̄)
Then [p̄] is the subspace of (2ω )λ consisting ofx̄ : supp(p̄) → 2ωsuch that for each n ∈ ωx̄(σn ) ∈ [Fn (x̄  σn )]Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201618 / 25

A counterexample
Let p̄ ∈ P. Fix ξ < λ.
Define a symmetric Borel function
c : [p̄]2 → {0, 1}by(1 if x̄0 (ξ) 6= x̄1 (ξ)
c(x̄0 , x̄1 ) =0 otherwise
Note:Every q̄ ≤ p̄ will meet both coloursc −1 (1) is open, c −1 (0) is closed.

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201619 / 25

For x̄0 , x̄1 ∈ [p̄], let∆(x̄0 , x̄1 ) = the least ξ such that x̄0 (ξ) 6= x̄1 (ξ).
Let∆ξ = {(x̄0 , x̄1 ) ∈ [p̄]2 | ∆(x̄0 , x̄1 ) = ξ}

∆0 is comeager in [p̄]2
So nice must be more restrictive than Baire measurable!
otherwise: take c arbitrary on ∆ξ , ξ > 0 (a meager set!)

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

20 / 25

Another counterexample:
Fix a bijection G : supp(p̄) → ω.
Define a symmetric function
c : [p̄]2 → {0, 1}
as follows:
Suppose we have x̄0 , x̄1 ∈ [p̄] and suppose x̄0 <lex x̄1 . Letξ = ∆(x̄0 , x̄1 ).
If ξ ∈ supp(p̄) and G(ξ) = k , setc(x̄0 , x̄1 ) = x̄i (0)(k ).
(When ξ ∈ supp(p̄) fails, set c to be 0; this case is irrelevant)
Now if c(·, ·) only depends on ∆(·, ·) on some [q], [q(0)] can contain at
most two branches, contradiction.
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 2016

21 / 25

The solution:Theorem (Galvin’s Theorem for iterated Sacks forcing)For every p̄ ∈ P and every symmetric universally Bairec : [p̄]2 → {0, 1}
there is q̄ ∈ P, q̄ ≤ p̄, with an enumeration hσk | k ∈ ωi of supp(q̄) anda function N : supp(q̄) → ω such that for (x̄0 , x̄1 ) ∈ [q̄]2 \ diag, the valueof c(x̄0 , x̄1 ) only depends onξ = ∆(x̄0 , x̄1 )and the following (finite) piece of information:(x̄0  K , x̄1  K )where K = {σ0 , . . . , σN(ξ) } × N(ξ).
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201622 / 25

Example 5: Cofinitary groups

Work in the space S∞ , the group of bijections from N to itself(permutations).
idN is the identity function on N, the neutral element of S∞ .

Definition
We say g ∈ S∞ is cofinitary ⇐⇒{n ∈ N | g(n) = n} is finite.
G ≤ S∞ is cofinitary ⇐⇒ every g ∈ G \ {idN } is cofinitary.

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201623 / 25

Definability of mcgs
Theorem (Kastermans)
No mcg can be Kσ .
Some history:
Gao-Zhang: If V = L, there is a mcg with a Π11 set of generators.
Kastermans: If V = L, there is a Π11 mcg.
Fischer-S.-Törnquist, 2015: The existence of a Π11 mcg isconsistent with arbitrarily large continuum.

Theorem (Horowitz-Shelah, 2016)(ZF) There is a Borel maximal cofinitary group.
By Σ12 absoluteness, a Borel mcg remains maximal in any outer model.
They also claim they will show there is a closed mcg in a future paper.
Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201624 / 25

Thank You!

Schrittesser (Copenhagen)Combinatorics, Definability & Forcing

RIMS 201625 / 25