Is it consistent for $P(\mathbb{N})$ to be present in a low layer of the Constructible Universe?

Question

$ZF+V=L$ implies that $P(\mathbb{N})$, the power set of the set of natural numbers, is a subset of $L_{\omega_1}$. But my question is, is it consistent with $ZF$ if $P(\mathbb{N})$ is a subset of $L_{\omega+1}$, i.e. the only subsets of $\mathbb{N}$ are arithmetical sets? Most mathematicians would definitely think it’s a false statement, but is it inconsistent with either $ZF$ or $ZFC$?

The reason I ask is that this is basically Bertrand Russell’s Axiom of Reducibility.

Answer 1

Let me compile my comments into an answer. I'll first explain (elaborating on Asaf's comment) why every model of ZF contains (things it thinks are) sets of naturals which (it thinks) have $L$-rank arbitrarily high below $\omega_1$. Then I'll talk about the relevant axiomatic strength.

---

If $M$ is a model of ZF, then $L^M$ is a model of ZF + V=L. So $L^M$ contains a real $r$ which $L^M$ thinks is not in $(L_{\omega+1})^M$. But clearly $r\in M$, and by absoluteness $M$ doesn't think $r\in (L_{\omega+1})^M$ either. So for any model $M$ of ZF, there is an $r\in \mathcal{P}(\mathbb{N})^M$ with $r\not\in (L_{\omega+1})^M$.

And the same argument works for any $\gamma<\omega_1^M$: if $\gamma<(\omega_1)^{L^M}$ then $L^M$ has a real $r$ it thinks has $L$-rank $>\gamma$, and this lifts to $M$.

---

Alright, so now let's talk about better logical strength bounds.

First, let me give an argument which gives a non-optimal upper bound but is rather elementary. Let $\mathcal{W}$ be the set of (indices of) computable linear orders without descending sequences. Any reasonable set theory at all (by far less than Z or KP or similar) proves that if $\mathcal{W}$ exists then it is non-arithmetic (indeed, RCA$_0$ proves this, appropriately phrased!). In particular, by Separation Zermelo set theory proves that there is a non-arithmetic set.

Unfortunately, the existence of $\mathcal{W}$ has rather high axiomatic strength; KP + Inf, for example, doesn't prove it exists. To bring things down we need to do some model theory. Inside any model of a tiny fragment of set theory - both Z and KP are already more than enough - truth for set-sized structures is definable (uniformly in the structure, even). Roughly speaking, a sentence $\varphi$ is true in $\mathcal{M}$ if there exists a family $\mathbb{F}$ of functions from finite powers of $\mathcal{M}$ to $\mathcal{M}$ which serve as Skolem functions for $\varphi$. This definition takes place (essentially) in $(\mathcal{P}(\mathcal{M}))^{<\omega}$, not in $\mathcal{M}$ itself, so we don't run up against Tarski here.

• This definition is just a piece of language; where the theory comes in is showing that $(i)$ for all $\mathcal{M}$ and $\varphi$ either $\mathcal{M}\models\varphi$ or $\mathcal{M}\models\neg\varphi$ and $(ii)$ $Th(\mathcal{M})$ (=$\{\varphi: \mathcal{M}\models\varphi\}$) exists.

Now the proof of Tarski's undefinability theorem goes through in a very very tiny fragment of ZFC, and so in particular we have that the theory of the natural numbers (as a semiring) is not arithmetic.

Answer 2

No: $L_\alpha$ is countable for any countable $\alpha$, so it cannot contain all of $P(\mathbb{N})$.