0
$\begingroup$

In Godel’s incompleteness theorem, his two statements relate to “non-trivial formal system”, but how are these determined? Is 1+1=2 one of these? What about P vs NP?

$\endgroup$
4
  • 2
    $\begingroup$ $1+1=2$ is not a system... neither is P vs NP... Begin by reading about formal systems on wikipedia. $\endgroup$
    – JMoravitz
    Apr 10 '17 at 17:48
  • $\begingroup$ "primitive symbols", "defined language", isn't that the very basis of mathematics? $\endgroup$
    – Goodwin Lu
    Apr 10 '17 at 17:53
  • $\begingroup$ @GoodwinLu Yes. Do you find that odd? $\endgroup$
    – skyking
    Apr 10 '17 at 17:59
  • 2
    $\begingroup$ The point is that mathematics doesn't have to look or feel or work the way that we are used to. It depends on what symbols we have available and defined, how they interact with one another, how logical implications work, and what we take for granted at the start. The study of formal systems allows us to study abstract scenarios where things don't necessarily work the way we are used to. The system as a whole is not just an expression, but rather the collection of all possible expressions, implications, rules, etc... $\endgroup$
    – JMoravitz
    Apr 10 '17 at 18:01
1
$\begingroup$

There is no general answer to that, but the incompleteness theorem states that any system that contains at least Robinson arithmetics, a weaker form of Peano arithmetics (natural numbers with addition and multiplication) is complex enough. Natural numbers with addition only, however, is complete and consistent. Also this does not mean that a system not containing Robinson arithmetics would not be complex enough.

$\endgroup$
1
  • $\begingroup$ +1. And to address a possible confusion on the OP's part, a system consists of a collection of sentences in a language (in a very specific, formal sense; and I'm folding the deduction rules into the axioms, so I can use modus ponens as my only deduction rule). So Goedel's theorem roughly says, "Given any "reasonable" set of axioms, there is a sentence in the language of arithmetic which those axioms don't prove." $\endgroup$ Apr 10 '17 at 18:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.