# Platonic Truth and 1st Order Predicate Logic

Consider the following simple example as motivation for my question. If it were the case that, say, the Riemann hypothesis turned out to be independent of ZFC, I have no doubt it would be accepted by many as a new axiom (or some stronger principle which implied it). This is because we intuitively think that if we cannot find a zero off of the half-line, then there is no zero off the half-line. It just doesn't "really" exist.

Similarly, if Goldbach's conjecture is independent of ZFC, we would accept it as true as well, because we could never find any counter-examples.

However, is there any reason we should suppose that adding these two independent statements as axioms leads to a consistent system? Yes, because we have the "standard model" of the natural numbers (assuming sufficient consistency).

But can this Platonic line of thinking work in a first-order way, for any theory? Or is it specific to the natural numbers, and its second-order model?

In other words, let $T$ be a (countable, effectively enumerable) theory of first-order predicate logic. Define ${\rm Plato}(T)$ to be the theory obtained from $T$ by adjoining statements $p$ such that: $p:=\forall x\ \varphi(x)$ where $\varphi(x)$ is a sentence with $x$ a free-variable (and the only one) and $\forall x\ \varphi(x)$ is independent of $T$. Does ${\rm Plato}(T)$ have a model? Is it consistent?

The motivation for my question is that, as an algebraist, I have a very strong intuition that if you cannot construct a counter-example then there is no counter-example and the corresponding universal statement is "true" (for the given universe of discourse). In particular, I'm thinking of the Whitehead problem, which was shown by Shelah to be independent of ZFC. From an algebraic point of view, this seems to suggest that Whitehead's problem has a positive solution, since you cannot really find a counter-example to the claim. But does adding the axiom "there is no counter-example to the Whitehead problem" disallow similar new axioms for other independent statements? Or can this all be done in a consistent way, as if there really is a Platonic reality out there (even if we cannot completely touch it, or describe it)?

The phenomenon accords more strongly with your philosophical explanation if you ask also that the sentences have complexity $\Pi^0_1$. That is, the universal statement $\forall x\ \varphi(x)$ should have $\varphi(x)$ involving only bounded quantifiers, so that we can check $\varphi(x)$ for any particular $x$ in finite time. If you drop that requirement, there are some easy counterexamples, hinted at or given already in the comments and other answers.

But meanwhile, even in the case you require $\varphi(x)$ to have only bounded quantifiers, there is still a counterexample.

Theorem. If $\newcommand\PA{\text{PA}}\newcommand\Con{\text{Con}}\PA$ is consistent, then there is a consistent theory $T$ extending $\PA$ with two $\Pi^0_1$ sentences $$\forall x\ \varphi(x)$$ $$\forall x\ \psi(x)$$ both of which are consistent with and independent of $T$, but which are not jointly consistent with $T$.

Proof. Let $T$ be the theory $\PA+\neg\Con(\PA)$, which is consistent if $\PA$ is consistent. Let $\rho$ be the Rosser sentence of this theory, which asserts that the first proof in $T$ of $\rho$ comes only after the first proof of $\neg\rho$ (see also my discussion of the Rosser tree). Our two $\Pi^0_1$ sentences are:

• every proof of $\rho$ from $T$ has a smaller proof of $\neg\rho$.
• every proof of $\neg\rho$ from $T$ has a smaller proof in $T$ of $\rho$.

The first statement is equivalent to $\rho$, and the second is equivalent over $T$ to $\neg\rho$, since $T$ proves that every statement is provable; the only question is which proof comes first. So both statements are consistent with $T$.

But the sentences are not jointly consistent with $T$, since in any model of $T$, both $\rho$ and $\neg\rho$ are provable from $T$, and so one of the proofs has to come first. QED

• This is excellent. I have two follow-up questions. First, after clicking on the link to "Rosser sentence", in the discussion they define a provability predicate using an unbounded existential quantifier. So why are your two sentences $\Pi_1^0$ rather than $\Pi_2^0$? Second, is ${\bf ZFC}$ $\Sigma_1^0$-complete like ${\rm PA}$, or is it like the theory $T$ above? (I couldn't find anything quickly googling). Commented Dec 27, 2016 at 22:05
• To ask if a given statement is provable, there is an unbounded existential ("there is a proof..."). But my statements are talking about the proofs themselves, not the provable statements. So $\rho$ is equivalent to: $\forall x$, if $x$ is a proof of $\rho$, then $\exists y<x$ such that $y$ is a proof of $\neg\rho$. This existential quantifier on $y$ is bounded by $x$, so it is still $\Pi^0_1$. Commented Dec 27, 2016 at 22:08
• Regarding your second statement, yes, ZFC proves all true $\Sigma^0_1$ assertions, just like PA. But my theory $T$ is not $\Sigma^0_1$-sound, since it proves $\neg\Con(\PA)$, which is not true. So this is a possible line of philosophical objection to my theorem, since it is talking about a theory $T$ that you may find reason to reject. So, the philosophical/mathematical question becomes: what exactly are the grounds you might adopt for accepting rejecting theories like this? Commented Dec 27, 2016 at 22:11
• I figured out what I was misunderstanding. Thanks for being patient with me. Commented Dec 28, 2016 at 2:42
• @PayamSeraji It isn't equivalent in PA, but it is equivalent in PA+$\neg$Con(PA). This is why I work over that theory. Commented Dec 31, 2016 at 20:43

This post is not an answer to your question, but it explains the reason that if $$\bf GC$$ (or $$\bf RH$$) is independent of $$\bf ZFC$$, $$\bf GC$$ (or $$\bf RH$$) is true in the standard model of natural numbers.

The reason is $$\bf GC$$ and $$\bf RH$$ are $$\Pi_1$$ sentences in the language of arithmetic.

Def.

1. $$x|y := \exists z(z \leq y \land x\cdot z = y)$$
2. $$Pr(x) := \forall y(y0 \land y|x \to y=1)$$

Therefor $$\bf GC$$ can be defined by $$\forall x\exists y,z(y+z = 2\cdot x+4 \land Pr(y) \land \Pr(z))$$ which is a $$\Pi_1$$ sentence. For $$\Pi_1$$ definition of $$\bf RH$$ see here.

Let $$\phi(x)$$ be a $$\Delta_0$$ formula and suppose $${\bf PA} \nvdash \exists x \neg \phi(x)$$, then $$\mathbb{N}\models \forall x \phi(x)$$. This is true because of $$\Sigma_1$$ completeness of $${\bf PA}$$, that is if $$\psi$$ be a $$\Sigma_1$$ sentence, then $$\mathbb{N}\models \psi$$ iff $${\bf PA}\vdash \psi$$.

The important thing in this argument is $$\Pi_1$$ definability of problem. For example consistency of $$\bf PA$$ is a $$\Pi_1$$ sentence and by second incompleteness theorem, $${\bf PA} \nvdash Con_{\bf PA}$$, but $$\mathbb{N}\not\models \neg Con_{\bf PA}$$, therefore we can not prove similar theorems for formulas in another level of Arithmetical Hierarchy except $$\Pi_1$$.

• Erfan, actually this is getting at the heart of my question. Thanks. Commented Dec 27, 2016 at 21:55
• @PaceNielsen: you are welcome :-) Commented Dec 27, 2016 at 21:58

It cannot be done in a consistent way.

Consider a closed statement $\psi$ which is independent of a theory $T$, and take $\forall x . \psi$ and $\forall x . \lnot\psi$. (I made the closed statement have a dummy free variable to satisfy your condition.) Both statements are of the kind you are asking for, but when we add both to $T$ we get an inconsistent theory.

It should be clear that one can come up with examples where the two sentences that contradict each other are not so blatantly in opposition with each other. And with a bit of work we can even come up with examples where the free variable $x$ is doing something.

• For such examples, one can consider on one side AC which is known to be independent from ZF, and can be expressed as a non trivial $\forall x, \phi(x)$ sentence (i.e. $x$ actually "does something"), and the other side an axiom such as "every set of reals is Lebesgue-measurable", or the axiom of determinacy which (under certain large cardinal assumptions) are known to be independent from ZF, and can also be expressed as a non trivial $\forall x, \psi(x)$ sentence. It is known that these two sentences are contradictory with one another. Commented Dec 27, 2016 at 20:55
• @AndrejBauer The same argument you gave would apply equally well to the natural numbers. Thus, I suppose my assumptions about the types of statements $p$ we would add to the theory $T$ were not sufficiently strong. What is it about the type of sentence RH consists of that allows us to say "If RH is independent of PA, then RH is true"? Then modify my question, accordingly. Commented Dec 27, 2016 at 21:39
• Erfan, just answered that question. Go ahead and limit the $p$'s to $\Pi_1$ statements. Commented Dec 27, 2016 at 21:52

By definition, if a sentence $\phi$ is independent from the theory $T$, then both $T + \phi$ and $T+\neg \phi$ are coherent. Gödel's completeness theorem shows that if a theory is coherent, then it is consistent, meaning there is a model that satisfies it. In less technical terms, if you cannot derive a contradiction from an axiom system, then there is a possible word in which this axiom system is satisfied. So if for example RH happened to be independent from ZFC, then you could add RH as an axiom to ZFC to obtain, say, ZFCR, and as long as ZFC is consistent, so is ZFCR (but also, ZFC+$\neg RH$ would be consistent). So to answer your question about $Plato(T)$: if $T$ has a model, $T$ does not prove $\neg p$, then $T+p =Plato(T)$ has a model. This has nothing to do with the integers. But of course, adding new axioms will change the statements that are independent. Maybe $ZFC + RH \vdash CH$, for instance, whereas ZFC alone doesn't.

EDIT: As has been pointed out in the comments below, $Plato(T)$ is obtained by adding all statements $p$ such that ... If you consider this rather than what I've considered before, then obviously $Plato(T)$ is inconsistent : consider $\phi(x)$ with only free variable $x$ such that $\forall x, \phi(x)$ is independent from $T$. Then you consider $\psi(y) := (\exists x, \neg \phi(x))\land (y=y)$ which is a formula with only free variable $y$, and is such that $\forall y, \psi(y)$ is independent from $T$. Then $Plato(T)$ contains both $\forall x, \phi(x)$ and $\forall y, \psi(y)$, from which you can derive $\exists x, \neg \phi(x)$, which is an immediate contradiction.

• I think $Plato(T)$ is the set of all such $p$ and the question is about the consistency of all $p$ together. Commented Dec 27, 2016 at 19:11