> On 19 Feb 2018, at 21:55, Brent Meeker <meeke...@verizon.net> wrote: > > Is there a non-constructive way to determine whether an axiomatic system > (axioms+inference rules) must be Goedel incomplete?
Basically there are two ways to prove that a system is incomplete. Either by a direct diagonalisation, or by representing in your system another system already proved incomplete. The interesting incompleteness à-la-Gödel is usually essential incompleteness or incompletability. Not only the system is (arithmetically) incomplete, but all its (transfinitely many) consistent extensions are incomplete too. The culprit of incompleteness is the presence of a universal machine (universal digital machine, or universal number, or universal set, or universal program, or universal word, or universal gas configuration, or universal pattern of the game of life, —depending what universal machinery you talk about). In classical or intuitionist logic the theory Q, with the axioms 0 ≠ s(x) s(x) = s(y) -> x = y x = 0 v Ey(x = s(y)) x+0 = x x+s(y) = s(x+y) x*0=0 x*s(y)=(x*y)+x give a Turing universal system, and thus the theory is essentially incomplete. It is the smaller one, (among the one with a finite number of axioms), as if you eliminate anyone of the axioms above, you lost Turing universality. There is a weaker Turing universal theory, but it has to be given by a scheme of axioms, like all n’ + m’ = (n+m)’, with n’ = s(s(s(s(s(…(0))…) with n s. And all axioms n’ * m’ = (n*m)’, and three other scheme, which are indeed proved in Q to get its Turing universality. Most theories in “usual mathematics” are not Turing complete, but some are like the theory of group (but not on abelian groups). The first order theory of the real number is complete (with respect to its propositions), and thus not Turing universal/complete. Tarski and its followers have proved the completeness and incompleteness/undecidability of many theories in mathematics. To be sure, Q is so weak that it is easy to show it incomplete without diagonalization. You can see almost directly that Q cannot prove 0+x = x, or you can “easily” build a model of Q + (0+x ≠ x). But the proof by diagonalization ensures its essential incompleteness, making Peano arithmetic, Zermelo-Fraenkel theory, and even formal string theory incomplete (with respect to the arithmetical truth). > Must one show that arithmetic is a model or is there some simpler method? Well, “simpler” is subjective, but as I say, you can always prove it by direct diagonalization, doing what Gödel did for a set theory (but using the numbers in it for the coding).(Or prove it directly because you see that the theory is weak). You also also prove quickly that anything capable of representing a universal Turing machine is incomplete, and then prove that your theory can represent all Turing machines, or equivalently the universal Turing machine (or any other universal system you know). For Gödel’s second incompleteness theorem, your theory needs enough induction axiom. Q + the induction axioms limited at sigma_0 (the recursive, the computable) is NOT Turing universal (and incomplete for other reason). But becomes Turing universal if you add the exponentiation axiom. It is called sigma_0-IND-Exp, and his the weaker fully Löbian machine I know. Q + sigma_1 induction is already Löbian (no need to add the exponentiation axiom). Bruno > > Brent > > -- > You received this message because you are subscribed to the Google Groups > "Everything List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to everything-list+unsubscr...@googlegroups.com. > To post to this group, send email to everything-list@googlegroups.com. > Visit this group at https://groups.google.com/group/everything-list. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
