patrick.net

Heraclitusstudent says

In fact to interpret this theorem as incompleteness, you need to assume there is step in the demonstration that is achieved by a human mathematician but cannot be achieved by executing logical rules

I don't follow this. There's no human anywhere in the theorem.

There is no assumption in the hypothesis or proof of the incompleteness theorem as to the humanity of anyone considering the truth or provability of a proposition. It simply says that in any consistent axiomatization there will be statements which are true but not provable from the axioms.

There are propositions which are true, such as A OR (~A). This means they hold in all possible models - no human mathematician required - A OR ~A has the added virtue of being provable. So at least some of these are provable (again, a statement not requiring a human to execute the proof of each one); in an incomplete system, not all are provable, in the sense that no proof from the axioms exists (and sending in teams of humans to search for one won't change this, because it won't create something that has been proven not to exist).

I really hate to use the term "paradox" around this stuff, because there is no paradox. All that happened here was that we humans were too optimistic when we assumed that a program to produce a consistent, complete axiomatization of mathematics could be successful. A total bummer, but not a paradox.

HydroCabron says

I don't follow this. There's no human anywhere in the theorem.

Well... it doesn't have to be human BUT:
- on 1 side you have a system mechanically deriving theorems as a way to prove something
- on the other side you have a human mathematician.

Then you exhibit this assertion that is proved true by the mathematician but you claim that the mechanical system will never be able to mechanically derive this assertion (the assertion corresponding to itself). Which is exactly why people refer to it in the context of the existence of God: You are implicitly saying that human mathematicians seem to be doing something that machines cannot do.

This is nonsense. Everything the mathematician has done can be done by a large enough formal system as well.

Which then implies inconsistency.

Heraclitusstudent says

With regard to the Godel theorem we are talking of the number theory as a logical theory. It's about logic more than arithmetic.

Most of mathematics exist without having to care about formal logic. Mathematicians use logic but not in a formal way.

I'm guessing you weren't a Math major.

I see you're still talking about "the number theory." I don't know, maybe it's different in Europe ? (you also referred to "Maths"). Canada maybe ?

I took an undergrad course called number theory. Number theory is hugely important to Abstract algebra which is about topics such as groups, fields, and rings built up off of axioms. But even basic arithmetic (not just doing it, but proving that it's valid) requires a lot of axioms and theorems.

Heraclitusstudent says

Most of mathematics exist without having to care about formal logic. Mathematicians use logic but not in a formal way.

Most of the Math classes I took that were 200 level or higher were 95% proofs. The professor would spend the entire class doing proofs. (somewhat formal) There were exercises, but we were on our own with those. It's not like they did examples of similar problems in class, which is what Math is at the level that I teach.

As for this discussion, I find Godel's Theorem to be fairly easy to understand, but not it's proof, but then I haven't dug that deep in to it. Maybe I'm too simple minded about this, but I think that if anything this theorem propelled Math forward by giving some Mathematicians the ability to be okay with a system being consistent and effective but not complete. Therefore even being okay with sometimes running in to an axiom that might be thought to be needed for some trivial theorem (not required for effectiveness), but which would cause an inconsistency and therefore leaving that axiom out.

One other thought that might be part of the confusion. The bizzarre logic Godel used proving that such a statement would exist: "A is true iff it's unprovable" or something to that effect, doesn't mean that therefore every inconsistency that you might run into as you added the possibly infinite number of axioms required for completeness is of a weird self referential nature. That's simply the route he went to prove the theorem.

marcus says

I took an undergrad course called number theory. Number theory is hugely important to Abstract algebra which is about topics such as groups, fields, and rings built up off of axioms. But even basic arithmetic (not just doing it, but proving that it's valid) requires a lot of axioms and theorems.

It looks like what you call Number Theory has nothing to do with logic. In the current context what I call Number Theory is a logical theory . A logical theory is a formal system where AXIOMS are used to mechanically derive THEOREMS using rules. I capitalize the terms because they don't mean exactly the same as in the rest of mathematics. In traditional mathematics is simply an assertion that is proven in given conditions. Here it is an assertion that is formally derived using a (long) sequence of small steps. No mathematicians ever bother with such formal methods.

marcus says

Maybe I'm too simple minded about this, but I think that if anything this theorem propelled Math forward by giving some Mathematicians the ability to be okay with a system being consistent and effective but not complete.

It didn't propel mathematics forward. It represented the failure of Hilbert's program: an attempt to establish sound basis for mathematics. The fact that they are incomplete means these formal logical systems are useless.

marcus says

I find Godel's Theorem to be fairly easy to understand, but not it's proof, but then I haven't dug that deep in to it.

To understand Godel's theorem you need to understand the proof. More specifically the final ad absurdum part I mentioned. You need to understand why it requires semantic, which is the part the human is doing but not the system.

marcus says

doesn't mean that therefore every inconsistency that you might run into as you added the possibly infinite number of axioms required for completeness is of a weird self referential nature. That's simply the route he went to prove the theorem.

Well, arithmetic is consistent if you have a physical interpretation of what numbers are. So you can't simply add any axiom you want: They have to be true within the usual interpretation of numbers. So inconsistencies do not simply arise like this. However there are a number of well known paradoxes, for example Russell's paradox in the set theory, and they all involve self-reference or referential loops. Self-reference within a language is the source of the problem, not arithmetic.

Heraclitusstudent says

You need to understand why it requires semantic, which is the part the human is doing but not the system.

As I said, this is just how he proved it. It doesn't mean that if complete, the inconsistencies will be of this nature.

Heraclitusstudent says

Self-reference within a language is the source of the problem, not arithmetic.

I believe you've got it wrong, and I'm not saying there is a problem with arithmetic. IT's that Godel used arithmetic(the existing axioms of arithmetic) regarding the properties of the natural numbers and logic to prove that a system such as this is either consistent or complete but not both. The self referential statements he came up with to prove this were the result of the logic mathematicians use. That is simply how he proved it. The result is generalizable and true not because of the way he proved it. That is, the result is not a special case as you believe having to do with the way he proved it.(this is logic)

But also, if you're interpretation were correct, then there isn't a problem anyway. In either interpretation, as long as there are no non-trivial inconsistencies we're good. That is, as long as all useful results are consistent, we're good.

By the way, I don't claim a high level of expertise in this topic, but I do have some understanding and experience with how an axiomatic system is built.

marcus says

It doesn't mean that if complete, the inconsistencies will be of this nature.

What other nature is possible? What paradox do you know that is not based on referential loop?
Do you believe arithmetic is in fact inconsistent?

marcus says

The self referential statements he came up with to prove this were the result of the logic mathematicians use. That is simply how he proved it. The result is generalizable and true not because of the way he proved it.

It is true what I said about self-reference is incidental here. It doesn't change what I said before about interpreting this as inconsistency rather than incompleteness.

marcus says

if you're interpretation were correct, then there isn't a problem anyway. In either interpretation, as long as there are no non-trivial inconsistencies we're good.

Well we're good except... as I said...
- First, admitting that there is an inconsistency utterly destroys the way logic itself was formalized in mathematics. Because if an inconsistency exists then every assertion becomes true, because of the way A => B is formalized. So we're good... provided you rewrite all mathematical logic since the 1900's in a different format.
- Second, you don't get to claim there is an inconsistency in this number theory without explaining what it means with regard to arithmetic in general. i.e. you need to explain why there is an inconsistency, and how to circumscribe it so that it doesn't contaminate standard arithmetic. This is what I did by ascribing it to self-reference in the language rather than a consequence of numbers properties.

Heraclitusstudent says

Then you exhibit this assertion that is proved true by the mathematician but you claim that the mechanical system will never be able to mechanically derive this assertion

Because he proved there are well-formed, true statements which cannot be derived from the axioms. That is, there exists no derivation - "mechanical" is meaningless in this context.

An analogous situation is trisecting the angle with the straightedge and compass, or squaring the circle (with just a straightedge and compass). In the 19th century, an understanding of the nature of number systems led to a categorization of all the line lengths and angles one could get - with straightedge and compass, starting with a line and an angle: it turned out that the lengths and angles achievable did not include either the length necessary to square a circle or the angle 1/3 of the original angle. This proved that you cannot trisect an angle or square the circle - there is no sequence of steps to do so with a straightedge and compass.

Many people refuse to believe that one can prove something impossible. Hence there are thousands of trisectors working on finding a solution as I write this. But you really can prove that there exists no algorithm to accomplish something, or that there is no proof of certain true statements.

HydroCabron says

Because he proved there are well-formed, true statements which cannot be derived from the axioms. That is, there exists no derivation - "mechanical" is meaningless in this context.

HydroCabron says

Many people refuse to believe that one can prove something impossible

I absolutely believe some things can be proven impossible. There are functions that are not calculable. They are not for humans. Neither are they for computers. There are numbers that cannot be described as rational nor roots of polynomials functions.

This is not what is going on here. What is going on is you are refusing to acknowledge the consequences of what you are saying. Mechanical is not meaningless at all. An axiomatic system acts mechanically. A computer acts mechanically. A computer can be fully described by an axiomatic system.
So you are saying a human did derived the fact that an assertion is true, but the same assertion cannot be derived by a computer within a formal system. Since everything physical can be modeled by computers, it follows you just proved human brains are not based on the laws of physics. Congratulation.

Heraclitusstudent says

So you are saying a human did derived the fact that an assertion is true, but the same assertion cannot be derived by a computer within a formal system.

That's exactly what I am saying. (Well, almost - I don't give a hoot about "physical," "mechanical," or computers doing this - the proof doesn't exist, no matter who attempts to find it. Saying "it doesn't exist" is stronger than saying "nobody can find it.")

And this is not a contradiction or paradox.

"True" in this setting means "valid for all models"; it does not mean "can be proven by a computer or a human being using mechanical methods, from the axioms."

Let T be the condition that a statement is valid for all models. Let D be the condition that the statement can be derived from particular chosen, consistent axioms.

Godel proved that T is not the same thing as D. That is, that there are statements for which T holds but not D. That the two conditions are not identical is surprising to humans; hence the impact of the theorem, which shut down Hilbert's program, as you mentioned. But I would not call it a paradox to say that T and D are different conditions, because the demonstration is accessible to motivated undergraduates. I would call it a discovery.

Most importantly: Godel did not prove that "computers/humans can't find such and such a demonstration of a true fact", although that is a consequence of the incompleteness theorem. He proved something stronger: the demonstration does not exist.

It's like proving that the moon is heavier than a golf ball. Sure, that implies that a computer will never show that a the moon is lighter than or the same weight as a golf ball, but that's a consequence of the fact that the moon is heavier than a golf ball, which is the stronger fundamental truth.

Seriously: the impossibility of trisecting an angle lies in the simple fact that a trisection does not exist. Human mathematicians proved that something does not exist; therefore, no computer or human can find it. It's the same situation. Please promise me you won't go and try to trisect angles.

HydroCabron says

"True" in this setting means "valid for all models"; it does not mean "can be proven by a computer or a human being using mechanical methods, from the axioms."

Yes and the whole point of a derivation - either in the formal system or as an 'informal' mathematic proof - is to establish that an assertion is valid for all models.

The bottom line is that, in the proof of Godel's theorem, the human mathematician finds a derivation of an assertion, i.e. a proof that this assertion is true, while claiming this cannot be done by a mechanical system.

Again you are just trying to dismiss the consequences of what you are saying.

HydroCabron says

I would not call it a paradox to say that T and D are different conditions

To be clear, I didn't say Godel's theorem itself is a paradox. I said the assertion G that is the object of Godel's proof is a paradox.

HydroCabron says

Godel did not prove that "computers/humans can't find such and such a demonstration of a true fact", although that is a consequence of the incompleteness theorem. He proved something stronger: the demonstration does not exist.

I'm wondering at that point if you are familiar with Godel's theorem proof.
This demonstration is all about showing that a given (carefully built) assertion is found true but not a theorem.
And when I say "not a theorem" I mean Godel never proved the demonstration doesn't exist . He simply said that if it exists then the system is inconsistent.

Heraclitusstudent says

Because if an inconsistency exists then every assertion becomes true, because of the way A => B is formalized.

No, if an inconsistency exists, you have too many axioms. Make do with fewer axioms and have a useful system that is consistent.

If you then run across something that's interesting and clearly true, and you can't prove it with existing axioms and theorems, and you want to make it an additional axiom, or you want to add some other primitive axiom that will allow you to prove this, but that new axiom leads to inconsistencies elsewhere, then don't add the axiom. Stick with fewer axioms, but a consistent system.

I don't see what's wrong with this. Such a system isn't false. IT just can't do everything that you want it to.

marcus says

Heraclitusstudent says

Because if an inconsistency exists then every assertion becomes true, because of the way A => B is formalized.

No, if an inconsistency exists, you have too many axioms.

You are missing the point.
A => B is modeled in mathematical logic by the following truth table:
A B A =>B
T T T
T F F
F T T
F F T

If A is false, A=> B is always considered True. Regardless of B. This normally doesn't cause any problem because if A is false this rule is never triggered, but as a result (P & ~P) => B can be proved in propositional calculus for all B.
It follows that ALL B can be proved in the number theory if it turns out to be inconsistent.
In other words: inconsistency = catastrophic failure of the system.
As I said, this is an idiosyncrasy of this particular formulation. A => B should not be considered a function of A and B.
But this needs to be dealt with.

Heraclitusstudent says

You are missing the point.

I understand boolean logic. More so years ago.

Someone is missing the point. I agree that if a system is inconsistent in nontrivial ways, then it's not useful and it can't be used with computers to do stuff.

But you don't seem to understand that you aren't going to have inconsistencies.

marcus says

No, if an inconsistency exists, you have too many axioms. Make do with fewer axioms and have a useful system that is consistent.

If you then run across something that's interesting and clearly true, and you can't prove it with existing axioms and theorems, and you want to make it an additional axiom, or you want to add some other primitive axiom that will allow you to prove this, but that new axiom leads to inconsistencies elsewhere, then don't add the axiom. Stick with fewer axioms, but a consistent system.

maybe the word trivial needs to be added: "If you then run across something trivial,that's interesting and clearly true"

Trivial, meaning it's not going to impact the usefulness of the system. It's not going to effect your computer program.

No need to inject your personal phonetic pronunciations...

marcus says

If you then run across something thivial,

marcus says

I understand boolean logic.

This is not about Boolean algebra. This is about mathematical logic: how new theorems are derived in an axiomatic system.

marcus says

I agree that if a system is inconsistent in nontrivial ways, then it's not useful and it can't be used with computers to do stuff.

marcus says

No, if an inconsistency exists, you have too many axioms. Make do with fewer axioms and have a useful system that is consistent.

Let's take simple examples:
- First let's consider the sentence "If Tokyo is in Italy then Athen is in England". This is a blatantly idiotic sentence. But nonetheless it is true in mathematic logic because Tokyo is not in Italy. It's really that stupid. When you talk about computer systems, it should be understood that clearly no computer system is bound to accept something like "If Tokyo is in Italy then Athen is in England" as a true assertion.

- Now let's say I build an intelligent program and that system considers the sentence "This sentence is false".
The system can apply excluded middle rule and see that it is either true or false and both possibilities lead to the sentence being both true and false. So any AI system capable of considering a sentence as simple as "This sentence is false" IS inconsistent.
So you are telling me to remove axioms and I'll be fine? Seriously? Which basic fact about arithmetic do you want to remove from such AI system because of this inconsistency????

Remember arithmetic axioms are not chosen randomly. They are a minimal set of truths that will allow to derive basic theorems we know to be true about numbers. Removing any one of them will badly truncate arithmetic and lead to something that is in fact useless for most practical purposes.

Not only that but even if I were to remove arithmetic axioms, there is no reason to think it would in any way address the core problem of the inconsistency brought about by "This sentence is false". This inconsistency has absolutely nothing to do with arithmetic. It is simply to the possibility of a language (data structures in a computer) to refer to itself.

And the AI system simply better be ready to deal with the existence of such paradoxes in a less brittle way than mathematic logic does.

Heraclitusstudent says

So any AI system capable of considering a sentence as simple as "This sentence is false" IS inconsistent.

So you are telling me to remove axioms and I'll be fine? Seriously? Which basic fact about arithmetic do you want to remove from such AI system because of this inconsistency????

No, what I told you is that you aren't going to have inconsistencies. Teaching a computer how to deal with absurdities is simple and beside the point.

I see that you're back to confusing Godel's method of proof with what the proof implies. The proof only implies something very simple and straight forward: that a system can not be both consistent and complete. It does not say that the only way in which such inconsistencies arise as the system becomes more complete (meaning as more axioms and theorems are added to cover the infinite directions and lengths to which you can go starting from the initial axioms) is with such absurd statements.

Maybe the issue is you don't get what complete means in this context ?

A system does not have to be anything close to complete to deal with the set of problems you are going to use it for. Or to prove what you set out to prove.

If you are going to have a computer do something useful such as proving the four color theorem, you are going to have precise definitions and some basic axioms and theorem of geometry that are consistent that were used in coming up with the proof. (actually most of the consistent basics of plane geometry are accepted and not really even addressed in such a proof). Also, I know that in that example the people did the proof simply using a computer under their guidance.

I have to stop. Either I am missing something or you don't really have a point to make that I understand. We're
going in circles, and you want to get your point across without really attempting to understand what I'm saying. I believe I understand what you're saying. We're talking at eachother. Maybe I'm right but you're saying something else ? Or maybe I'm wrong, and you can't explain why ?

marcus says

A system does not have to be anything close to complete to deal with the set of problems you are going to use it for.

That's simply not true. To be useful a system needs to have a complete picture of what geometry is, or what numbers are. You can't leave half the definition out of it.

marcus says

The proof only implies something very simple and straight forward: that a system can not be both consistent and complete.

I 100% agree with that.

marcus says

It does not say that the only way in which such inconsistencies arise as the system becomes more complete (meaning as more axioms and theorems are added to cover the infinite directions and lengths to which you can go starting from the initial axioms) is with such absurd statements.

So you are saying the problem is not necessarily with self referential assertions.
Well, I agree I don't have a formal proof that there is not an other problem outside self-referential assertions.... But....

But first let me return this: there is no formal proof that there is an other problem outside self-referential assertions. In particular everything Godel did in his proof is about a self-referential assertion.

Second I would argue there are very strong reasons to believe there is no other problem. Because to believe there is an other problem you basically need to believe either:
- there is something intrinsic about a complete arithmetic picture that is rotten (inconsistent with itself);
- there is no way to derive in formal logic everything a human can "prove" as true.
Either of these are extremely strong assertions that fly in the face of everything we observe in practice.