22
$\begingroup$

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)?

$\endgroup$
0

5 Answers 5

19
$\begingroup$

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

$\endgroup$
16
  • $\begingroup$ 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). $\endgroup$ Dec 27, 2016 at 22:05
  • 2
    $\begingroup$ 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$. $\endgroup$ Dec 27, 2016 at 22:08
  • 2
    $\begingroup$ 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? $\endgroup$ Dec 27, 2016 at 22:11
  • 3
    $\begingroup$ I figured out what I was misunderstanding. Thanks for being patient with me. $\endgroup$ Dec 28, 2016 at 2:42
  • 1
    $\begingroup$ @PayamSeraji It isn't equivalent in PA, but it is equivalent in PA+$\neg$Con(PA). This is why I work over that theory. $\endgroup$ Dec 31, 2016 at 20:43
8
$\begingroup$

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(y<x\land y>0 \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$.

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

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Dec 27, 2016 at 20:55
  • $\begingroup$ @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. $\endgroup$ Dec 27, 2016 at 21:39
  • $\begingroup$ Erfan, just answered that question. Go ahead and limit the $p$'s to $\Pi_1$ statements. $\endgroup$ Dec 27, 2016 at 21:52
1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ I think $Plato(T)$ is the set of all such $p$ and the question is about the consistency of all $p$ together. $\endgroup$ Dec 27, 2016 at 19:11
  • $\begingroup$ Oh my bad, I had read that wrong. Let me edit my answer $\endgroup$ Dec 27, 2016 at 19:21
1
$\begingroup$

My poor understanding of Platonism, as a philosophy of mathematics, is that there is a common universe composed of pure thought, representing a collection of idealized objects, about which people can reason and discover (not invent!) new relationships and previously unconceived objects. For example, any arrangement of perfect spheres that can be imagined exists in this universe. By discussion, one "projects" these idealisations into our real universe to model our perceptions of what (barring solipsism, we presume) is our common reality.

I mention this because I see model theory as an applied form of Platonism in the small. When one decides to work with a definable piece of the idealized universe one can specify the domain of objects and the allowed basic operations and relations and then work through or deduce all the desired or at least conceptually feasible combinations and arrangements of these. In particular, if you have a theory T and a statement q in the same language that is independent of T, then T with q is another theory, and since q was independent of T, both T and T with q are theories that share a model. However, if we pick p and q, both can be individually independent from T, but p and q may separately restrict the collection of models into two disjoint parts, and there may be no model shared by T and p and by T and q. So it is possible (and likely) that Plato(T) does not have a model, as Plato(T) may include both statements p and q. You may feel sure that RH and Goldbach both have the natural numbers (and other structures) as a model; I am not so confident. Put another way, I have my reason for believing that it is possible there is no such model.

I am rusty on the technical detail, but I believe there is something like the Lindenbaum algebra (LA) for realizable types inside a given first order language L, that one element of this (thing which resembles a Boolean) algebra represents (up to logical equivalence or some other equivalence) the given axioms for some effective theory T of which the natural numbers is a model, that there are a continuum of elements which represent completions (or extensions) of T, and that only one of them is Nat(T), the complete first-order theory of the natural numbers. There are many members which represent large subsets of Plato(T), but I am not convinced that there is even one member that represents T with p and q, with T a standard effective first-order axiomatization of the naturals, p an appropriate equivalent version of the Riemann hypothesis, and q an equivalent version of Goldbach.

In addition to (whatever it is that corresponds to Lindenbaum algebras that escapes me for realizing types), there is the notion of prime model, which gets at part of your post and says something like "if there is a sentence p of a special form which is independent of T, then p must be true in the naturals because the naturals are a prime model of T". Since you are using ZFC for one part of your post and the natural numbers (whose theories are expressed using a different language and axiom system, say first order Peano Arithmetic) in another part, people may conflate the two and assume the naturals are a prime model for ZFC: the naturals are a prime model for (a version of) PA, not for ZFC. To get at your notion properly ( as well as the LA notion above), one needs to fix a first order language and recast RH and GC into appropriate versions in that language, and consider things modulo logical equivalence. I apologize for not recalling of the details.

Gerhard " Hasn't Had Enough Eggnog Yet" Paseman, 2016.12.27.

$\endgroup$
1
  • $\begingroup$ When you say "I am not so confident" I actually feel the same way. Hence, when people assert "Goedel's unprovable sentence is true" even though it is independent of PA, that surprises me. Perhaps Goedel's sentence is sufficiently different than what I used in my post, to merit the claim of truth. $\endgroup$ Dec 27, 2016 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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