complete negation See NECESSITY, PHILOSOPHY OF. MIN. completeness, a property that something – typically, a set of axioms, a logic, a theory, a set of well-formed formulas, a language, or a set of connectives – has when it is strong enough in some desirable respect. (1) A set of axioms is complete for the logic L if every theorem of L is provable using those axioms. (2) A logic L has weak semantical completeness if every valid sentence of the language of L is a theorem of L. L has strong semantical completeness (or is deductively complete) if for every set G of sentences, every logical consequence of G is deducible from G using L. A propositional logic L is Halldén-complete if whenever A 7 B is a theorem of L, where A and B share no variables, either A or B is a theorem of L. And L is Post-complete if L is consistent but no stronger logic for the same language is consistent. Reference to the ‘completeness’ of a logic, without further qualification, is almost invariably to either weak or strong semantical completeness. One curious exception: second-order logic is often said to be ‘incomplete,’ where what is meant is that it is not axiomatizable. (3) A theory T is negation-complete (often simply complete) if for every sentence A of the language of T, either A or its negation is provable in T. And T is omega-complete if whenever it is provable in T that a property f / holds of each natural number 0, 1, . . . , it is also provable that every number has f. (Generalizing on this, any set G of well-formed formulas might be called omega complete if (v)A[v] is deducible from G whenever A[t] is deducible from G for all terms t, where A[t] is the result of replacing all free occurrences of v in A[v] by t.) (4) A language L is expressively complete if each of a given class of items is expressible in L. Usually, the class in question is the class of (twovalued) truth-functions. The propositional language whose sole connectives are – and 7 is thus said to be expressively (or functionally) complete, while that built up using 7 alone is not, since classical negation is not expressible therein. Here one might also say that the set {-,7} is expressively (or functionally) complete, while {7} is not.
See also GÖDEL’S INCOMPLETENESS THEO- REMS , SECOND – ORDER LOGIC , SHEFFER STROK. G.F.S.