MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.


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).


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.

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
Glad I could help. – Andrés 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.