1
$\begingroup$

In any formal system S that is susceptible to Godel's proof, we can make a formula G which is undecidable. That should mean that we can add either $G$ or $\neg G$ as an axiom to S and still end up with a consistent system, but I'm not sure exactly how $S + \neg G$ can be consistent.

So, $G$ says: "There does not exist a number $n$, which is the Godel number for a proof of $G$." If G were provable, it would be false, and the system would be inconsistent (because $G$ implies $\neg G$). If $\neg G$ were provable, however, the system does not have to be blatantly inconsistent, but only omega-inconsistent. $\neg G$ says "There does exist a number $n$, which is the Godel number for a proof of $G$." But it doesn't specify what that number is. So S can still have theorems: "1 does not prove $G$", "2 does not prove $G$", "3 does not prove $G$" and so on, and it would only be omega-inconsistent (since there is no provable statement that is blatantly the negation of another). But we assume that $S$ is omega-consistent, so we are forced to conclude that $G$ is undecidable. Okay. (as a side-note, I thought that Godel's proof didn't need the assumption of omega-consistency, but it seems required here ... ?)

Now, I understand what happens when you add $G$ to S. In this new $S+G$ system, $G$ says, "There is no number which is the Godel number of a proof for $G$ in S", which is, of course, true (and presumably consistent).

But in $S + \neg G$, $\neg G$ says "There is a number which is the Godel number of a proof for $G$ in S"; yet, since every provable statement of $G$ is also provable in $S + \neg G$, this new system will also say "1 does not prove $G$ in S", "2 does not prove $G$ in S", ... and so on. So isn't $S + \neg G$ omega-inconsistent? And doesn't that go against the idea that we should be able to add either $G$ or $\neg G$ to S and still end up with a consistent system? Does that "consistency promise" not extend to omega-consistency? If not, isn't there a "logically better" way to extend S, even though both extensions are possible?

  • 0
    The notion of "number" in $S+\neg G$ is not the same. In fact, you want to understand $G$ as saying "there does not exist an '$S$-number' that is the number of a proof of $G$.", however, there well can be an "$S+\neg G$"-number that *is* a proof (and indeed there is), because you have new axioms, so your function "is a proof in $S$ of" is different from the function "is a proof in $S+\neg G$ of". Also, note that there are versions of Goedel's proof that avoid the issue of $\omega$-inconsistent.2012-04-16
  • 0
    In addition to Arturo's previous comment, your first paragraph is slightly wrong. No one guarantees that $S+G$ and $S+\lnot G$ are consistent. However *if* $S$ is consistent then so are $S+G$ and $S+\lnot G$. We simply did not introduce contradictions to the system, but we might not be able to prove the consistency of $S$.2012-04-16
  • 0
    @ArturoMagidin I understand that $\neg G$ in $S + \neg G$ talks about provability in $G$, but why would it talk about S numbers and not $S + \neg G$ numbers? I understand that the function "is provable in S" is different from the function "is provable in $S + \neg G$". But when I prove, in $S + \neg G$, that "there is a number that proves G in S" and "1 is not that number", "2 is not that number", etc., am I not talking about the same type of numbers in each case?2012-04-16
  • 0
    @AsafKaragila But we *assume* the consistency of S, don't we? We assume it, and then go ahead and show that $S + \neg G$ must be omega-inconsistent! How does that work? Surely, Godel's proof does not say that a consistent formal system cannot exist?2012-04-16
  • 0
    @Ord: The notion of "number" depends on the model; what you call a "number" in the model $M$ of $S$ need not be the same things that you call a "number" in the model $M'$ of $S+\neg G$. In particular, there can be "numbers" other than the ones that were already identified as "numbers" in $M$. Note that Goedel uses $\omega$-inconsistency in order to show that $\neg G$ cannot be a theorem; as I said, there are refinements of Geodel's argument that completely avoid the issue of $\omega$-inconsistency.2012-04-16
  • 0
    @ArturoMagidin Okay, but within the model M-prime of $S + \neg G$, when we say "number" we mean the same thing, right? So the statements in $S + \neg G$ "there exists a *number* which proves G in S" and "1 is not that *number*" and "2 is not that *number*" must all use the same definition for *number* (namely, a $S + \neg G$ number), right? If not, why?2012-04-16
  • 1
    @Ord: There is no "absolute" consistency, you need to have some basic system which you *believe* is consistent. Even the rules of first-order logic require a certain degree of belief or the fact we can use induction. We have good reasons to believe these are consistent, but no proof of that. Suppose that we are all wrong, and all mathematics in its current form is inconsistent and we can only prove these things because our most basic intuition is inconsistent? This is why we say that *if* $S$ is consistent then $S+G$ and $S+\lnot G$ are, but this is a big if sometimes.2012-04-16
  • 0
    @AsafKaragila, I understand, but if we assume the consistency of S, then show that G is undecidable, then show that $S + \neg G$ is inconsistent, the inconsistency cannot have been introduced by $\neg G$, so S must have been inconsistent to begin with! This amounts to a proof by contradiction that no S which is susceptible to Godel's method is consistent. That is definitely **not** what Godel proved!2012-04-16
  • 0
    @AsafKaragila and why can't there be "absolute consistency"? Certainly, consistency is a very well-defined concept (namely, that no two propositions P and $\neg P$ are both provable within the system), so any system either has it or doesn't. Whether or not we can *prove* consistency is, of course, a different matter, but does that really mean that there is no "absolute" consistency?2012-04-16
  • 0
    @Ord: You are trying to prove an implication $Con(S)\rightarrow Con(S+G)$, and you make use of the Deduction theorem. You really assume $Con(S)$ and you then prove $Con(S+G)$. Your problem is that you also do the same to prove $Con(S+\lnot G)$, and then you get that $Con(S)$ proves seemingly "incompatible" statements. My point, in the "absolute consistency" argument is that suppose you show that $PA$ is consistent. Relative to what, $ZFC$? Okay, but why is $ZFC$ consistent? We find a stronger theory to prove that. We can keep going further but we cannot stop unless you reach contradiction.2012-04-16
  • 0
    Anyway, I feel that I am getting sucked into a discussion which I cannot fully commit to right now. If you prefer I can delete those comments of mine to clear space for other comments which might be actually useful to the question.2012-04-16
  • 0
    @Ord: In $M'$, when we say "number" we mean whatever it is that "number" means in $M'$, which may be something completely non-standard as far as $M$ is concerned. Think about non-standard analysis, where suddenly the statement "there is no number $r$ greater than $0$ such that $r\gt n$ for all natural numbers $n$" is no longer true, because the meaning of "number" and of "natural number" is now different. At least one of the statements "$n$ is not the number of a proof of $G$ in $S$" is no longer true in $S+\neg G$, because "number" now means something different.2012-04-16
  • 0
    @Arturo, by that argument, can't we say that the original S *can* prove $\neg G$ without being omega-inconsistent - we just need a modified definition of number? I thought that the definition of omega-consistency is that you never have the statements: "there exists an n such that P(n)" but also "$\neg P(a)$" for all a in the set of natural numbers. So even if there is a number n in $S+\neg G$ such that "n is the proof of G in S", it is not a natural number, so $S + \neg G$ is omega-inconsistent.2012-04-16
  • 0
    @Ord: I'm not a model theorist, you are going past my ability to answer coherently. Perhaps you should look at one of the variations of Goedel's Theorem that does *not* rely on $\omega$-inconsistency? My understanding is that Goedel wasn't entirely happy with the latter in any case. If $S$ is consistent, then there *are* models of $S$ where $\neg(G)$ is *true* (that's the reason why $G$ cannot be proven); and there are model of $S$ where $G$ is true (because $\neg G$ cannot be proven). But "true" does not imply "provable". (cont)2012-04-16
  • 0
    @ArturoMagidin: okay, maybe I will look at these variations.2012-04-16
  • 0
    @Ord: And as I understand it, the whole point of $\omega$-inconsistency (rather than simple inconsistency) is that we *cannot* prove "for all $a$ in the set of natural numbers, $\neg P(a)$". We only prove that $\neg P(0)$, $\neg P(1)$, etc. We *cannot* prove $\forall a\in\mathbb{N}(\neg P(a))$ (as I undrstand it, the "inconsistency" in $\omega$-inconsistency is precisely that disconnect).2012-04-16
  • 0
    @ArturoMagidin, yes, sorry I didn't make myself clear - when I said "for all a", I didn't mean that was part of the theorem that was proven, rather that, from the "outside", it is apparent that we can prove $\neg P(a)$ individually for every natural number a.2012-04-16
  • 0
    This is an old post but there was something in the comments that was not cleared up properly. You claimed that consistency is a very well-defined concept, but the definition you proceeded to give used "provable", which is not well-defined! If you unpack what you 'mean', you will see why. You would need to say "there exists a proof of ...", but what **exactly** is a proof? Ok, you say, "there exists a (finite) string of symbols such that ...". Now we've hit the infinite regress, since you can't possibly define "(finite) string" non-circularly!2016-05-02

2 Answers 2

5

Your conclusion that $S+\neg G$ is not $\omega$-consistent is right. It is (assuming that $S$ is consistent) consistent, but fails to be $\omega$-consistent. Being $\omega$-consistent is a stronger condition than consistency, satisfied by fewer systems.

Would it be "logically better" to extend $S$ in an $\omega$-consistent way than in one that isn't? I don't think so. As a sometimes Platonist, I would certainly favor the extension $S+G$ over $S+\neg G$, perhaps even claiming that the former is true whereas the latter isn't, but that preference is not based on logical properties (being true is not a logical property).

Part of the confusion is that "$\omega$-consistency" is something of a misnormer -- because the name contains "consistency" one is tempted to think that like ordinary consistency it is an intrinsic property of the theory. But really it isn't; saying that a theory is $\omega$-consistent is a statement between the relation between what the theory proves and arithmetic at the meta-level. Being $\omega$-consistent is a necessary criterion for the theorems of the theory to be truths about the intuitive naturals, but failure to express arithmetic truth is not a logical problem for the theory -- it is innocent of our ambitions about what we might like it to model or not.

One might consider modifications of the concept of $\omega$-consistency such that it looks more intrinsic to the theory. For example we could define that a theory $T$ is $\omega'$-consistent iff, whenever $T\vdash \exists x. \phi(x)$ there is some closed term $t$ such that $T\vdash \phi(t)$. (The difference is that in ordinary $\omega$-consistency we require $t$ to be a "numeral"; the generalized definition allows arbitrary closed terms). However, under this generalization it is still not clear why one would consider $\omega'$-consistency to be a desirable property of theories in general, even if we don't intend the theory to model arithmetic.

  • 0
    Excuse my ignorance, but what exactly is a "closed term", and why would omega-prime-consistency be undesirable?2012-04-16
  • 0
    A closed term is one that contains no variables -- such as $S(S(S(0)))+S(0)$ in the language of arithmetic opposed to $S(S(S(x)))+y$. -- I'm not saying that $\omega'$-consitency would be actively _undesirable_, just that I don't see why one would explicitly _desire_ it. For example, ZFC is not $\omega'$-consistent, but I don't think one should count that as a disadvantage.2012-04-16
  • 0
    Okay, thank you very much for your response! I think I have a much better handle on the situation now.2012-04-16
  • 0
    But your notion of $ω'$-consistency is not analogous, because it is not at all related to the original. To even say that ZFC is $ω$-consistent, we need a suitable translation of arithmetical terms and sentences into terms and sentences over ZFC, so of course the nature of natural numbers and their codes is inbuilt into the notion of $ω$-consistency. So it is justifiable to consider $ω$-consistency desirable but consider $ω'$-consistency a completely different notion, namely that the term model exists. No?2016-05-02
  • 0
    @user21820: The relation is that a theory _in the language of arithmetic_ that extends Q is $\omega'$-consistent if and only if it is $\omega$-consistent. The last paragraph was intended to explain that at least one way to escape the non-logicalness of $\omega$-consistency by attempting to phrase it in a way that is not specific to the language of arithmetic, doesn't seem to work very well.2016-05-02
  • 0
    @HenningMakholm: I agree with your comment, but I interpreted your statement that "under this **generalization** it is **still** not clear why ... $ω'$-consistency [is] **desirable**" to imply that you felt that it is not clear why $ω$-consistency is desirable. Clearly we do desire it (as long as we believe natural numbers exist).2016-05-02
1

Omega-consistency is certainly a syntactical property; in that sense, it is an intrinsic property of systems, not a property they have under a particular interpretation.

However, if consistency is desirable on simple logical grounds, the desirability of omega-consistency is arithmetical, for only if we take our universe of discourse to be the natural numbers (or some other items with the same structure), we will consider desirable for a system denying a property P of each numeral (0, S0, SS0, ...) to not prove the existence of an object with P.

If we wish to admit objects other than the naturals in our universe, omega-consistency need not be desirable.