Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I was reading a paper by David Marker, whose main theorem was that if $T$ is a first-order theory which is not small, then $F_2\leq_B \cong_T$. That's not especially relevant to the question at hand, except to point out that it comes with no set-theoretic hypotheses and no "it is consistent that..." hedging. So the techniques involved shouldn't involve forcing without some sort of explanation and/or absoluteness argument, I would expect.

Anyway, along the way we have the following lemma:

For any countable set of Borel functions $\mathcal{F}$, there is a perfect $\mathcal{F}$-independent set.

Note here he's talking about functions on and subsets of Cantor space, so it should be applicable to any uncountable Polish space. The supplied proof is the following (verbatim):

If $P$ is a perfect set of suitably generic Cohen reals, then $P$ is $\mathcal{F}$-independent.

Now, I have no problem believing the lemma is true- there are a lot of reals, they tend to be transcendental over each other, and so on. But I have no idea what the proof means. When someone says "Cohen reals," my first thought is to say we can force this to be true, which feels believable, but that doesn't seem to be what he's saying.

So I have two questions.

  1. What is meant by "Cohen reals" in this context?
  2. How can we guarantee there is a perfect set of "suitably generic" ones?

I would be happy with a citation, too; no need to type out five pages of math if there's a published source out there that does a good job. But Google and my own math experience are giving me the same (unhelpful) answer.

Note: A set $I$ is said to be $\mathcal{F}$-indepedent if, for all $A\subseteq I$, $cl_{\mathcal{F}}(A)\cap I=A$.

That is, given some elements of $I$, and all the functions of $\mathcal{F}$, you can't get any new elements of $I$ just by using terms from $\mathcal{F}$. We are not concerned with any other notions of independence or closure (be they model-theoretic or topological).

share|improve this question
add comment

2 Answers 2

up vote 7 down vote accepted

A Cohen generic real, over a model $M$ of set theory, is an infinite binary sequence $g$ whose initial segments get eventually inside any dense set $D$ of finite sequences with $D\in M$. (The set $D$ is dense, if it contains extensions of any given finite sequence.)

When one speaks informally about "sufficiently generic" Cohen reals, without forcing, what is meant is that the sequence has initial segments that are elements of a lot of particularly relevant dense sets. Such generic sequences are often constructed by the following procedure: first, one enumerates the "requirements", which correspond to having certain initial segments (where any finite sequence can be extended to one meeting the requirement), and thus correspond to certain dense sets $D_0,D_1,\ldots$. Next, one constructs an infinite sequence by successively meeting the requirements, one after the next. Thus, one constructs a sequence that is generic with respect to those dense sets and meets all the requirements.

In your case, since you aim to have a perfect set of reals, one constructs the tree, whose branches will be the desired perfect set. You build your tree by finite initial segments, such that at a given level, the nodes are extended in such a way so as to meet the next requirement for its paths. In this way, the branches through the tree will satisfy all the requirements. The key idea will be to design the requirements on the collection of finite trees, so that every finite tree can be top-extended to a tree meeting that particular requirement. In your case, the requirements will correspond to the functions and particular finite nodes currently at the top of the tree we are building---we want to extend those nodes and a target node so that the function value is sufficiently determined and different from the value of the target. In this way, we gradually build up the tree, so that its paths have the desired property for each instance of independence. The main point is that you will have only countably many requirements to meet, and thus only countably many dense sets.

This kind of argument is pervasive in computability theory, and he method can be used as Liang Yu suggests to build perfect sets exhibiting many other kinds of independence.

Meanwhile, the claim becomes obvious once one has knowledge of forcing, and it is to this familiarity that Marker was presumably alluding. Specifically, if $c_0,\ldots,c_n,d$ are mutually $V$-generic Cohen reals and $f$ is a Borel function with a Borel code in $V$, then $f(c_0,\ldots,c_n)\in V[\vec c]$ and therefore cannot be equal to $d$. So mutually generic reals have the desired independence property for Borel functions coded in the ground model. Further, adding a single $V$-generic Cohen real creates a perfect set of finitely mutually generic Cohen reals. So the desired perfect set exists in $V[c]$. But the assertion that there is such a perfect set has complexity $\Sigma^1_2$, and thus is absolute to $V$ by the Shoenfield absoluteness theorem. So you had the desired perfect set already without forcing.

This is a general argument method that works for many constructions in computability theory---one simply argues that fully generic Cohen reals (or Sacks reals, or random reals, or reals generic for some other kind of forcing) have the desired property, and then appeals to absoluteness to get such reals in the original universe.

share|improve this answer
Another way to use knowledge of forcing, without needing Shoenfield absoluteness, is to add Cohen-generic reals over a countable elementary submodel of $V$ (or some big piece of $V$ to be really honest) that contains codes for the countably many Borel functions in $\mathcal F$. –  Andreas Blass Jun 4 at 14:41
add comment

This is essentially a recursion theoretic question. Just check how to use Cohen forcing to construct a perfect set of independent hyperarithmetic degrees. (See higher recursion theory of Sacks) Then relativize the proof to the family $\mathcal{F}$.

Or even simpler, just construct a perfect set of independent Turing degrees. Then relativize it to some oracle in which the hyperjump of every function in $\mathcal{F}$ is recursive.

share|improve this answer
add comment

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.