patrick.net

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.