Here are the answers to yesterday’s puzzle. The first correct solution came from our commenter Leo (comment #18 on yesterday’s post).
The assumptions of the problem were: Everything I say out loud can be deduced from my axioms. My axioms include the ordinary axioms for arithmetic, among other things. And I recently said out loud that “I cannot prove that God does not exist”.
The questions were: Can I prove there is no God? Can I prove there is a God? And is there enough information her to determine whether there actually is a God?
The answers are yes, yes and no: Yes, I can prove there is no God. Yes, I can also prove there is a God. And no, you can’t use any of this to determine whether there is a God.
To explain, I’ll use the phrase “logical system” to refer to a system of axioms sufficiently strong to talk about basic arithmetic (and perhaps a whole lot of other things), together with the usual logical rules of inference. It’s given in the problem statement that I am a logical system.
Here are two background facts about logical systems:
A. An inconsistent logical system can prove anything at all. That’s because it’s tautological that if P is self-contradictory, then any statement of the form “P implies Q” is valid. If I’m inconsistent, that means I can prove at least one statement (call it P) that’s self-contradictory. Then if I want to prove, say, that the moon is made of green cheese, I note that:
- I can prove P
- It’s tautological that “P implies the moon is made of green cheese”
- Therefore I can conclude by modus ponens that the moon is made of green cheese.
B. No consistent logical system can prove its own consistency. This is Godel’s celebrated Second Incompleteness Theorem.
Now here’s the argument:
1) I’ve asserted that I can’t prove that atheism is true.
2) I only assert things I can prove, so I must be able to prove that I can’t prove atheism is true.
3) Therefore I can prove that there’s something I can’t prove.
4) Therefore I can prove that I am consistent (because if I were inconsistent, I’d be able to prove everything — that’s background fact A).
5) Therefore I am inconsistent (because no consistent system can prove its own consistency — that’s background fact B).
6) Therefore I can prove anything (that’s background fact A again). (More precisely, I can prove anything I can state.)
In particular:
Yes, I can prove there is no God (because I can prove anything!).
Yes, I can prove there is a God (because I can prove anything!).
No, you can’t use any of this to learn anything about whether there is a God (or any other aspect of reality) because you already know that I can prove anything — so my (in)ability to prove something carries no information whatsoever.
More generally, the moral is this: As a matter of pure logic, If there is anything that you can prove you can’t prove, then you can prove anything.
Fascinating, and I will have to contemplate for a bit. I am not getting this yet.
Statement A – example. Say P is that eggs are not eggs which is self contradictory.
The next step is to say it is tautological that P (that eggs are not eggs) implies the moon is made of green cheese. I am not quite getting why any such statement is valid from the first proof of P
I am not doubting the validity, but comprehending it is another matter.
I am sure it will all start to make sense eventually, and it seems we cannot operate within a system of logic, Mr Spock regardless.
Steve, Godel’s 2nd Theorem is a very precise mathematical result. For any given (sufficiently strong) formal system T, you can define a statement of arithmetic Con(T) which translates, via Godel coding, to the notion that T is consistent. And what Godel’s 2nd theorem says is that assuming T is consistent, T will be unable to prove Con(T).
But that says nothing about the English statement “T is consistent”. You can even take as an axiom “All my beliefs are consistent with one another.” or even the stronger statement “My belief system is not only consistent, but it is sound.” and no inconsistencies will arise. (Incidentally a proposition asserting the soundness of a sufficiently strong formal system cannot even be expressed in arithmetic via Godel coding, as a consequence of Tarski’s theorem.)
Is the implication of this that anyone who says ‘I can’t prove that is true’ either has an inconsistent logical system or is saying something that cannot be deduced from the axioms they hold to be true ?
It didn’t like square brackets – was supposed to say
Is the implication of this that anyone who says ‘I can’t prove that {fact X}is true’ either has an inconsistent logical system or is saying something that cannot be deduced from the axioms they hold to be true ?
I suppose one problem is moving from formal systems to the informal ones we live in and the precise meanings of terms in different contexts.
Taking steps, although I don’t fully get it, it seems plausible that an inconsistent logical system can prove anything at all. So if I just accept that.
I also accept the second theorem, that a consistent logical system cannot prove its consistency.
SL says he can prove that he can’t prove something. What that thing is doesn’t matter, but he chose atheism.
Step 4. The fact that he can prove he can’t prove something is said to mean he is consistent, because an inconsistent thing can prove anything. That does mean he is not inconsistent. However, is it possible to be not inconsistent, and also not consistent? Why can SL’s system be something else? Just because I can’t think of what that might be does not mean it is a logical impossibility. Does not being one necessitate being the other?
If the answer is yes I must be consistent (which I guess it is), that proves you are inconsistent. I find it hard that a valid proof for one thing can also be a valid proof for the exact opposite. We have established that not inconsistent = consistent, and now we have consistent = inconsistent.
Ahh, the penny drops! Maybe I am getting this. You are inconsistent, therefore you can prove anything, even that you are consistent.
You say “If there is anything that you can prove you can’t prove, then you can prove anything.” Going back to Godel, he proved that no system can prove it is consistent. Therefore Godel proved “there is something that you can prove you can’t prove” in every system. Does that mean you can prove anything in all systems? If not why not?
Keshav (#2): Point taken, but the setup of the problem is that I never say anything I can’t prove (which means, among other things, that everything I say is a syntactically well-formed logical statement), and that I make a specific statement about what I can (or can’t prove), which means that my system must have *some* formal way of encoding such things as syntactically well-formed logical statements — i.e. some form of Godel coding is already implicitly assumed. So I stand by the puzzle.
Harold (#1):
It is a tautology that “If some egg is not an egg, then the moon is made of green cheese”.
This is because (if you remember your basic logic), any if/then statement with a false antecedent is automatically true.
Therefore if you can prove that some egg is not an egg, then you can combine that proof with the above tautology to conclude that the moon is made of green cheese.
Note: I changed your “inconsistency” from “eggs are not eggs” (which is not a real inconsistency) to “some egg is not an egg” (which **is** a real inconsistency). Your version is not inconsistent because it might be the case that there are no eggs, in which case it is *true* that every egg is not an egg.
Harold (#5): I’m not sure I quite understand what you’re asking at the end.
But maybe this will help:
If you are consistent, there is at least one thing you can’t prove. For example, if you are consistent, you can’t prove that “some egg is not an egg”.
But it’s also true that if you are consistent, you can’t prove that you can’t prove that some egg is not an egg.
It can still be the case, though, that *I* can prove that you can’t prove that some egg is not an egg.
In brief:
If you’re inconsistent, you can prove anything.
If you’re consistent, there are things you can’t prove, but you can’t prove that you can’t prove them. [But others *can* prove that you can’t prove at least some of those things!]
Rob Rawlings (#3 and #4): Yes, that is the implication. Of course, nobody believes in the first place that any human being has ever restricted him/herself to making statements that are valid logical consequences of a fixed set of axioms.
Presumably when you say I can’t prove X, your are often doing it in a context where Godel’s second incompleteness theorem does not hold as you aren’t talking about your own logical system.
For example you might be talking about whether someone committed a crime and the logical system you are talking about might be the criminal justice system.
Also in conversation when you say “I cannot prove X” then you are often mean “I cannot prove X to you” which is a statement about the implicit logical system that you can use to persuade other people, which may have different axioms to your system.
I think this is more of a logic puzzle than a heavily applicable theorem.
@Harold
Regarding your Gödel question, he proved that no consistent system can prove it is consistent *using its own axioms*. No inconsistency arises from proving this fact using meta-analysis outside the system.
If you know anything about computers, it might be useful to compare it to the halting problem (since they’re very closely related). There’s no computer program that can prove whether or not it will eventually halt while calculating a given set of inputs. That doesn’t mean that we can’t prove there’s no such computer program. It’s a very easy proof by contradiction using a logic system that doesn’t share the same properties of computer programs.
The incompleteness theorem is not proven for all conceivable systems–only for those that contain specific properties. (Completeness and consistency, for example.)
SL “But others *can* prove that you can’t prove at least some of those things!”
Swimmy ” No inconsistency arises from proving this fact using meta-analysis outside the system.”
Ok, thanks.
Steve, even if your belief system can be translated into symbolic language as some formal system T, it is still the case that the statement “My belief system is consistent” is not the same as Con(T). Con(T) is a very specific statements. Con(T) states (informally) “There is no natural number n which is the Gödel number of a proof in T that (say) 0 = 1.” That is very different from the metatheoretic statement “There is no proof in T that 0 = 1.” One is a statement of arithmetic, the other is a statement of metamathematics. But statements are formalizable, but they’re formalized differently. There is a formal language of metamathematics which is different from the mere language of arithmetic.
Keshav: yes, this is my point exactly. The setup of the problem clearly says that anything I assert must be read as a formal statement of the system, not a statement in some metasystem. The distinction is critical, which is why the problem is presented as it is.
Steve, I am not at all talking about statements that cannot be expressed in the formal system T. What I am saying is that the formal language of T can contain far more than the formal language of first-order arithmetic. In particular, it can contain the language of, say, quantified provability logic, and thus talk explicitly about the notion of proofs. So it can make explicit statements of the form “there does not exist a proof P that 0=1”. And that would be a very different statement than a statement of arithmetic that asserts that there exists no Gödel number n which is the code for a proof that 0=1.
The best offer of proof of God is, I’d say, that numbers appear to have a necessary existence (in that their non-existence is impossible – this is called Aseity), and that it appears to be the case that numbers (or we could say mathematics) require an up and running sentience to have any meaning at all.
Jim WK. Your proof seems to assume things must have meaning.
“any if/then statement with a false antecedent is automatically true.”
I had to look this up as it appeared to make no sense, but when unwrapped I can see it is very clear. For anyone else out there struggling.
The point is that if the antecedent does not happen, we cannot say anything about what would have happened had it occured.
say “if the mouse steps on the mousetrap then it will spring”
If the mouse does not step on the mousetrap our statement is true whether if not the mousetrap springs. We did not say anything about what would happen if the mouse did not step on the trap so the statement remains true as there is no contradiction.
Harold “Jim WK. Your proof seems to assume things must have meaning.”
It depends what we mean by meaning. Perhaps we could call it ‘implicit in reality’.
That is to say, the 2 most fundamental, indubitable truths about reality are as follows:
1) Existence is
2) Consciousness is
1 is a certain true proposition because there is existence, and 2 is a certain true proposition because there is consciousness.
There also doesn’t seem to be a way for existence be an ‘is’ without the ‘is-ness’ of mathematics.
Given the foregoing, either consciousness gave rise to mathematics, mathematics gave rise to consciousness, or consciousness and mathematics are inextricable.
‘Mathematics gave rise to consciousness’ seems to be the most epistemologically problematic one of the three, with the other two hinting at consciousness being the primary ‘is’ in existence.
“‘Mathematics gave rise to consciousness’ seems to be the most epistemologically problematic one of the three, ” Not according to what I understand is our hosts position in the universe being a mathematical object.
kewl
do hope the puzzle book is a little more accessible tho
Hey Steve,
This is really cool; no matter what, I appreciate Godel’s 2nd theorem better. (Before I really only studied the 1st.)
If you are still reviewing these comments, can you let me know what you think of the following?
Suppose you are teaching a geometry class and a student says to you, “I can prove that in a right triangle, a^2 + b^2 does NOT equal 2c^2. Specifically, I first prove that it equals c^2, and since c>0, it must not equal 2c^2. qed”
Would you say the student just did something wrong?
Bob Murphy: This sounds fine to me (as an outline of a proof). I have a feeling you’ve got a larger point to make, but I fear I’m missing it.
Oops I wasn’t careful in how I worded it, Steve, and I’m guessing that’s relevant. So I presume you are saying the following are NOT equivalent:
(A) “I can prove that a^2+b^2 does NOT equal 2c^2.”
(B) “I can prove that one can’t prove a^2+b^2 = 2c^2.”
So you’re saying statement (A) is fine, but statement (B) is false?
Bob Murphy:
So you’re saying statement (A) is fine, but statement (B) is false?
In essence, yes, but let’s be a little more careful.
Statement A could well be true, and I could well be able to say it. Not necessarily, though, because if my only axiom is “I am not Bob Murphy”, then I can’t say anything at all about numbers, which are never mentioned in my axioms. But yes, if I’ve got a sufficiently rich (and true) set of axioms, then A) is true and I can prove A) is true.
Statement B should be reworded to “I can prove that I can’t prove a^2+b^2=2c^2″. If this statement is true, then I can prove there’s something I can’t prove, which means I can prove I am consistent, which implies (by Godel) that I am inconsistent. Because I am inconsistent, I can prove anything, so in particular I can prove (and can therefore state) statement B). In that case I can also, of course, prove (and therefore state) its negation. So Statement B could be true, but only if I am inconsistent.
One last clarification if you don’t mind, Steve…
In my comments above, I was *not* operating in the world of your blog post. Rather, I was saying in the real world, with mathematics as you would be teaching it in a normal class on Euclidean geometry, consider the following statements from one of your students:
Stmt A: “For a right triangle it can be proven that a^2+b^2 does NOT equal 2c^2.”
Stmt B: “It can be proven that one cannot prove that a^2+b^2 equals 2c^2.”
So if I’m understanding you, you would say your student is right to utter Statement A, but wrong to utter Statement B?
Bob: Once again, you’ve got to be very careful about the distinction between “I cannot prove” (as in the puzzle) and “one cannot prove” (as in your comment). These are very different. You and I might be starting with very different axioms.
It’s entirely possible that neither of us can prove that a^2+b^2=2c^2, that I *can* prove that *you* can’t prove it, but I *can’t* prove that *I* can’t prove it.
So it’s very hard for me to parse your statements without knowing what “it can be proven” and “one cannot prove” mean. You have to tell me whether “it can be proven” means “it can be proven by Bob” or “it can be proven by Bryan” or “it can be proven by at least one person” or…. —- and you have to tell me who the “one” is in “one cannot prove”. Without this extra information, your statements are ambiguous and I cannot know exactly what they mean, let alone whether they are (or might be) true.
>>“‘Mathematics gave rise to consciousness’ seems to be the most epistemologically problematic one of the three, ” Not according to what I understand is our hosts position in the universe being a mathematical object.<<
But we are not talking about the universe, Harold. We are talking about the ultimate explanation for existence – i.e. why anything exists at all. The universe is a mathematical object, but even something as informationally complex as the universe is only a fractional subset of the mathematical complexity that exists.
But here's where things get even tricker, because just as physics doesn't amount to a complexity powerful enough to contain an ultimate explanation, neither does mathematics appear to, unless we can conceive of some kind of cosmic sentience that underpins mathematics through the host owner of mind.
In short, even mathematics doesn't seem to have an existence without an up and running sentience to think it – a mind that could aptly be referred to as God. When we think of complexity we think of a lower level complexity and an upper level complexity. The lowest level complexity would be something containing just a single bit of information. But once we start to think of an upper level complexity, we find that there really is no limit to how complex complexity can get – we are into the realms of infinite complexity with no upper limit – and that seems to be tapping into something associated with God.
This discussion has been useful for me, for I’ve often asserted (carelessly) that we’ll never be able to prove the continuum hypothesis or its negation. What I should have been saying is that if we do succeed in proving one of those, then we’ll be able to prove both of those, i.e., we’ll know our foundational logical system is inconsistent.
Bob Murphy again: My apologies; I’d somehow overlooked your proviso thst we are not in the world of the blog post. Therefore there’s no rwason to assume that any of us is a “logic machine” to whom Godel’s theorems apply.
That said, if a student made either statement—and in particular the second one — then, depensing on how energetic I felt at the moment, I might point out that “one” can (or cannot) prove anything at all, depending on one’s axioms.
Steve,
I appreciate you going through this. FWIW, if you did another post on this, I bet a lot of your readers would understand these issues better. (I.e. rather than you just helping me in the comments here.)
What was tripping me up in your initial post above, was that I thought, “Hang on. This has nothing to do with God. If I say that ‘in standard geometry, I can prove that it can’t be proven that a^2+b^2 equals 2c^2, then couldn’t Steve come back and say I must be assuming I can prove the consistency of mathematics, which Godel showed was impossible?”
So in my back-and-forth with you, I’m gathering that my mistake is in thinking there is an agreed-upon list of axioms for “mathematics.” Like, that’s the whole point, right? Hilbert et al. thought this was the goal, but Godel showed it’s impossible?
If I’m vaguely on the right track, then, can you explain what it means when we casually say stuff like, “Andrew Wiles proved Fermat’s Last Theorem”?
I.e., it seems like mathematicians have no problem talking about somebody proving something. But then when I say, “OK so could I prove that X can’t be proven?” then all of a sudden the waiters drop their dishes and you announce, “We must be careful in our words, young lad. WHO is attempting to prove this?”
Do you see what I mean? I’m not challenging you, I’m just hoping you can clarify.
Bob Murphy:
First, yes, this has absolutely nothing to do with God.
Your geometry example doesn’t *quite* work, because Godel’s theorem only applies to logical systems that can talk about arithmetic. (Which is why I specified in the problem that my axioms include all the standard axioms for mathematics.)
So let me change your example. Suppose you say “I can prove that it can’t be proven that 0=1”.
First of all, it certainly *can* be proven that 0=1; it can be proven by anyone who takes 0=1 as an axiom. So if your statement is true, then it follows that you are able to prove a falsehood, which means that at least one of your own axioms must be false. It is, of course, not too surprising to learn that some people reason from false axioms.
Now let’s make things more interesting by changing your statement to “I can prove that I can’t prove that 0=1″. If this statement is true then you can prove that there’s something you can’t prove, which means that you can prove your own consistency, which means you are inconsistent, which means you can prove that 0=1. So in this case the statement “I can prove that I can’t prove that 0=1” is true, the statement “I can’t prove that 0=1” is false, and the statement “0=1” is of course false. [This analysis continues to assume that your axioms include enough about arithmetic to make Godel’s theorem apply.]
You are right that there is no agreed-upon list of axioms for mathematics. The closest approximation to such a list is probably ZFC (Zermelo Frankel set theory with Choice) but mathematicians routinely and freely adopt axioms beyond ZFC when it suits their convenience. Wiles certainly assumed more than ZFC in his published proof of the Taniyama conjecture (which, together with Frey and Ribet’s work, settles Fermat’s Last Theorem), which occasioned a bit of a scramble to figure out how many of his extra assumptions were really necessary. I am not fully up on the state of affairs there.
Finally, when mathematicians say “prove” in the context of, say, algebraic geometry, they’re usually using the word quite informally in the sense of “give an argument that no reasonable person could dispute”. Of course there can be room for dispute about what reasonable persons can dispute. But when you start talking about logic, the phrase “prove P” takes on a different, very precise meaning, i.e. “provide a list of formal statements, each of which is either one of your axioms or can be deduced from previous statements by standard rules of inferences, and the last of which is P”. Because this was a logic puzzle, that’s the appropriate interpretation of “prove” here.
This is, of course, by no means unique to math/logic. I am perfectly willing to tell my non-economist friends that I “invested” in Bitcoin, but at the same time to deduct points from an exam answer that describes a Bitcoin purchase as an investment.
Thanks Steve this is awesome.
And if you want fodder for a future post, I’d also love to see your argument for why it’s not correct to call the purchase of Bitcoin an investment. (For example, I think if push comes to shove we have to say someone who accumulates $100 bills under his mattress is both saving and investing in cash balances. I’m guessing you would say it is saving but not investment?)
According to physicist Ethan Siegel,
“[Evidence doesn’t support the theory that the universe began with] an arbitrarily hot Big Bang [that is, a singularity], but rather one that achieved a maximum temperature that’s at most hundreds of times smaller than the scale at which a singularity could emerge. In other words, it leads to a hot Big Bang that arises from an inflationary state, not a singularity.
The information that exists in our observable Universe, that we can access and measure, only corresponds to the final ~10-33 seconds of inflation, and everything that came after. If you want to ask the question of how long inflation lasted, we simply have no idea. It lasted at least a little bit longer than 10-33 seconds, but whether it lasted a little longer, a lot longer, or for an infinite amount of time is not only unknown, but unknowable.”
Does it follow that Ethan Siegel’s axioms are inconsistent?
nobody: My pet peeve is his use of this expression: “at most hundreds of times smaller”
What would it mean to be 1x smaller than something? The same size? Is 2x smaller the same as “half as big”?
This is a follow up (I think) to Keshav’s objection.
I have a system in which I can prove there is no countable set that contains my universe. But by the Skolem theorems there is a countable model of my theory. This is not a contradiction because the statements that embody this apparent conflict are different.
So, isn’t my theory just like yours? I cannot prove the existence of an enumeration of everything. In fact I can prove such a set, call it god for fun, does not exist. I can prove enumeration atheism.
I think Keshav is right.
Daniel Grayson
The continuum hypothesis is independent of the other axioms. This was proven by Gödel and Cohen.
Ken: for starters, your assertion is about something you **can** prove; mine is about something I **can’t** prove, so I think your analogy breaks down right out of the box.