Thread: The problem with NP

Originally Posted by laserlight

The way I understand this is that the set of natural numbers is not closed under subtraction (and division): it is possible to subtract (or divide) one natural number from (by) another and get a result that is not a natural number.

Yup. That's the modern way of describing it. Under Set Theory (developed around Peano's time), which is what we use today to describe number sets in more formal ways, an operation must have the following attributes:

Closed
Total
Onto the set

Closed means what you just said. Total means for any pair of numbers in the set, you can add or multiply them. Onto means that for any number x in the set, you can find an operation where a + b = x and r + s = x.

Originally Posted by manasij7479

Doesn't Gödel's incompleteness theorems - Wikipedia, the free encyclopedia contradict this line of thought ?

Not really, because Peano's arithmetic isn't a recursively generated formal system. I myself have a little trouble explaining what a recursively generated set of axioms is. Godel's theorems are too complex to explain in simple sentences. And I can't fully understand them either. But I'll try and give you two ideas that hopefully will help clarify where and how should Godel's Incompleteness apply.

1.
Peano axioms (collectively called Peano's arithmetic) are a set of axioms that are true in N (natural numbers). Emil Post soon demonstrated that Peano's arithmetic has no turing degree (everything has a turing degree, but Peano Arithmetic's is 0^w). This means it is not recursively enumerable. Naturally Godel's had a feeling for this. This is probably why he wrote that any formal system capable of expressing Peano's arithmetic is either inconsistent or incomplete. Note that he didn't say Peano's arithmetic was inconsistent or incomplete. It is. And other systems are too. He said that any formal system (a set of numbers and their rules) built from Peano's arithmetic would be the one that would become either inconsistent or incomplete. Peano's Arithmetic is the basis from which you build other formal systems.

2.
To get a feeling of where do Godel's theorems fit, Bertrand Russel was the center stage of probably the most spectacular (although brilliant) mathematical failure in all of history. Principia Mathematica was going to be the work of ages. A complete formalization of mathematics lead by Bertrand Russel and Whitehead in one single formal system. Every statement about mathematics was going to be proved either true or false. Just so you have a feeling of the depth of this work, it took them over 350 pages of nothing but pure mathematics to prove that 1+1 = 2 (essentially just to start proving Peano's Sucessor Rule).

But Godel came in with his Incompleteness Theorems. In fact he published them separately. The first theorem alone halted Principia Mathematica. Spectacularly. It demonstrated that they couldn't create both a complete and a consistent formal system. They would have to let go of one of them. They couldn't let go of consistency because naturally, if some truth could be proved false, the whole system would become false. But they couldn't let go of completeness because that was after all the point of the whole thing; a complete formal system, the whole edifice of mathematics in one system.

Bertrand Russel left mathematics and worked for the rest of his life as a lighthouse keeper on a distant island in the North Atlantic. Not really.

PS: I forgot to write the point of all this. The corollary -- and what I probably should have just wrote instead -- is that you can define a formal system and make it true. It's when you try to create a set of axioms that prove the axioms in your formal system that you fall under Godel's Incompleteness. You have a philosophical equivalent in the Laplace's Demon.