Inconsistent theory with long contradiction

Question

What can one say about an inconsistent theory $T$ which has no contradictions (i.e. deductions of $P \wedge \neg P$) of length shorter than $n$, where $n$ is some huge number?

There have been some discussions about the consistency of ZFC, for instance, where it has been asserted that it would be OK for ZFC to be inconsistent as long the contradiction was enormous. However, this still seems like a bad situation to me since there are constructions which depend on consistency but don't care about deduction per se. For example, constructing a model of a theory.

Can someone explain the consequences of this?

EDIT: After hearing some good feedback, I think I can phrase this question in a more concrete way:

To what extent, and in what situations, is it possible to work consistently with a theory that is inconsistent?

Answer 1

This is quite possible, that a theory $T$ is inconsistent but any deduction takes so long that we do not know.

Hugh Woodin has a short, nice paper, that I recommend you take a look at, where he addresses the possibility that (a fragment of) Peano Arithmetic (PA) is inconsistent, but any inconsistency is too long for us to be able to detect it. The paper is "The Tower of Hanoi", in Truth in mathematics (Mussomeli, 1995), 329–351, Oxford Univ. Press, New York, 1998.

Part of his point is that although people discuss the possibility of inconsistency of large cardinals or strong set theoretic axioms,

"there are limitations on the extent to which our experience in mathematics to date refutes the existence'' of certain sequences of natural numbers with 'undesirable' consequences. (pg. 330)

He uses the idea of the tower of Hanoi to construct a sequence showing that exponentiation would be ill-defined, starting from such an assumption on the inconsistency of PA. (Actually, he uses that PA is bi-interpretable with what we call ZFC${}^{fin}$, so we can argue about sequences very much in combinatorial terms without worrying much about coding issues.)

Now, strong theories such as PA of ZFC can prove the consistency of all their finite fragments. Of course, the proof of the consistency of a fragment tends to use axioms that are outside of that fragment, so we are not violating the incompleteness theorem in this process. However, the experience we have gained from the analysis of this local property hints at what Gowers suggests in his comment, that we can still obtain a meaningful local theory even if the global version makes no sense.

Since it would turn into a bit of a quagmire to carry this discussion with PA, for simplicity here I am simply assuming PA is consistent, but let me clarify this "meaningfulness" somewhat in the context of ZFC. Most of what we do with ZFC can actually be carried out in the theory where replacement is restricted to $\Sigma_2$-formulas, and there is reasonable 'evidence' that if ZFC is inconsistent, then its inconsistency comes from an instance of replacement applied to formulas of larger complexity than $\Sigma_2$. This means that a non-negligible fragment of our intuition about models of set theory would actually be correct, only that it would not be about ZFC, but about this restricted form.

Inconsistencies would simply not affect that part of our understanding, and if they ever were to surface, we could probably do damage control in a less panicked fashion than usually feared. We would in fact, in hindsight, see that the inconsistencies would explain how our intuitions about the $\Sigma_2$-case simply cannot carry to larger fragments, and for day-to-day practice, what most of us do would be completely unaffected.

[That said, of course I should add the usual disclaimer that I do not presently believe ZFC is inconsistent, so whatever I say may be considered suspect.]

---

It occurs to me that there is a formal setting where one could explore this scenario (an infinite theory such as PA or ZFC that is inconsistent but any proof of an inconsistency is too long, and there are significant fragments (of feasible length) that are consistent): That of paraconsistent logic (http://plato.stanford.edu/entries/logic-paraconsistent/). However, it is my (limited) understanding of paraconsistency that the theory is not yet developed enough to handle something like ZFC. However, researchers in the area may have good suggestions on what one would have to look at with the goal of developing intuitions that would help us foresee a contradiction even if short of actually proving it.

Answer 2

I’m kind of surprised that no one mentioned the classical paper Existence and Feasibility in Arithmetic by Rohit Parikh, which discusses inconsistent theories with no short proof of contradiction in §2.

Answer 3

Let me expound on a somewhat plausible scenario of an inconsistency in the large cardinal hierarchy that may take a very long time to appear.

A rank-into-rank embedding is an elementary embedding $j:V_{\lambda}\rightarrow V_{\lambda}$.

Lemma If $j$ is a rank-into-rank embedding, then $(j*j)(\alpha)\leq j(\alpha)$ for all ordinals $\alpha$.

Proof Suppose that $\alpha<\lambda$. Let $\beta$ be the least ordinal such that $j(\beta)>\alpha$. Then $$V_{\lambda}\models\forall x<\beta,j(x)\leq\alpha.$$ Therefore, by elementarity, $$V_{\lambda}\models\forall x<j(\beta),(j*j)(x)\leq j(\alpha).$$ In particular, since $\alpha<j(\beta)$, we conclude that $(j*j)(\alpha)\leq j(\alpha)$. $\mathbf{QED}.$

The above lemma has the following corollary as a purely combinatorial consequence.

If $1\leq x\leq 2^{n}$, then let $o_{n}(x)$ be the least natural number such that if $A_{n}$ is the classical Laver table of cardinality $2^{n}$, then $A_{n}\models x*2^{o_{n}(x)}=2^{n}$. In other words, $o_{n}(x)=\text{log}_{2}(p)$ where $p$ is the period of $x$ in the classical Laver table $A_{n}$.

Corollary Assume there exists a rank-into-rank cardinal. Then for all natural numbers $n$, one has $o_{n}(1)\leq o_{n}(2)$.

The functions $n\mapsto o_{n}(1)$ and $n\mapsto o_{n}(2)$ are strictly increasing. However, Randall Dougherty has shown that these functions increase very very slowly. A straightforwards computer calculation shows that $o_{n}(1)\leq o_{n}(2)$ whenever $o_{n}(1)\leq 4$.

Under large cardinal hypotheses, we have $o_{n}(1)\rightarrow\infty$. However, the statement $o_{n}(1)\rightarrow\infty$ does not seem to imply that $o_{n}(1)\leq o_{n}(2)$ for all $n$. In the following theorem, $f_{n}^{\text{Ack}}$ is a version of the Ackermann function.

Theorem (Dougherty) The least natural number $n$ such that $o_{n}(1)\geq 5$ is at least $f_{9}^{\text{Ack}}(f_{8}^{\text{Ack}}(f_{8}^{\text{Ack}}(254)))$.

Corollary If there is a natural number $n$ with $o_{n}(1)>o_{n}(2)$, then the least natural number $n$ such that $o_{n}(1)>o_{n}(2)$ is greater than $f_{9}^{\text{Ack}}(f_{8}^{\text{Ack}}(f_{8}^{\text{Ack}}(254)))$.

Therefore if one tries to prove that rank-into-rank cardinals are inconsistent by exhibiting an $n$ such that $o_{n}(1)>o_{n}(2)$, then one would need to take more than $f_{9}^{\text{Ack}}(f_{8}^{\text{Ack}}(f_{8}^{\text{Ack}}(254)))$ steps.

Of course, there may be short-cuts in showing that $o_{n}(1)>o_{n}(2)$ for some $n$ which take much less time than actually calculating the least $n$ such that $o_{n}(1)=5$. Or there could be an entirely different sort of contradiction with the assertion that there exists a rank-into-rank cardinal.

For the record, here are the first few values of $o_{n}(1)$ and $o_{n}(2)$.

$o_{1}(1)=0,o_{1}(2)=1;o_{2}(1)=1,o_{2}(2)=1;o_{3}(1)=2,o_{3}(2)=2;o_{4}(1)=2,o_{4}(2)=2;o_{5}(1)=3,o_{5}(2)=3;o_{6}(1)=3,o_{6}(2)=3;o_{7}(1)=3,o_{7}(2)=4;o_{8}(1)=3,o_{8}(2)=4;o_{9}(1)=4,o_{9}(2)=4$.

If such an inconsistency were to pop up only very far away, then such an inconsistency will not have any effect on the mathematics that mathematicians here on Earth will do because nobody will live long enough to observe such a contradiction.

This being said, set theorists generally do not think that there is any contradiction anywhere in the large cardinal hierarchy up until say $I0$ no matter how distant the contradiction is located.

Answer 4

Your question is excellent, and touches upon a topic that has not yet been investigated as it should. The typical answers are: well, we will have some mitigation strategy, such as scrutinizing the theory and doing some surgery, to salvage what we can. That is indeed a strategy, but does not go to the core of the problem. Gowers has, in his short glowing comment above:

" if a theory has only very long contradictions, then I would have thought it might well have a structure that is in some sense "locally" a model (a bit like the surface of the Earth being locally a model for an infinite plane). "

Unfortunately our model theory now is black and white:

IF a theory is consistent, THEN it has a model, ELSE no models.

What would be needed is this (in the light of the seminal 1971 result of Parikh quoted by Emil): theories which are quasi-consistent (by this I mean that their inconsistency is unfeasible, in some suitable sense) should have a quasi-model, or a local/partial model.

What is needed is a completeness theorem for feasibly consistent (but classically inconsistent) theories.

How to articulate the basic intuition of Gowers is, to my knowledge, still a missing piece in the FOM landscape (I have made a provisional sketch of an attempt in my manifesto here.).

This place is not the right one for discussing proposals in this direction, but I still wish to give some perspective:

the Tarksian notion of truth, as it stands now, is too rigid.

One should extend it, by loosening the coupling theory-model, so as to include partial models of a theory T, and conversely consider situations in which a structure is described not by a single theory, but by a patchwork of theories ( a bit like a manifold is represented locally by copies of $R^n$, glued together.). Hopefully, when that happens, we will have removed the consistency angst from our lives.