As the title says, I wish to know if every system that is not axiomatic, not consistent or it's theorems can not be listed by an effective procedure is not complete.

I think that this is false. That is because The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of the natural numbers.

It does not say anything about the negation of this statement. Therefore, my intuition is that it is false. I just wish I could find an example that shows it.

  • $\begingroup$ We need an exact definition of "complete". Does it mean, that we can prove any true claim (and only the true claims) ? Or is an inconsistent system (which can prove anything!) also considered to be complete ? This definition is crucial to answer the question $\endgroup$ – Peter Dec 24 '16 at 13:31
  • $\begingroup$ It means that every for statment that I can create with the dictionery of the system is either provable or disprovable. $\endgroup$ – NotSure Dec 24 '16 at 13:41
  • $\begingroup$ What is a system that is not axiomatic? $\endgroup$ – Jacob Wakem Dec 24 '16 at 13:59
  • 3
    $\begingroup$ If $T$ is not consistent (i.e. inconsistent), then it proves all formulae. So it is complete (in the sense that there is no sentence $\varphi$ such that neither $T \vdash \varphi$ nor $T \vdash \lnot \varphi$). $\endgroup$ – Mauro ALLEGRANZA Dec 24 '16 at 14:13
  • $\begingroup$ Sorry about that, I meant arithmetic, not axiomatic, edited. $\endgroup$ – NotSure Dec 24 '16 at 14:16

Sure, there are lots.

  • Any inconsistent theory is complete, as Mauro ALLEGRANZA's comment states.

  • The true theory of arithmetic $TA$ is complete, and is not effectively axiomatizable.

  • If by "arithmetic" you mean "in the arithmetic hierarchy," then $TA$ still works.

  • And if by "arithmetic" you meant "true of the natural numbers," then consider the theory of dense linear orders without endpoints.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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