Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was asked by a professor a while ago to prove $(p \wedge \neg p)$ implies $q$. Whether through laziness or cleverness, I came up with the following proof:

  • $p \wedge \neg p$ (by assumption).

  • Assume by way of contradiction $\neg q$.

  • $p \wedge \neg p$, therefore $p$ (I forget what this rule is called).

  • Similarly, $p \wedge \neg p$, therefore $\neg p$.

  • We have both $p$ and $\neg p$, a contradiction.

  • Therefore, our assumption, $\neg q$, must have been false, i.e., $q$ is true, the desired result.

Is this right? I keep going either way about it to myself. On the one hand, it definitely feels circular. On the other hand, it seems contain all the correct elements of a contradiction proof.

EDIT: many commenters seem concerned about what I am allowed or not allowed to "use". I am allowed to use whatever you feel mathematically is correct, and not allowed to use things that aren't. The context of the exercise was not a course in logic, or even in mathematics. It was a computer science class in algorithms. I think the professer just wanted to get a feel for our understanding of logic, and also wanted to demonstrate why inconsistant assumptions can be used to prove anything. I don't even remember if the assignment was graded, or if it was what I got. I do remember that when I presented it on the board that it (obviously) wasn't quite what the professor was looking for.

share|improve this question
3  
A formal proof requires us to know what all your axioms and rules of inference are. Without them, it is impossible to tell. –  Arturo Magidin Jun 20 '12 at 20:56
2  
Notice that $p \wedge \neg p \implies \neg q$ is also true, so point 2 doesn't contradict anything. What tools are you allowed to use for the proof? –  Karolis Juodelė Jun 20 '12 at 20:57
5  
If you are "allowed to use whatever you feel is mathematicall correct", then the assignment is nonsense. One cannot produce a formal proof in the absence of a logical framework. If you are allowed to build whatever framework you want, then just assume the proposition you want to show as an axiom and be done with it. For this assignment to make sense, you must have specific axioms and rules of inference at play (a deductive system). There are deductive systems where this implication is not valid, after all. –  Arturo Magidin Jun 20 '12 at 21:09
4  
@asmeurer: I quoted what you said. And, in the realm of formal logic, there is no such thing as an absolute "is mathematical correct." As I pointed out, there are deductive systems where the implication you want is invalid; and what is mathematically correct in a particular deductive system will depend on what that particular deductive system is. There are many ways of formalizing deductive systems, but most practicing mathematicians don't care what are the axioms and what the conclusions, they just use all. But for this problem to make sense, you do need to care. –  Arturo Magidin Jun 20 '12 at 21:33
5  
@asmeurer: "that all mathematicians work in" is incorrect, as it turns out. Constructivists, for example, do not accept proofs by contradiction. Be cautious with universal statements, as they are always false. (That last part was a joke.) –  Cameron Buie Jun 20 '12 at 21:42
show 6 more comments

5 Answers

up vote 5 down vote accepted

Given the tools you have chosen to work with, you have a valid proof of $p\land \neg p\Rightarrow \neg\neg q$. Formally you would need an extra step where you point out that $\neg\neg q$ is the same as $q$, but that's not the real problem here.

The reason why it feels circular is that what you're being asked to prove if one of several possible logical axioms that can be used to justify proof by contradiction in the first place, so the difference between the rule you use and the conclusion is only very slight. It is then natural to wonder whether you're supposed to prove it from more primitive ingredients than proof by contradiction. However, what those particular ingredients might be varies considerably between formalizations of logic.

Basically one can choose any of quite a lot of possible logical foundations to use as axioms, and then prove that all of the other ones follow as logical consequences of the axioms we have chosen. (For pedants in the audience, this is assuming that the axiom sets in question are all for classical first-order logic, blah blah blah). In ordinary mathematical reasoning one tacitly allows all of those standard consequences as single proof steps that need no explanation because the reader is always expected to be able to formalize them in his own favorite logic if he wants to. However, that won't work here, because then there wouldn't be anything for you to prove! So it is necessary to be explicit about which proof steps one allows here, because otherwise your excercise just implodes.

If one happens to choose an axiom set that includes $p\land \neg p\Rightarrow q$ as an axiom, then there's nothing to prove -- a full and complete proof would consist of the words "it's an axiom". But if you choose not to make it an axiom, then what counts as a valid proof depends critically upon what you do consider axioms.


If you do not have a particular formal system you must do your proof in, then I suspect that the expected solution is simply by truth tables -- for each of the possible 4 combinations of whether $p$ and $q$ are true or false, show that $p\land \neg p\Rightarrow q$ evaluates to true.

Then you have proved "$p\land \neg p\Rightarrow q$ is always true" which is just a more convoluted way of saying that you have proved $p\land \neg p\Rightarrow q$ itself.

share|improve this answer
    
I think the only logical steps I used are $\neg \neg q \Rightarrow q$ and $p \wedge q \Rightarrow p$. Its probably clear by the way that I am not a logician. I have never taken a course on formal logic (or else I probably would have never come up with such a silly proof). –  asmeurer Jun 21 '12 at 2:48
    
Oh and I guess also the rule of proof by contradiction, which I would call assume $q \rightarrow$ reducto ad absurdum $\rightarrow \neg q$. The reducto ad absurdum part doesn't seem to me to really rely on any axiom, just the implicit assumption that the logic system is self consistent. –  asmeurer Jun 21 '12 at 2:51
1  
Essentially you're saying: "That's not an axiom; it's just how things work". But that does not really make sense, because the word "axiom" is nothing more nor less than a fancy way of saying "that's just how it works". Every proof step is supposed to be justified either by an axiom or by a rule of inference (the distinction between these two categories is somewhat fluid, however), and if you say of some step that it doesn't need any justification, that just means that you're implicitly relying on some axiom or rule that you haven't enunciated. –  Henning Makholm Jun 21 '12 at 11:05
1  
Also, "the implicit assumption that the logic system is consistent" can never be used to justify a proof step. In logic, "consistency" is a property of a system that requires that something (i.e., an contradiction) does not have a proof. If you have a choice between allowing a proof step or not, allowing it would make more proofs legal than there would be without it, and so could never make the system closer to being consistent. Conversely, picking any rule or axiom and arbitrarily disallowing it can never make a system inconsistent that wasn't already so. –  Henning Makholm Jun 21 '12 at 11:10
1  
Fianlly, you're using a rule saying "if you assume $A$ and using that assumption can prove $B$, then you have proved $A\Rightarrow B$". This rule is usually known as the Deduction Theorem, because in the trend-setting formalizations of logic it is not a primitive proof rule but can be reduced to a combination of other axioms. –  Henning Makholm Jun 21 '12 at 11:13
show 1 more comment

Some authors will say that the (p∧¬p) consists of a contradiction, while having p as well as ¬p is not a contradiction. One definition of a contradiction comes as a formula F such that for all possible truth values of F's atomic propositions, F has truth value of false. Under this definition, having p as well as ¬p is not a contradiction, and you can only infer a contradiction from having p as well as ¬p if you have a conjunction introduction rule, or something equivalent to such a rule.

Not all mathematicians use a framework where ((p∧¬p)$\implies$q) will hold. You might want to see the applications of relevance logic here. Mitch points out here that ((p∧¬p)$\implies$q) fails for relevance logic.

Though we can fairly easily guess something about the formation rules of your logical system, we know nothing about the semantics of your logical system, nor anything about the rules of inference of your system, nor anything about the axioms of such a system. Since we don't know the rules of inference and don't know the axioms of your system, we don't know what qualifies as a formal proof and what doesn't qualify as a formal proof for your logical system.

If we had a completeness meta-theorem (if a formula qualifies as a tautology, then it qualifies as a theorem), and knew the semantics of your logical system (the truth values that can get meaningfully assigned to propositions), then we could know what we could prove for your logical system, just from calculations with truth values. We just verify that some formula qualifies as a tautology via truth-value calculations, and then we can invoke the respective completeness meta-theorem which implies all tautologies as theorems. This all presupposes the rules of inference and axioms your logical system adequate with respect to the semantics of your system, whatever they might consist of. But, even given just a completeness meta-theorem, since we know nothing about the semantics of your system, and we have nothing which suggests anything about the semantics of your logical system, we don't even know if a given formula comes as provable or not. Not all logical systems have the same tautologies even those that do have a completeness meta-theorem, let alone the same theorems, since the semantics of logical systems does differ significantly.

Your proof comes as not even wrong, since we have no idea of what consists of a proof for your system.

The statement "((p$\land$$\lnot$p)$\implies$ q)" also comes as not even wrong, since we can't even tell if it consists of a tautology, nor can we tell if it qualifies as a theorem for what you want to talk about.

If you presuppose classical logic with its two truth values, and presuppose that your system has a completeness meta-theorem, in an informal context, you really only need to proceed as follows:

  1. (0^$\lnot$0)=0
  2. (1^$\lnot$1)=0
  3. (0$\implies$Q)=1
  4. So, ((P$\land$$\lnot$P)$\implies$Q)=1.
  5. Completeness Meta-Theorem
  6. Therefore, ((P$\land$$\lnot$P)$\implies$Q) is a theorem.

Really, this proof should work for any adequate system of logic where (0$\implies$P)=1, (P$\land$$\lnot$P)=0, which has a completeness meta-theorem also. But, not all logical systems have this going on, and since we have no idea about your rules of inference and your axioms, nor any idea about your semantics, your proof is not correct in a certain sense where "not correct" just means "other than correct" rather than "wrong" necessarily. In truth, your proof is not wrong either, since we have no idea what right and wrong mean in your context. To repeat, your proof is not even wrong.

share|improve this answer
add comment

You make the assumptions that $(p \wedge \neg p)$ is true and that $\neg q$ is true. When you arrive at the contradiction you know that your assumption is wrong but as a whole not which part of it.

Hint 1: It is not $\neg q$.

Hint 2: Your task is not to prove that $q$ is true but rather the validity of the whole form of $(p\wedge\neg p)\to q$.

share|improve this answer
    
I've proven that $q$ is true given $p \wedge \neg p$. This shows the whole form. –  asmeurer Jun 20 '12 at 21:08
    
As you state "Therefore our assumption [..] must have been false". Now, your assumption is not $\neg q$ but rather $(p\wedge\neg p)\wedge\neg q$ so you only know that the latter is wrong and nothing about the validity of the former. Instead you know that $(p\wedge\neg p)$ is wrong or $q$ is wrong. –  valid Jun 20 '12 at 21:27
5  
@valid: That's not a valid criticism. In formal systems that incorporate the deduction theorem, the assumption part of the deduction theorem is immune from being identified as responsible for a contradiction, because the possibility that the assumption might be false is taken care of by the semantics of the $\Rightarrow$ in the eventual conclusion. Provided that we have something like the deduction theorem and proof by contradiction, the OP does have a valid proof of $(p\land \neg p)\to\neg\neg q$. However, this is not (in all formal systems) the same as proving $(p\land\neg p)\to q$. –  Henning Makholm Jun 20 '12 at 22:09
    
@HenningMakholm: "Valid cristicisim", gold :) Of course you are right insofar as the DT does not address the case of the assumption being invalid. Then again, a system incorperating the DT is not precluded from incorporating proof by contradiction as well so the assumption's immunity may still be at jeopardy. Plus, isn't OP's assumption really $p\wedge\neg p\wedge\neg q$, thus under hypothetical provision of DT and proof by contradiction proving the validity of $(p\wedge\neg p)\wedge\neg q\to\neg((p\wedge\neg p)\wedge\neg q)$? If so, OP's proof was not headed in the intially stated direction. –  valid Jun 20 '12 at 23:49
    
Suppose you have a three-valued logic where $\lnot$U=T, where "U" indicates the third truth value and "T" truth. Also suppose that (U $\land$ T)=T. Then it follows that (p $\land$ $\lnot$ p) is true, if p has truth value U. Thus, you can assume that (p∧¬p) is true and ¬q is true, and no contradiction can exist, if say q is false, or takes on the third truth value. So, the suggestion of such a proof here doesn't work, since we have no idea about the system in terms of rules of inference, axioms, or in terms of its semantics. –  Doug Spoonwood Jun 20 '12 at 23:50
show 8 more comments

The answer is: yes, your proof is correct.

Instead of reductio ad absurdum, your can use the principle of explosion. Falsum $\bot$ follows from $p$ and $\neg p$, and ex falso sequitur quodlibet, so one can conclude $q$ directly from $\bot$. This is trivial though, whereas your proof shows the strength of double negation elimination.

share|improve this answer
3  
Using the principle of explosion while attempting to prove the principle of explosion itself is not really convincing, methinks. –  Henning Makholm Jun 20 '12 at 22:10
1  
"Falsum ⊥ follows from p and ¬p, and ex falso sequitur quodlibet, so one can conclude q directly from ⊥." No, it doesn't. It only follows given either certain rules of inference and axioms, or a certain semantics (usually both). "This is trivial though, whereas your proof shows the strength of double negation elimination." No, the principle of explosion doesn't even come as wrong for logical systems in general, as some have it, and some don't have it. –  Doug Spoonwood Jun 21 '12 at 0:00
    
Spoonwood, do you really think he needs to consider logical systems more general then constructive propositional ones? –  Wouter Stekelenburg Jun 26 '12 at 18:17
    
I was using the deduction system in staff.science.uu.nl/~ooste110/syllabi/setsproofs09.pdf, which is used in a university level introductory course in the foundations of mathematics. –  Wouter Stekelenburg Jun 26 '12 at 18:53
add comment

By definition : $P \Rightarrow Q $ is $\neg P \vee Q$

Then : $$((p \wedge \neg p ) \Rightarrow q) \Leftrightarrow (\neg (p \wedge \neg p)) \vee q \Leftrightarrow (\neg p \vee p \vee q)$$

The disjonction $\neg P \vee P$ is true forall proposition $P$, then the proposition in the right side is true.

Note: Generally we have : if $P$ is false thens $P \Rightarrow Q$ is true forall $Q$.

share|improve this answer
    
I'm not asking how to "correctly" prove it. I know how to do that. I'm asking if my "proof" is a correct one. –  asmeurer Jun 20 '12 at 21:10
    
I think your proof is correct but the assumption that '$q$ is false ' is without never utility because the implication is realy independant on $q$ since $p \wedge \neg p$ is false all implications beginning with it are trues. –  Mohamed Jun 20 '12 at 21:18
    
Not all logical systems have that (P⇒Q) is definable as (¬P∨Q). Suppose that we can compute (P⇒Q) by min(1, 1-P+Q), where 1 indicates truth, 0 falsity, and truth values can take on any value in [0, 1]. Suppose that we can compute (P∨Q) by max(P, Q), and ¬P by 1-P. Then if P=.5, and Q=.5, (P⇒Q) has truth value of 1, while (¬P∨Q) has truth value of .5. Thus, (P⇒Q) does not always come out equal to (¬P∨Q) in terms of truth values, and thus such a definition does not come as permissible, since all definitions like this must have a corresponding logical equivalence. –  Doug Spoonwood Jun 20 '12 at 23:58
1  
@ Doug Spoonwood: This is new to me this discussion about systems of logic in mathematics in my above interventions, I mean the sub-system in two truth values. Thank you for these valuable feedback. –  Mohamed Jun 21 '12 at 0:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.