Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic. It was first proved by Kurt Gödel in 1929.

A first-order formula is called logically valid if it is true in every structure for its language. The completeness theorem shows that if a formula is logically valid then there is a finite deduction (a formal proof) of the formula. The deduction is a finite object that can be verified by hand or computer. This relationship between truth and provability establishes a close link between model theory and proof theory in mathematical logic.

An important consequence of the completeness theorem is that it is possible to enumerate the logical consequences of any effective first-order theory, by enumerating all the correct deductions using axioms from the theory.

Gödel's incompleteness theorem, referring to a different meaning of completeness, shows that if any sufficiently strong effective theory of arithmetic is consistent then there is a formula (depending on the theory) which can neither be proven nor disproven within the theory. Nevertheless the completeness theorem applies to these theories, showing that any logical consequence of such a theory is provable from the theory.

Reference:
http://en.wikipedia.org/wiki/Completeness_theorem

Posted by 알 수 없는 사용자
,