“With no restrictions on their other axioms, why can’t they both be false?” What? My head is spinning from trying to understand this answer in the context of logic. A has to have a truth value by LEM. ~A would have to have the opposite truth value. How could they both be false?
“*‘theorems which cannot be proved’ is a contradiction in terms. *” I apologize, that was sloppy wording. I meant true statements that cannot be proved. These are not legal moves for Life, and so they can never happen. Life is incomplete.
“It may not find all the sentences that are true in that theory, but that’s not a problem for a theorem-prover.” But it is a problem when my point is that the universe is either incomplete or inconsistent, see?
“*The game of life is only Turing-complete when played on an infinite grid. *” I mentioned this caveat.
I didn’t have time to address this question yesterday, but happily the issue has come up again.
Let’s be absolutely clear: Godel’s incompleteness theorem uses the term “formal system” in a very specific sense, that of an “axiomatic formulation of number theory”, as your link puts it. That’s a very specific mathematical object, containing a set of sentances (the well-formed statements of number theory), a subset of axioms, and rules for constructing valid proofs.
Now my next question is going to sound incredibly pedantic, but it has to be asked: what are the axioms of the formulation of number theory known as “the universe”? Where are its rules for constructing valid proofs?
Saying that I have a formal system of number theory in my head…that is, saying that the universe contains things capable of reasoning about number theory…isn’t good enough. That’s the point of my hypothetical cellular automaton universe. It contains programs which are capable of manipulating statements of number theory, but the automaton itself isn’t somehow inconsistent. It works just fine. The only effect that Godel’s theorem has on the automaton’s behaviour is this: that the program being simulated by the automaton can never prove certain statements.
[QUOTE] Originally posted by erislover *
**Let me restate my problem for clarity[list=1][li]The operation of the universe may be abstracted to the level of a formal system[]This formal system is a subject of GITs.Thus, the universe is incomplete or inconsistent[/list=1]**[/li][/quote]
The problem is step one. The operation of the universe may be abstracted to the level of a mathematical system, but not the kind of formal system of number theory to which Godel’s theorem applies.
This, at least, is true…but it has nothing to do with Godel’s theorem specifically. The program running on the automaton will never prove that 2+2=5 either, assuming that the program is correctly written.
This, quite simply, is not a correct statement and is symptomatic of my problems with the OP. You’re applying Godel’s Incompleteness Theorem way too broadly. A formal system of number theory cannot be described as “Turing-complete” or “not Turing-complete” because a formal system of number theory doesn’t perform computations. And something which does perform computations is not a formal system of number theory, and hence is not within the domain of Godel’s Incompleteness Theorem.
You claim that “adding a middleman”, as you put it, is an unnecessary complication, but I content that it’s a vital step. Godel’s theorem itself draws a very sharp distinction between models of number theory and physical reality, between the concepts of “provable” and “true”. And that’s the brilliance of it. Without that distinction, the second part of Godel’s theorem, the part that says there exists a statement which is either true and unprovable or false and provable, wouldn’t be meaningful.
Sorry, I wasn’t clear. I didn’t mean to say that A and ~A are both false, but that if I take two theories and add A as an axiom to one and ~A as an axiom to the other, then it’s possible that both theories can have false axioms. Either A or ~A is true, but the other axioms can be true or false as you like. Hope this is clearer.
**
I think you’re confused by the difference between Godel-style completeness and Turing-completeness. Life can’t find all the true statements, but it can do everything a Turing machine can. Since Turing machines can’t even decide (in general) whether a given statement is true, how should one expect them to find all the true statements.
As for the universe being complete and consistent, I still maintain that the universe is not a formal system in the Godel sense, and so those adjectives don’t apply. The burden of proof is on you to show that it does fit the definition of a formal system.
Math Geek
“That’s a very specific mathematical object, containing a set of sentances (the well-formed statements of number theory), a subset of axioms, and rules for constructing valid proofs.” And I don’t want to be too bogged down in this, but I raised the issue so it is my cross to bear. If the universe is not inconsistent, then it has atomic things (in the semantic sense, not in the physicist’s use of “atom”). It also has well-formed relationships between these things (forces, perhaps?), and let us say initial conditions. I think it is absurd to say that the abstract mathematical object finds expression no where but in our heads. Math has, for a very long time, been linked to exploring the real world, and it is no trick. Math and the real world are linked (by my assertion in the OP, too). Their structure is entirely similar, and the quest for understanding math is roughly parallel to the quest for understanding the universe; so much so that at times it is difficult to distinguish the two.
You want to say that the structure math takes is somehow not indicative of the state or nature of the universe as a whole, but this still seems downright paradoxical to me. The game of Life discussed here can be said to perform certain mathematical operations. But the game of Life is undeniably a “physical” thing (however we metaphysically dfine physical; that is, in the Berkeley sense or not). It operates within the construct of the universe!
So how can we say there is no reverse implication?
“The program running on the automaton will never prove that 2+2=5 either, assuming that the program is correctly written.” That’s an unfair statement. You suggested that the program would seek out true statements, and I suggested that (by ultrafilter’s mention) there were true statements which it wouldn’t produce. It produces all theorems, yet falls short of all true statements. Of course it wouldn’t prove 2+2=5. You programmed it! Don’t blame me
“A formal system of number theory cannot be described as ‘Turing-complete’ or ‘not Turing-complete’ because a formal system of number theory doesn’t perform computations. And something which does perform computations is not a formal system of number theory, and hence is not within the domain of Godel’s Incompleteness Theorem.” If this is a crucial error I would like to correct it if I can, and perhaps in working with this can further the issue. Let me mention here as a preface, and with a voice loud enough for ultrafilter to hear, that I did not bring Turing machines into this at all. I was happy not ever even discussing them. But they were brought up, and so I will have to integrate them or dismiss them. I think they illustrate the point rather well, though this is another nonsense alert. I am stubborn, but I will admit an error (unless the error is in seeing an error, of course, in which case I’m screwed ;)).
You are trying to seperate the system from a tool which acts inside the system. Godel’s theorem only applies to the actual formal system, and decidablity in those systems. Let us take formal system A. Turing machine T acts to prove all true statements of A.
Tell me why this is impossible without linking “statements about” the formal system and operations of the tool. If you can do that, I think I will be convinced rather quickly.
“Godel’s theorem itself draws a very sharp distinction between models of number theory and physical reality, between the concepts of ‘provable’ and ‘true’.” No doubt. So tell me when we get to the point that we can’t make a mathematical model of the universe, because until then I have a hard time not looking at the universe as the game of Life operating within “God’s” math.
ultrafilter, gotcha on the a/~a thing. It seems that a response to your points is actually given above.
—Math has, for a very long time, been linked to exploring the real world, and it is no trick.—
But don’t get tripped up in using that word “linked.” Just because something is “linked” (associated with) doesn’t mean that it is “linked”(has a two-way causal connection with).
—So how can we say there is no reverse implication?—
Just because one is carefully modeled to be useful for dealing with the other, does not mean that the defects of the model even have any MEANING for the original.
At this point, I have no idea what you mean by “the universe is not inconsistent”. I know what it means for an axiomatic formulation of number theory to be inconsistent, but it hasn’t been established to my satisfaction (or ultrafilter’s, it seems) that this definition extends to the universe as a whole in a meaningful way.
I do not want to say any such thing.
Look. I am not denying that the universe has mathematical structure. That would be as silly, to my mind, as denying that Conway’s Game of Life has mathematical structure. But the nature of that mathematical structure is not that of an axiomatic formulation of number theory!
(How the heck is this an “unfair” statement???)
First of all, I never suggested the program would seek out true statements, I said it would seek out provable ones. You said, correctly, that this meant the automaton was “forbidden” to perform actions that would result in the proof of an undecidable theorem. But that’s hardly a deep consequence of Godel’s theorem, that’s just logic! Of course a program which produces correct proofs won’t produce a proof of something for which no correct proof exists!
Hence the “2+2=5” comment. The only thing proved by the fact that the automaton’s program won’t proof undecidable statements is the fact that a logical proof can’t be produced for something for which a logical proof doesn’t exist. This is hardly a significant physical consequence of Godel’s incompleteness theorem.
Okay, time for a deep breath…I think you’re missing the intended point of my whole automaton example. Think of the infinite array of cells as the “universe”, and Conway’s rules (2 neighbours=life, 3 neighbours=growth, etc.) as the “laws of physics”. The question then becomes, “What effect does Godel’s theorem have on the functioning of this universe?”
More specifically, you asked the following questions in your OP:
**
None of the three options presented in the paragraph above apply to the automaton “universe”. Clearly the automaton “universe” is deterministic. It’s also quite consistent: the “laws of physics” never break down, and a cell is always either “on” or “off”. And the automaton “universe” is self-evidently completely describable by mathematics. And yet the laws of this universe are still rich enough to permit it to contain entities which can “reason” about the behaviour of formal systems of number theory, namely the program which the automaton is simulating.
So why should we assume that one of the three options above must hold for the real universe? Why can’t the real universe be deterministic, “consistent”, and completely describable by mathematics…despite the existence of Godel’s theorem?
The only necessary effect of Godel’s theorem on the real world that I see is the self-evident one: that it is impossible for there to exist a logical proof of certain statements in certain formulations of number theory. Just like it is impossible for there to exist a logical proof that 2+2=5.
To recap: I am not denying the existence of a mathematical model of the universe. I am denying that Godel’s theorem applies directly to that model. As a consequence, the term “inconsistent”, as applied to the universe as a whole, is not well-defined; the definition Godel used certainly doesn’t apply.
"At this point, I have no idea what you mean by ‘the universe is not inconsistent’. It could mean more than one thing. I don’t know how you think of the universe, so it is difficult for me to say what would please you. The existence of identity would be a good one. If the universe is deterministic, then every possible state will lead to a definite possible state unambiguously. That’s another.
Inconsistant = has a contradiction. You later use the term in connection with this life game, so I think you have a pretty good grasp of what it means to have a consistent universe.
“But the nature of that mathematical structure is not that of an axiomatic formulation of number theory!” Hahaha, I feel like Abbott and Costello here, as my response will be the same. But this structure can output number theory! In doing so, it will output Godel’s Theorem. If we want it to, it can output a description of itself. In doing so, it will tell anyone who can read its output that it can’t output all true statements, that it is incomplete.
"Why can’t the real universe be deterministic, ‘consistent’, and completely describable by mathematics…despite the existence of Godel’s theorem?" Actually, I rather think it is. It is just incomplete. There are states that the universe can be in which it never will, and which we can never show it will, or that it won’t. If we could, then I think it wouldn’t be consistent in that we would have a state of the universe which could lead to two or more different states without an unambiguous resolution. That’s my point.
Consistency is not the same as deterministic. In fact, I can’t think of anything to which both terms apply. I hate to say it, but I’m starting to think this whole debate is based on confusion. I wish I could offer a pointer to a nice book that explains these things, but all the books I can think of are graduate-level math texts.
Not to confuse the issue more, but a formal system is consistent iff there is some sentence which is not a theorem of that system. There are systems which contain contradictions and are still consistent; they just have different rules of inference. If that doesn’t make sense, forget I said it.
**
Maybe not. Maybe it only outputs its initial conditions and the rules for moving along. I don’t think (but I’m not sure) it’s possible to prove that a formal system is incomplete within that system, so those of us in the universe are in trouble wrt your project.
Well, I was going of Mathworld’s definition, which is pretty much the regular dictionary definition, too, of consistency which said that there was no contradiction. Especially since it was linked from the GIT page. Wikipedia also seems to agree with this, so you have indeed confused the issue.
I have never before heard that consistency didn’t imply non-contradiction, and yet I have no reason to doubt you, and I certainly can’t just forget something like that! lol
At any rate, I never said determinism was the same as consistency, but rather what consistency (as non-contradiction) would mean in a deterministic universe. In a deterministic universe without contradiction with respect to determinism, every state leads unambiguously to another state. Consistency with respect to identity would mean that for every object, that object is uniquely definable (for instance, though there could be other definitions I’m sure).
I mean, shit, I don’t have God’s math, so I can’t tell you exactly what consistency (or non-contradiction, pending your most recent post) means with respect to it. The hypothesis is that God’s math exists, and I don’t think it to be so unreasonable since that’s why we do science in the first place.
Sure. The reason that a contradiction implies inconsistency in standard predicate calculus is because the rules of inference allow you to derive any statement from a contradiction. Change the rules of inference, and you’ve got a different system.
Suppose I design a system U as follows:[ol][li] The underlying language and rules of sentence formulation are the same as in the standard predicate calculus.[/li][li] There are no logical axioms.[/li][li] The only rule of inference is U-introduction. If, when all the variables of a sentence [symbol]g[/symbol] are replaced by constants (in accordance with the rules laid out in the standard predicate calculus), the main connective of [symbol]g[/symbol] is not [symbol]«[/symbol], then [symbol]g[/symbol] is a theorem of U.[/ol]Contradictions can definitely be derived in U, but no statement of the form A [symbol]«[/symbol] B can be derived. Therefore, U is not inconsistent, even though it has many contradictions as theorems.[/li]
Of course, I don’t have my logic book here with me, so I’ve probably messed a couple of the details. Nonetheless, I think the basic idea comes through. Does this make sense?
I have to ask: if we can never show it will or that it won’t, how do you know it never will?
More seriously though, what are these states you’re talking about? The only thing in the universe precluded by Godel’s theorem is a number-theoretic proof or disproof of certain number-theoretic statements. And that’s not a case of a state “that the universe can be in but which it never will”. It’s a case of something which can’t happen, period.
The rest of it, the stuff about a state which could to lead to two or more different states, is pretty much gobbledygook because Godel’s theorem has absolutely nothing to do with determinacy.
I stand by my contention that you’re applying Godel’s theorem way too broadly.
Three is obviously the sticker, but it seems to me to be a direct rejection of the transitive property, which means it is not a system which could ever express multiplication, and so for the purposes of discussion wouldn’t fall prey to GIT anyway.
“I have to ask: if we can never show it will or that it won’t, how do you know it never will?” Because it getting there would show it could get there!
“The only thing in the universe precluded by Godel’s theorem is a number-theoretic proof or disproof of certain number-theoretic statements. And that’s not a case of a state “that the universe can be in but which it never will”. It’s a case of something which can’t happen, period.” Then you are missing the point I was trying to make. Consider that if the universe is in a particular state it means the proposition is true; i.e.- a possible state (“The world is everything that is the case”, as Wittgenstein would put it). This theorem (proposition p is true; the universe will be in such a state) is unprovable. This means the universe could never get to that state through its physical laws, as the act of getting there would be the theorem which is unprovable. This means the universe is incomplete; that is, all possible states of existence (all propositions) won’t happen (can’t be shown to be true).
“…is pretty much gobbledygook because Godel’s theorem has absolutely nothing to do with determinacy.” It has everything to do with mathematical determinacy. By hypothesis, the universe is math. Please tell me you see what these two statements have to do with each other.
I’m sorry to be asking such a basic question, but if I don’t ask I won’t learn …
Does Godel’s theorem only apply to number theoretical systems that follow standard predicate formulations? Would it apply to systems that accept that both A and notA are true to various degrees? (I’m getting at quantum formulations here).
Thanks for the help from one of us who is trying to play along at home.
Oops, you’re right. That was very sloppy logic on my part. GIT (and it’s converse) do not make assertions about anything that is not a formal number theory.
But count me with DSeid as curious about the quantum angle. As a novice, Eigenstates look an awful lot like a paradox embodied in a physical system. Could a formal number theory embrace that system? Perhaps one with different rules of inference, as Ultrafilter pointed out?
Very elementary quantum computers have been created, right? Maybe their logic embodies a formal number system, but they are physically able to perform formal operations on several statements simultaneously.
One half of GIT says that there will be inconsistencies in any formal system that isn’t incomplete, so with respect to my OP you might be putting the cart before the horse.
Yes, Godel’s theorem does require that. I don’t know if quantum logic rejects the LEM, but I think it’s only been formulated for propositional logic (no variables or quantifiers), so there may be no room for incompleteness, if it’s decidable (i.e., a computer can check whether a sentence is a theorem). Whether quantum logic is decidable is still an open question, I believe.
