What does T+non-Cons(T) mean?

Question

I am puzzled by the following question, which is about the philosophical meaning of some axiomatic system.

Suppose that a formal axiomatic system (containing arithmetics) $T$ is consistent. Let a statement $S$, expressible within $T$, be indecidable. Then (correct me if I am wrong) both theories $T$+($S$ is true), and $T$+(non-$S$ is true) are consistent.

According to Gödel, the consistency of $T$ is expressible but indecidable within $T$. Thus it seems that the theory $T$+(non-Cons($T$)) is consistent.

What should I understand ? The above argument let me think that if $T$ is consistent, then it is not... Something must be wrong in the few lines above, but I can't see where.

Answer 1

For mathematicians of an algebraic bent it may be helpful to think of a nonstandard model of, say, Peano arithmetic as a very funny sort of ring (really a semiring), obtained by starting from $\mathbb{N}$ and adjoining some nonstandard numbers, in the same way we construct $\mathbb{C}$ by starting from $\mathbb{R}$ and adjoining a square root of $-1$. A model of $PA + \text{Con}(\neg PA)$ is like "$\mathbb{N}$ adjoin the Godel code $p$ of a proof of a contradiction in PA."

It's worth saying "Godel code" because $p$ is not a proof that PA is inconsistent. What it is is something stranger: we use the fact that PA can talk about, say, Turing machines to write down a complicated first-order formula $\phi$ which, when applied to standard natural numbers, tells us which standard natural numbers are the Godel codes of a proof of a contradiction in PA. Then we adjoin a "formal solution" $p$ satisfying $\phi$.

$\phi$ has only been constructed to have a particular interpretation when applied to standard natural numbers, and as it turns out the behavior of $\phi$ on nonstandard natural numbers is otherwise pretty unconstrained. There's an analogous but simpler discussion we can have about passing from $\mathbb{R}$ to $\mathbb{C}$ by adjoining a square root of $-1$; you might imagine a 14th century mathematician being very confused about the fact that [the field axioms + the axiom that there exists an element $x$ such that $x^2 = -1$] is consistent, because they're used to a particular interpretation of what $x^2$ means (say that it measures the area of a square of side length $|x|$) that is only valid in $\mathbb{R}$, and the existence of a solution in a larger field involves a different interpretation from the one they're used to.

I am not sure what happens exactly if you attempt to decode $p$ as Andres describes in the comments. I think basically if you ask any question about the proof $p$ is supposed to be encoding which can be expressed as a first-order proposition, $p$ will just respond in whatever way it needs to to avoid a contradiction, but you won't learn anything useful. One possibility (and I haven't thought carefully through how much sense this makes) is that you can only ask questions about, say, the first $n$ lines of the proof, and $p$ will just tell you, for any particular $n$, that the first $n$ lines of the proof are totally fine, no problem here, but the proof may be "infinite" in the sense that $p$ may just sit around proving useless lemmas forever.

There's again an analogous but simpler discussion to have about the first-order properties of $i \in \mathbb{C}$: our 14th century mathematician may attempt to ask questions like "is $i$ contained in the interval $[a, b], a, b \in \mathbb{Q}$?" In $\mathbb{R}$ this question can be asked in the first-order language of fields, because in $\mathbb{R}$ we can encode $x \le y$ as $\exists z : y - x = z^2$. But this encoding only has its intended interpretation in $\mathbb{R}$: in $\mathbb{C}$ every number has a square root so "$x \le y$" is always true in $\mathbb{C}$, so our mathematician will learn that "$i$ is contained in every interval $[a, b]$," except not really, because again the construction we're using to talk about $\le$ only has its intended interpretation in $\mathbb{R}$.

The opposite sort of thing happens if we try to locate $p$: it will happily report that, for any positive integer $n$, it is greater than $n$. It does not follow, of course, that $\forall n : p \ge n$, because PA proves that no such number exists. This is already a little wacky if you're not used to it: if you add a constant symbol $p$ to PA and the axioms $p \ge 0, p \ge 1, p \ge 2, \dots$, this set of axioms is consistent (e.g. by the compactness theorem) and so has a model, which we can take to be an ultrapower of $\mathbb{N}$. It is maybe worth working carefully through why the statement $\neg \forall n : p \ge n$ continues to be true in this ultrapower: it's because we are now quantifying over all nonstandard natural numbers.

Answer 2

While I don't disagree with the substance of what Qiaochu Yuan and Andrés Caicedo have said, I'm not happy with the terms "gibberish" or "useless."

It's important to bear in mind that when we say "consistency," we have a particular syntactic notion in mind, and that there is no canonical way of expressing it in terms of the semiring operations $+$ and $\times$. It is easy to glibly write down "Con" and think that it means "consistent," but in fact "Con" is an enormously complicated formula. We construct it by noting that syntactic operations on strings can be faithfully mimicked by arithmetic operations on natural numbers. Strings—sequences of symbols—can be faithfully encoded as natural numbers, and proofs—sequences of strings—can also be faithfully encoded as natural numbers. Formally, "Con(PA)" is just an assertion that a certain $x$ satisfying certain properties does not exist.

When all the dust settles, we can examine this monstrous expression "Con(PA)" and confirm that if the quantifiers are interpreted as quantifying over the natural numbers and the symbols $+$ and $\times$ are interpreted as addition and multiplication, then the resulting statement will be true if and only if PA is consistent. But it's very important to notice that "Con(PA)" does not directly "mean" that PA is consistent. It's a formal string that is getting interpreted as a statement about the natural numbers, and the statement about the natural numbers is something that we can see, because of the way we carefully mimicked syntactic operations by arithmetic operations at every step of the construction, will be true if and only if PA is consistent.

If we now interpret "Con(PA)" in terms of the elements of some other semiring, then it is certainly true that the resulting statement will no longer have the property that it will be true if and only if PA is consistent. But I think it is unfair, and more importantly misleading, to say that the statement is "gibberish." "Con(PA)" has a perfectly meaningful interpretation in any semiring satisfying the axioms of PA. What moral obligation does this other semiring have to mimic our intuitions about syntax? None, of course. If we call certain types of semiring elements "proofs" and if that choice of terminology causes us to mistakenly assume that "proofs" will always have the same properties in other semirings that they do in the natural numbers, then that's our fault for choosing terminology that confuses ourselves. Similarly, to use the word "useless" seems to presuppose that the only purpose in life a semiring might have is to satisfy our desire to understand syntax, but who are we to play God to semirings?

It's entirely conceivable to me that the theory of "generalized proofs" in "generalized natural numbers" will one day yield important mathematical insights. Admittedly they don't seem to have done so yet, but that's not a reason to dismiss it all as useless gibberish.

Answer 3

My answer is more of an extended comment on what Tim has already said. I guess what is at stake here is precisely this question: what does it mean the expression $CON(PA)$?

The common consensus is that it is a metamathematical statement, and indeed it is.

But what is metamathematics? Answer: other mathematics. In principle there is no distinction between Proof Theory of Peano Arithmetics, and , say, the Theory of Sobolev Spaces. In proof theory one studies structures, such as proof trees, which, in their intended meaning, talk about formal proofs of an underlying math theory, in this case Peano Arithmetics. But here is the deal: thanks to a special encoding, one can express certain statements of the "meta"-theory in the base theory, and so, in the case of PA, models of such a theory have some arithmetical statements which code some metamathematical facts on the theory. One of these is the infamous CON(PA).

Now, let us imagine the category of countable models of PA, with corresponding maps. That is our "Arithmetical Multiverse". The chief point to unravel the seeming paradox raised by the PO is that PA does not know anything about actual infinity.

All models, bar none, "think" that they are made of standard numbers.

It so happens that, "from outside" (ie from the perspective of an underlying set theoretical universe), the category above has a distinguished object, namely an initial object. We call that initial object $N$. The metamathematics encoded in $N$ is the "true" metamathematics, and everything else is (again, that is common folklore), gibberish.

But let us take a slightly different look at the story:

let us assume for a moment that all models of PA are in some sense equal. Each has its own coded meta-theory. In some of them, NON-CON(PA) is true. If this statement happened to be true in $N$ it would be an earthquake, because in that case there would be a finite term witnessing a proof of inconsistency. But (assuming the consistency of PA), that is not the case. Note that, although N is an initial segment of all of the arithmetical universes, none has any idea about it, they have no capability to define it with a first-order formula. Everything looks to them just some standard arithmetics.

Now, let us play this game: to every model of PA let us assign a radius, the Radius of Consistency: it is measured by an element in the model, the minimal element (when it is there!) that proves the inconsistency of PA.

If that element does not exist, we say that the radius for that model is unbounded. Note en passant: as all models have the same order type, namely ω + (ω* + ω) ⋅ η, we can actually define the radius of consistency by its position in this order. I shall not pursue this topic further here, for the sake of brevity.

Armed with the Radius of Consistency, we can say that the conventional consistency of PA is the meta-statement that N 's radius is unbounded.

Similarly, there are models of PA who have a much larger radius. Those are exactly the models which are conjured up by the PO.

You may say: all good and well, but these statements are still gibberish to me. Perhaps they encode garbage, useless information, as far as metamathematics goes (obviously, their are legitimate statements from the point of view of algebra).

Perhaps, but not so fast. For instance, sub-theories of PA such as $I\Sigma_1$ are finitely axiomatizable, so for those arithmetical multiverses the axioms involved in the "gibberish "are in fact real axioms. And things may get even odder. I think it is fair to say that so far nobody has done a detailed analysis of these statements of inconsistencies in complete details. There may be many surprises there. But here I stop...