m522
⚠️EXPERIMENTAL WORK IN PROGRESS⚠️

Suppose towards a contradiction that the set of all real numbers is countable. Then there exists a sequence $(a_n)_{n\in\NN}$ such that $\RR=\set{a_n\mid n\in\NN}$. Our strategy will be to inductively construct a decreasing sequence of closed intervals $I_n=[l_n,r_r]$ such that for all $n$, $a_n\notin I_n$. Then if $r$ lies in the intersection of these intervals, $r$ cannot be equal to $a_n$ for any $n$, a contradiction.

The construction itself is straightforward. For the base case let $I_1=[l_1,r_1]$ be any interval which omits $a_1$. For the inductive step, if $I_{n-1}$ has been defined, let $I_n=[l_n,r_n]$ be any subinterval of $I_{n-1}$ which omits $a_n$.

We can now find a point in the intersection of the $I_n$ using the completeness property. First observe that since $I_n\subset I_{n-1}$ for all $n$, the set of left endpoints $\set{l_n\mid n\in\NN}$ is bounded above by any and all of the right endpoints $r_n$. By the completeness property, the set of left endpoints has a least upper bound $x$. Since $x$ is an upper bound for $\set{l_n\mid n\in\NN}$, we have $l_n\leq x$ for all $n$. Since $x$ is the least possible upper bound for $\set{l_n\mid n\in\NN}$, we have $x\leq r_n$ for all $n$. Therefore we have $x\in[l_n,r_n]=I_n$ for all $n$.

Since $x$ lies in $I_n$ for all $n$, and since we chose $I_n$ in such a way that it omits $a_n$, we know that $x\neq a_n$ for all $n$. This contradicts the hypothesis that $\RR=\set{a_n\mid n\in\NN}$, and concludes the proof.

First compute that the sum of the lengths of all of those middle thirds removed in the construction of the cantor set is exactly $1$ (). It follows from this that $C$ does not contain any positive-length intervals. Now if $I$ is any positive-length interval, then $I$ must contain a point $x\notin C$. Now note that $C$ is closed because it is an intersection of closed sets, and hence $\RR\smallsetminus C$ is open. Thus there is an open interval $J$ centered at $x$ such that $J\subset\RR\smallsetminus C$. Shrinking the radius of $J$ if necessary, we can suppose that $J\subset I$. This shows that $C$ is nowhere dense.

Preservation to subsets is immediate from the definition.

For preservation to unions, suppose that $A,B$ are nowhere dense and let $I$ be a positive-length interval. Since $A$ is nowhere dense, there is a positive-length interval $J\subset I\smallsetminus A$. Since $B$ is nowhere dense there is a further positive-length interval $J'\subset J\smallsetminus B$. It follows that

This establishes that $A\cup B$ is again nowhere dense.

Preservation to closures is immediate from condition (b) of , but we can also give a direct argument. Let $A$ be nowhere dense and let $I$ be a given positive-length interval. Since $A$ is nowhere dense there is a positive-length interval $J$ such that $J\subset\RR\smallsetminus A$. Removing endpoints if necessary, we may suppose that $J$ is open. It follows that $J\subset\RR\smallsetminus\cl(A)$ (recall that since $\cl(A)$ is the intersection of all closed sets containing $A$, we have that $\RR\smallsetminus\cl(A)$ is the union of all open sets disjoint from $A$). This shows that $\cl(A)$ is nowhere dense.

The proof is very similar to Cantor's proof of . Let $I$ be a positive-length interval and suppose towards a contradiction that $I$ is meager. Then there exists a sequence $(A_n)_{n\in\NN}$ of nowhere dense sets such that $\bigcup A_n=I$. We will inductively construct a decreasing sequence of closed subintervals $J_n\subset I$ such that for all $n$, $J_n\cap N_n=\emptyset$.

The induction is again straightforward. First apply the definition of $A_1$ being nowhere dense to obtain $J_1$. Inductively apply the definition of $A_n$ being nowhere dense to $J_n$ to obtain $J_{n+1}$. (Each time we may shrink the newly obtained interval slightly to suppose that it is closed.)

We can now argue just as in the proof of that there exists a point $x\in\bigcap J_n$. It follows that $x\notin\bigcup A_n$, which contradicts the assumption that $I=\bigcup A_n$, and completes the proof.

For condition (a), let $I$ be an interval. It is clear that $m(I)\leq\ell(I)$, since $I$ itself is an interval covering $I$. For the other direction, we will show that $I\subset\bigcup I_n$ implies $\sum\ell(I_n)\geq\ell(I)$. Then taking the infemum over all such coverings this allows us to conclude that $m(I)\geq\ell(I)$.

Let us first handle the case when $I=[a,b]$ is closed and bounded, and all of the $I_n$ are open intervals $(a_n,b_n)$. Then since $I$ is compact, $I$ is covered by just finitely many of the $I_n$, without loss of generality we may assume they are indexed $I_0,\ldots,I_N$. Now after further renaming or removing intervals from the list, we may suppose that $I_0$ covers the left endpoint of $I$, each $I_{n+1}$ covers the right endpoint of $I_n$, and $I_N$ covers the right endpoint of $I$. We can now compute that

If $I$ is not necessarily closed and the $I_n$ are not necessarily open, then we look instead at $I'=\cl(I)$ and $I_n'=(I_n)^\circ$. Then the $I_n'$ cover all but a countable subset of $I'$, so for any $\epsilon$ we can find additional open intervals $J_n$ with $\ell(J_n)\leq\epsilon/2^n$ covering these missing points. Now the previous argument shows that $\sum\ell(I_n)+\sum\ell(J_n)\geq\ell(I)$. Using the geometric series formula we obtain $\sum\ell(I_n)+\epsilon\geq\ell(I)$. Letting $\epsilon\to0$ we have the desired result.

Finally if $I$ is not bounded, we let $A_k$ be a sequence of bounded subintervals of $I$ such that $\ell(A_k)\to\infty$. The above result implies that $\sum\ell(I_n)\geq\ell(A_k)$, and letting $k\to\infty$ we once again achieve the desired result. This concludes the proof of condition (a).

Condition (b) follows directly from the fact that the length function $\ell$ is translation invariant, and the definition of $m$ depends only on $\ell$.

For the proof that $m$ satisfies condition (c), we refer the reader to any standard measure theory text.

It is clear that $|A|\leq|\mathcal P(A)|$, since the map $i(a)=\{a\}$ is an injection from $A$ into $\mathcal P(A)$.

To see that there is no bijection between $A$ and $\mathcal P(A)$, let $f\colon A\to\mathcal P(A)$ be any function. Then build the set $D$ of all elements $a\in A$ such that $a\notin f(a)$. We claim that $D$ is not in the range of $f$, and therefore that $f$ is not a bijection.

To see this, suppose towards a contradiction that there exists $a_0\in A$ such that $D=f(a_0)$. Then by the definition of $D$, we have that $a_0\in D$ iff $a_0\notin f(a_0)$. And since $D=f(a_0)$ we can write this as $a_0\in D$ iff $a_0\notin D$, which is a clear contradiction.

Replacing $B$ with $j(B)$, we may suppose that that $B\subset A$. Then we have

Now $A$ can be written as the union of the successive differences of these sets, together with the intersection of them all:

Meanwhile, $i$ gives bijections

It follows that the map

is a bijection from $A$ to $B$.

Consider the family $\mathcal F$ of all injective functions whose domain is a subset of $A$ and whose range is a subset of $B$. Then $\mathcal F$ is partially ordered by extension of functions, and it is easy to check that this ordering satisfies the hypothesis of Zorn's lemma. Thus there is a maximal element $f$, and since it is maximal either the domain of $f$ is all of $A$ or the range of $f$ is all of $B$. In the first case $f$ is an injection from $A$ to $B$, and in the second case $f^{-1}$ is an injection from $B$ to $A$.

We argue very similarly to , but in order to apply Zorn's lemma we must first suppose that $\mathcal A$ really is a set. Fix any element $A\in\mathcal A$ and let

This time $\mathcal F$ is partially ordered by coordinatewise extension of functions. By Zorn's lemma there is a maximal element $(f_B)_{B\in\mathcal A}$, and since it is maximal either the domain $A_0$ is all of $A$ or the range of one of the functions $f_B$ is all of $B$. In the first case $f_B$ is an injection from $A$ to $B$ for all $B$. In the second case, fix $B$ such that $f_B(A_0)=B$. Then for any $C\in\mathcal A$, the composition $f_C\circ f_B^{-1}$ is an injection from $B$ to $C$, so $B$ is as desired.

In the general case when $\mathcal A$ is a class, we can reduce to the set case as follows. Fix an element $D\in\mathcal A$ and let $\mathcal A'$ denote the collection of subsets of $D$ that are in bijection with some element of $\mathcal A$. Since $\mathcal A'$ is a set, we can find $A\in\mathcal A$ which injects into all elements of $\mathcal A'$. It follows that $A$ injects into all other elements of $\mathcal A$ too. Indeed if $B\in\mathcal A$ and $A$ does not inject into $B$, then by , $B$ injects into $A$. It follows that $B$ is in bijection with a subset of $D$ and hence $A$ injects into $B$ after all.

It is easy to check $\alpha=\beta\cup\{\beta\}$ is indeed an ordinal (it is transitive and well-ordered by $\in$). Since the ordinals are well-ordered we may let $\alpha'$ be the least ordinal greater than $\beta$; we want to show that $\alpha=\alpha'$. If this were not the case, then by totality we would either have $\alpha'\in\alpha$ or $\alpha\in\alpha'$. In the first case either $\alpha=\beta$ or $\alpha\in\beta$, which contradicts that $\alpha'$ is greater than $\beta$. The second case contradicts that $\alpha'$ is the least such.

Next let $\alpha$ be a limit ordinal, and let $\alpha'$ be the union of all $\beta\in\alpha$. Since $\alpha$ is transitive we easily have that $\alpha'\subset\alpha$. On the other hand if $\gamma\in\alpha$ then by the previous paragraph $\gamma+1\leq\alpha$ and since $\alpha$ is limit we must have $\gamma+1\in\alpha$. Thus $\gamma\in\gamma+1\in\alpha$ and it follows that $\gamma\in\alpha'$.

We give the proof in the case of the Cantor space, and a brief hint in the case of the Baire space.

The Cantor middle thirds set $C$ has a natural description in terms of ternary expansions. If $a\in[0,1]$ then $a$ lies in the Cantor set if and only if it has a ternary expansion that does not contain the digit $1$. Thus there is a simple bijection $2^\omega\to C$ given by replacing the $1$'s in $x$ with $2$'s:

The map is continuous: if $f(x)\in(a,b)$ then there exists $n$ such that if we round $f(x)$ down at its $n$th digit then it is still $\gt a$ and if we round it up at its $n$th digit then it is still $\lt b$. It follows that if $s=x\restriction n$, then we have $f(V_s)\gt a$. Finally recall that a continuous bijection between compact spaces is always ahomeomorphism.

For the Baire space, it is common to use the values of $x\in(\omega\smallsetminus\{0\})^\omega$ as the entries in a continued fraction:

With some elementary number theory, it is possible to verify that this map is a bijection onto the set of irrational numbers, and even a homeomorphism.

Let $x_i$ be a Cauchy sequence in $A^\omega$. We can inductively construct an increasing sequence of indices $i_0,i_1,\ldots$ such that for all $n$ and $i\geq i_n$ we have $d(x_i,x_{i_n})\lt 1/n$. In other words for $i\geq i_0$ the $x_i(0)$ all agree, for $i\geq i_1$ the $x_i(1)$ all agree, etc. Thus we may define an element $x$ by letting $x(i)=$ this agreed upon value. Now it is easy to check that $x_i\to x$.

Given any set $B\subset A^\omega$, we let $T_B$ be the tree consisting of all $s$ such that $V_s\cap B\neq\emptyset$ (that is, all initial segments of elements of $B$). We will show that the set $[T_B]$ of all branches through the tree $T_B$ is precisely the closure of $B$, which implies the desired result. For this, note that $x$ lies in the closure of $B$ if and only if every open neighborhood of of $x$ meets $B$. This is equivalent to the statement that for every initial segment $s\subset x$, $V_s\cap B\neq\emptyset$. Finally, this is equivalent to the statement that $x$ is a branch through $T_B$.

We will use the fact that a countable product of finite metric is compact (this follows from Tychonoff's theorem, but it's easy to check directly too). Since a closed subspace of a compact metric space is again compact, it follows that any closed subset of a product $\prod_{n\in\omega}\{0,\ldots,K_n\}$ is compact. For the converse suppose that $A\subset\omega^\omega$ is compact, and suppose towards a contradiction that $A$ is not contained in a product of bounded intervals. Then there exists some coordinate $n$ such that $A$ contains a sequence of elements $f_i$ with $f_i(n)\to\infty$. Then $f_i$ clearly does not have any convergent subsequence, contradicting that $A$ was compact.

It is clear that $\aleph_1\leq\non(\Ksigma)$ because every countable set is $\Ksigma$, being the union of its points. To see that $\non(\Ksigma)\leq\mathfrak c$ it is enough to show that $\omega^\omega$ itself is not $\sigma$-compact. So suppose towards a contradiction that $\omega^\omega=\bigcup A_n$ where each $A_n$ is compact. Then by the Baire category theorem, at least one of the $A_n$ must have a nonempty interior, say $V_s\subset A_n$. But $V_s$ is not contained in a product of bounded intervals, so by this contradicts that $A_n$ is compact.

To show that $\aleph_1\leq\cov(\Ksigma)$, suppose a countable family of $\sigma$-compact sets covered all of $\omega^\omega$. Then a countable family of compact sets would also cover all of $\omega^\omega$, again contradicting that $\omega^\omega$ is not $\sigma$-compact. Finally it is clear that $\cov(\Ksigma)\leq\mathfrak c$, since the whole space $\omega^\omega$ is the union of its points and $|\omega^\omega|=\mathfrak c$.

We begin by showing that $\mathfrak{b}$ is uncountable. For this, it is enough to show that every countable family $\mathcal F\subset\omega^\omega$ is bounded by some $h\in\omega^\omega$. So let $\mathcal F\subset\omega^\omega$ be a countable family and enumerate its elements $f_0,f_1,\ldots$. To construct the bound $h$, we use a diagonalization process similar to the proof of Cantor's theorem. More specifically, we define $h(n)$ so that it dominates $f_0(n),\ldots,f_n(n)$:

Then for each $i$ we have $f_i(n)\leq h(n)$ for all $n\geq i$, and therefore $f_i\leq^*h$, as desired.

To show that $\mathfrak{b}\leq\mathfrak{d}$, it is enough to show that every dominating family is unbounded. Let us establish the contrapositive: if $\mathcal F$ is bounded, say by $h\in\omega^\omega$, then every $f\in\mathcal F$ satisfies $f\leq^*h$. Letting $h'(n)=h(n+1)$, it follows that every $f\in\mathcal F$ satisfies $h'\not\leq^*f$, and hence that $\mathcal F$ is not a dominating family.

Finally, $\mathfrak d\leq\mathfrak c$ since $\mathcal F=\omega^\omega$ is itself a dominating family, and $|\omega^\omega|=\mathfrak c$.

Let us say that a family $\mathcal F\subset\omega^\omega$ is $\leq$-bounded if there is an $h\in\omega^\omega$ such that $f\leq h$ for all $f\in\mathcal F$, and that $\mathcal F$ is $\leq^*$-bounded if there is an $h\in\omega^\omega$ such that $f\leq^*h$ for all $f\in\mathcal F$. Then it is clear from that a family $\mathcal F$ is $\leq$-bounded if and only if $\mathcal F$ is contained in a compact set. To establish the first equality in the theorem, it suffices to show that a family $\mathcal F$ is $\leq^*$-bounded if and only if $\mathcal F$ is contained in a $\sigma$-compact set.

For this, suppose that $\mathcal F$ is $\leq^*$-bounded by $h\in\omega^\omega$. Let $h_i$ enumerate all finite modifications of $h$, so that for all $f\in\mathcal F$ there is some $i$ such that $f\leq h_i$. It follows that $\mathcal F$ is contained in the $\sigma$-compact set of functions that are $\leq$-bounded by some $h_i$. Conversely, suppose that $\mathcal F\subset\bigcup A_i$, where each $A_i$ is compact. Then for each $i$ there exists some $h_i\in\omega^\omega$ such that $A_i$ is $\leq$-bounded by $h_i$. Since $\aleph_1\leq\mathfrak b$, there exists $h$ such that $h_i\leq^*h$ for all $i$. It follows that $\mathcal F$ is $\leq^*$-bounded by $h$.

The second equality is similar. If $\mathcal F$ is a dominating family then consider the collection of all $A_f=\set{g\mid g\leq f}$ for $f$ a finite modification of an element of $\mathcal F$. This latter collection is a family of compact sets that covers all of $\omega^\omega$. Conversely if $\mathcal F$ is a family of compact subsets of $\omega^\omega$ that covers all of $\omega^\omega$, then each $F\in\mathcal F$ is $\leq$-bounded by some $h_F\in\omega^\omega$. It follows that the collection of all $h_F$ is a dominating family.

The additivity of $\mathcal I$ is uncountable simply because $\mathcal I$ is a $\sigma$-ideal. In the next lemma we will show that if $\mathcal I$ is a proper $\sigma$-ideal containing the singletons, then the additivity of $\mathcal I$ is a lower bound for all four cardinal characteristics of $\mathcal I$, and hence all four are uncountable.

Next, it is easy to verify that for any proper $\sigma$-ideal $\mathcal I$ containing the singletons, the additivity, uniformity, and covering number of $\mathcal I$ are bounded above by $\mathfrak c$. If additionally $\mathcal I$ has a basis consisting of Borel sets, then since there are only $\mathfrak c$ many Borel sets, we have that the cofinality of $\mathcal I$ is bounded above by $\mathfrak c$ too.

For the inequality $\add(\mathcal{I})\leq\non(\mathcal{I})$, we will show that for every set $A$ not in $\mathcal I$, we can find a family $\mathcal F$ of the same (or lower) cardinality such that $\bigcup\mathcal F\notin I$. This is easy: if $A\notin\mathcal I$, then the family $\mathcal F$ consisting of all $\{a\}$ such that $a\in A$ has the same cardinality as $A$ and satisfies $\bigcup\mathcal F\notin\mathcal I$.

The proofs of each of the next three inequalities follows the same form: given a set indicated by the right-hand side, find a set of the same or lower cardinality indicated by the left-hand side. So to show $\non(\mathcal I)\leq\cof(\mathcal I)$, let $\mathcal F\subset \mathcal{I}$ be a basis for $\mathcal I$. For each set $B\in\mathcal F$ choose an element $x_B\notin B$ and let $A=\set{x_B\mid B\in\mathcal F}$. Then $A$ has the same or lower cardinality as $\mathcal F$, and we claim that $A\notin\mathcal{I}$. Indeed if $A\in\mathcal{I}$ then we would have $A\subseteq B$ for some $B\in\mathcal F$, contradicting that $x_B\notin B$.

For the inequality $\add(\mathcal I)\leq\cov(\mathcal I)$, if $\mathcal F\subset\mathcal{I}$ satisfies $\bigcup\mathcal F=X$, then $\mathcal F$ itself satisfies $\bigcup\mathcal F\notin\mathcal I$.

For the inequality $\cov(\mathcal I)\leq\cof(\mathcal I)$, again suppose that $\mathcal F$ is a basis for $\mathcal I$. Since $\mathcal I$ contains the singletons, it follows that $\mathcal F$ itself covers $X$.

We have already shown that $\add(\Ksigma)\leq\non(\Ksigma)=\mathfrak b$. For the reverse inequality, first recall from that a subset of $\omega^\omega$ is unbounded if and only if it is not $\Ksigma$. Now suppose that $\mathcal F$ is a family of $\Ksigma$ subsets of $\omega^\omega$ such that $\bigcup\mathcal F$ is not $\Ksigma$. For each $F\in\mathcal F$ let $g_F$ be a bound for $F$. Then $\set{g_F\mid F\in\mathcal F}$ is an unbounded family: Indeed, otherwise the set of things bounded by some $g_F$ would be bounded and hence so would $\bigcup\mathcal F$. This shows that $\add(\Ksigma)\geq\mathfrak b$.

The second equality is similar and left as .

The key is that we can construct dense open sets of arbitrarily small measure. That is, for each $n$ we will construct a dense open set $A_n$ such that $m(A_n)\gt 1/n$. Assuming we have done so, we let $A=\bigcap A_n$. Clearly the set $A$ is null. To see that it is comeager note that for all $n$, we have that $\RR\smallsetminus A_n$ is closed and nowhere dense. Thus $\RR\smallsetminus A=\bigcup(\RR\smallsetminus A_n)$ is meager.

To construct the set $A_n$, let $q_0,q_1,\ldots$ be an enumeration of the rational numbers, and for each $i$ let $I_{n,i}$ be the open interval centered at $q_i$ of length $1/(n2^{i+1})$. We then let $A_n=\bigcup_iI_{n,i}$. Clearly $A_n$ is dense and open, and $m(A_n)\leq\sum_i1/(n2^{i+1})=1/n$.

Finally, since $A$ is null and comeager, we clearly have that $\RR\smallsetminus A$ is meager and conull.

For the first inequality, recall our observation in that $\Ksigma\subset\Meager$, so any nonmeager subset of $\omega^\omega$ is certainly not $\Ksigma$. But we also know that every non-$\Ksigma$ set is unbounded. It follows that every nonmeager subset of $\omega^\omega$ is unbounded, which implies $\mathfrak b\leq\non(\Meager)$.

The second inequality again uses the fact that $\Ksigma\subset\Meager$, and we leave it as .

For the first inequality, we must show that given a nonmeager set $X$, we can find a family $\mathcal F$ of null sets of smaller or equal size such that $\bigcup F=\RR$. For this, we let $A$ be the null comeager set constructed in , and consider the family of null sets $\mathcal F=\set{x+A\mid x\in X}$.

To see that $\bigcup F=\RR$, suppose towards a contradiction that this is not the case. Then there exists $z\in\RR$ such that $z\notin x+A$ for all $x\in X$. It follows that $z-x\notin A$ for all $x\in X$, or in other words that $z-X$ is disjoint from $A$. But $A$ is comeager, so this would imply that $z-X$ is meager, which is a contradiction.

The proof of the second inequality is identical but with the terms meager and null exchanged. This time let $X$ be nonmeager, and let $A$ be meager conull. Then the same argument shows that the family $\mathcal F$ defined above covers $\RR$, since otherwise there would be a translate $z-X$ of $X$ which is null.

It is straightforward to see the characterizations of $\cof(\mathcal I)$ and $\cov(\mathcal I)$. The characterizations of $\non(\mathcal I)$ and $\add(\mathcal I)$ both use the downward closure property: $A$ lies in $\mathcal I$ if and only if $A$ is a subset of an element of $\mathcal I$.

For the first statement, it is enough to show that if $\mathcal F$ is an $R$-dominating family, then the image $\psi(\mathcal F)$ is an $S$-dominating family. Indeed, the image $\psi(\mathcal F)$ has the same or smaller cardinality than $\mathcal F$. To check this we simply chase the diagram: since $\mathcal F$ is $R$-dominating, for any $d\in\dom(S)$ there exists $f\in\mathcal F$ such that $\phi(d)\mathrel{R}f$. Since $(\phi,\psi)$ is a morphism, it follows that $d\mathrel{S}\psi(f)$. This confirms that $\psi(\mathcal F)$ is an $S$-dominating family.

For the second statement, just take the contrapositive of the morphism property, $\phi(c)\mathrel R d\implies c\mathrel S\psi(d)$, to arrive at the property required of a morphism from $\hat S$ to $\hat R$.

First suppose that $A\subset\Diff_P(x)$, we will show $A$ is meager. For this, let

Thus $A\subset\bigcup A_n$, and it is clear that $A_N$ contains no interior. Moreover $A_N$ is a countable intersection of boolean combinations of basic open sets, and hence $A_N$ is closed. Thus we have shown that $A$ is meager.

Conversely suppose $A=\bigcup A_n$ where each $A_n$ is nowhere dense, and suppose without loss of generality that $A_n\subset A_{n+1}$ for all $n$. We will define an interval partition $P=(I_n)$ and an element $x\in2^\omega$ recursively. To begin, since $A_0$ isn't dense there exists $s\in2^{\lt\omega}$ such that $A_0\cap V_s=\emptyset$. We let $I_0=\dom(s)$ and $x\restriction I_0=s$.

Now suppose that $I_i$ and $x\restriction I_i$ have been constructed for $i\lt n$ and let $s=x\restriction\bigcup_{i\lt n}I_i$ be the initial segment built so far. Since $A_n$ is nowhere dense, by we can find an extension $t$ of $s$ such that $A_n\cap V_t=\emptyset$. But we can do even better: we can find an extension $t$ of $s$ such that even if $y\in2^\omega$ only agrees with $t$ on $\dom(t\smallsetminus s)$, then we still have $y\notin A_n$.

Such a $t$ is built in $k$ many steps: Let $s_0,\ldots,s_{k-1}$ enumerate all elements of $2^{\lt \omega}$ whose domain is exactly $\dom(s)$. Repeatedly using that $A_n$ is nowhere dense, we can find a sequence of successive extensions $s\subset t_0\subset\ldots\subset t_{k-1}=t$ such that $A_n\cap V_{s_i\cup(t_i\smallsetminus s)}=\emptyset$. We then let $I_n=\dom(t\smallsetminus s)$ and $x_n=t\restriction I_n$. This concludes the construction of $x$ and $P$.

To see that $A\subset\Diff_P(x)$, observe that whenever $y\restriction I_n=x\restriction I_n$ we have $y\notin A_n$. In other words, whenever $y\in A_n$ we have that $y$ differs from $x$ on $I_n$. Since the $A_n$ are increasing, any $a\in A$ lies in all but finitely many of the $A_n$. Thus we can conclude that any $a\in A$ strongly differs from $x$ on $P$.

We first construct a morphism from $\prec$ to $\leq^*$. Given any interval partition $P$ we define the element $\psi(P)\in\omega^\omega$ by $\psi(P)(n)=$ the right endpoint of the interval after the one containing $n$. Moreover for any function $f\in\omega^\omega$ define an interval partition $\phi(f)$ consisting of intervals $[a,b]$ such that $\max\{f(n)\mid n\lt a\}\leq b$.

Now, if $\phi(f)\prec P=(I_m)$, we must verify that $f\leq^*\psi(P)$. Indeed, given any $n$ we may find $I_m$ such that $n\in I_m$. Then if $n$ is large enough, since $\phi(f)\prec P$ we know there exists an interval $J\in\phi(f)$ such that $J\subset I_{n+1}$. Then by definition of $\phi$ we have $f(n)\leq\max J$. And by definition of $\psi$ we have $\max J\leq\psi(P)(n)$. Hence $f(n)\leq\psi(P)(n)$, as desired.

The morphism from $\prec$ to $\leq^*$ is the same, but with the roles of $\phi$ and $\psi$ reversed. We leave it to the reader to check that this is indeed the case.

We prove the second inequality by finding a morphism from the $\subset$ relation on $\Meager$ to the $\prec$ relation on interval partitions. We therefore obtain the first inequality as a consequence of duality. For this it is enough to consider the $\subset$ relation just on the basis of meager sets of the form $A=\Diff_Q(y)$. We let:

Then by , $\Diff_P(0)\subset\Diff_Q(y)$ in particular implies that $P\prec Q$, and hence $\phi(P)\subset A\implies P\prec\psi(A)$, as desired.

We have already shown that $\add(\Meager)\leq\mathfrak b$ and $\add(\Meager)\leq\cov(\Meager)$. Hence it remains only to show that $\add(\Meager)\geq\min\{\mathfrak b,\cov(\Meager)\}$. For this we must show that if $\mathcal F$ is a family of meager subsets of $\omega^\omega$ such that $|\mathcal F|\lt \min\{\mathfrak b,\cov(\Meager)\}$ then $\bigcup\mathcal F$ is meager. Without loss of generality, we can suppose that $\mathcal F$ consists of closed nowhere dense sets.

We begin by finding a countable dense subset $Q\subset\omega^\omega$ disjoint from $\bigcup\mathcal F$. Indeed, since $|\mathcal F|\lt \cov(\Meager)$ we have that $\bigcup\mathcal F\neq\omega^\omega$. In fact for any basic open set $V_s$ we must have that $\bigcup\mathcal F$ does not cover $I$, since otherwise we could use to find a countable family of translates of $\bigcup(\mathcal F)$ which covers all oof $\omega^\omega$. This shows $\bigcup\mathcal F$ is co-dense, and therefore we can find $Q$ as required.

Now enumerate $Q=(q_n)_{n\in\NN}$. Then for each $F\in\mathcal F$ and $n\in\NN$, since $F$ is nowhere dense, we can find a finite initial segment $q_n\restriction g_F(n)$ such that $V_{q_n\restriction g_F(n)}$ is disjoint from $F$. Since $|\mathcal F|\lt \mathfrak b$, the family of functions $\set{g_F\mid F\in\mathcal F}$ is bounded by a single function $h\in\omega^\omega$. Finally we use this $h$ to define the set:

Then $R$ is a countable intersection of dense open sets, and hence it is comeager. Moreover since for all $F\in\mathcal F$ we have $g_F\leq^*h$, we have that $R$ is disjoint from $\bigcup\mathcal F$. We can thus conclude that $\bigcup\mathcal F$ is meager, as desired.

We must define $\phi\colon\omega^\omega\to\Null$ and $\psi\colon\Null\to SL$ such that for all $f\in\omega^\omega$ and null sets $A\subset2^\omega$ we have $\phi(f)\subset A$ implies $f\in^*\psi(A)$.

To define $\phi$, we start with a sequence of open subsets $E_{n,i}\subset2^\omega$ such that $m(E_{n,i})=2^{-n}$, and given $f\in\omega^\omega$ we let

Then it is clear that $\phi(f)$ is a null set. For technical reasons later on, we will need to assume that the sets $E_{n,i}$ are mutually independent events (the measure of the intersection is the product of the measures). It is not difficult to write down such $E_{n,i}$ explicitly.

Before defining $\psi$, given a null set $A\subset2^\omega$ let us preview what properties we will need of the slalom $\psi(A)$. So suppose that $f$ is given and $\phi(f)\subset A$. Let $K$ be chosen as in , so that we have $K\cap\bigcap_N\bigcup_{n\geq N}E_{n,f(n)}=\emptyset$. Since $K$ is complete and the sets $\bigcup_{n\geq N}E_{n,f(n)}$ are open, the Baire category theorem implies that at least one of them is non-dense in $K$. Thus there is a basic open set $V_s$ such that $V_s\cap K\neq\emptyset$ and eventually we have $V_s\cap K\cap E_{n,f(n)}=\emptyset$. We will define the slalom $\psi(A)=(I_n)$ so that for $n$ large enough, $I_n$ it includes all such $f(n)$. This will guarantee that $f\in^*\psi(A)$ as required.

As a first approximation to this, whenever $V_s\cap K\neq\emptyset$ we begin by letting

and otherwise we simply let $I_n(s)=\emptyset$. We now have two issues to deal with:

• We need a single slalom $(I_n)$ that handles all $s$ at once.
• The $I_n(s)$ don't necessarily satisfy $|I_n(s)|\leq2^n$; we need $|I_n|\leq2^n$.

Tackling the second issue first, we will show that the sets $|I_n(s)|$ are not too large. More specifically we claim that the sum $\sum2^{-n}|I_n(s)|$ converges. Indeed, by the independence of the sets $E_{n,i}$ we have

By our choice of $K$, the left-hand side is positive. Hence the right-hand side is positive too and taking a logarithm we obtain

From the Taylor series expansion we always have $-\log(1-x)\gt x$, and the claim now follows.

To deal with the first issue we construct a single slalom $I_n$ such that for all $s$ we eventually have $I_n(s)\subset I_n$. To do this fix an enumeration $s_1,s_2,\ldots$ of the elements of $2^{\lt \omega}$. By the convergence shown in the previous paragraph we can find $k(s_j)$ such that for all $n\geq k(s_j)$ we have $2^{-n}|I_n(s_j)|\leq1/2^j$. We then let $I_n=\bigcup\set{I_n(s_j)\mid n\geq k(s_j)}$. Then clearly

Thus $\psi(A)=(I_n)$ is a slalom, and this completes the construction of $\psi$.

To quickly recapitulate why this works, again suppose that $\phi(f)\subset A$. By the above reasoning we can find $V_s$ such that $V_s\cap K\neq\emptyset$ and for almost all $n$, $V_s\cap K\cap E_{n,f(n)}=\emptyset$. Thus for $n$ large enough we have both $f(n)\in I_n(s)$ and $I_n(s)\subset I_n$. It follows that $f\in^*\psi(A)$.

We must define $\phi\colon\Meager\to\omega^\omega$ and $\psi\colon SL\to\Meager$ such that whenever $\phi(A)\in^*S$ we have $A\subset\psi(S)$.

To construct $\psi$, first let $s_1,s_2,\ldots$ be an enumeration of $2^{\lt \omega}$, and for each $n$ apply to $\mathcal O=V_{s_n}$ to obtain a family $\mathcal U_n=\{U_{n,i}\}$. Now if $S=(I_n)$ is a slalom we let

Then by the first property of the $\mathcal U_n$, for all $n$ we have that $\bigcap_{i\in I_n}U_{n,i}$ is a nonempty subset of $V_{s_n}$. It follows that each set $\bigcup_{n\geq N}\bigcap_{i\in I_n}U_{n,i}$ is dense and open, and hence that $\psi(S)$ is meager.

To define $\phi$, let $A$ be a meager subset of $2^\omega$ and write $A$ as an increasing union of nowhere dense sets $A=\bigcup A_n$. By the second property of the $\mathcal U_n$, for all $n$ there exists $i$ such that $A_n\cap U_{n,i}=\emptyset$. We let $\phi(A)(i)=$ this value $i$.

Finally let $A$ and $S=(I_n)$ be given and suppose that $\phi(A)\in^*S$. Then for $n$ large enough we have that $I_n$ contains an element $i$ with $A_n\cap U_{n,i}=\emptyset$. Thus for $N$ large enough we have that $A_n$ is disjoint from $\bigcup_{n\geq N}\bigcap_{i\in I_n}U_{n,i}$. It follows that $A_n\subset\psi(S)$, and hence $A\subset\psi(S)$ as desired.

It is enough to show that if $G\subset\PP$ is a filter then its complement $D=\PP\smallsetminus G$ is dense. For this, let $p\in\PP$ be arbitrary and by the hypothesis on $\PP$ let $q,r$ be incompatible elements such that $q,r\leq p$. Since $G$ is a filter, it cannot contain both $q$ and $r$. Thus $D$ contains at least one of them, and this shows $D$ is dense.

Let $\PP$ be any partial order and let $D_0,D_1,\ldots$ be a countable family of dense subsets of $\PP$. Fix $p_0\in D_0$, and inductively let $p_{n+1}\leq p_n$ be an element of $D_{n+1}$. Then the set $\{p_n\}$ is downwards directed, and hence closing it upwards generates a filter $G$ which meets each of the $D_i$.

We again go to our favorite partial ordering $\omega^{\lt \omega}$ with the upside-down order. This time, for each $f\in\omega^\omega$ we consider the set

It is easy to see that $D_f$ is dense: any sequence $s$ can be extended to a sequence $t$ that disagrees with $f$. Now if MA were to hold with respect to families of dense sets of size continuum, then there would be a filter $G$ that meets $D_f$ for every $f\in\omega^\omega$. It follows from this that the function $g=\bigcup G$ is an element of $\omega^\omega$ which disagrees with every $f\in\omega^\omega$, a contradiction.

This time we let use the partial order $\PP=\omega_1^{\lt \omega}$ with the upside-down order. We have already seen that $\PP$ is not ccc. Now for each $\alpha\in\omega_1$ we consider the set

Then $D_\alpha$ is dense: any $s\in\omega_1^{\lt \omega}$ can be extended to include $\alpha$ in its range. Now if MA were to hold with respect to this partial order, then there would be a filter $G\subset\omega_1^{\lt \omega}$ that meets $D_\alpha$ for all $\alpha$. It follows from this that there is an onto function $g=\bigcup G$ from $\omega$ to $\omega_1$, a contradiction.

Let $\mathcal F$ be a family of nowhere dense subsets of $\RR$ of cardinality less than continuum. We will construct $x\in\RR$ such that $x\notin\bigcup\mathcal F$. Let $\PP$ be the partial order consisting of all bounded, positive-length intervals in $\RR$, ordered by $I'\leq I$ iff $I'\subset I$. Then $\PP$ is easily seen to be ccc by the same argument as in . For each $A\in\mathcal F$, we consider the set

Then $D_A$ is dense for any $A$: since $A$ is nowhere dense, for any positive-length interval $I$ there is a positive length $J\subset I$ such that $J\cap A=\emptyset$. We may then shrink $J$ further to suppose that $\overline{J}\subset I$.

Now by MA, we can find a filter $G\subset\PP$ such that $G$ meets $D_A$ for every $A\in\mathcal F$. Then the sets $\overline{I}$ for $I\in G$ have the finite intersection property, and it follows from the completeness of $\RR$ that there is a point $x\in\bigcap\set{\overline{I}\mid I\in G}$. Then if $A\in\mathcal F$, since $G\cap D_A\neq\emptyset$ we can find a positive-length interval $I$ such that $I\in G$ and $\overline{I}\cap A=\emptyset$. That is, we have $x\in\overline{I}$ and $\overline{I}\cap A=\emptyset$, and so $x\notin A$. We conclude that $x$ is not an element of $\bigcup\mathcal F$, as desired.

Suppose towards a contradiction that $\mathfrak d\lt \mathfrak c$, and fix a dominating family $\mathcal F\subset\omega^\omega$. Let $\PP$ be the partial order $\omega^{\lt \omega}$ with the upside-down ordering. For each $f\in\mathcal F$ we consider the family sets

Observe that $D_{f,n}$ is dense for all $f$ and $n$: if $s\in\omega^{\lt \omega}$ we can easily find $n'\gt n,|s|$ and find $t\supset s$ such that $t(n')\gt f(n)$. Thus by MA we can find a filter $G$ which meets $D_{f,n}$ for all $f\in\mathcal F$ and $n\in\NN$. Letting $g=\bigcup G$, it is clear that $g$ is not dominated by $f$ for any $f\in\mathcal F$, contradicting that $\mathcal F$ is a dominating family.

Suppose towards a contradiction that $\mathcal F$ is an unbounded family of size $\lt \mathfrak c$, and let $\PP$ be the Hechler forcing $\mathbb H_{\mathcal F}$. We now consider two families of dense sets. First, for each $n$ we consider the set

To see that $D_n$ is dense, let $(s,F)$ be a given element of $\mathbb H_{\mathcal F}$. If $n\notin\dom(s)$ then we extend the stem $s$ to a sequence $t$ defined by $t(i)=\max_{f\in F}f(i)+1$ for all $i\notin\dom(s)$ such that $i\leq n$. Then clearly $(t,F)\leq(s,F)$ and $(t,F)\in D_n$.

Next, for each $f\in\mathcal F$ we consider the set

Then $D_f$ is again dense, since given $(s,F)$ we have $(s,F\cup\{f\})\leq(s,F)$ (Observe that the promises $F$ are trivially satisfied since we have not lengthened the stem!)

Now by MA we cand find a filter $G$ that meets $D_n$ for all $n\in\NN$ and $D_f$ for all $f\in\mathcal F$. We then let

be the element of the Baire space determined by $G$. Given $f\in\mathcal F$ and $n\in\NN$ we first find an element $(s,F)\in G\cap D_f$, and then letting $n'=\max(n,\dom(s))+1$ we find an element $(s',F')\in G\cap D_{n'}$. Since $G$ is a filter we can find $(s'',F'')\in G$ which is stronger than both. Then by the definition of the ordering on $\mathbb H_{\mathcal F}$, there is some $n''\gt n$ such that $s''(n'')\gt f(n'')$ and hence $g(n'')\gt f(n'')$. Since $f$ and $n$ were arbitrary, it follows that $f\leq^*g$ for all $f\in\mathcal F$, contradicting that $\mathcal F$ is unbounded.

Given an uncountable family $\mathcal F\subset\mathbb A_\epsilon$ we must show that at least two elements $O,O'\in\mathcal F$ are compatible, that is, $m(O\cup O')\lt \epsilon$. We first give ourselves a little wiggle room as follows: since $\mathcal F$ is uncountable and there are only countably many values of $n\in\NN$, by the pigeon-hole principle we can find a fixed $n$ and an uncountable subset $\mathcal F_0\subset\mathcal F$ such that for all $O\in\mathcal F_0$ we have $m(O)\lt \epsilon-1/n$.

Now for each $O\in\mathcal F_0$ we can find an open set $B_O\subset O$ which is a finite union of intervals with rational endpoints and such that $m(O\smallsetminus B_O)\lt1/2n$. Once again, since there are only countably many possible sets $B_O$, we can find a fixed set $B$ and an uncountable $\mathcal F_{00}\subset\mathcal F_0$ such that $B=B_O$ for every $O\in\mathcal F_{00}$.

We claim that any two elements $O,O'\mathcal F_{00}$ are compatible. Indeed, we compute:

Thus we can conclude that $\mathcal F$ is not an antichain, as desired.

Given a family $\mathcal F$ of fewer than continuum many null sets, we wish to show that $\bigcup\mathcal F$ is again null. For this, it is sufficient to show that for any $\epsilon\gt 0$ we have $\bigcup\mathcal F$ is contained in an open set of measure $\leq\epsilon$.

For this, let $\epsilon$ be given and let $\mathbb A_\epsilon$ be the corresponding amoeba forcing. For each $A\in\mathcal F$ we consider the set

To see that $D_A$ is dense, let $O$ be a given open set with $m(O)\lt \epsilon$. Since $A$ is null we can find an open set $U$ such that $A\subset U$ and $m(U)\lt \epsilon-m(O)$. Then $m(O\cup U)\lt \epsilon$ and $A\subset O\cup U$, and so $O\cup U$ is stronger than $O$ and $O\cup U\in D_A$. (Kunen says: The amoeba $O$ reached out a pseudopod $U$ to engulf the morsel of food $A$.)

Now by MA there is a filter $G\subset\mathbb A_\epsilon$ such that $G$ meets $D_A$ for all $A\in\mathcal F$. Letting $U=\bigcup G$ be the open set determined by $G$, we clearly have that $\bigcup\mathcal F\subset U$. To conclude, we claim that $m(U)\leq\epsilon$. For this, since $\mathbb R$ is second countable we can find countably many elements $O_1,O_2,\cdots\in G$ such that $U=\bigcup O_n$. Since measure is continuous from below (similar to ) for all $\delta\gt 0$ there exists some $N$ such that $m(O_1\cup\cdots\cup O_N)\geq m(U)-\delta$. Since $G$ is downwards-directed we inductively have $O_1\cup\cdots\cup O_n\in G$, which implies that $m(O_1\cup\cdots\cup O_N)\lt \epsilon$. It follows that $m(U)\leq\epsilon+\delta$, and since $\delta$ was arbitrary we have $m(U)\leq\epsilon$, as desired.

To prove the statements, we need only write down explicit $\PP$-names for the objects in question. First recall that we are always assuming $\PP$ has a maximum element $\mathbb 1$. Thus if $x\in V$ we can write the recursive definition

The idea here is to take the tree of $x$ and label each node with a $\mathbb 1$. To see that $\check x_G=x$, suppose inductively that $\check y_G=y$ for all $y\in x$. Then since $\mathbb 1$ always lies in $G$, the definition implies that $\check x_G=\set{\check y_G\mid y\in x}=\set{y\mid y\in x}=x$.

To see that $G\in V[G]$ we construct a single name

Then by the previous paragraph, we have that $\Gamma_G=\set{p\mid p\in G}=G$, as desired.

Finally, if $W$ is a model of ZFC which contains $V$ as a submodel and $G$ as an element, we must check that $W$ contains $\tau_G$ for all names $\tau$. For this, $W$ can simply evaluate $\tau_G$ as in its definition, and $W$ will be correct in this evaluation because the definition of $\tau_G$ is $\Delta_0$ and hence absolute to transitive models. [ref]

It is clear that $V[G]$ is countable from its definition; each element of $V[G]$ is determined by a name which lies in $V$.

For the statement about ordinals, first recall that the property of being an ordinal is absolute to transitive models. Now suppose that $\alpha$ is an ordinal of $V[G]$ and let $\tau$ be a name such that $\alpha=\tau_G$. Note that when we construct $\tau_G$ from $\tau$ we essentially throw stuff away, and so $\tau$ is in a sense more complicated than $\tau_G$. We can make this precise using the notion of a rank: for any set $x$ we can define the $\in$-rank $\rk(x)=\sup\set{\rk(y)+1\mid y\in x}$. Then it is easy to see inductively that $\rk(\tau_G)\leq\rk(\tau)$. In our case, $\tau_G=\alpha$ and the rank of an ordinal $\alpha$ is always $\alpha$. We conclude that $\alpha\leq\rk(\tau)$, and since rank is an absolute notion and $V$ is transitive, we have $\alpha\in V$.

Every set satisfies the axiom of foundation. Since $V[G]$ is tansitive and infinite, it must contain $\omega$ and therefore satisfies the axiom of infinity. To show $V[G]$ satisfies extensionality, it is enough to show that $V[G]$ is a transitive set. For this, let $\tau_G$ is an arbitrary element of $V[G]$ and $x\in\tau_G$. Then by definition of $\tau_G$, we have $x=\sigma_G$ for some $\sigma\in\dom(\tau)$. In particular, $x\in V[G]$.

The pairing and union axioms are existence axioms, which means we must devise names for the two constructions. First suppose $\sigma_G,\tau_G\in V[G]$ and let $\rho$ denote the name $\set{(\sigma,\mathbb1),(\tau,\mathbb1)}$. Then it is immediate to see that $\rho_G=\{\sigma_G,\tau_G\}$. Next suppose $\tau_G\in V[G]$, and define the name:

Then since $\xi$ includes names for all conceivable elements of elements of $\tau_G$, we have that $\bigcup\tau_G\subset\xi_G$. (To hit $\bigcup\tau_G$ exactly we can either refine this argument or appeal to the comprehension axiom after we have proved it.)

If $\phi(x,y)$ and $a,b\in V[G]$ are as above, we need to cook up a name for the set $a_0=\set{x\in a\mid\phi(x,b)}$. For this, let $\dot a,\dot b$ be names for $a,b$ respectively, and let

Here we are using the definability theorem even to know that $\rho$ lies in $V$. To see that $\rho_G=a_0$, first suppose that $\pi_G\in\rho_G$. Then there is $p\in G$ such that $p\forces\pi\in\dot a$ and $p\forces\phi(\pi,\dot b)$. By definition of $\forces$, it follows that in $V[G]$ we have both $\pi_G\in\dot a_G$ and $\phi(\pi_G,\dot b_G)$. In other words, in $V[G]$ we have both $\pi_G\in a$ and $\phi(\pi_G,b)$, and therefore $\pi_G\in a_0$.

Conversely if $\pi_G\in a_0$ then $V[G]$ satisfies the sentences of the forcing language $\pi\in\dot a$ and $\phi(\pi,\dot b)$. By the forcing theorem there exist $q,r\in G$ such that $q\forces\pi\in\sigma$ and $r\forces\phi(\pi,\dot b)$. Letting $p\in G$ be such that $p\leq q,r$ we clearly have $(\pi,p)\in\rho$ and also $\pi_G\in\rho_G$.

This is a straightforward consequence of the fact that if $p'\leq p$ and $p'\in G$, then since $G$ is closed upwards we have $p\in G$.

First suppose that $p\forces\neg\phi$ and let $q\leq p$. Then by we have $q\forces\neg\phi$. Now we cannot have $q\forces\phi$, since in that case if $G$ is a $V$-generic filter with $q\in G$ we would have that $V[G]$ satisfies both $\phi$ and $\neg\phi$.

For the converse we proceed by contrapositive and suppose that $p\not\forces\neg\phi$. Then there is a $V$-generic filter $G$ with $p\in G$ such that $V[G]$ satisfies $\phi$. By the forcing theorem, there is $p'\in G$ such that $p'\forces\phi$. Letting $q\in G$ be such that $q\leq p,p'$ we have $q\forces\phi$ too, as desired.

Fix a $V$-generic filter $G$ with $p\in G$. Then $V[G]$ satisfies $\exists x\phi(x)$, and hence there is a name $\tau$ such that $V[G]$ satisfies $\phi(\tau_G)$. By the forcing theorem there is $p'\in G$ such that $p'\forces\phi(\tau)$. Letting $q\in G$ be such that $q\leq p,p'$, we have that $q$ is as desired.

We prove this by induction on the complexity of the formula $\phi$. For example, let us check that the induction passes through the first clause of . Suppose $\sigma,\tau$ are names and that the lemma holds for the sentence $\sigma'=\sigma$ whenever $\sigma'\in\dom(\tau)$. Then if $p\forces_0\sigma\in\tau$, there is $(\sigma',q)\in\tau$ such that $p\leq q$ and $p\forces_0\sigma'=\sigma$. If also $p'\leq p$, then clearly also $p'\leq q$ and by inductive hypothesis $p'\forces_0\sigma'=\sigma$. Hence $p'\forces_0\sigma\in\tau$, as desired. The verification of the remaining four clauses is similar, and we leave them for .

Once again we prove this by induction on the complexity of $\phi$. To check that the induction passes through the first clause of , suppose that $\sigma,\tau$ are names and that the lemma holds for the sentence $\sigma'=\sigma$ whenever $\sigma'\in\dom(\tau)$. We must show that the lemma holds for the sentence $\sigma\in\tau$. For this, first suppose that $p\in G$ and $p\forces_0\sigma\in\tau$. Then by there exists $(\sigma',q)\in\tau$ such that $p\leq q$ and $p\forces_0\sigma'=\sigma$. Clearly $V[G]$ satisfies $\sigma'\in\tau$, and by the inductive hypothesis $V[G]$ also satisfies $\sigma'=\sigma$. It follows that $V[G]$ satisfies $\sigma\in\tau$.

Conversely, suppose that $V[G]$ satisfies $\sigma\in\tau$. Then there must be some $(\sigma',q)\in\tau$ such that $V[G]$ satisfies $\sigma'=\sigma$. By the inductive hypothesis, there exists $r\in G$ such that $r\forces_0\sigma'=\sigma$. Since $G$ is downwards-directed we can find $p\in G$ such that $p\leq q,r$. Then by , $p\forces_0\sigma'=\sigma$, and so by we have $p\forces_0\sigma\in\tau$.

The verification that the induction goes through the second, fourth, and fifth clauses of is similar and we leave them for .

Finally, we verify that the induction passes through the third clause of . So suppose the lemma is true for $\phi$, and let us show it holds for $\neg\phi$. For this, first suppose that there is $p\in G$ such that $p\forces_0\neg\phi$. Then for all $q\leq p$ we have $q\not\forces_0\phi$. It follows from that for all $q\in G$ we have $q\not\forces_0\phi$. By inductive hypothesis, we must have that $V[G]$ does not satisfy $\phi$, and hence $V[G]$ satisfies $\neg\phi$.

Conversely suppose that $V[G]$ satisfies $\neg\phi$. Then $V[G]$ does not satisfy $\phi$, so by inductive hypothesis, for all $p\in G$ we have $p\not\forces_0\phi$. We now consider the set

Then $D$ is dense: given any $p$, if $p\forces_0\phi$ then $p$ itself lies in $D$. Otherwise $p\not\forces_0\phi$, so by there is $q\leq p$ such that $q\forces_0\neg\phi$. Thus in this case $q\in D$, and we have verified $D$ is dense. Finally, since $G$ is $V$-generic there exists $p\in G\cap D$. Since we know $p\not\forces_0\phi$, we must have instead that $p\forces_0\neg\phi$, as desired.

First suppose that $p\forces_0\neg\neg\phi$, and let $G$ be a $V$-generic filter with $p\in G$. Then by we have $V[G]$ satisfies $\neg\neg\phi$, and hence $V[G]$ satisfies $\phi$. This shows that $p\forces\phi$.

Conversely, suppose that $p\forces\phi$. By , to show $p\forces_0\neg\neg\phi$ it is equivalent to show that for all $q\leq p$ there exists $r\leq q$ such that $r\forces_0\phi$. So let $q\leq p$ be given, and let $G$ be a $V$-generic filter such that $q\in G$. The since $q\forces\phi$ we have $V[G]$ satisfies $\phi$. By there exists $q'\in G$ such that $q'\forces_0\phi$. Finally we may let $r\in G$ with $r\leq q'q'$, and by we have that $r\forces_0\phi$ too, as desired.

If $V[G]$ satisfies $\phi$, then $V[G]$ satisfies $\neg\neg\phi$. Hence by there exists $p\in G$ such that $p\forces_0\neg\neg\phi$, and by this implies $p\forces\phi$.

Let $G\subset\PP$ be a $V$-generic filter, and let $g=\bigcup G$. Now, for any limit ordinal $\alpha\lt \kappa$ we let $f_\alpha\in\omega^\omega$ be the function defined by $f_\alpha(n)=g(\alpha+n)$. It is clear that there are $\kappa$ many of these functions. We claim that if $\alpha\neq\beta$ then $f_\alpha\neq g_\alpha$. Indeed, consider the set

Then $D_{\alpha,\beta}$ is dense: indeed, given $s\in\Fn(\kappa,\omega)$, since $s$ is finite we can find $n\in\omega$ such that neither $\alpha+n$ nor $\beta+n$ lies in the domain of $s$. Then if we let $t\in\Fn(\kappa,\omega)$ be an extension of $s$ such that $t(\alpha+n)\neq t(\beta+n)$, we clearly have $t\in D_{\alpha,\beta}$.

Now since $G$ is $V$-generic, there exists $s\in G\cap D_{\alpha,\beta}$. Then there exists $n\in\omega$ such that $s(\alpha+n)\neq s(\beta+n)$. Since $s\subset g$ it follows that $g(\alpha+n)\neq g(\beta+n)$ and therefore that $f_\alpha\neq f_\beta$, as desired.

Let $\dot f$ denote a name for $f$, so that by the forcing theorem there exists $p\in G$ such that $p\forces \dot f\colon\check A\to\check B$. Define

To see that $f(a)\in F(a)$, note that if $f(a)=b$ then by the forcing lemma there is some $q\in G$ such that $q\forces\dot f(\check a)=\check b$. Using the downwards-directed property of $G$ we can assume that $q\leq p$, and hence obtain that $b\in F(a)$.

To see that $F(a)$ is countable, for each $b\in F(a)$ select a particular $q_b\leq p$ such that $q_b\forces\dot f(\check a)=\check b$. We claim that if $b\neq b'$ then $q_b$ is incompatible with $q_{b'}$. Otherwise, we would be able to find $b\neq b'$ with $r\leq q_b,q_{b'}$. Letting $H$ be a $V$-generic filter with $r\in H$, then in $V[H]$ we would have both $f(a)=b$ and $f(a)=b'$, a contradiction. Thus the set of $q_b$ for $b\in F(a)$ forms an antichain, and so by the ccc property we must have that $F(a)$ is countable.

Let $\kappa$ be a cardinal in $V$, and first assume that $\kappa$ is a successor cardinal $\aleph_{\alpha+1}$. Suppose towards a contradiction that in $V[G]$ there is a cardinal $\gamma\lt \kappa$ and an onto function $f\colon\gamma\to\kappa$. By the previous lemma, in $V$ there is a function $F\colon\gamma\to\mathcal P(\kappa)$ such that $F(a)$ is countable for all $a\in\gamma$ and $\bigcup F(a)=\kappa$. But now in $V$ we can use $F$ together with a bijection between $\gamma$ and $\gamma\times\omega$ to obtain an onto function $F'\colon\gamma\to\kappa$, contradicting that $\kappa$ is a cardinal in $V$.

Finally if $\kappa$ is a limit cardinal $\aleph_\lambda$, then $\kappa$ is the limit of the successor cardinals $\lt \kappa$. Since we have just shown that successor cardinals are preserved, $\kappa$ remains a limit of cardinals in $V[G]$. Since a limit of cardinals is a cardinal, $\kappa$ is a cardinal in $V[G]$.

Since there are only countably many possible values of $|F|$ for $F\in\mathcal F$, by the pigeon-hole principle we can replace $\mathcal F$ with an uncountable subset of it such that $|F|=$ some fixed value $n$ for all $F\in\mathcal G$.

Now we use induction on $n$. If $n=1$, then $\mathcal G$ forms a delta system automatically. Next suppose that the claim is true for families of sets of size $\lt n$. First consider the case that there is some $\alpha\in\kappa$ which lies in uncountably many of the $F\in\mathcal G$. Then by the inductive hypothesis we can find a delta system $\mathcal H_0$ contained in $\set{F\smallsetminus\{\alpha\}\mid F\in\mathcal G}$. It follows that the family $\mathcal G_0=\set{F_0\cup\{\alpha\}\mid F_0\in\mathcal H_0}$ is a delta system too.

Second consider the case that every $\alpha\in\kappa$, is contained in just countably many of the $F\in\mathcal G$. Then we can inductively find an uncountable subfamily $\mathcal G_0\subset\mathcal G$ that is pairwise disjoint, and hence a delta system with trivial root. Indeed, if countably many pairwise disjoint sets $F_0,F_1,\ldots$ have been found so far, then all the ordinals in $\bigcup F_n$ are still only contained in countably many of the $F\in\mathcal G$. This means that we can find an $F$ disjoint from them all, and completes the proof of the claim.

It suffices to show that any uncountable $\mathcal G\subset\Fn(\kappa,\omega)$ contains two compatible elements. In fact we will show that it contains uncountably many pairwise compatible elements. For this we first consider the corresponding family of domains $\mathcal F=\set{\dom(f)\mid f\in\mathcal G}$. Then $\mathcal F$ is an uncountable family of finite subsets of $\kappa$. Thus by , we can find an uncountable subset $\mathcal F_0\subset\mathcal F$ which forms a delta system with some root $A$.

Now, let $\mathcal G_0\subset\mathcal G$ be the subset of $\mathcal G$ consisting of functions $g$ such that $\dom(g)\in\mathcal F_0$. These functions may disagree on $A$, but they can never disagree elsewhere. Since there are only countably many possibilities for $g\restriction A$, by the pigeon-hole principle we can replace $\mathcal G_0$ with an uncountable subset of it such that $g\restriction A=$ some fixed function $g_0$ for all $g$. It follows from this that every pair of elements of $\mathcal G_0$ is compatible.

Let $f$ be an element of $\omega^\omega$ in $V[G]$, and let $\dot f$ be a name for $f$. We will show that in fact $f$ lies in $V$. To begin, by the forcing theorem we can find some $q\in G$ such that $q\forces \dot f\colon\check\omega\to\check\omega$. Now, since $f(0)$ has some value in $\omega$, there is some $n_0\in\omega$ such that $V[G]$ satisfies $f(0)=\check n_0$. Hence we can find $p_0\in G$ and such that $p_0\forces\dot f(0)=\check n_0$. Moreover since $G$ is downwards directed, we can suppose without loss of generality that $p_0\leq q$.

Repeating this argument inductivley, we can find $n_i\in\omega$ and $p_i\in G$ such that $p_i\forces f(\check i)=\check n_i$. Moreover we can assume that $p_i\leq p_{i-1}$ for all $i$. Since $\PP$ is countably closed, there exists $p\in\PP$ such that $p\leq p_i$ for all $i$. Then $p\forces\dot f(\check i)=\check n_i$ for all $i$, which means that $p$ ``knows'' every value of $f$. It follows that $f$ is definable in $V$ by $f(i)=n$ if and only if $p\forces\dot f(\check i)=\check n$.

To see that $\PP$ does not collapse $\aleph_1$, let $\kappa$ denote the ordinal such that in $V$ we have $\aleph_1=\kappa$, and suppose towards a contradiction that in $V[G]$ we have that $\kappa$ is countable. Then in $V[G]$ there is a surjective function $f\colon\omega\to\kappa$. Note that in the argument of the previous paragraph we only needed that the domain of $f$ was $\omega$ and the codomain of $f$ was a set in $V$. Hence we can use the same reasoning to conclude that $f$ is definable in $V$, contradicting that $\kappa$ is uncountable in $V$.

By , the notions of $\omega^\omega$ and $\aleph_1$ are identical in $V$ and $V[G]$. Thus in the rest of this argument we need not distinguish in which model they are computed.

To begin, it is clear that $g=\bigcup G$ is a new function from $\omega_1\to\omega$. Now for each $f\in\omega^\omega$ consider the set

Then $D_f$ is dense: indeed, if $s$ is element of $\Fn_{\aleph_0}(\omega_1,\omega)$ then we can find some $\alpha$ such that $\dom(s)\lt\alpha$, and define an extension $t\supset s$ such that $t(\alpha+n)=s(n)$.

It follows that $g=\bigcup G$ has the property: for every $f\in\omega^\omega$ there exists $\alpha\lt\omega_1$ such that for all $n\in\omega$ we have $g(\alpha+n)=f(n)$. In other words, every element of the Baire space is coded in the values of $g$. Since there are only $\aleph_1$ many possible functions coded in this way, we have $|\omega^\omega|\leq\aleph_1$.

We have already shown that in $V[G]$ we have $\mathfrak c\geq\kappa$. To show that $\mathfrak c\leq\kappa$, it suffices to show that in $V[G]$ there are at most $\kappa$ many subsets of $\omega$. To this end, we claim that every subset of $\omega$ in $V[G]$ has a nice name, that is, a name of the form

where for each $n$, $A_n$ is an antichain of $\PP$.

Admitting this claim, since $\PP$ is ccc, we know that each antichain $A_n$ is countable. It follows that there are only $\kappa^{\aleph_0}$ many possibilities for the name $\tau$, and hence only $\kappa^{\aleph_0}$ many possibilities for the set $S$. Since we have assumed that $\kappa^{\aleph_0}=\kappa$, this completes the proof.

To establish the claim, let $S\in V[G]$ be a subset of $\omega$ and let $\dot S$ be a name for $S$. By the forcing theorem there is some $q\in G$ such that $q\forces\dot S\subset\check\omega$. Now consider the sets

Using Zorn's Lemma, we can find a maximal antichain $A_n\subset B_n$. We will show that the corresponding nice name $\tau$ is a name for $S$.

First, it is clear that $\tau_G\subset S$, since if $(\check n,p)\in G$ then $p\forces\check n\in\dot S$ and hence $V[G]$ satisfies $n\in S$. Conversely, suppose that $V[G]$ satisfies $n\in S$ and let $q'\in G$ be such that $q'\forces\check n\in\dot S$. As usual since $G$ is downwards directed we can suppose that $q'\leq q$. We now consider the set

Then $D$ is dense: given any $p_0\in\PP$, if $p_0$ is incompatible with $q'$, then $p_0$ itself lies in $D$. Otherwise $p_0$ is compatible with $q'$ and hence there is $p_1\leq p_0,q'$. Then $p_1$ lies in the set $B_n$, and since $A_n$ is a maximal antichain in $B_n$, we must have that $p_1$ is compatible with some $a\in A_n$. Hence we can find $p_2\leq p_1,a$, and then $p_2\in D$.

Finally, since $G$ is generic, there is some $p\in G$ and an element $a\in A_n$ with $p\leq a$. Since $G$ is closed upwards, $a\in G$ too, and since $(\check n,a)\in\tau$ we have $n\in\tau_G$. This shows that $S\subset\tau_G$, as desired.

The proof of the first statement is a simple density argument, which we leave for .

For the second statement, let $h\in V[G]$ and let $\dot h$ be a $\PP$-name for $h$. We wish to define a function $f\in V$ which is not dominated by $h$. For this, since $\PP$ is countable, we can enumerate $\PP=\{p_i\mid i\in\omega\}$. For each $i$, we then define the approximation to $h$ given by

(If the above maximum is undefined, then set $h_i(n)=0$ by default.) We now diagonalize against these approximations to $h$ to define a function $f$ such that $h_i\lt ^*f$ for all $i$. Specifically we let

and observe that $f$ lies in $V$ by the definability theorem. We claim that this $f$ is in fact not dominated by $h$.

For this, if we have $f\leq^*h$ then we can find $N$ such that for all $n\geq N$ we have $f(n)\leq h(n)$. By the forcing theorem, we can find $p_i\in\PP$ such that $p_i\forces(\forall n\geq\check N)\;\check f(n)\leq\dot h(n)$. But now if we choose any $n\geq N,i$, then by definition of $h_i$ we have $f(n)\leq h_i(n)$, and by definition of $f$ we have $h_i(n) \lt f(n)$. This is a contradiction!

It is straightforward to verify that $G_1$ and $G_2$ are filters. Moreover, since $G_1$ and $G_2$ are defined from $G$, and $G$ can be recovered from $G_1$ and $G_2$, it follows easily that $V[G]=V[G_1][G_2]$.

To show that $G_1$ is $V$-generic for $\PP_1$, let $D\in V$ be a dense subset of $\PP_1$. Letting

it is trivial to see that $D'$ is dense in $\PP$. Since $G$ is $V$-generic for $\PP$, there exists an element $p\cup q\in G\cap D'$. Then $p\in D$, and since $G$ is closed upwards, we have $p\in G$ too. Thus $G\cap D\neq\emptyset$, as desired.

To show that $G_2$ is $V[G_1]$-generic for $\PP_2$ is analogous but slightly trickier. For this, let $D\in V[G_1]$ be a dense subset of $\PP_2$, and let $\dot D$ be a $\PP_1$-name for $D$. Using the forcing theorem, we can find $p_1\in G_1$ such that $p_1\forces$ ``$\dot D$ is dense in $\check\PP_2$''. Let

We claim that $D'$ is dense in $\PP$. Indeed, let $p\cup q$ be an arbitrary element of $\PP$, where $p\in\PP_1$ and $q\in\PP_2$. If $p\perp p_1$ then we are done, so suppose instead that $p\leq p_1$. Since $D$ is dense in $\PP_2$, there exists $q'\leq q$ such that $q'\in D$. Then by the forcing theorem there exists $p'\in G_1$ such that $p'\forces\check q'\in\dot D$. Letting $p''\leq p,p'$, we have that $p''\cup q'\in D'$, as desired.

Now, since $G$ is $V$-generic for $\PP$, there exists an element $p\cup q\in G\cap D'$. Then $q\in G_2$, and by definition of $D'$ we have that $q\in D$ too. Thus again we have $G_2\cap D\neq\emptyset$, as desired.

We first show that $\mathfrak d=\kappa$. Recall that we already know that $\mathfrak d\leq\mathfrak c=\kappa$. Now suppose, towards a contradiction, that $\mathfrak d\lt\kappa$. That is, in $V[G]$ there exists a dominating family $\mathcal F$ such that $|\mathcal F|\lt\kappa$. We claim that there is some $I\subset\kappa$ such that $|I|\lt\kappa$ and $\mathcal F$ is added by the forcing $\Fn(I,\omega)$.

To establish the claim, we first code $\mathcal F$ as a subset of $\lambda\times\omega\times\omega$ by enumerating $\mathcal F=\set{f_\alpha\mid\beta\lt\lambda}$ and letting

Now let $\tau$ be a nice name for $S_{\mathcal F}$ (see the proof of ), and note that since $\PP$ is ccc there are at most $\lambda$ many elements of $\PP$ mentioned in $\tau$. Each of these $\lambda$ many elements of $\PP$ in turn has just finitely many ordinals in its domain. Letting $I$ be the union of all these domains, we have that $\tau$ is a $\Fn(I,\omega)$-name and hence is added by the forcing $\Fn(I,\omega)$.

We now reach a contradiction as follows. Let $\PP_1=\Fn(I,\omega)$, $G_1=G\cap\PP_1$, $\PP_2=\Fn(\kappa\smallsetminus I,\omega)$, and $G_2=G\cap\PP_2$. Then the dominating family $\mathcal F$ lies in $V[G_1]$. But forcing with $\PP_2$ over $V[G_1]$ adds the generic element $g_2=\bigcup G_2$ to the Baire space. Applying to the ground model $V[G_1]$, we see that $g_2$ is not dominated by any element of $V[G_1]$, a contradiction.

We now turn to the proof that $\mathfrak b=\aleph_1$. Since the Baire space of the ground model, $\omega^\omega\cap V$, is itself a family of size $\aleph_1$, it suffices to show that $\omega^\omega\cap V$ remains unbounded in $V[G]$. So suppose to the contrary that some $h\in V[G]$ is a bound for $\omega^\omega\cap V$.

We first show that we can suppose $h$ is added by a countable fragment of the forcing $\PP$. For this, let $\dot h$ be a nice name for $h\subset\omega\times\omega$. Then once again since $\PP$ is ccc, $\dot h$ mentions just countably many elements of $\PP$ and these elements each use just finitely many elements of the domain $\kappa$. Hence there exists a countable subset $I\subset\kappa$ such that $h$ is already added by the partial order $\PP_1=\Fn(I,\omega)$.

Now, since $\PP_1\cong\Fn(\omega,\omega)$, by we have that $h$ does not dominate the Baire space of $V$. This is a contradiction!

Then it is easy to see that $D_N$ is dense: given $s\in\PP$ one can choose $n$ large enough so that $I_n\cap\dom(s)=\emptyset$, and then extend $s$ to $I_n$ as required. It follows that $g$ has the property that for all $N$ there exists $n\geq N$ such that $g\restriction I_n=x\restriction I_n$. This means precisely that $g$ does not lie in $\Diff_P(x)$.

For the second statement, let $Q=(J_n)$ be an interval partition and $y\in\omega^\omega$, with both $Q,y\in V[G]$. Let $\dot Q$ and $\dot y$ be $\PP$-names for $Q$ and $y$ respectively. We will recursively construct an element $x\in\omega^\omega\cap V$ which does not lie in $\Diff_Q(y)$.

To do this, first enumerate the set of pairs $\PP\times\omega$ as $\set{(p_i,N_i)\mid i\in\omega}$. We will construct $x$ as the union of approximations $x_i\in\omega^{\lt\omega}$ as follows. Assuming $x_{i-1}$ has already been defined, choose $n\gt n_i$ large enough that $J_n\gt \dom(x_{i-1})$. Using we can find $q\leq p_i$ and a fixed sequence $s$ such that $q\forces \dot y\restriction J_n=\check s$. We now define $x_i$ to be an extension of $x_{i-1}$ such that $x_i\restriction J_n=s$ too.

Finally, we let $x=\bigcup x_i$ and claim that $x\notin\Diff_Q(y)$. To see this, suppose towards a contradiction that $x\in\Diff_Q(y)$. Then by the forcing theorem we could find $p\in\PP$ and $N\in\omega$ such that $p\forces(\forall n\geq N)\;x\restriction J_n\neq y\restriction J_n$. But now if $i$ is such that $(p_i,N_i)=(p,N)$, then by construction there exists $n\geq N$ and $q\leq p$ such that $q\forces\dot y\restriction J_n=\check x\restriction J_n$. This is a contradiction, since $q$ is an extension of $p$ that forces something contrary to $p$!

Once again, the proofs of these two statements are similar to the arguments of .

We first show that $\cov(\Meager)=\kappa$. So suppose, towards a contradiction, that $\cov(\Meager)\lt\kappa$. That is, in $V[G]$ there exists a family $\mathcal F$ of meager subsets of $\omega^\omega$ such that $|\mathcal F|\lt\kappa$ and $\bigcup F=\omega^\omega$. Note that we can suppose without loss of generality that every element of $\mathcal F$ is of the form $\Diff_P(x)$.

We again claim that there is some $I\subset\kappa$ such that $|I|\lt \kappa$ and $\mathcal F$ is added by the forcing $\Fn(I,\omega)$. To see this, observe that an interval partition can be coded by its sequence of endpoints, and hence $\mathcal F$ can be coded as a subset of $\lambda\times\omega^4$. Thus we can use a nice name argument as in the proof of to find $I$ as required.

Now let $\PP_1=\Fn(I,\omega)$, $G_1=G\cap\PP_1$, $\PP_2=\Fn(\kappa\smallsetminus I,\omega)$, and $G_2=G\cap\PP_2$. Then the covering family $\mathcal F$ lies in $V[G_1]$. But now by , $g_2=\bigcup G_2$ does not lie in any set of the form $\Diff_P(x)$ of $V[G_1]$, a contradiction.

To show that $\non(\Meager)=\aleph_1$, it suffices to show that $\omega^\omega\cap V$ itself remains nonmeager in $V[G]$. So suppose to the contrary that $\omega^\omega\cap V$ is meager in $V[G]$. Then there exist some $Q,y\in V[G]$ such that $\omega^\omega\cap V\subset\Diff_Q(y)$.

Using a nice name argument, we can as usual suppose that the countable objects $Q$ and $y$ are added by a countable fragment of the forcing $\PP_1=\Fn(I,\omega)$. But now $\omega^\omega\cap V$ is becomes meager after forcing with $\PP_1$, contradicting .

First suppose that $A$ is open, that is, has the form $A=\bigcup_nV_{s_n}$, and assume that $A$ is conull. Then the set

is dense: any nonnull $B$ has nonnull intersection with some $V_{s_n}$ and therefore $[B\cap V_{s_n}]$ is an element of $\PP$ which lies in $D$. Since $G$ is generic, there is some $n$ such that $[V_{s_n}]$ lies in $G$. By definition of $g$, it follows that $g\in V_{s_n}$ and therefore $g\in A$.

Now suppose that $A$ is $G_\delta$, so $A$ has the form $\bigcap_m\bigcup_nV_{s_{n,m}}$, and that $A$ is conull. Then each of the sets $A_m=\bigcup_nV_{s_{n,m}}$ is conull too. By the previous argument, $g$ lies in $A_m$ for all $m$. Thus $g\in A$, as desired.

Finally if $A$ is null then $A^c$ has the form $\bigcup_m\bigcap_nV_{s_{n,m}}$ and $A^c$ is conull. By a similar dense set argument, one of the sets $A_m=\bigcap_nV_{s_{n,m}}$ must satisfy $[A_m]\in G$. Thus for this $m$ we have that for all $n$, $[V_{s_{n,m}}]\in G$ and hence $g\in V_{s_{n,m}}$. Therefore we have that for some $m$, $g\in A_m$, in other words, $g\in A^c$.

We first claim that $\PP$ is ccc, and hence $\kappa$ remains a cardinal in $V[G]$. To see this, first note that two elements $[A],[B]$ of $\Nonnull(2^\kappa)$ are incompatible if and only if $A\cap B$ is null. Thus it suffices to show that if $\mathcal F$ is a family pairwise disjoint, nonnull subsets of $2^\kappa$, then $\mathcal F$ is countable. For this, since the full space $2^\kappa$ has measure $1$, for each $n$ there can be just finitely many elements of $\mathcal F$ of measure $\geq1/n$. It follows that there can be just countably many elements of $\mathcal F$ in total, and so $\PP$ is ccc.

Next, we claim that $\PP$ adds $\kappa$ many distinct elements to $2^\omega$. First, by the definition given above in the case of $\Nonnull(2^\omega)$, we can use $G$ to define a corresponding function $g\in2^\kappa$. We then define a family of $\kappa$ many elements of $2^\omega$ by letting $g_\alpha(n)=g(\alpha+n)$ for every limit ordinal $\alpha\lt\kappa$. Then the $g_\alpha$ are pairwise distinct because this happens with probability one. More percisely, for any distinct limit ordinals $\alpha,\beta\lt\kappa$ let

Then $A_{\alpha,\beta}$ is $G_\delta$ and null. To see that it is null, note that $A_{\alpha,\beta}$ is the intersection of the independent events

Since each of these events has probability $1/2$, we have $m(A_{\alpha,\beta})=\prod_n\frac12=0$ and so $A_{\alpha,\beta}$ is null. It now follows from that $g$ lies in the complement of $A_{\alpha,\beta}$ (interpreted in $V[G]$) and therefore that $g_\alpha\neq g_\beta$.

We can now conclude that in $V[G]$ we have $\mathfrak c\geq\kappa$. Finally by the nice name argument of , it is also easy to argue that $\mathfrak c\leq\kappa$.

It suffices to define a function $f$ in $V$ with the property that for every $p\in\PP$ there exists $q\leq p$ such that $q\forces(\forall n)\;\dot h(n)\leq\check f(n)$. Indeed, if this is the case then the set of such $q$ is dense, and so there is such a $q$ in $G$. Then by the forcing theorem we will have that $V[G]$ satisfies $h\leq f$.

For each fixed $n\in\omega$, we define $f(n)$ as follows. For each $m$, let $p_m\leq p$ be such that $p_m\forces\dot h\in\omega^\omega\wedge\dot h(\check n)=\check m$. If there is no such $p_m$, simply let $p_m=[\emptyset]$. Then the collection of $p_m$ is pairwise incompatible, or in terms of representing sets, pairwise disjoint. Letting $p'=\bigcup p_m$, choose $f(n)$ to be large enough so that the measure of $q_n=\bigcup_{m\leq f(n)}p_m$ is at least $(1-2^{-n-2})m(p)$.

Now clearly $q_n\forces\dot h(\check n)\leq\check f(\check n)$. Therefore, if $q=\bigcap q_n$ then $q\forces(\forall n)\;\dot h(n)\leq\check f(n)$ as desired. However, we must check that $q$ is not null, and this follows from our choice of the $f(n)$:

It follows that $m(q)\gt 0$, and this completes the proof.

By the previous lemma, the ground model $V\cap\omega^\omega$ is a dominating family of size $\aleph_1$ in $V[G]$.

The proofs are analogous to the proofs of the two equalities in . To show that $\cov(\Null)=\kappa$, assume to the contrary that $\cov(\Null)\lt\kappa$. Then there exists a cardinal $\lambda\lt\kappa$ and a family $\mathcal F$ of null sets such that $|\mathcal F|=\lambda$ and $\bigcup F=2^\omega$.

Since every null set is contained in a null $G_\delta$ set, we can suppose that every element of $\mathcal F$ is a $G_\delta$ set. Thus every $A\in\mathcal F$ has a code, which is a countable collection binary sequences on a finite subset of $\kappa$. Using a now-familiar nice name argument, we can find a set $I\subset\kappa$ with $|I|=\lambda$ such that if $\PP_1=\Nonnull(2^I)$ and $G_1$ is as above, then the codes for all elements of $\mathcal F$ appear in $V[G_1]$.

But now, the forcing $\PP_2$ adds a random real $g$. By we know that $g$ does not lie in any null set coded in $V[G_1]$. This contradicts that $\mathcal F$ is a covering family in $V[G]$.

To see that $\non(\Null)=\aleph_1$, one can argue that the ground model reals form a nonnull set in the forcing extension. Alternatively we may let $g_\alpha$ be the sequence of random reals added by the forcing, and show that the set $\mathcal F=\set{g_\alpha\mid\alpha\lt\omega_1}$ is nonnull in $V[G]$.

For this, suppose to the contrary that $\mathcal F$ is null. Then there is some $G_\delta$ null set $A$ such that $\mathcal F\subset A$. Once again using a nice name argument, we can find a countable set $I\subset\kappa$ such that if $\PP_1=\Nonnull(2^I)$ and $G_1$ is as above, then $c$ appears in $V[G_1]$.

Finally, since $\mathcal F$ is uncountable we can find some element $g_\alpha\in\mathcal F$ which is not added by $\PP_1$, and instead added over $V[G_1]$ by the forcing $\PP_2$. Once again using , since $A$ is a null $G_\delta$ set in $V[G_1]$ we have that $g_\alpha$ lies in the complement of $A^*$. In particular, $g_\alpha$ doesn't lie in $\mathcal F$, a contradiction.