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

  • 1
    $\begingroup$ If $L$ is the smallest inner model, how can that even be possible? $\endgroup$ – Asaf Karagila May 2 at 7:54
  • $\begingroup$ @AsafKaragila What does $L$ being the smallest inner model have to do with anything? $\endgroup$ – Keshav Srinivasan May 2 at 13:01
  • 2
    $\begingroup$ Any subsets of $\Bbb N$ in $L$ are also subsets of $\Bbb N$ in the actual universe. If $L$ cannot capture all the subsets of $\Bbb N$ in the first transfinite step of the constructible hierarchy, what hope do larger class-models have? $\endgroup$ – Asaf Karagila May 2 at 13:02
  • 1
    $\begingroup$ @KeshavSrinivasan Elaborating on Asaf's comment: 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$.) $\endgroup$ – Noah Schweber May 2 at 13:58
  • $\begingroup$ For all "small" countable ordinals $\alpha$ (certainly for all $\alpha<\varepsilon_0$, for instance, in particular for $\alpha=\omega+1$) you can exhibit explicit sets of natural numbers that are in $L$ but first appear at $L_{\alpha+1}$, which gives you an explicit counterexample to the claim that $\mathcal P(\omega)\subset L_\alpha$. $\endgroup$ – Andrés E. Caicedo May 2 at 20:56

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.


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

  • $\begingroup$ Do you know what exact axioms are used to prove that $L_{\omega+1}$ is countable? $\endgroup$ – Keshav Srinivasan May 2 at 11:59
  • $\begingroup$ @KeshavSrinivasan Few enough that it doesn't seem a good question. In particular, note that there's an obvious surjection from $\omega\times L_\omega$ to $L_{\omega+1}$ which you can define as long as you can talk about theories of structures, and the Ackermann interpretation gives an as-concrete-as-imaginable bijection between $L_\omega$ and $\omega$. In particular, KP + infinity is already overkill. $\endgroup$ – Noah Schweber May 2 at 12:32
  • $\begingroup$ The body of your question, though, rephrases things even more simply: you ask whether it's consistent that every set of naturals is arithmetic. Well, it's easy to show that if the theory of $(\mathbb{N};+,\times)$ exists, then it's not arithmetic, so again as soon as you can talk about the set of natural numbers and can talk about theories of structures that's already too much. So it's really impossible to escape this without killing so much of set theory that I'm not sure what's left. $\endgroup$ – Noah Schweber May 2 at 12:36
  • $\begingroup$ @NoahSchweber What about Zermelo set theory, i.e. ZF without replacement? Does that suffice that $P(\mathbb{N}$ contains things other than arithmetical subsets? And what do you mean by “if the theory of $(ℕ;+,×)$ exists, then it's not arithmetic”? $\endgroup$ – Keshav Srinivasan May 2 at 13:00
  • $\begingroup$ @KeshavSrinivasan I'm not sure what your last question means. The theory of $(\mathbb{N}; +,\times)$ is the set of Godel numbers of sentences $\varphi$ such that $(\mathbb{N}; +,\times)\models\varphi$. This is definable in set theory (indeed, we can uniformly define truth of set-sized structures), and we can prove that, if it exists, it's not arithmetic. $\endgroup$ – Noah Schweber May 2 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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