2
$\begingroup$

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.

  • 0
    @asmeurer In addition to Arturo's excellent comments here, when you write "Not what I "feel" is mathematically correct, what "is" mathematically correct. There is a commonly accepted framework of logic that all mathematicians work in." there exist several problems. 1. There exists no answer which comes as mathematically correct here. 2. The commonly accepted framework, having only two truth values, doesn't prove anything about what qualifies as mathematically correct. There's *nothing* wrong with consider a system of logic with more than two truth values, one where (p^~p) isn't always false.2012-06-20

5 Answers 5

6

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 is 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 exercise 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.

  • 0
    "(For pedants in the audience, this is assuming that the axiom sets in question are all for classical first-order logic, blah blah blah)." As long as you haven't mentioned anything explicitly about semantics, the axiom sets could come for something else than classical first-order logic. Bochvar's external system of three-valued logic (see an _Introduction to Many-Valued and Fuzzy Logic_ by Merrie Bergmann p. 82-83) has the same set of tautologies as classical logic. So, given completeness of such a system, all classical logic proofs work for Bochvar's external system also.2012-06-21
2

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.

0

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$.

  • 0
    @valid: Each assumption needs to be discharged _once_, and you only discharge one assumption at a time. When you discharge an assumption by PoC, any _other_ assumptions that are still open will need to be discharged _later_, and discharging them will make the "awfully powerful" conclusion that the assumption was false invisible from the outside.2012-06-21
0

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$.

  • 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.2012-06-21
-1

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.

  • 0
    I was using the deduction system in http://www.staff.science.uu.nl/~ooste110/syllabi/setsproofs09.pdf, which is used in a university level introductory course in the foundations of mathematics.2012-06-26