# 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. –  Andres 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