The answer to Friday’s puzzle is YES. If I am a logic machine who only states what I can prove, and if I say “If I can prove there is no God, then there is no God”, it does follow that I can prove there is no God.
Once again, it was our commenter Leo who got this first (in Friday’s comment thread, graciously rot-13’d).
As with Thursday’s solution to Wednesday’s puzzle, there are two key relevant background facts:
A) An inconsistent system can prove anything.
B) A sufficiently complex consistent system cannot prove its own consistency. (This is Godel’s second incompleteness theorem.)
Here’s the logic:
1) I’ve asserted that “if I can prove there is no God, then there is no God”. We know that I assert only things that I can prove. Therefore I can prove this assertion.
2) That means I can also prove the equivalent assertion that “if there is a God, I cannot prove otherwise”.
3) Therefore, if I take my axioms and add the axiom “There is a God”, then I can prove that there is something I cannot prove.
4) Therefore, if I take my axioms and add the axiom “There is a God”, then I can prove that my axiom system is consistent (by Background Fact A.)
5) Therefore, if I take my axioms and add the axiom “There is a God”, my axiom system is inconsistent. (Because only an inconsistent system can prove its own consistency — that is, Background Fact B.)
6) Therefore the statement “There is a God” must contradict my axiom system.
7) This can happen only if my axiom system is able to prove that “There is no God”.
So yes, I can prove there is no God.
Of course, from this you can conclude nothing at all about the actual existence of God, because although you’ve learned that my axiom system proves there is no God, you still know nothing about whether my axioms are true.
For more fun along these lines, see here.
All clear now. I have clicked the link but I don’t know if I can take that much fun just yet, so I will read it later.
For the equivalence in (2), I think you’re assuming that excluded middle is one of your axioms.
Daniel R. Grayson: No, not an axiom—a rule of inference. (Or, I suppose, you could make it an axiom schema.)
Ok, I can’t say that I’ve fully digested this stuff yet. So let’s jump in at the shallow and deep ends simultaneously.
1.
Can we think of examples of simple systems that could prove their own consistency? Or is Landsburg using the term “sufficiently complex” to gloss over some technical specification that does not lend itself to a conversational level of analysis?
2. I can’t tell if Landsburg’s various puzzles are examples of David Hilbert’s Entscheidungsproblem. Curiously, Alonzo Church and Alan Turing each concluded that the problem (when defined with sufficient rigor) could not be solved. I understand that to mean that they concluded that a solution does not exist.
Shall I also conclude that they drew this conclusion by analyzing the problem from some logical framework beyond the context of the Entscheidungsproblem?
(At this point I feel like Costello:
Costello: “So I pick up the ball and throw it to who?”
Abbott: “Now that’s the first thing you’ve said right.”
Costello: “I DON’T EVEN KNOW WHAT I’M TALKING ABOUT!”)
Steve,
Like Daniel Grayson, that particular step in your argument tripped me up a bit. It wasn’t jumping out at me that those 2 statements were equivalent.
Also, sorry to post about it here in public, but I tried sending you an email about a professional matter, just want to make sure you got it. (Not sure if I used the right address.)
Among the many things that puzzle me about this problem, now I’m struggling to understand Grayson’s and Murphy’s concerns.
Landsburg postulates at 2 that “if I can prove there is no God, then there is no God” implies “if there is a God, I cannot prove otherwise.” This looks a lot like modus tollens to me.
Ok, perhaps we could say that the better translation is “If not (there is no God), then not (I can prove there is no God),” or perhaps more colloquially, “If God’s existence is indeterminate, then I can’t prove God’s non-existence.”
If we substitute this sentence for Landsburg’s sentence at 2, does any of the rest of Landsburg’s argument change? I don’t think so.
Yikes! You’re right nobody.really, I think I misread it (or just had an inconsistent mental framework…). Yeah the one statement obviously implies the other, not sure why I wasn’t seeing that initially.
Steve wrote:
“because although you’ve learned that my axiom system is consistent”
Didn’t we learn that your axiom system is *in*consistent?
I wrote:
“Didn’t we learn that your axiom system is *in*consistent?”
I take that back, but I still disagree that we learned that your axiom system is consistent. Nothing you say can convince us of that, since if your system is inconsistent, you can prove and therefore say anything.
Dan Christensen: you’ve caught a key typo. Editing to correct. Thanks.
@nobody.really:
You say: “Landsburg postulates at 2 that “if I can prove there is no God, then there is no God” implies “if there is a God, I cannot prove otherwise.” This looks a lot like modus tollens to me.”
At 2 Landsburg says the two statements are *equivalent*, not just the one implies the other.
Steve:
You say “Daniel R. Grayson: No, not an axiom—a rule of inference.”
If Excluded Middle is actually needed for solving the puzzle, then the statement of the puzzle needs to reveal it is in use.
Dan Grayson:
You might have a better sense of the conventions than I do, but:
1) clearly there are some venues in which (by convention) excluded middle is generally assumed when it’s not mentioned (e.g. most graduate level math classes)
2) clearly there are other, much less numerous, venues in which excluded middle is **not** generally assumed when it’s not mentioned (e.g. a conference on constructive methods in algebra)
3) I’m pretty sure that even most courses in mathematical logic fall into the former category, and that (by convention) so do most problems and puzzles about logic (excluding those which are in some sense **about** dependence on excluded middle). That would include the case at hand.
But if you disagree, I’m happy to reword the puzzle accordingly.
Dear Steve,
You make a good point, which might be used to resolve any ambiguity in the phrase ” … from those axioms via the rules of logic.” I might be tempted to insert the word “classical”, though.
However, maybe the equivalence referred to in 2 is not needed, and only the modus tollens implication is needed. I did not check the rest of the argument for a use of the equivalence.
Dan