Mathematics desk
< February 19	<< Jan \| February \| Mar >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 20

A question of negation in Logic

I have a question, the article on the interpretation of intuitionist logic says "It is not, in general, possible for a logical system to have a formal negation operator such that there is a proof of "not" P exactly when there isn't a proof of P ; see Gödel's incompleteness theorems."
I can't help but feel that this statement seems illogical. There is already a negation in the predicate logic of Step 1 and you can generalize it to the higher levels. Is it my fault or is the article wrong?--82.82.214.197 (talk) 20:25, 20 February 2020 (UTC)[reply]

I don't follow your objection; could you restate it carefully? Step 1 of what? What does it mean to "generalize it to the higher levels", and how would that bear on the assertion you're questioning? --Trovatore (talk) 20:27, 20 February 2020 (UTC)[reply]

I too have a problem with the statement in that I do not see how the supposition of the existence of such a negation operator contradicts Gödel's theorems. While the statement is only about formal systems, let us assume we also can assign a meaning to its propositions. Let ⊨P denote the assertion that P holds (in the world of meanings), and ⊭P that P does not hold. Let ⊢P stand for the existence of a proof of P in the system, and ⊬P for the nonexistence of a proof. The formal negation operator is denoted by ¬. Assume that the system is consistent, so we can't have both ⊢P and ⊢¬P. Let us go even further and assume soundness as well, so that we may conclude ⊨P from ⊢P, and ⊭P from ⊢¬P.

Now let P be some proposition for which ⊨P. It follows that ⊬¬P, for if, on the contrary, ⊢¬P, then by soundness ⊭P, contradicting the assumption on P. The supposition regarding the negation operator now implies there is a proof of ¬¬P, or, symbolically, ⊢¬¬P. If on the other hand P is such that ⊭P, we have ⊬P, for if ⊢P, then ⊨P, likewise contradicting the assumption. Now we may conclude that ⊢¬P.

Recapitulating: if ⊨P then ⊢¬¬P, and if ⊭P then ⊢¬P. OK, so what? To contradict the incompleteness theorems, we somehow have to get to "for all P, either ⊢P or ⊢¬P". But we aren't nearly there. A necessary first step would be to have, "for all P, either ⊨P or ⊭P". But that is not very meaningful when interpreting intuitionist logic. Another issue is that ⊢¬¬P is not quite the same as ⊢P, but that may be repairable by adjusting Gödel's (constructive) proof to accommodate a weaker notion of completeness. The apparently necessary assumption of tertium non datur in the semantic world seems an unsurmountable obstacle, though.

For all clarity, I think the statement is true; such a negation operator is not possible. My only problem is in the reduction to Gödel's results. --Lambiam 23:45, 20 February 2020 (UTC)[reply]

A system in which not-P is provable whenever P is not provable is called "complete": Presburger arithmetic and the theory of real closed fields are well-known examples of complete theories. Gödel's incompleteness theorems tell us that any theory strong enough to include basic arithemtic (e.g. Robinson arithmetic, which is a weaker subtheory of Peano arithmetic), if consistent, cannot be complete. So only very weak theories like Presburger arithmetic (which has addition but not multiplication) can satisfy the property that $\forall P.\neg Provable(\neg P)\implies Provable(P)$ . (More formally here, P would range over Gödel numbers of formulas, and "Provable" would be an arithmetic provability predicate, one of the devices in Gödel's proof of the incompleteness theorems). Is that what you wanted to know? 2601:648:8202:96B0:0:0:0:7AC0 (talk) 01:42, 21 February 2020 (UTC) Also, see the article Double-negation translation for a reference about how Peano arithmetic and its intuitionistic counterpart Heyting arithmetic prove essentially the same formulas. 2601:648:8202:96B0:0:0:0:7AC0 (talk) 02:03, 21 February 2020 (UTC)[reply]

That is not the definition of "complete" given in our article Complete theory. There we read, "for every formula in the theory's language, that formula or its negation is demonstrable". The section Gödel's incompleteness theorems#Completeness refers to this. The two may seem equivalent, but only if you embrace the equivalence of double negation with positive assertion. --Lambiam 06:02, 21 February 2020 (UTC)[reply]

Just wanted to acknowledge that I saw this and haven't had a chance to think about it or read up on it. I'll be away a few days but maybe after I get back. It does sound harder for an intuitionistic theory to be complete, since by definition, for a given provable p, you don't always have

Provable(\neg \neg p)

. 2601:648:8202:96B0:C8B1:B369:A439:9657 (talk) 05:47, 23 February 2020 (UTC)[reply]

I don't see the problem. Double negation introduction (P → ¬¬P) is a theorem of intuitionistic propositional calculus. Using Gentzen's system LJ, starting from the pair of axiom instantiations P ⊢ P and ⊥ ⊢ ⊥ and successively applying the rules (→L) and (→R), we obtain P ⊢ ¬¬P. Then cut elimination, the counterpart of modus ponens at the sequent level, shows that from ⊢ P we may conclude ⊢ ¬¬P. --Lambiam 08:32, 23 February 2020 (UTC)[reply]