Completeness - Revision history

Hannibal at 15:31, 16 May 2009

Hannibal — Sat, 16 May 2009 15:31:57 GMT

←Older revision		Revision as of 15:31, 16 May 2009
Line 1:		Line 1:
-	~~==Logical completeness==~~	+	In logic, semantic completeness is the [[contraposition\|converse]] of [[soundness]] for [[formal systems]]. A formal system is "semantically complete" when all [[tautology (logic)\|tautologies]] are [[theorems]] whereas a formal system is "sound" when all theorems are tautologies. [[Kurt Gödel]], [[Leon Henkin]], and [[Emil Post]] all published proofs of completeness. (See [[History of the Church–Turing thesis]].) A system is [[consistency\|consistent]] if a proof never exists for both ''P'' and not ''P''.
-	In [[logic]], semantic completeness is the [[contraposition\|converse]] of [[soundness]] for [[formal systems]]. A formal system is "semantically complete" when all [[tautology (logic)\|tautologies]] are [[theorems]] whereas a formal system is "sound" when all theorems are tautologies. [[Kurt Gödel]], [[Leon Henkin]], and [[Emil Post]] all published proofs of completeness. (See [[History of the Church–Turing thesis]].) A system is [[consistency\|consistent]] if a proof never exists for both ''P'' and not ''P''.	+

	*For a formal system S in formal language L, S is '''semantically complete''' or simply '''complete''', [[iff]] every logically valid formula of L (every formula which is true under every interpretation of L) is a theorem of S. That is, <math> \\models_{\\mathrm S} A\\ \\to\\ \\vdash_{\\mathrm S} A</math>.<ref name="metalogic">Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971</ref>		*For a formal system S in formal language L, S is '''semantically complete''' or simply '''complete''', [[iff]] every logically valid formula of L (every formula which is true under every interpretation of L) is a theorem of S. That is, <math> \\models_{\\mathrm S} A\\ \\to\\ \\vdash_{\\mathrm S} A</math>.<ref name="metalogic">Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971</ref>

Hannibal at 15:30, 16 May 2009

Hannibal — Sat, 16 May 2009 15:30:31 GMT

←Older revision		Revision as of 15:30, 16 May 2009
Line 1:		Line 1:
-
-	~~In general, an object is '''complete''' if nothing needs to be added to it. This notion is made more specific in various fields.~~
-
	==Logical completeness==		==Logical completeness==
	In [[logic]], semantic completeness is the [[contraposition\|converse]] of [[soundness]] for [[formal systems]]. A formal system is "semantically complete" when all [[tautology (logic)\|tautologies]] are [[theorems]] whereas a formal system is "sound" when all theorems are tautologies. [[Kurt Gödel]], [[Leon Henkin]], and [[Emil Post]] all published proofs of completeness. (See [[History of the Church–Turing thesis]].) A system is [[consistency\|consistent]] if a proof never exists for both ''P'' and not ''P''.		In [[logic]], semantic completeness is the [[contraposition\|converse]] of [[soundness]] for [[formal systems]]. A formal system is "semantically complete" when all [[tautology (logic)\|tautologies]] are [[theorems]] whereas a formal system is "sound" when all theorems are tautologies. [[Kurt Gödel]], [[Leon Henkin]], and [[Emil Post]] all published proofs of completeness. (See [[History of the Church–Turing thesis]].) A system is [[consistency\|consistent]] if a proof never exists for both ''P'' and not ''P''.

Hannibal at 15:29, 16 May 2009

Hannibal — Sat, 16 May 2009 15:29:12 GMT

New page

In general, an object is '''complete''' if nothing needs to be added to it. This notion is made more specific in various fields.

==Logical completeness==
In [[logic]], semantic completeness is the [[contraposition|converse]] of [[soundness]] for [[formal systems]]. A formal system is "semantically complete" when all [[tautology (logic)|tautologies]] are [[theorems]] whereas a formal system is "sound" when all theorems are tautologies. [[Kurt Gödel]], [[Leon Henkin]], and [[Emil Post]] all published proofs of completeness. (See [[History of the Church–Turing thesis]].) A system is [[consistency|consistent]] if a proof never exists for both ''P'' and not ''P''.

*For a formal system S in formal language L, S is '''semantically complete''' or simply '''complete''', [[iff]] every logically valid formula of L (every formula which is true under every interpretation of L) is a theorem of S. That is, <math> \\models_{\\mathrm S} A\\ \\to\\ \\vdash_{\\mathrm S} A</math>.<ref name="metalogic">Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971</ref>

*A formal system ''S'' is '''strongly complete''' or '''complete in the strong sense''' iff for every set of premises ''T'', any formula which semantically follows from ''T'' is derivable from T. That is, <math> T\\models_{\\mathrm S} A\\ \\to\\ T\\vdash_{\\mathrm S} A</math>.

*A formal system S is '''syntactically complete''' or '''deductively complete''' or '''maximally complete''' or simply '''complete''' iff for each formula A of the language of the system either A or ¬A is a theorem of S. This is also called '''negation completeness'''. In another sense, a formal system is '''syntactically complete''' iff no unprovable axiom can be added to it as an axiom without introducing an inconsistency. [[Truth-functional propositional logic]] and [[first-order predicate logic]] are semantically complete, but not syntactically complete (for example the propositional logic statement consisting of a single variable "a" is not a theorem, and neither is its negation, but these are not tautologies). [[Gödel's incompleteness theorem]] shows that no recursive system that is sufficiently powerful, such as the [[Peano axioms]], can be both consistent and complete.

*A formal system is '''inconsistent''' iff every sentence is a theorem.<ref>Alfred Tarski, ''Über einige fundamentale Begriffe der Mathematik'', Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie 23 (1930), Cl. III, pp. 22–29. English translation in: Alfred Tarski, ''Logic, Semantics, Metamathematics'', Claredon Press, Oxford, 1956, pp. 30–37.</ref>

*A system of [[logical connective]]s is [[functional completeness|functionally complete]] iff it can express all propositional functions.

*A language is '''expressively complete''' if it can express the subject matter for which it is intended.{{Fact|date=December 2008}}

*A formal system is '''complete with respect to a property''' iff every sentence that has the [[property (philosophy)|property]] is a theorem.

== References ==
1. ^ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Pres, 1971
2. ^ Alfred Tarski, Über einige fundamentale Begriffe der Mathematik, Comptes Rendus des séances de la Société des Sciences et des Lettres de Varsovie 23 (1930), Cl. III, pp. 22–29. English translation in: Alfred Tarski, Logic, Semantics, Metamathematics, Claredon Press, Oxford, 1956, pp. 30–37.