2
$\begingroup$

As an algebraist, I have some strong intuitions about what it means for an algebraic result to be true. In particular, my intuition would lead me to believe that if I cannot construct a counter-example to a claim, then the claim must be true. This is what motivated my previous question, where it became clear that my intuition needed some tweaking. (In other words, in some contexts it just doesn't hold true!) The answers given there are excellent, and I recommend people read them before continuing.

So here is a follow-up question to see just how far we can take the intuition.

Let $T_0$ be the theory ${\rm PA}$ over a countable language. Let $T_1$ be the extended theory obtained by adding as new axioms all $\Pi_1^0$ statement which are independent of ${\rm PA}$. This new theory is consistent and sound, assuming that the standard model of the natural numbers exists.

I would guess that this new theory $T_1$ is already not effectively computable. At any rate, suppose now that we let $T_2$ be the extended theory of $T_1$ obtained by adding as new axioms all $\Pi_2^0$ statement which are independent of $T_1$.

Is $T_2$ consistent? If so, is the theory $T_n$ (defined in the obvious recursive way) consistent? If so, is $\bigcup_{n\in \mathbb{N}}T_n$ the true theory of the standard model?

If $T_2$ is not consistent, is there some natural way to fix the problem?

Finally, what happens if we repeat these ideas for ${\rm ZFC}$ instead?

Improve this question
$\endgroup$
2
  • $\begingroup$ Perhaps it would help clarify the question to say that you are adding all independent $\Pi^0_1$ sentences as new axioms. (The word "any" could be misunderstood as allowing you to add any such axioms you like.) $\endgroup$
    – Joel David Hamkins
    Commented Dec 28, 2016 at 17:51
  • $\begingroup$ @JoelDavidHamkins Done, thanks for the suggestion. $\endgroup$
    – Pace Nielsen
    Commented Dec 28, 2016 at 18:59

2 Answers 2

Reset to default
5
$\begingroup$

Yes, your theory is the same as the true arithmetic. In particular, yes, it is consistent.

I claim that at stage $n$, your theory $T_n$ consists of PA plus the collection of true $\Pi^0_n$ sentences (that is, true in the standard model). This starts out true with $T_0$. If $T_n$ is like that, then consider $T_{n+1}$. If $\psi$ is a true $\Pi^0_{n+1}$ statement, then in particular, it is consistent with $T_n$, since both are true in the standard model. So either it is provable from $T_n$, in which case it is already there, or else it is independent, in which case you add it at stage $n+1$. Conversely, if $\psi$ is a $\Pi^0_{n+1}$ statement that is independent of $T_n$, then in particular, it asserts $\forall x\ \phi(x)$, where $\phi(x)$ is $\Sigma_n$. Since $\psi$ is true in a model of $T_n$, it follows that $\phi(m)$ must hold of every standard $m$, since if $\phi(m)$ failed then $\neg\phi(m)$ would be a true $\Pi^0_n$ sentence and hence part of $T_n$, preventing $\psi$ from being consistent with $T_n$. So $\psi$ is true.

Thus, by induction, you are adding all and only the true $\Pi^0_n$ statements at each stage, and you've got the theory of true arithmetic.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Excellent. What happens for ZFC if we try to do the same thing? $\endgroup$
    – Pace Nielsen
    Commented Dec 28, 2016 at 18:59
  • $\begingroup$ An essentially similar argument works with ZFC, if one has a strong enough meta theory. For example, if there is an $\omega$-model of ZFC, then you are again adding the true $\Pi^0_n$ sentences of arithmetic at stage $n$. But if ZFC is not arithmetically sound, for example, in a model of ZFC+$\neg$Con(ZFC), then things will go awry already at $T_2$, giving an inconsistent theory. $\endgroup$
    – Joel David Hamkins
    Commented Dec 28, 2016 at 19:21
  • $\begingroup$ Supposing that there is an $\omega$-model of ZFC, are there any statements known to belong to $T_2$, such as $V=L$ (which, as I understand it, is equivalent to a $\Pi_2^0$ statement in KP)? If any case, what would be a good resource for me to learn more? $\endgroup$
    – Pace Nielsen
    Commented Dec 28, 2016 at 19:26
  • $\begingroup$ Oh, I may have misunderstood your proposal in the case of ZFC, since I had thought you were only adding arithmetic assertions, but $V=L$ is not arithmetic. Do you intend to add $\Pi^0_n$ statements now in the Levy hierarchy, rather than the arithmetic hiearchy? $\endgroup$
    – Joel David Hamkins
    Commented Dec 28, 2016 at 19:30
  • 2
    $\begingroup$ This last comment of mine is not quite right, if one is referring to $\Pi^0_1$ sentences in the language of set theory, in the Levy hierarchy. The reason is that every arithmetic assertion is $\Delta^0_1$ in set theory, since the arithmetic quantifiers are bounded by $\omega$. Thus, $T_1$ is already inconsistent, since we will add both the Rosser sentence and its negation. $\endgroup$
    – Joel David Hamkins
    Commented Jan 4, 2017 at 23:41
0
$\begingroup$

No. It works with T0 and Π01 sentences, as PA refutes any false Π01 sentence. But not so with T1 and Π02 sentences: there are false Π02 sentences which are independent of T1.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Although there are false $\Pi^0_2$ sentences that are independent of PA, there are no such sentences that are independent of $T_1$, and this is what I proved in my answer. If $\forall x\ \phi(x)$ is a $\Pi^0_2$ sentence that is consistent with $T_1$, then $\phi(m)$ must hold for every standard $m$, since otherwise $\neg\phi(m)$ would be a true $\Pi^0_1$ sentence, making it part of $T_1$ and preventing $\forall x\ \phi(x)$ from being consistent with $T_1$. So $\forall x\ \phi(x)$ is true. $\endgroup$
    – Joel David Hamkins
    Commented Dec 28, 2016 at 20:09
  • $\begingroup$ Hi Panu, welcome to MO. $\LaTeX$-like math formatting works here; just enclose math in $ signs. See math.stackexchange.com/help/notation for more details. $\endgroup$
    – Nate Eldredge
    Commented Dec 28, 2016 at 20:27
  • $\begingroup$ I beg to differ. There are true $\Sigma_2^0$ sentences which are not provable even in $T_1$. $\endgroup$
    – Panu Raatikainen
    Commented Jan 2, 2017 at 16:00
  • 1
    $\begingroup$ @PanuRaatikainen How is that the case? If $\varphi=\exists x\forall y\theta(x, y)$ (with $\theta$ using only bounded quantifiers) is a true $\Sigma^0_2$ sentence, then - for some numeral $n$ - the sentence "$\forall y(\theta(n, y))$" is true. But this is a true $\Pi^0_1$ sentence, hence in $T_1$ (since every $\Pi^0_1$ sentence independent of $PA$ is true). So $T_1$ proves "$\forall y(\theta(n, y))$," so $T_1$ proves "$\exists x\forall y(\theta(x, y))$." Or am I missing something? $\endgroup$
    – Noah Schweber
    Commented Jan 4, 2017 at 17:55
  • $\begingroup$ @PanuRaatikainen I've just been reminded (very circuitously) of this answer. Per my and Joel's comments, are you sure this is correct? $\endgroup$
    – Noah Schweber
    Commented Oct 7, 2019 at 19:27

You must log in to answer this question.

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