9
$\begingroup$

I want to think of ZFC as not fully determining the powerset of the naturals, because you can add subsets with forcing and otherwise have a lot of control over the cardinality of the powerset of the naturals. But that suggests the question: what subsets does ZFC determine? There is also the related question: how complicated are the sets added by forcing?

Since Turing machines are absolute, models of ZFC should have the same hyperarithmetical sets. So $\Delta_1^1$ is absolute.

Can Cohen forcing add a $\Pi_1^1$ set? If not, what is the descriptive complexity of sets added by Cohen forcing?

This isn't my field so I apologize if this question is ill formed or naive. References would also be appreciated.

Edit: I'm specifically interested in where a set/real $c$ added by forcing fits into the lightface hierarchy.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Do you know Shoenfield's absoluteness theorem? $\endgroup$
    – Asaf Karagila ♦
    Commented Nov 30, 2016 at 12:09
  • $\begingroup$ I am vaguely aware of it and I just looked it up. So forcing should not add $\Pi_2^1$ sets, and maybe $\Sigma_3^1$ sets? Then what sets does/can it add? $\endgroup$
    – fhyve
    Commented Nov 30, 2016 at 20:51

3 Answers 3

Reset to default
12
$\begingroup$

Since Cohen forcing is weakly homogeneous, all hereditarily ordinal definable sets in the Cohen extension are already in the ground model. That applies in particular to any ordinal definable real, and (in even more particular) to any real with a lightface $\Sigma^m_n$ definition.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ +1. For the OP, here's an outline of how this is shown: suppose $\nu$ was a name for an OD real in the generic extension. (That is, it is forced that $\nu$ is defined by some formula $\varphi$ with ordinal parameters.) Suppose $p$ is some condition forcing $k\in \nu$ ($k$ some natural number). Then $p$ forces "The unique real satisfying $\varphi$ contains $k$." Now suppose $q$ were any other condition which forced $k\not\in \nu$. By homogeneity, we can find generics $G\ni p, H\ni q$ yielding the same forcing extension: $V[G]=V[H]$. (cont'd) $\endgroup$
    – Noah Schweber
    Commented Nov 30, 2016 at 22:02
  • 2
    $\begingroup$ But $V[H]$ satisfies "The unique real satisfying $\varphi$ does not contain $k$" - note that since the ordinals of $V[G]$ and $V[H]$ agree (being those of $V$), this is really the same sentence as the opposite one satisfied by $V[G]$. And that's a contradiction. So we can define the real $\nu$ names as "The set of all $k$ such that some condition forces $k\in\nu$" (this uses that the forcing relation is appropriately definable), and so the real named by $\nu$ in fact exists in $V$ already. $\endgroup$
    – Noah Schweber
    Commented Nov 30, 2016 at 22:03
8
$\begingroup$

Jensen proved in this paper that, beginning with $V = L$, it is possible to add a real $a$ by forcing such that $a$ is $\Delta^1_3$ in $L[a]$.

This result is the best possible, in the sense that one can never add $\Sigma^1_2$ or $\Pi^1_2$ reals by forcing. This follows from Shoenfield's Absoluteness Theorem (mentioned already by Asaf in the comments). In fact, Shoenfield's theorem implies that all $\Sigma^1_2$ and $\Pi^1_2$ reals are constructible; so they can't be added by forcing because they're already in the ground model. (For a proof, see Theorem 25.20 and Corollary 25.21 in Jech's book).

I do not know whether anyone has improved on Jensen's result to show that a $\Delta^1_3$ real can be added to any ground model by forcing.

Jensen's forcing is a bit difficult to understand. For an easier-to-understand example of a non-constructible $\Delta^1_3$ real, there is $0^\sharp$. Even if $0^\sharp$ does exist (which is not provable in ZFC -- it is a large cardinal axiom), it cannot be added by any set-sized notion of forcing. So $0^\sharp$ does not answer your question, but it seems related, so I thought I'd share.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Also, in case you can't access Jensen's paper, Jech discusses this result in chapter 28 of his book (which is how I know about it). $\endgroup$
    – Will Brian
    Commented Nov 30, 2016 at 20:56
  • $\begingroup$ Note, however, that this isn't Cohen forcing. And indeed, Cohen forcing can do no such thing, as Andreas states. $\endgroup$
    – Noah Schweber
    Commented Nov 30, 2016 at 22:00
  • $\begingroup$ @NoahSchweber: Yes, that's right. I'm just pointing out that, even though Cohen forcing won't add projective reals, there are other forcings that will (at least with the right ground model). (Notice that, even though the title just refers to Cohen forcing, the OP does ask about arbitrary forcings in the first paragraph.) $\endgroup$
    – Will Brian
    Commented Nov 30, 2016 at 22:03
  • $\begingroup$ Oh, indeed, that wasn't meant as criticism, just elaboration for the OP - I wanted to clarify the relation between your answer and the Cohen-specific case. (I +1'ed, by the way.) $\endgroup$
    – Noah Schweber
    Commented Nov 30, 2016 at 22:05
  • $\begingroup$ Maybe I shouldn't have said Cohen in particular. Cohen forcing is what I'm (vaguely) familiar with. Can you go any lower than $/Delta_3^1$? $\endgroup$
    – fhyve
    Commented Dec 1, 2016 at 7:12
7
$\begingroup$

Cohen forcing (or any forcing adding a new real) adds new boldface sets on all levels. For example, if $c$ is the Cohen real, then $\{c\}$ is a new closed set.

Lightface sets may change. For example, the set of all nonconstructible reals has a $\Pi^1_2$ definition; this definition $\varphi(x)$ defines a set $A_\varphi=\{x: \varphi(x)\}$ in every model, but these sets are in general not equal; for example, $A_\varphi$ is empty in $L$, and nonempty everywhere else, e.g. in any Cohen extension.

(For a more trivial example, the set $\mathbb R $ changes whenever you add reals. The set $\mathbb R^{V[c]}$ is a "new" set in the Cohen extension. In fact, any perfect set will "change" in this way. This is probably not what you meant.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm interested in the lightface hierarchy and arithmetic. $c$ is also a subset of the natural numbers by the obvious bijection with the reals. Where does it fit in the lightface hierarchy? $\endgroup$
    – fhyve
    Commented Nov 30, 2016 at 20:49
  • 4
    $\begingroup$ Nowhere, I think. It is not even ordinal definable. $\endgroup$
    – Goldstern
    Commented Nov 30, 2016 at 20:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .