42
$\begingroup$

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?

$\endgroup$
9
  • 8
    $\begingroup$ I'm not the person to explain this in detail, but 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). $\endgroup$
    – gowers
    Jan 14, 2011 at 15:43
  • 6
    $\begingroup$ I guess you need to somehow say that $n$ should be large in relation to the size of the 'specification' of the theory? Otherwise, you could construct such a theory artificially: for example, $T$ could contain statements $P_0, P_1, \ldots, P_n$, with $P_0$ as the single axiom, and rules of deduction $P_m \Rightarrow P_{m+1}$ and $P_n \Rightarrow \neg P_0$. (Similarly, any inconsistent theory could be turned into one satisfying your criterion, by 'stretching' the rules sufficiently.) $\endgroup$ Jan 14, 2011 at 20:04
  • 4
    $\begingroup$ I posted the following as an answer and then deleted it after it appeared that I misunderstood the question. But maybe it's worth bearing in mind here: It is a corollary of some theorems of logic discovered in the 1930s that the ratio of lengths of proofs to lengths of theorems is unbounded. (If it were bounded, then there would be an algorithm for deciding which formulas of first-order logic are universally valid, contradicting the conjunction of Church's theorem with Gödel's completeness theorem:...... $\endgroup$ Jan 14, 2011 at 23:11
  • 4
    $\begingroup$ ......just systematically search for a proof until one has exhausted those shorter than the bound. Gödel tells us that if the formula is universally valid, then there's a proof.) Hence, just take any theorem whose shortest proof is long. Deriving a contradiction from its negation will take a long time. $\endgroup$ Jan 14, 2011 at 23:11
  • 2
    $\begingroup$ What if the contradiction is too long to be written down explicitly, but there is a systematic way of constructing it? (In the same way that for every given Goodstein sequence, there is a proof in PA that it terminates. Even though it can become arbitrarily large, we can still construct it, in a sense.) $\endgroup$ Jan 14, 2011 at 23:27

4 Answers 4

25
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ @David: Say we are studying an infinite theory $T$. Of course, at any given time, we have only seriously considered a finite fragment of $T$ and, perhaps, some very general consequences of the whole theory. There is a good chance our intuitions about $T$ are plain wrong in several important respects, since they have been developed from a limited pool of results. This is actually a common phenomenon: Based on our knowledge up to a point, we believe of two options $A$ and $B$ that $A$ must hold. Then we prove that $B$ holds, and this forces us to reexamine our supposed understanding. (Cont.) $\endgroup$ Jan 14, 2011 at 23:14
  • 1
    $\begingroup$ @David: This helps us to develop more accurate intuition and to refine our mental pictures about the theory and its consequences but, again, our knowledge may be seriously flawed although it is better than before. Say that $T$ is inconsistent, but the fragment of $T$ that we have seriously studied so far is not. We develop good intuitions about this fragment, and erroneously believe these intuitions apply to the whole. Most of our efforts center on developing the consequences of the consistent fragment, because it is the one we manage best. We do not seriously expect an inconsistency. (Cont.) $\endgroup$ Jan 14, 2011 at 23:18
  • 1
    $\begingroup$ @David: So we do not look for one. Even if we actively looked for one, it is possible that any direct proof of an inconsistency is unfeasibly long by our standards. We then have a situation were we are not actively developing tools to foresee a contradiction, since we do not expect one, and a direct proof of one would take too long for us to discover. Sure, there is a chance that eventually we will develop intuitions that cannot be fully formalized that will lead us to suspect a contradiction is hiding somewhere, but even this may be a very long process. That's the situation I was suggesting. $\endgroup$ Jan 14, 2011 at 23:22
  • 1
    $\begingroup$ Andres, it appears the phenomenon you are referring to is that "most of T is consistent." This is not equivalent to "the contradiction is long." A finitely axiomatizable theory could still have the property that the only contradictions are long. Being able to work with either of these properties would be interesting. $\endgroup$ Jan 14, 2011 at 23:27
  • 2
    $\begingroup$ @Andres: The intersection between paraconsistent logic and intuitionist logic (= paracomplete logic) is minimal logic. Although I had some hope a couple of years ago that paraconsistent logic is more consistent than other logics, it is not so. Assertions of the kind of Currys paradox which have the shape of a comprehension axiom lead still to inconsistencies in such a logic, since the inconsistency already arises in minimal logic. $\endgroup$
    – Countably Infinite
    Jun 9, 2011 at 18:31
9
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Hmm. $f_{9}^{\mathrm{Ack}}(f_{8}^{\mathrm{Ack}}(f_{8}^{\mathrm{Ack}}(254)))$ is so insanely huge number it squarely defeats human imagination, nevertheless it has a short and simple description, and it’s quite possible it could usefully appear in a short proof. $\endgroup$ Feb 5, 2016 at 14:18
  • $\begingroup$ @EmilJeřábek That may be plausible. I have also been able to (assuming large cardinal hypotheses) compute many quotients of subalgebras of $A_n$ (for presumably very large $n$) without needing to compute $A_n$ itself. $\endgroup$ Jun 26, 2023 at 15:35
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Never heard of fallible Beth models? $\endgroup$ Jun 8, 2011 at 20:02
  • $\begingroup$ @WouterStekelenburg: Could one have a Beth model of, say, $ZFC$? Any references to that effect? $\endgroup$ Oct 22, 2018 at 14:31

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.