Godel 12

Consistency and Completeness. We say a formal theory is consistent if you cannot prove both P and ¬P in the theory for some sentence P. In fact, because from P and ¬P you can prove anything using classical logic, it is equivalent that a theory is consistent if and only if there is at least one sentence Q such that there is no proof of Q in the theory.


By contrast, a theory is said to be complete if given any sentence P, either [it] has a proof of P or a proof of ¬P. (Note that an inconsistent theory is necessarily complete).


Hilbert proposed to find a consistent and complete axiomatization of arithmetic, together with a proof (using only the basic mathematics that both camps agreed on) that it was both complete and consistent, and that it would remain so even if some of the tools that his camp used (which the other found unpalatable and doubtful) were used with it.

— This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

— Mathematics – Stack Exchange

— Jan 5 ’11 at 3:21

— Arturo Magidin

2013.09.27 Friday ACHK