Wikipedia:Reference desk/Archives/Mathematics/2019 May 29

Mathematics desk
< May 28	<< Apr | May | Jun >>	May 30 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 29

Theories Proving Their Own Consistency

I'm aware that any theory that does enough arithmetic to let you code things into it can't prove its own consistency, but I dont understand why we should care what a theory says about itself to begin with.

A consistent theory should either say it is consistent or not say anything, an inconsistent theory should say it is consistent. So, if Godel's stuff wasn't the case, shouldn't the expectation be that every theory would demonstrate it's own consistency? Since if it accurately said it was not consistent, then it would be inconsistent, so it would also prove it was consistent.

It sort of seems like asking someone if they lie, you would still need some sort of independent reason to believe them. In short, am I missing something? — Preceding unsigned comment added by 216.49.241.133 (talk) 05:02, 29 May 2019 (UTC)

Link: Gödel's incompleteness theorems#Second incompleteness theorem. You're right that the way the theorem is often stated is an oversimplification, but from what I'm reading it isn't so much whether the theory can prove itself consistent but whether the theory can prove a certain formula, and this formula can be interpreted as saying that the theory is consistent. This is actually not as strong a statement, but it gets around to the philosophical issues that you raise. --RDBury (talk) 13:29, 29 May 2019 (UTC)

Thank you, that's interesting to read. Though, this brings up a second question: if T is consistent and contains enough arithmetic, then T should have a model in which Con(T) is false. In that case, what does this say about the meaning of Con(T)? Is it just that in such models, Con(T) no longer correctly encodes consistency, it is just some number theory statement that doesn't have a meaning in the meta theory, or is this the wrong track?2600:100A:B02C:77B:0:5:8227:9401 (talk) 20:08, 29 May 2019 (UTC)

Should have warned you, the whole subject is rabbit hole down which only the brave should venture. Basically if P is a proposition which is true but not provable, then adding ¬P as an axiom results in a consistent theory, or at least it's as consistent as the original theory. We now have a new consistent theory in which some provable statements are false (in ordinary math). Not only that, but you can prove that two Peano systems are isomorphic (see [1]), which would seem to imply that the statement P in one system would be equivalent to P in another system, making it impossible to have P in one theory and ¬P in another. So yeah, start getting into the details and it confuses the heck out me too. --RDBury (talk) 00:59, 30 May 2019 (UTC)

Does that depend on some standard model, though? If P is true in every model, it is provable; so in the case you are discussing, it sounds like it is more a matter of capturing N by PA and assessing the failure (which is a rabbit hole, indeed). But, when talking about Con(T), in particular, there is a model of T in which it is false if T is consistent. I can't reconcile Con(T) capturing consistency with that unless it is something purely syntactic and only has meaning when provable, if that makes sense. I know enough logic to have philosophical issues, not enough to resolve them:p2600:100A:B026:43A4:0:56:29A4:2901 (talk) 17:40, 30 May 2019 (UTC)

@216.49.241.133: your basic point seems to be (correct me if I'm wrong) that a theory's assertions about its own consistency are no more reliable than its assertions about anything else, so without an independent reason to think the theory is reliable, then even if it did prove its own consistency, that would not particularly be evidence in its favor.

That point is well taken.

However, there are still reasons to care about the Second Incompleteness Theorem. Here's a philosophical one: If we believe that theory T consists entirely of true statements, then we should also believe that Con(T) is a true statement. So the truth of all of T entails the truth of Con(T). But T does not formally prove Con(T) in first-order logic. Therefore there are valid inferences that go beyond first-order logic.

Here's a more technical one: Second Incompleteness is critical to the hierarchy of theories based on consistency strength. Without it, the whole hierarchy might collapse. It's also a very useful tool in examining the hierarchy.

For example, is it possible that ZFC proves that there is an inaccessible cardinal? No. Why not? Well, suppose instead that ZFC proves that there is some inaccessible cardinal κ. Then ZFC proves that V_κ is a model of ZFC, and thereby that Con(ZFC) holds. But then by second incompleteness, ZFC must be inconsistent (which we do not believe). --Trovatore (talk) 18:16, 30 May 2019 (UTC)

Thank you, that is very helpful and very interesting. I do think the 2nd incompleteness theorem is both interesting and useful (and, it also improves the situation since sufficiently strong theories proving their consistency aren't consistent, which is more definite than the alternative universe where the 2nd fails). But, most of the time I see it being discussed, a lot of people seem to be talking about how it introduces some element of untrustworthiness into mathematical foundations. I suppose this is more a question about the things people say about the result than the theorem, I feel like I am missing something since I don't see why foundations would be any more trustworthy if the the theorem wasn't true. I've come across a lot of discussions starting with, "ZFC can't prove it is consistent because Godel, that's a big deal because we can never truly trust foundations to be consistent", it just seems to me that that would always be the case, and it doesn't seem that big of a deal (I've never found Godels completeness nor incompleteness results to be that counterintuitive, no more so than the existence of uncomputable functions, or any other such, it seems like it should be expected and that they don't diminish the epistemic trust one should place in foundational mathematics.) (Then again, I'm amateur lover of mathematics and foundations and have no formal education past high school calculus, so I could be confused).2600:100A:B010:FBAD:0:5F:FE13:301 (talk) 17:41, 31 May 2019 (UTC)

I'm aware that any theory that does enough arithmetic to let you code things into it can't prove its own consistency -- not quite right, see self-verifying theories. Historically the search for consistency proofs was from the Hilbert program, when nobody had real doubts about the consistency of primitive recursive arithmetic but some were suspicious of set theory and maybe Peano arithmetic. So the idea was to use PRA to prove the consistency of those bigger theories and presumably quiet the doubters. However, Gödel showed that PRA couldn't even prove its own consistency, much less that of the bigger theories, so the Hilbert program in that regard failed. Improved understanding came out of it though. 67.164.113.165 (talk) 04:45, 31 May 2019 (UTC)

Thank you, that is a very interesting read - I was trying to reference "enough to code what you need for Godel's result" since I knew Robinson Arothmetic was enough, but wasn't sure if you can go weaker and still have them - a lot of people I've seen say PA, or just strong enough arithmetic, I'm never sure how to phrase it. Are there any systematic results relating what a theory can say about itself and how strong that theory is, going beyond just Con? Like how Rices Theorem talks about all the things comparable functions can't say about computation?2600:100A:B010:FBAD:0:5F:FE13:301 (talk) 17:46, 31 May 2019 (UTC)