Definitions

I believe set theorists have studied all of the following three notions in the context of forcing extensions of a model of ZFC, $M$ (hopefully the terminology is the standard one).

1. A function $f:\mathbb N\rightarrow\mathbb N$ is eventually different if for each function $g:\mathbb N\rightarrow\mathbb N$, $g\in M$, the set $\{n: f(n)=g(n)\}$ is finite.

2. A real $r\in [0,1]$ is a Solovay random real if for each measure-zero subset $S$ of $\mathbb R$ with $S\in M$, we have $r\not\in S$.

3. A function $f:\mathbb N\rightarrow\mathbb N$ is dominating if for each function $g:\mathbb N\rightarrow\mathbb N$ in the ground model $M$, the set $\{n: f(n)\le g(n)\}$ is finite.

Motivation

An eventually different function that is not too fast-growing is reminiscent of a random real. Can we always use it to construct a random real? The analogous problem in computability theory was quite difficult but has been solved by Kumabe and Lewis (J. LMS, 2009).

Question

I. Is it possible to add an eventually different function to $M$ while adding neither a Solovay real nor a dominating function?

EDIT: Now stating the question in the strongest possible form, which is the one Andrés Caicedo answers below.

-

Hi Bjørn, and congratulations to you and Bonnie!

The answer to I is yes. In fact, there is a standard way of doing this, with the "eventually different forcing ${\mathbb E}$". This notion does not add random or dominating reals, and adds an eventually different function.

Conditions have the form $(s, A)$ where $s\in\omega^{<\omega}$ and $A\in[\omega^\omega]^{<\omega}$, with $(s, A)\le(s',A')$ iff $s\supseteq s'$, $A\supseteq A'$, and for all $f\in A'$ and $j\in[|s'|,|s|)$, we have $s(j)\ne f(j)$. (For me, $p\le q$ means that $p$ is stronger.)

This is a nice forcing: It is ccc, in fact, $\sigma$-centered, since any two conditions with the same first coordinate are compatible. But no $\sigma$-centered forcing adds random reals.

That ${\mathbb E}$ does not add dominating reals is a tad more work. But you can find a written proof in section 7.4.B of "Set Theory: On the structure of the real line", by Tomek Bartoszy´nski and Haim Judah. Let me know if you do not have access to a copy.

-
Glad I could help. – Andrés E. Caicedo Oct 7 '10 at 22:13
Thanks, Andrés (and similar belated congratulations), this is great. In retrospect I had seen $\mathbb E$ and the book you mention, but at least the random part is news to me. – Bjørn Kjos-Hanssen Oct 7 '10 at 22:13