Sign up ×
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'm seeing math logic and I have a question.

Let $p$ be a proposition. Let's suppose I have $\lnot p$.

By disjunction rule, this implies $\lnot p \vee q$, where $q$ is any proposition.

This is equivalent (looking at the truth tables) to $p \implies q$

Does this mean that we only have to prove $\lnot p$ in order to prove $p \implies q\;$?

share|cite|improve this question
Let $p \equiv ( 2b^2=a^2 )$ and $q \equiv (a,b\notin \mathbb N$) now how does $\neg p$ proves $p \implies q$? –  Arjang Jun 12 '11 at 16:56
See my post below; the point is the statements p->q and ~p\/q are logically equivalent, i.e., they're either simultaneously true or simultaneously false, butthe logical equivalence does not extend to the existence of a proof of one from the other. So if you are given ~p, you can conclude ~p\/q. Then, any truth-value assignments to p,q will give the same truth values to the two sentences. In other types of implication, you may require that one sentence follows from the other to conclude p->q. Material implication may be part of the price to pay for the bakcboxing that goes on in sentence logic. –  gary Jun 12 '11 at 17:41
@ gary Logical equivalence between "p" and "q" DOES extend to the proof of "p" from "q" and conversely for classical propositional calculus and classical predicate calculus. The respective completeness theorems imply precisely that. @ Arjang Neither of what you meant by "p" nor "q" in your comment qualify as propositions here, so I don't see how what you wrote comes as relevant. –  Doug Spoonwood Jun 12 '11 at 23:44
@gary Actually, that should go that the respective completeness theorems, along with the converse of the deduction theorem we have that from the logical equivalence of "p and "q", we have the existence of a proof of one from the other. For if |=Epq, the by the completeness theorem we have |-Epq. By equivalence elimination we can obtain |-Cpq and |-Cqp. Then by the converse of the deduction theorem we obtain p|-q, and q|-p. So "p" yields "q" and "q" yields "p", given that p and q come as semantically equivalent in this context. –  Doug Spoonwood Jun 13 '11 at 0:24
Thanks everyone, all the answer were very useful. –  user12047 Jun 13 '11 at 0:53

4 Answers 4

This is correct. A false statement implies anything. However, in practice, we do not always prove an implication by proving the premise is never true; hence, this technique has limited scope.

share|cite|improve this answer
This has to see with the paradox of material A stronger condition for concluding anything from a false statement is often made, by demanding that there be an actual syntactic proof of q from ~P. –  gary Jun 12 '11 at 16:17
Maybe to make my point more precisely, the semantic content of ~p is irrelevant to arriving at p-->q. In sentence logic, the semantic content is reduced to either T or F. As an example, if p were "All buildings are Red" (in a universe where this is false), then I can conclude anything in 2-valued sentence logic, without making use of the fact that buildings are not red. It is only the formal, syntactic relations that I need to conclude p->q, not the inner semantic content. –  gary Jun 13 '11 at 3:18

As has already been said, yes, it is true.

In mathematical work, the usual net effect of this fact is that if we wish to prove $p \longrightarrow q$, we do not need to even think about the situations in which $p$ is false, so we don't.

So for example if we want to prove that every finite integral domain is a field (crudely, $p$ is then "is finite integral domain" and $q$ is "is field") there is no reason to bother examining things that are not finite integral domains.

Although "false implies everything" is in the background of the way we use "implies," it is seldom if ever explicitly invoked by most working mathematicians.

share|cite|improve this answer
@Zev Chonoles: Thanks! –  André Nicolas Jun 12 '11 at 18:07
He isn't talking about "false implies everything". That phrase, basically means "a logical contradiction implies any proposition", which can get formally written as CKpNpq, where K stands for conjunction, and "q" some arbitrary proposition. He's talking about "if not p, then if p then q." We have two hypotheses here, while "false implies everything" has only one. From the hypothesis "not p" along with the hypothesis "p" if may conjoin them into "not p AND p". Then we have a falsity. But, we need to have some way to conjoin them first (a rule of conjunction introduction) before that happens. –  Doug Spoonwood Jun 12 '11 at 23:54

If the logic involved come as a two-valued logic, then yes. However, if we have some other system of logic involved, perhaps, perhaps not. To see what's going on here, consider how from Np (the negation of p) we can legitimately infer Cpq (that's (p->q) in Polish notation). Now, "from Np, we may infer Cpq", though it could get used as such, doesn't usually get taken as a basic rule of inference for two-valued propositional logic. Instead, CNpCpq exists as a theorem of classical two-valued logic. Consequently if "Np" gets proven, then by application of modus ponendo ponens (the rule of detachment, conditional elimination), we can obtain "Cpq". So, we can simply obtain a proof for Cpq also by adding one "Cpq" to the end of the proof of "Np". So, basically if a system of logic has the rule of modus ponendo ponens, has CNpCpq as a logical theorem, then in order to prove Cpq, you just have to prove Np.

share|cite|improve this answer

As previous answers state $\lnot p$ implies $p \to q$ (the converse however is not true).

I'll just provide some motivation for such choice of truth values for material implication. Consider for example the the statement "for each natural number $x$, if $x$ is equally divisible by 4, then it is equally divisible by 2." You obviously want this statement to be true. Now if you take $x = 2$ then you'll have $false \to true$, and if you take $x = 5$ you'll have $false \to false$. Thus a $false$ statement implies everything.

share|cite|improve this answer

Your Answer


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.