Saturday 8th August, 2020 (09:59)

DEFINABLE MAD FAMILIES AND FORCING AXIOMS

VERA FISCHER, DAVID SCHRITTESSER, AND THILO WEINERT

Abstract. We show that ZFC+ BPFA (i.e., the Bounded Proper Forcing Axiom) + “there are no Π_{2}^{1} infinite MAD families” implies that ω_{1} is a remarkable cardinal in L. In other words, under BPFA and an anti-large cardinal assumption there is a Π_{2}^{1} infinite MAD family. It follows that the consistency strength of ZFC+ BPFA + “there are no projective infinite MAD families” is exactly a Σ_{1}-reflecting cardinal above a remarkable cardinal. In contrast, if every real has a sharp—and thus under BMM—there are no Σ_{3}^{1} infinite MAD families.

1. Introduction

A. By a MAD family, we mean a collection A with the following two properties: Firstly, A is an almost disjoint (short: a.d.) family, that is, A consists of infinite subsets of ω and any two distinct a, a′ ∈ A are almost disjoint, i.e., a ∩ a′ is finite. Secondly, for any infinite set b ⊆ ω there is a ∈ A such that |a ∩ b|= ℵ_{0}; that is, A is maximal among a.d. families under inclusion.

While finite MAD families exist trivially, infinite MAD families can be constructed using the Axiom of Choice. This makes them an example of an irregular set somewhat analogous to a set without the Baire property or a non-measurable set.

As is well-known, Mathias [16, 15] proved that no infinite MAD family can be analytic. On the other hand, Arnie W. Miller in [17] constructed a co-analytic infinite MAD family under the assumption that V = L, showing that Mathias’ result is optimal.

Mathias [16] also produced a model of ZF + DC in which there are no infinite MAD families, starting from the assumption of a Mahlo cardinal. Much later, Törnquist showed that there are no infinite MAD families in Solovay’s model [28], and Horowitz and Shelah produced a model of ZF + “there are no infinite MAD families” without making any large cardinal assumption [9].

The definability of MAD families has been investigated under many natural extensions of the axiomatic system ZFC. It was shown recently by Neeman and Norwood and independently by Bakke-Haga, Törnquist and the second author, that under the Axiom of Determinacy (AD) no infinite MAD family can be an element of L(ℝ); and under the Axiom of Projective Determinacy and the Axiom of Dependent Choice (DC) there is no projective infinite MAD family [19, 2, 25]. In fact, as Neeman and Norwood were first to show, under AD^{+} (a technical strengthening of AD introduced by Woodin) there are no infinite MAD families.

Another natural family of extensions of ZFC are forcing axioms. Definability properties of irregular sets of reals under such axioms have long been investigated. An early example is work of Martin and Solovay [14] showing that Martin’s Axiom for sets of size ℵ_{1} (MA_{ℵ_{1}})

Key words and phrases. Maximal almost disjoint families, MAD families, Bounded proper forcing axiom, remarkable cardinals.

Saturday 8th August, 2020 (09:59)

implies that all Σ_{2}^{1} sets are measurable and have the Baire property. It was shown by Törnquist [28] that similarly MA_{ℵ_{1}} rules out the existence of infinite MAD families which are Σ_{2}^{1} in terms of definitional complexity.

As is well-known, MA_{ℵ_{1}} is equiconsistent with ZFC; adding assumptions about regularity of definable sets of reals can increase this consistency strength. For instance it was shown by Harrington and Shelah [8] that MA_{ℵ_{1}} together with “all projective sets are measurable and have the Baire property” is equiconsistent with ZFC+ there is a weakly compact cardinal (in fact, it suffices to add “all Δ_{3}^{1} sets have the Baire property” or “all Δ_{3}^{1} sets are measurable” to MA_{ℵ_{1}} to drive up its consistency strength).^{1}

On the other hand, the theory MA_{ℵ_{1}} + “there is no infinite projective MAD family” (and even MA_{ℵ_{1}} + “there is no infinite MAD family which is definable from a parameter in On^{ω}”) is equiconsistent with ZFC; this is a by-product of Horowitz and Shelah’s construction in [9] of a model of ZF + “there are no infinite MAD families” (since as part of this construction they force MA_{ℵ_{1}} to hold).

Stronger forcing axioms such as the Proper Forcing Axiom (PFA) imply that AD holds in L(ℝ), as was shown by Steel [26]. Thus under PFA, just as under AD, all sets of reals in L(ℝ) are regular: They are measurable, have the Baire property, and no infinite MAD family can be found among them. As we shall show, this is not the case for the so-called bounded version of this axiom, the Bounded Proper Forcing Axiom (BPFA). This axiom was introduced by Goldstern and Shelah in [7] and later recognized to be equivalent to a principle of generic absoluteness by Bagaria [1]; it is quite a bit stronger than MA_{ℵ_{1}} but much weaker than PFA.

In the present paper, we show that the assumption that there are no infinite MAD families with a simple definition drives up the consistency strength of BPFA.

Theorem 1.1. ZFC + BPFA+ “there is no infinite Π_{2}^{1} MAD family” implies that ω_{1} is a remarkable cardinal in L.

This is indeed remarkable, since ZFC + BPFA alone is known to have consistency strength of a Σ_{1}-reflecting cardinal, which is weaker than a remarkable cardinal. As we have already mentioned, it is known that BPFA (in fact, just MA_{ℵ_{1}}) rules out the existence of Σ_{2}^{1} (in fact, of ω_{1}-Suslin) infinite MAD families [28], so the complexity of Π_{2}^{1} in the above theorem cannot be improved.

By results of Schindler (see [22]) the consistency strength of ZFC+BPFA+ “every set in L(ℝ) is measurable” is exactly a Σ_{1}-reflecting cardinal above a remarkable cardinal. With Theorem 1.1 and Törnquist’s result from [28] at our disposal, we can adapt Schindler’s argument to gauge the exact consistency strength of ZFC + BPFA+ “there is no infinite Π_{2}^{1} MAD family”.^{2}

Corollary 1.2. The following are equiconsistent:

(1) ZFC + “there exists a Σ_{1}-reflecting cardinal above a remarkable cardinal.”

(2) ZFC + BPFA + “there is no infinite Π_{2}^{1} MAD family.”

(3) ZFC + BPFA+ “there is no infinite MAD family in L(ℝ).”

1The reader can find a wealth of further results in [3, Chapter 9].

2We thank the anonymous referee for calling Corollary 1.2 to our attention.

Saturday 8th August, 2020 (09:59)

Proof. Clearly, Item (2) implies that the theory in Item (1) is consistent: It is well-known that BPFA implies that ω_{2} is Σ_{1}-reflecting in L; by Theorem 1.1 ω_{1} is remarkable in L.

It suffices to show that the theory in Item (3) is consistent assuming Item (1). So suppose κ < λ, κ is remarkable, and λ is Σ_{1}-reflecting in V. Let G be Coll(ω, < κ)-generic over V, and let H be generic for a proper forcing over V [G] such that V [G][H] ⊨ BPFA. Since κ is remarkable, it follows as in [22, Lemma 24] that for any x ∈ P(ω) ∩ V [G][H] there is ξ < κ and some generic G′ for Coll(ω, ξ) over V such that x ∈ V [G′]. It follows from this as in Lemma 8 of [22] (described as “folklore” there) that the first-order theory of L(ℝ)^{V [G][H]} is the same as the theory of L(ℝ) after forcing with Coll(ω, < κ). But in the latter model, there is no infinite MAD family by [28]—or because universal Ramsey regularity and Ramsey-positive uniformization hold in this model, and by [25]. □

We can also view Theorem 1.1 from a different perspective. We have seen that forcing axioms which are strong enough to imply AD^{L(ℝ)}, rule out the existence of definable infinite MAD families. Our result shows that under an anti-large cardinal assumption, forcing axioms can lead to the opposite result: They imply the existence of infinite MAD families at a rather low level of the projective hierarchy.

Theorem 1.3. Suppose BPFA holds and that ω_{1} is not remarkable in L. Then there is an infinite Π_{2}^{1} MAD family.

We take this as evidence that under certain forcing axioms and anti-large cardinal assumptions, the universe behaves somewhat like L (as in L there are infinite Π_{1}^{1} MAD families). This idea is also corroborated by the proof of the above theorem.

An obvious question is to which degree the above theorem can be generalized in the sense of replacing “almost-disjointness” by other relations. To state this question precisely, let us introduce some terminology: Let E be a binary, symmetric, and anti-reflexive relation on a Polish space X. We view G = ⟨X, R⟩ as a simple graph with vertex set X and edge relation E. To say such G is Borel, Σ_{1}^{1}, … means that E is Borel, Σ_{1}^{1}, … as a subset of X^{2} (a Polish space, with the product topology). A set D ⊆ X is called G-discrete if no two of its elements are E-related, and maximal discrete if it is G-discrete and maximal with respect to ⊆ among G-discrete subsets of X.

We can now ask: Under the same hypothesis as in Theorem 1.3, which Borel graphs on Polish spaces have an infinite Π_{2}^{1} maximal discrete set? What about Σ_{3}^{1} graphs?

That the answer is not “all of them” is obvious from the fact that maximal discrete sets for the relation xEy ⟺ (x ≠ y ∧ |xΔy| < ℵ_{0}) on P(ω) cannot be measurable and hence not Π_{1}^{1}. Likewise, under MA_{ℵ_{1}} no Π_{2}^{1} maximal discrete set for this relation can exists, since under MA_{ℵ_{1}} all Σ_{2}^{1} sets are measurable.

The obstacle to generalizing our construction to arbitrary Borel (or Σ_{3}^{1}) graphs is the coding mechanism in Fact 4.5 which relies heavily on the combinatorics of our specific graph. Vidnyánszky [29] has found a large class of graphs which admit a co-analytic maximal discrete set if P(ω) ⊆ L: For instance, this holds for Borel graphs G = ⟨X, E⟩ with the property that for each countable D ⊆ X and d ∈ X such that D ∪ {d} is G-discrete, the set

{d′ ∈ X | D ∪ {d′} is G-discrete and D ∪ {d,′ d} is not}

Saturday 8th August, 2020 (09:59)

is cofinal in the hyperarithmetic degrees. Vidnyánszky’s construction uses properties specific to Π_{1}^{1} sets, and it is not clear how to carry out this argument at the level of Π_{2}^{1} sets (under BPFA).

Inspired by a question put to us by the anonymous referee, for which we are thankful, we proved the following theorem. Recall that Bounded Martin’s Maximum (BMM) is the bounded forcing axiom for stationary set preserving forcing.

Theorem 1.4. ZFC + BMM implies that there are no infinite Σ_{3}^{1} families.

However, as is not hard to see, under just BPFA and thus also under BMM, there is an infinite MAD family which is Δ_{1} allowing a parameter from P(ω_{1}) (using the wellordering of P(ω) from Theorem 2.1 below). The consistency strength of BMM is not known; the best upper bound, to our knowledge, is (ω + 1)-many Woodin cardinals (an unpublished result due to Woodin); the current lower bound is a strong cardinal [24].

B. Our work has some precursors in the literature: In [4] it is shown that under BPFA, if ω_{1} is not remarkable in L every predicate on P(ω) which has a Σ_{1} definition in H(ω_{2}) also has a Σ_{3}^{1} definition.

It was shown by Asger Törnquist in [27] that if there is an infinite Σ_{2}^{1} MAD family, there is an infinite Π_{1}^{1} MAD family. Unfortunately, the latter proof does not lift to show that there exists a Π_{2}^{1} infinite MAD under BPFA+ω_{1} is not remarkable in L. The reason for this is that Törnquist’s proof relies on properties of Σ_{2}^{1} and Π_{1}^{1} sets which do not hold for Σ_{3}^{1} and Π_{2}^{1} sets.

C. The paper is organized as follows. In section §2 we discuss a result of Caicedo and Velickovic which can be summed up as follows: BPFA implies that there is a well-ordering of P(ω) of length ω_{2} with definable initial segments. In §3 we discuss the role of the anti-large cardinal assumption, referring to work of Schindler, and discuss a technique of localization which we have used before (e.g., [6]) and which takes a particularly simple form under BPFA + ω_{1} is not remarkable in L. In §4 we prove Theorem 1.3, and in the short §5 we prove Theorem 1.4 We close with open questions in §6.

Acknowledgements: The first, second and third authors would like to thank the Austrian Science Fund (FWF) for the generous support through START Grant Y1012-N35. The second author would also like to thank the FWF through generous support from project P 29999. We thank the anonymous referee for their effort and their comments, which have greatly improved this paper.

2. A well-ordering with definable initial segments

It was shown by Moore [18] that under BPFA there is a well-ordering of P(ω) of ordertype ω_{2}. Improving Moore’s result, Caicedo and Velickovic [5] obtained, under BPFA, such a well-ordering which is definable by a Σ_{1} formula with a parameter from P(ω_{1}).

Their well-ordering has the following property which will be crucial to our argument.

Theorem 2.1. Under BPFA there is a well-ordering ≺ of P(ω) such that for some Σ_{1} formula Φ_{≺}(u, v, w) and some parameter c_{≺} ⊆ ω_{1},

(∀x ∈ P(ω))(∀I) (Φ_{≺}(x, I, c_{≺}) ⟺ I = {y ∈ P(ω) : y ≺ x})

Saturday 8th August, 2020 (09:59)

Such a well-ordering is obviously very useful when one is interested in devising a recursive definition of optimal complexity. For convenience, we give a name to this type of well-order:

Definition 2.2. We say a well-order ≺ of P(ω) with the property from Theorem 2.1 has (Σ_{1}, P(ω_{1}))-definable good initial segments.

In fact, what Caicedo and Velickovic show in their article [5] is that P(ω) carries a well-order ≺ with the properties (i) and (ii) in the fact below. Of course, this is equivalent to having (Σ_{1}, P(ω_{1}))-definable initial segments.

Fact 2.3. That a well-ordering of P(ω) has (Σ_{1}, P(ω_{1}))-definable initial segments (i.e., has the property from Theorem 2.1) is equivalent to the conjunction of the following:

(i) ≺ is Σ_{1} with a parameter c_{≺} ⊆ ω_{1}, (ii) There is a formula Φ_{is}(u) such that for any transitive model M with c_{≺} ∈ M,

M ⊨ Φ_{is}(c_{≺}) if and only if ≺ is absolute for M and M ∩P(ω) is an initial segment of ≺.

Remark 2.4. The requirement in (ii) above that M ⊨ Φ_{is}(c_{≺}) implies that ≺ is absolute for M is redundant; it follows from Requirement (i) if we replace Φ_{is}(c_{≺}) by its conjunction with (∀x, y ∈ P(ω)) x ≺ y ∨ y ≺ x.

Proof. To see that (i)∧(ii) implies that ≺ is a well-ordering with (Σ_{1}, P(ω_{1}))-definable initial segments let Φ_{≺}(x, I, c_{≺}) be the formula

(∃M) M is a transitive ∈-model with {x, c_{≺}, I} ⊆ M and M ⊨ “Φ_{is}(c_{≺}) ∧ I = {y ∈ P(ω) | y ≺ x}”

and observe I = {y ∈ P(ω) : y ≺ x} ⟺ Φ_{≺}(x, I, c_{≺}).

For the other direction, firstly observe that if ≺ has (Σ_{1}, P(ω_{1}))-definable initial segments then obviously ≺ is Σ_{1} in the parameter c_{≺}. Secondly, let Φ_{is}(c_{≺}) be the formula

(∀x, y ∈ P(ω)) x ≺ y ∨ y ≺ x ∧ (∀x ∈ P(ω))(∃I) Φ_{≺}(x, I, c_{≺}).  □

For a proof that under BPFA there is such a well-ordering of P(ω) with (Σ_{1}, P(ω_{1}))- definable good initial segments, we refer the reader to the excellent exposition in [5].

3. Coding, reshaping, and localization

We start by recalling the following well-known fact.

Fact 3.1. Let B = ⟨b_{ξ} : ξ < ω_{1}⟩ be an arbitrary sequence of pairwise almost disjoint infinite subsets of ω. Under MA_{ℵ_{1}}, for every subset of S ⊆ ω_{1} there is a c ⊆ ω such that

(1)  S = {ξ < ω_{1} : c ∩ b_{ξ} is infinite}.

The proof of this fact is equally well-known; it uses Solovay’s almost disjoint coding (see [10] or, e.g., [12]).

We take the opportunity to introduce the following rather natural terminology:

Definition 3.2. We shall say that c ⊆ ω almost disjointly via B codes the set S to mean precisely that (1) holds.

Our only use of the assumption that ω_{1} is not remarkable in L is in the following fact (this was shown by Ralf Schindler in [20, 21]).

Saturday 8th August, 2020 (09:59)

Fact 3.3. Suppose ω_{1} is not remarkable in L and BPFA holds. Then there exists r ∈ P(ω) such that ω_{1} = (ω_{1})^{L[r]}.

Notation 3.4.

(1) For the rest of this article, let us suppose that ω_{1} = (ω_{1})^{L[r]} for some r ∈ P(ω) which from now on shall remain fixed.

(2) Fix an almost disjoint family F = ⟨f_{ξ} : ξ < ω_{1}⟩ which has a Σ_{1} definition in L[r] and such that for any α < ω_{1}, ⟨f_{ξ} : ξ < (ω_{1})^{L_{α}[r]}⟩ is the set satisfying this definition in L_{α}[r].

It is a consequence of ω_{1} = (ω_{1})^{L[r]} and MA_{ℵ_{1}} that any predicate which is Σ_{1} in H(ω_{2}) (with a parameter) can be localized in a strong sense. A version of this result can, e.g., be found in [4].

To state the following localization lemma, let us make a definition which will be used throughout the paper.

Definition 3.5 (Suitable models). A suitable model is a countable transitive ∈-model N such that r ∈ N, N ⊨ ZF^{−} and N ⊨“ω_{1} exists”.

Lemma 3.6 (A form of localization). Suppose MA_{ℵ_{1}} holds (and recall that we are working under the assumption that ω_{1} = (ω_{1})^{L[r]} made in 3.4). Let ϕ(y, ω_{1}) be an arbitrary formula, where y ∈ P(ω) and ω_{1} are parameters, and suppose that for some transitive ∈-model M with {ω_{1}, y} ∈ M it holds that M ⊨ ϕ(y, ω_{1}). Then there is c ⊆ ω such that the following holds:

(2)

Given any suitable model N with {c, y} ⊆ N the following must hold in N: “There is a transitive ∈-model M^{∗} such that {y, (ω_{1})^{N}} ⊆ M^{∗} and M^{∗} ⊨ ϕ(y, (ω_{1})^{N})”.

Proof. Fix a transitive model M as in the lemma. We can assume M to have size ω_{1}. Find S ⊆ ω_{1} such that via Gödel pairing, S gives rise to a well-founded binary relation S^{∗} on ω_{1} whose transitive collapse is ⟨M, ∈ ↾M⟩. We can ask that y and ω_{1} are mapped to specific points in ⟨ω_{1}, S^{∗}⟩ by the inverse of the collapsing map, say to 0 and 1.

Let

(3)  D = {β ∈ ω_{1} : (∃N^{∗}) N^{∗} ≺ L_{ω_{2}}[S^{∗}, y], {S^{∗}, y} ∈ N^{∗}, β = ω_{1} ∩ N^{∗}}.

For Y ⊆ On, let Even(Y) = {ξ : 2ξ ∈ Y } and Odd(Y) = {ξ : 2ξ + 1 ∈ Y }. Choose Y to be any subset of ω_{1} such that Even(Y) = S^{∗} and for each β ∈ D, the preimage under Gödel pairing of Odd(Y) ∩ [β, β + ω) is a well-founded binary relation of rank at least min (D \ (β + 1)).

Claim 3.7. Y ⊆ ω_{1} satisfies the following:

(4)

Given any suitable model N with {Y ∩(ω_{1})^{N}, y} ⊆ N the following must hold in N: “There is a transitive ∈-model M^{∗} such that {y, (ω_{1})^{N}} ⊆ M^{∗} and M^{∗} ⊨ ϕ(y, (ω_{1})^{N})”.

Proof. To see that Y indeed satisfies (4) let N as in (4) be given. Letting β = (ω_{1})^{N} it must hold that β ∈ D: For if β′ < β, since β ∩Y ∈ N, this model contains a well-founded binary relation of length min (D \ (β′ + 1)) as an element, and so min (D \ (β′ + 1)) < β = (ω_{1})^{N} because N is a model of ZF^{−}. As D is closed, β ∈ D. It also follows that S^{∗} ∩ β ∈ N.

Saturday 8th August, 2020 (09:59)

By definition of D we may pick N^{∗} as in (3). Letting \overline{N}^{∗} be the transitive collapse of N^{∗} we obtain an elementary embedding j : \overline{N}^{∗} → L_{ω_{2}}[S^{∗}, y] with critical point β = (ω_{1})^{N} (namely, the inverse of the collapsing map) such that {S^{∗}, y, ω_{1}} ⊆ ran(j). By elementarity \overline{N}^{∗} ⊨“The transitive collapse of ⟨β, S^{∗} ↾ β⟩ is a transitive ∈-model M^{∗} such that M^{∗} ⊨ Φ(y, β)”. But this transitive collapse is also an element of N, so by absoluteness of Δ_{1} formulas N must satisfy the same sentence. Claim 3.7. □

Finally, we find c ∈ P(ω) which almost disjointly via F codes the set Y ⊆ ω_{1} constructed above. To see that c satisfies (2) let N as in (2) be given. By choice of F (see Notation 3.4) ⟨f_{ξ}: ξ < (ω_{1})^{N}⟩ ∈ N and so since N ⊨ ZF^{−} it holds that Y ∩ (ω_{1})^{N} ∈ N. By (4) the sentence “there is a transitive ∈-model M^{∗} such that {y, (ω_{1})^{N}} ⊆ M^{∗} and M^{∗} ⊨ ϕ(y, (ω_{1})^{N})” holds in N, verifying (2). Lemma 3.6. □

4. Proof of Theorem 1.3

In this section we prove Theorem 1.3 in the following, slightly more general form:

Theorem 4.1. Suppose there is a well-ordering of P(ω) of length ω_{2} with (Σ_{1}, P(ω_{1}))- definable initial segments, MA_{ℵ_{1}} holds, and ω_{1} = (ω_{1})^{L[r]} where r ∈ P(ω). Then there is an infinite Π_{2}^{1} MAD family.

It is clear by Theorem 2.1 and Fact 3.3 that BPFA + ω_{1} is not remarkable in L implies the hypothesis, so proving the above theorem will indeed prove Theorem 1.3.

Notation 4.2. From now on, we suppress the parameter r and assume ω_{1} = (ω_{1})^{L}; our argument will relativize to r trivially.

By Theorem 2.1 we can fix a well-ordering ≺ of P(ω) with (Σ_{1}, P(ω_{1}))-definable initial segments, together with a parameter c_{≺} ⊆ ω and a formula Φ_{is}(c_{≺}) as in Fact 2.3.

We shall inductively construct a sequence ⟨a_{ν} : ν < ω_{2}⟩ such that A = {a_{ν} : ν < ω_{2}} will be a Π_{2}^{1} MAD family.

The most straightforward formula defining a MAD family A would express that a ∈ A iff there is an initial segment ⟨a_{ν} : ν ≤ ξ⟩ of the construction with a = a_{ξ}; that is, assuming we can find a formula expressing that ⟨a_{ν} : ν ≤ ξ⟩ is an initial segment of this construction. But of course it is not clear how any projective formula should express such a fact about ⟨a_{ν} : ν < ξ⟩, this being an object of size ω_{1}. A first step towards a solution is that a_{ξ} should code certain sets of size ω_{1}, including ⟨a_{ν} : ν < ξ⟩. Almost disjoint coding via F (see Fact 3.1) allows us to find a real coding these large sets. We then want to find a real ‘localizing’ this coding, i.e., ensuring that the property of coding an initial segment of the construction is expressible by a Π_{2}^{1} formula. Using a variant of the coding from [17] we can then code these reals into a_{ξ}.

4.1. Coding into an almost disjoint family. We call the following fact from Miller’s article [17] to the reader’s attention.

Fact 4.3 (see [17, Lemma 8.24, p. 195]). Fix z ∈ P(ω) and suppose a⃗ = ⟨a_{ν} : ν < ξ⟩ is a countable sequence of pairwise almost disjoint infinite sets. For any d ∈ [ω]^{ω} which is almost disjoint from every element of a⃗ there is a ∈ [ω]^{ω} such that

• a ∩ d is infinite,

• a is almost disjoint from each a_{ν} for ν < ξ,

• and z is computable from a and a⃗ ↾ ω = ⟨a_{n} : n < ω⟩.

Saturday 8th August, 2020 (09:59)

Using this fact, Miller succeeds in constructing a co-analytic MAD family in L: he recursively constructs ⟨a_{ν} : ν < ω_{1}⟩ such that in the end, A = {a_{ν} : ν < ω_{1}} turns out to be a Π_{1}^{1} MAD family. At some initial stage ξ < ω_{1} having constructed a⃗ = ⟨a_{ν} : ν < ξ⟩ he considers a counterexample d to the maximality of the family {a_{ν} : ν < ξ} constructed so far. Instead of adding this set d to a⃗, he adds a as in the fact above, which in addition codes some information z so as to bring down the definitional complexity of A.

Since we shall need a variant of this type of coding, let us repeat Miller’s proof of the above fact.

Proof of Fact 4.3. Let b⃗ = ⟨b_{n} : n ∈ ℕ⟩ enumerate {a_{ν} : ω ≤ ν < ξ}. For each n ∈ ω, choose a finite set G_{n} ⊆ a_{n} \ ⋃ ({ b_{k} : k < n} ∪ { a_{k} : k < n}) so that |G_{n} ∪ (a_{n} ∩ d)| is even if n ∈ z, and odd otherwise. Finally, let a = d ∪ ⋃{G_{n} : n ∈ ω}. □

For our purposes the previous fact is useless, since as 2^{ω} = ω_{2} under BPFA we shall have to deal with uncountable sequences a⃗ = ⟨a^{ν} : ν < ξ⟩. Interestingly, there is a variant of the above construction that allows us to deal with uncountable sequences.

Before we describe this variant let us commit, once and for all, to some sequence (to be used for coding purposes) as an initial segment of the MAD family we are about to construct.

Notation 4.4. Let us fix, for the rest of this article, some sequence a⃗_{ω} = ⟨a_{n} : n ∈ ω⟩ of infinite sets any two of which are almost disjoint.

We now state our variant of Miller’s coding lemma. For this variant, we must make an additional assumption (the existence of c below) which in our case will easily be seen to follow from MA_{ℵ_{1}} (see Remark 4.6 below)

Fact 4.5. Suppose a⃗ = ⟨a_{ν} : ν < ξ⟩ is a (possibly uncountable) sequence of pairwise almost disjoint infinite subsets of ω such that a⃗ ↾ ω = a⃗_{ω}. Further suppose we have c ∈ [ω]^{ω} satisfying the following:

• c is almost disjoint from each a_{ν}, for ω ≤ ν < ξ, and

• c ∩ a_{n} is infinite for each n ∈ ω. Then for any z ∈ P(ω) and any d ∈ [ω]^{ω} which is almost disjoint from every element of ran(a⃗) there is a ∈ [ω]^{ω} such that

• a ∩ d is infinite,

• a is almost disjoint from each a_{ν} for ν < ξ,

• and z is computable from a and a⃗ ↾ ω = ⟨a_{n} : n < ω⟩. In fact there are functions dc: P(ω) → P(ω) and cd: P(ω)^{3} → P(ω), both of which are computable in a⃗_{ω}, such that a as above is given by a = cd(d, c, z) and z can be recovered from a as z = dc(a).

The name dc was chosen to remind us that this function will be used to ‘decode’ z from a, and likewise, the name cd should remind us that the function produces a ‘code’ (for z).

Remark 4.6. We will use Fact 4.5 in the situation where a⃗ = ⟨a_{ν} : ν < ξ⟩ is of length ξ < ω_{2} and MA_{ℵ_{1}} holds. Then it is easy to see c as in Fact 4.5 exists: Just use Fact 3.1 to obtain c so that {ν < ξ | c ∩ a_{ν} is infinite } = ω.

Saturday 8th August, 2020 (09:59)

Proof of Fact 4.5. We define cd: P(ω)^{3} → P(ω) as follows. Let F_{n} be the shortest finite initial segment of

c ∩ a_{n} \ ⋃{a_{k} : k < n}

such that |F_{n} ∪ (d ∩ a_{n})| is even if n ∈ z and odd otherwise. Clearly, F_{n} can be found by a procedure which is computable in a⃗_{ω}, c, d, and z. Now define the function cd by

cd(d, c, z) = d ∪ ⋃{F_{n} : n ∈ ω}.

Moreover, we define dc: P(ω) → P(ω) as follows: Given a ∈ [ω]^{ω} let

dc(a) = {n ∈ ω : |a ∩ a_{n}| is even}.

Clearly, these functions satisfy the conditions in the lemma. □

4.2. Minimal local witnesses. The functions cd and dc together with the almost disjoint coding into reals of subsets of ω_{1} via F will help us arrange that a_{ξ} codes ⟨a_{ν} : ν < ξ⟩. But crucially, we need the fact that a_{ξ} codes an initial segment of the construction (up to stage ξ, some ordinal below ω_{2}) to be witnessed by a Π_{2}^{1} formula (the same formula for all ξ < ω_{2}). This involves uniquely selecting a real c_{ξ} ∈ P(ω) which we call a minimal local witnesses and whose task is to localize the coding to suitable countable models. Uniquely selecting such a real is a non-trivial task, and to tackle it we introduce some terminology.

Notation 4.7. Let F: ω^{2} → ω denote some fixed recursive bijection for the remainder of this article.

Definition 4.8.

(1) Given c ⊆ ω and n ∈ ω we write (c)_{n} for {m ∈ ω : F (n, m) ∈ c}.

(2) Given c ⊆ ω we write Seq (c) for the sequence ⟨(c)_{n} : n ∈ ω⟩.

(3) Let G: On^{2} → On denote the Gödel pairing function. We say c ⊆ ω almost disjointly via F codes the sequence b⃗ to mean that c ⊆ ω almost disjointly via F codes a set S ⊆ ω_{1} and b⃗ = ⟨b_{ν} : ν < ξ⟩ where:

• For θ < ω_{1}, letting

S_{θ} = {η < ω_{1} | G(θ, η) ∈ S},
S_{θ}^{∗} = {(ζ_{0}, ζ_{1}) ∈ (ω_{1})^{2} | ω + G(ζ_{0}, ζ_{1}) ∈ S_{θ}},

it holds that ⟨ω_{1}, S_{θ}^{∗}⟩ is a well-ordering and ξ = {otp S_{θ}^{∗} | θ < ω_{1}, S_{θ} ≠ ∅};

• For each ν < ξ there is exactly one θ such that S_{θ} ≠ ∅ and otp S_{θ}^{∗} = ν, and for this θ it holds that

b_{ν} = ω ∩ S_{θ}.

The crucial definition for our proof of Theorem 4.1 (and thus, of Theorems 1.1 and 1.3) is that of minimal local witness.

Remark 4.9. In the end, our MAD family will be

A = {a_{n}: n ∈ ω}∪

{a ∈ [ω]^{ω} : c = dc(a) is a minimal local witness and a = cd ((c)_{0}, (c)_{1}, c)}.

We will show below that being a minimal local witness is expressible by a Π_{2}^{1} formula. Thus, A will be Π_{2}^{1}. The low definitional complexity will be achieved through a careful

Saturday 8th August, 2020 (09:59)

recursive construction of A. We will have A = {a_{ξ} : ξ < ω_{2}} where letting c_{ξ} = dc(a_{ξ}), (c_{ξ})_{2} almost disjointly via F codes ⟨a_{ν} : ν < ξ⟩.

Before we introduce the notion of minimal local witnesses, we make another convenient definition, for which some motivation should be provided by the previous remark.

Definition 4.10. We shall say that a sequence b⃗ = ⟨b_{ν} : ν < ξ⟩ is a coherent candidate if a⃗_{ω} ⊆ b⃗ and moreover, for each ν < ξ it holds that ( dc(b_{ν}))_{2} almost disjointly via F codes the sequence b⃗ ↾ ν.

We proceed towards the definition of minimal local witness, by defining the notions of k-witness, minimal k-witness and k-localizer, by induction on k ∈ ω, k ≥ 3.

Definition 4.11. We say c̄ ∈ P(ω)^{3} is a 3-witness if and only if

(∗)_{3} (a) c̄(2) almost disjointly via F codes a sequence b⃗ = ⟨b_{ν} : ν < ξ⟩.

(b) b⃗ is a coherent candidate.

(c) c̄(1) is subset of ω such that c ∩ b_{ν} is infinite if ν < ω and finite for all other ν < ξ.

(d) c̄(0) is an element of [ω]^{ω} which is almost disjoint from each b_{ν} for ν < ξ;

Remark 4.12. Clearly, the sequence b⃗ from (a) is intended to be an initial segment of the MAD family under construction. We ask (b) as a first step towards ensuring that this is indeed the case. The reader will notice that in (c) we require that c̄(1) has the same properties as c in Fact 4.5, and in (d) we require that c̄(0) has the same properties as d in said fact. The reader may think of c̄(0) as a counterexample to maximality of b⃗ which we wish to eliminate at stage ξ of our construction of A by adding a ‘self-coding’ element to our MAD family which has infinite intersection with c̄(0).

We continue with the definition of minimal 3-witness to a sequence b⃗ of subsets of ω.

Definition 4.13. For any 3-witness c̄ ∈ P(ω)^{3}, we say c̄ is a witness to b⃗ if b⃗ is the sequence coded by c̄(2) as in (a) above. We also write b⃗(c̄(2)) for this sequence. Write ≺^{3} for the lexicographic ordering on P(ω)^{3} induced by ≺. We call a 3-witness c̄ ∈ P(ω)^{3} minimal if it is ≺^{3}-minimal among all 3-witnesses to the same sequence b⃗. This is the same as saying that c̄(2) is ≺-minimal satisfying (d) in (∗)_{3}, c̄(1) is ≺-minimal satisfying (c), and c̄(0) is ≺-minimal satisfying (a).

As is not hard to see, the notion of minimal 3-witness is sufficiently absolute for our purposes:

Lemma 4.14. The notion of 3-witness is absolute for transitive models M of ZF^{−} such that ω_{1} ∈ M and the notion of minimal 3-witness is absolute for such models if in addition M ⊨ Φ_{is}(c_{≺}).

Proof. The statement (∗)_{3}(a) that c̄(2) almost disjointly via F codes a sequence b⃗ is easily seen to be equivalent in ZF^{−} to a Σ_{1} property of c̄(2), allowing ω_{1} as a parameter. Moreover, this Σ_{1} statement is absolute for transitive models M of ZF^{−} since a witness can be constructed inside M using the Replacement Axiom, and as F ∈ M by choice of F. That b⃗ is a coherent candidate is absolute for the same reasons. Statements (c) and (d) are obviously Δ_{1} in the parameters b⃗ and c̄. This shows that the notion of 3-witness is absolute for transitive models M of ZF^{−}.

Saturday 8th August, 2020 (09:59)

Minimality of 3-witnesses is now easily seen to be absolute provided that in addition M ⊨ Φ_{is}(c_{≺}) since ≺ is absolute for such M and P(ω) ∩ M is an initial segment of ≺: If c̄ ∈ M is a minimal 3-witness, M ⊨“c̄ is a minimal 3-witness” by absoluteness of ≺ and of the notion of 3-witness. Vice versa, suppose c̄ ∈ M and M ⊨“c̄ is a minimal 3-witness”. Then c̄(0) must minimal satisfying (∗)_{3}(a) since if there were c′ ≺ c̄(0) satisfying (a), it would have to be the case that c′ ∈ M since P(ω)∩M is a ≺-initial segment, contradicting M ⊨“c̄ is a minimal 3-witness”. Likewise for c̄(1) and c̄(2). □

We now give the crucial definition of a 3-localizer—a real which ensures that minimal 3-witnesses can be recognized from a local (i.e., a Π_{2}^{1}) property.

Definition 4.15. Given c̄ ∈ P(ω)^{3} (a putative 3-witness) we say c ∈ P(ω) is a 3-localizer for c̄ if and only if:

(∗)_{4} For any suitable model N with {c̄, c, a⃗_{ω}} ⊆ N, the following holds in N: There is a transitive model M of ZF^{−} such that M ⊨ Φ_{is}(c_{≺}), {ω_{1}, c̄, a⃗_{ω}} ⊆ M, and

(a) M ⊨“c̄ is a minimal 3-witness”.

(b) Writing b⃗(c̄(2))^{M} as ⟨b_{ν} : ν < ξ⟩ it holds that for each ν < ξ, M ⊨“c̄_{ν}^{∗} ↾ 3 is a minimal 3-witness”, where c̄_{ν}^{∗} = Seq (dc(b_{ν})).

Remark 4.16. Note that “c̄_{ν} ↾ 3 is a minimal 3-witness” is a statement which uses a⃗_{ω} as a parameter.

We need the following crucial lemmas:

Lemma 4.17. Suppose c̄ ∈ P(ω)^{3} is a minimal 3-witness, b⃗(c̄(2)) = ⟨b_{ν} | ν < ξ⟩ and for each ν < ξ it holds that Seq (dc(b_{ν})) ↾ 3 is a minimal 3-witness. Then there exists a 3-localizer for c̄.

Proof. Suppose c̄ ∈ P(ω)^{3} is as in the lemma. Fix a transitive model M of ZF^{−} such that {ω_{1}, c̄} ⊆ M and so that M ⊨ Φ_{is}(c_{≺}). By Lemma 4.14 the property of being a minimal 3-witness is absolute for M, so M ⊨“c̄ is a minimal 3-witness” and M ⊨“c̄_{ν}^{∗} ↾ 3 is a minimal 3-witness” where c̄_{ν}^{∗} = Seq (dc(b_{ν})) for each ν < ξ.

Now as in the proof of Lemma 3.6, find c coding almost disjointly via F a subset of ω_{1} which is isomorphic to ∈ ↾M and such that for any suitable model N, if c, c̄ ∈ N then it holds in N that c codes a model M^{∗} which witnesses the Σ_{1} statement expressing c̄ and each c̄_{ν}^{∗} ↾ 3 are minimal 3-witnesses. Clearly, c is a 3-localizer for c̄. □

Lemma 4.18. Suppose c̄ ∈ P(ω)^{3}. If there exists a 3-localizer for c̄, then c̄ is a minimal 3-witness, and letting b⃗(c̄(2)) = ⟨b_{ν} | ν < ξ⟩ it holds for each ν < ξ that Seq (dc(b_{ν})) ↾ 3 is a minimal 3-witness.

Proof. Suppose c is a 3-localizer for c̄. Let N̄ be a countable elementary submodel of L_{ω_{2}}[c, c̄, a⃗_{ω}] with {ω_{1}, c, c̄, a⃗_{ω}} ⊆ N̄ and let N be the transitive collapse of N̄. Then N is suitable, and so by (∗)_{4} the following holds in N: There is a transitive model M of ZF^{−} such that M ⊨ Φ_{is}(c_{≺}), {(ω_{1})^{N}, c̄, a⃗_{ω}} ⊆ M, and

(a) M ⊨“c̄ is a minimal 3-witness”.

(b) Writing b⃗(c̄(2))^{M} as ⟨b_{ν} : ν < ξ⟩, for each ν < ξ, M ⊩“c̄_{ν}^{∗} ↾ 3 is a minimal 3-witness”, where c̄_{ν}^{∗} = Seq (dc(b_{ν})).

Saturday 8th August, 2020 (09:59)

By elementarity, there exists such a model M in L_{ω_{2}}[c, c̄, a⃗_{ω}] with all of the above properties, where (ω_{1})^{N} is replaced by ω_{1}. Since ω_{1} ∈ M and M ⊨ ZF^{−} ∧ Φ_{is}(c_{≺}), by Lemma 4.14 the property of being a minimal 3-witness is absolute for M. Hence c̄ and each c̄_{ν}^{∗} ↾ 3 for ν < ξ are a minimal 3-witnesses, finishing the proof. □

Thus we have shown, roughly, that c̄ is a minimal 3-witness coding a coherent candidate consisting of minimal 3-witnesses if and only if there exists a 3-localizer for c̄. Of course, there may be more than one 3-localizer for a given minimal 3-witness.

Definition 4.19. We say c̄ ∈ P(ω)^{4} is a minimal 4-witness if and only if c̄(3) is the ≺-least localizer for c̄ ↾ 3.

We now continue the definition of k-localizer and minimal k + 1-witness for elements of P(ω)^{k} by induction on k, following the template given by the definition for k = 3.

Definition 4.20. Let k ∈ ω \ 4 and suppose we have already defined what it means to be a minimal k-witness for elements of P(ω)^{k}. Given c̄ ∈ P(ω)^{k} (a putative k-witness) we say c ∈ P(ω) is is a k-localizer for c̄ if and only if the following holds:

(∗)_{k} For any suitable model N with {c̄, c, a⃗_{ω}} ⊆ N, the following holds in N: There is a transitive model M of ZF^{−} such that M ⊨ Φ_{is}(c_{≺}), {ω_{1}, c̄, a⃗_{ω}} ⊆ M, and

(a) M ⊨“c̄ is a minimal k-witness”,

(b) Writing b⃗(c̄(2))^{M} as ⟨b_{ν} : ν < ξ⟩, for each ν < ξ it holds that M ⊨“c̄_{ν} ↾ k is a minimal k-witness”, where c̄_{ν} = Seq (dc(b_{ν})).

Moreover, we say c̄ ∈ P(ω)^{k+1} is a minimal (k + 1)-witness if and only if c̄(k) is the ≺-least k-localizer for c̄ ↾ k.

Finally, we say c̄ ∈ P(ω)^{ω} is a minimal local witness if and only if

(∗∗)  for each k ∈ ω \ 3, c̄(k) is a k-localizer for c̄ ↾ k

and we say c ∈ P(ω) is a minimal local witness if and only if Seq (c) is a minimal local witness.

Given arbitrary c̄ ∈ P(ω)^{≤ω} let us say c̄ codes b⃗ if c̄(2) almost disjointly via F codes the sequence b⃗. In this case let us also write b⃗(c̄) for b⃗. We shall also say c̄ is a witness to b⃗ to mean that c̄ is a lh(c̄)-witness or, if lh(c̄) = ω, a minimal local witness, and b⃗(c̄) = b⃗.

Just as before for k = 3 we have the following crucial lemma:

Lemma 4.21. Suppose k ∈ ω \ 4 and c̄ ∈ P(ω)^{k}. There exists a k-localizer for c̄ if and only if c̄ is a minimal k-witness, and letting b⃗(c̄(2)) = ⟨b_{ν} | ν < ξ⟩ it holds for each ν < ξ that Seq (dc(b_{ν})) ↾ k is a minimal k-witness.

Proof. This is shown precisely as Lemmas 4.18 and 4.17 above. □

In the next lemma, we verify for the reader’s convenience that the minimal local witness to a sequence is uniquely determined by this sequence.

Lemma 4.22. For each sequence b⃗ = ⟨b_{ξ} : ξ < ν⟩, there is at most one minimal local witness c̄ ∈ P(ω)^{ω} coding b⃗. Likewise, if two sequences c̄ and c̄′ are minimal local witnesses and c̄(2) = c̄′(2), then c̄ = c̄′.

Saturday 8th August, 2020 (09:59)

Proof. Suppose c̄ and c̄′ are minimal local witnesses coding b⃗. Since c̄(3) is a 3-localizer to c̄ ↾ 3, by Lemma 4.18 the latter is a minimal 3-witness to b⃗. The same holds for c̄′. But obviously, there is only one minimal 3-witness to b⃗, so c̄ ↾ 3 = c̄′ ↾ 3. But since c̄(4) is a 4-localizer for c̄ ↾ 4, c̄(3) is the ≺-least 3-localizer by Lemma 4.21. Since the same holds for c̄′(4) we have c̄(3) = c̄′(3). Continue by induction to obtain c̄ = c̄′. The second statement follows, since if c̄(2) = c̄′(2), also b⃗(c̄) = b⃗(c̄′). □

We are now ready to begin the proof.

Proof of Theorems 1.3 and 4.1. As we have stated earlier, we shall inductively construct a sequence ⟨a_{ν} : ν < ω_{2}⟩ such that A = {a_{ν} : ν < ω_{2}} will be a Π_{2}^{1} MAD family. For the first ω elements of ⟨a_{ν} : ν < ω_{2}⟩ take the sequence a⃗_{ω} = ⟨a_{k} : k ∈ ω⟩ fixed in 4.4 (since our coding functions cd and dc use a⃗_{ω}). Fix c_{A} ∈ P(ω) from which both a⃗_{ω} and c_{≺} are computable; in the end A will be Π_{2}^{1}(c_{A}).

Suppose we have already constructed ⟨a_{ν} : ν < ξ⟩ (where ω ≤ ξ < ω_{2}) and assume as induction hypothesis that for each ν < ξ, letting c_{ν} = dc(a_{ν}) and c̄_{ν} = Seq (c_{ν}) we have that a_{ν} = cd(c̄_{ν}(0), c̄_{ν}(1), c_{ν}) and c̄_{ν} (or equivalently, c_{ν}) is a minimal local witness. Also, let us write d_{ν} = c̄_{ν}(0).

Write A_{ξ} = {a_{ν} : ν < ξ}. We will now define a_{ξ}. First find d_{ξ} such that

(5) d_{ξ} is the ≺-least element of [ω]^{ω} which is almost disjoint from every element of A_{ξ}.

Such d_{ξ} exists since BPFA implies that there is no MAD family of size less than ω_{2}.

We now find a minimal local witness c̄_{ξ} ∈ P(ω)^{ω} to ⟨a_{ν} : ν < ξ⟩ (see Definition 4.13). • Of course, we let c̄_{ξ}(0) = d_{ξ}.

• By Fact 3.1 (see also Remark 4.6) there exists c ∈ [ω]^{ω} satisfying the requirement from Fact 4.5 that {ν < ξ : |c ∩ a_{ν}| < ω} = ξ \ ω. We let c̄_{ξ}(1) be the ≺-least such c.

• Also by Fact 3.1, there exists a subset of ω which almost disjointly via F codes

⟨a_{ν} : ν < ξ⟩; let c̄_{ξ}(2) be the ≺-least such subset. By construction c̄_{ξ} ↾ 3 is a minimal 3-witness. Let c̄_{ξ}(3) be the ≺-least 3-localizer for c̄_{ξ} ↾ 3, which exists by Lemma 4.18. Continue defining c̄_{ξ} ↾ k + 1 by recursion on k for k > 3, letting c̄_{ξ}(k) be the ≺-least k-localizer for c̄_{ξ} ↾ k, using Lemma 4.21, arriving at a minimal local witness c̄_{ξ} to ⟨a_{ν} : ν < ξ⟩ with c̄_{ξ}(0) = d_{ξ}.

Finally, we write c_{ξ} for the element of P(ω) such that Seq (c_{ξ}) = c̄_{ξ} and define

a_{ξ} = cd(c̄_{ξ}(0), c̄_{ξ}(1), c_{ξ}),

finishing the recursive definition of ⟨a_{ξ} : ξ < ω_{2}⟩. Write A = {a_{ξ} : ξ < ω_{2}}. Clearly, by choice of c_{ξ}(0) = d_{ξ} and c̄_{ξ}(1) and by the properties of the function cd from Fact 4.5, this is an almost disjoint family.

It is not hard see that A is maximal. We first point out the following simple observation:

Claim 4.23. Whenever ν < ξ < ω_{2}, d_{ν} ≺ d_{ξ}.

Proof. This is clear by the definition: Suppose otherwise that d_{ξ} ⪯ d_{ν}. Since A_{ν} ⊆ A_{ξ}, d_{ξ} is almost disjoint from every set in A_{ν}. So by minimality of d_{ν}, we infer d_{ν} = d_{ξ}. But then since d_{ν} ∩ a_{ν} is infinite by the properties of the function cd from Fact 4.5,

Saturday 8th August, 2020 (09:59)

d_{ξ} is not almost disjoint from every element of A_{ξ}, contradicting how d_{ξ} was chosen.

Claim 4.23. □

Claim 4.24. The set A is a maximal almost disjoint family.

Proof. Suppose towards a contradiction that d ∈ [ω]^{ω}\A and A∪{d} is an almost disjoint family. Let ξ < ω_{2} be the least ordinal such that d ⪯ d_{ξ}; such an ordinal exists since ≺ well-orders the reals in ordertype ω_{2} and so the sequence ⟨d_{ξ} : ξ < ω_{2}⟩ is ≺-cofinal in P(ω). But since at stage ξ in the construction of A, d_{ξ} was chosen to be the least element almost disjoint from every element of {a_{ν} : ν < ξ}, we have d = d_{ξ}. Then since a_{ξ} = cd(c̄_{ξ}(0), c̄_{ξ}(1), c̄_{ξ}) and c̄_{ξ}(0) = d_{ξ} = d, a_{ξ} ∩ d is infinite by the properties of the function cd from Fact 4.5, contradiction. Claim 4.24. □

We now show that A is Π_{2}^{1}(c_{A}). We first show:

Claim 4.25. There is a Π_{2}^{1}(c_{A}) formula Θ(x) such that Θ(c̄) holds if and only if c̄ is a minimal local witness.

Proof. It is easily seen that for each k ∈ ω \ 3 the set

{(c, c′) ∈ P(ω) × P(ω)^{k} : c is a k-localizer for c′}

is definable by a Π_{2}^{1}(c_{A}) formula Θ_{k}(x, y), namely, the formula obtained by expressing (∗)_{k} in the language of set theory. In fact, ⟨Θ_{k}(x, y) : k ∈ ω⟩ is a recursive sequence of formulas, and so using a universal definable Π_{2}^{1} truth predicate we can find a Π_{2}^{1}(c_{A}) formula Θ(c̄) equivalent to

(∀k ∈ ω) Θ_{k}(c̄(k + 3), c̄ ↾ (k + 3)).  □

Let now Ψ(a) be defined as follows:

Ψ(a) ⟺^{def} [(∃n ∈ ω) a = a_{n}]∨

(∀c ∈ (P(ω)) [c = dc(a) ⇒ (a = cd ((c)_{0}, (c)_{1}, c) ∧ Θ( Seq (c) ))].

Clearly this formula is Π_{2}^{1}(c_{A}). We will show that Ψ(a) ⟺ a ∈ A. The non-trivial direction is “⇒,” which we show first.

Lemma 4.26. (∀a ∈ [ω]^{ω}) Ψ(a) ⇒ a ∈ A.

Proof. Suppose Ψ(a) and to avoid trivialities let us suppose a ∉ {a_{n} | n ∈ ω}. Then c̄ = Seq (dc(a)) is a minimal local witness and so b⃗(c̄) is defined, namely as the unique sequence coded by c̄(2) as in (∗)_{3}(a). Let us write b⃗(c̄) = ⟨b_{ξ} : ξ < α⟩. We need the following claim:

Claim 4.27. The sequence b⃗(c̄) = ⟨b_{ξ} : ξ < α⟩ is an initial segment of ⟨a_{ν} : ν < ω_{2}⟩.

Proof. Suppose not. Let ν < α be least such that b_{ν} ≠ a_{ν}. Write c_{ν}^{∗} = dc(b_{ν}) and c̄_{ν}^{∗} = Seq (c_{ν}^{∗}). Since c̄ is a minimal local witness, b⃗(c̄) is a coherent candidate, and so (c_{ν}^{∗})_{2} codes almost disjointly via F the sequence b⃗(c̄) ↾ ν, which by assumption is ⟨a_{ξ} : ξ < ν⟩.

We verify that c̄_{ν}^{∗}, too, is a minimal local witness: Firstly, c̄(3) is a 3-localizer for c̄↾ 3. Then by (b) in (∗)_{4} and by Lemma 4.18 it holds that c̄_{ν}^{∗} ↾ 3 is a minimal 3-witness. More generally, since c̄(k) is a k-localizer for c ↾ k, by (b) in (∗)_{k} we see that c̄_{ν}^{∗} ↾ k is a

Saturday 8th August, 2020 (09:59)

minimal k-witness (cf. Lemma 4.21). Since this holds for each k ∈ ω, c̄_{ν}^{∗} is a minimal local witness.

But then since c̄_{ν}^{∗} and c̄_{ν} are both minimal local witnesses for the sequence ⟨a_{ξ} : ξ < ν⟩, we must have c̄_{ν}^{∗} = c̄_{ν} by the definition of minimal local witness (see also Lemma 4.22). It follows that a_{ν} = cd(c̄_{ν}(0), c̄_{ν}(1), c_{ν}) = cd(c̄_{ν}^{∗}(0), c̄_{ν}^{∗}(1), c_{ν}^{∗}) = b_{ν}, contradicting the choice of ν. Claim 4.25. □

By the claim we can fix ν < ω_{2} such that b⃗(c̄) = ⟨a_{ξ} : ξ < ν⟩. By the same argument as in the previous paragraph, a = a_{ν}. Lemma 4.26. □

Finally, for any ξ such that ω ≤ ξ < ω_{2} it is clear by construction that a_{ξ} = cd(c̄_{ξ}) and c̄_{ξ} is a minimal local witness. Therefore Ψ(a_{ξ}) holds. So a ∈ A ⇒ Ψ(a).

Theorems 1.3 & 4.1. □

5. Infinite MAD families, sharps, and Bounded Martin’s Maximum

In this section, we proove Theorem 1.4, i.e., that under ZFC + BMM there are no infinite Σ_{3}^{1} MAD families. In fact, we show the following:

Theorem 5.1. Suppose for every a ∈ P(ω), a^{♯} exists. Then there are no infinite Σ_{3}^{1} families.

Proof. Under the assumption of the theorem, any Σ_{3}^{1}(a) set, where a ∈ P(ω), is equal to p[T] for some tree T on ω × κ (for some ordinal κ); in fact one can take T ∈ L[a^{♯}] (this is implicit in [13]; see [11, pp. 198–204] for a proof, where the result is credited to Martin). Since also (a^{♯})^{♯} exists, P(P(ω))^{L[a^{♯}]} is countable. Now let us suppose that p[T], for some such tree T, is an infinite almost disjoint family. Following [2] we show that p[T] cannot be maximal: For let r be generic over L[a^{♯}] for Mathias forcing relative to the ideal generated by p[T], as computed in L[a^{♯}]; then r is almost disjoint from any element of p[T] by [2, Main Proposition 3.6]. □

Theorem 1.4 follows by a result of Schindler:

Proof of Theorem 1.4. As Schindler showed in [23, Theorem 1.3], BMM implies that every set has a sharp. Now use the previous theorem. □

6. Questions

Question 6.1. Can BPFA be replaced by the Bounded Forcing Axiom for Axiom A in Theorem 1.3?

Question 6.2. Can we assume a forcing axiom stronger than BPFA but still compatible with an appropriate, weaker anti-large cardinal assumption and derive a form of Theorem 1.3?

References

[1] Joan Bagaria, Bounded forcing axioms as principles of generic absoluteness, Arch. Math. Logic 39 (2000), no. 6, 393–401. MR 1773776

[2] K. Bakke Haga, D. Schrittesser, and A. Törnquist, Mad families, determinacy, and forcing,

    arXiv:1810.03016[math.LO], October 2018.

[3] Tomek Bartoszyński and Haim Judah, Set theory - on the structure of the real line, A K Peters, Ltd., Wellesley, MA, 1995. MR 1350295

Saturday 8th August, 2020 (09:59)

[4] Andrés Eduardo Caicedo and Sy-David Friedman, BPFA and projective well-orderings of the reals, J. Symbolic Logic 76 (2011), no. 4, 1126–1136. MR 2895389

[5] Andrés Eduardo Caicedo and Boban Veličković, The Bounded Proper Forcing Axiom and well orderings of the reals, Math. Res. Lett. 13 (2006), no. 2-3, 393–408. MR 2231126

[6] Vera Fischer, Sy Friedman, David Schrittesser, and Asger Törnquist, Good projective witnesses, preprint, 2018.

[7] Martin Goldstern and Saharon Shelah, The Bounded Proper Forcing Axiom, J. Symbolic Logic 60 (1995), no. 1, 58–73. MR 1324501

[8] Leo Harrington and Saharon Shelah, Some exact equiconsistency results in set theory, Notre Dame J. Formal Logic 26 (1985), no. 2, 178–188. MR 783595

[9] Haim Horowitz and Saharon Shelah, Can you take Törnquist’s inaccessible away?,

arXiv:1605.02419[math.LO], May 2016.

[10] R. B. Jensen and R. M. Solovay, Some applications of almost disjoint sets, Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968), North-Holland, Amsterdam, 1970, pp. 84–104. MR 0289291

[11] Akihiro Kanamori, The higher infinite, second ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2009, Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition. MR 2731169

[12] K. Kunen, Set theory. an introduction to independence proofs, North Holland, 1980.

[13] D. A. Martin and R. M. Solovay, A basis theorem for Σ_{3}^{1} sets of reals, Ann. of Math. (2) 89 (1969), 138–159. MR 255391

[14] , Internal Cohen extensions, Ann. Math. Logic 2 (1970), no. 2, 143–178. MR 270904

[15] A. R. D. Mathias, On a generalization of Ramsey’s Theorem, Research Fellowship, Peterhouse, Cambridge 1969 and Ph.D. thesis Cambridge, 1970, available at the author’s website.

[16] , Happy families, Ann. Math. Logic 12 (1977), no. 1, 59–111. MR 0491197

[17] Arnold W. Miller, Infinite combinatorics and definability, Ann. Pure Appl. Logic 41 (1989), no. 2, 179–203. MR 983001

[18] Justin Tatch Moore, Set mapping reflection, J. Math. Log. 5 (2005), no. 1, 87–97. MR 2151584 [19] Itay Neeman and Zach Norwood, Happy and mad families in L(ℝ), J. Symb. Log. 83 (2018), no. 2,

572–597. MR 3835078

[20] Ralf-Dieter Schindler, Proper forcing and remarkable cardinals, Bull. Symbolic Logic 6 (2000), no. 2, 176–184. MR 1765054

[21] , Proper forcing and remarkable cardinals. II, J. Symbolic Logic 66 (2001), no. 3, 1481–1492. MR 1856755

[22] , Forcing axioms and projective sets of reals, Classical and new paradigms of computation and their complexity hierarchies, Trends Log. Stud. Log. Libr., vol. 23, Kluwer Acad. Publ., Dordrecht, 2004, pp. 207–222. MR 2156740

[23] , Semi-proper forcing, remarkable cardinals, and bounded Martin’s maximum, MLQ Math. Log. Q. 50 (2004), no. 6, 527–532. MR 2096166

[24] , Bounded Martin’s maximum and strong cardinals, Set theory, Trends Math., Birkhäuser, Basel, 2006, pp. 401–406. MR 2267158

[25] David Schrittesser and Asger Törnquist, The Ramsey property implies no mad families, Proc. Natl. Acad. Sci. USA 116 (2019), no. 38, 18883–18887. MR 4012549

[26] John R. Steel, PFA implies AD^{L(ℝ)}, J. Symbolic Logic 70 (2005), no. 4, 1255–1296. MR 2194247 [27] Asger Törnquist, Σ_{2}^{1} and Π_{1}^{1} mad families, J. Symbolic Logic 78 (2013), no. 4, 1181–1182.

MR 3156517

[28] , Definability and almost disjoint families, Adv. Math. 330 (2018), 61–73. MR 3787540 [29] Zoltán Vidnyánszky, Transfinite inductions producing coanalytic sets, Fund. Math. 224 (2014), no. 2,

155–174. MR 3180585

Saturday 8th August, 2020 (09:59)

Vera Fischer, Institut für Mathematik, UZA 1, Universität Wien. Augasse 2–6, 1090 Vienna, Austria

Email address: vera.fischer@univie.ac.at

David Schrittesser, Institut für Mathematik, UZA 1, Universität Wien. Augasse 2–6, 1090 Vienna, Austria

Email address: david@logic.univie.ac.at

Thilo Weinert, Department of Mathematics National University of Singapore Blk S17 Level 4 10 Lower Kent Ridge Road 119076 Singapore

Email address: thilo.weinert@univie.ac.at