5
$\begingroup$

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\;$?

  • 0
    Let $p \equiv ( 2b^2=a^2 )$ and $q \equiv (a,b\notin \mathbb N$) now how does $\neg p$ proves $p \implies q$?2011-06-12
  • 0
    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.2011-06-12
  • 1
    @ 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.2011-06-12
  • 0
    @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.2011-06-13
  • 0
    @Doug: I took these two statements to be "blackboxed" sentences, and I did not consider any predicates. AFAIK, in sentence logic, the inner-structure of the sentences do not matter; as sentences ~p\/q is equivalent to p->q , independently of the meaning assigned to either--and this leads to what some would consider flaws. This is what I meant; that--when p,q are sentences-- the content of the sentences ~p,q is not needed in order to conclude p->q , while in predicate logic this is not the case.2011-06-13
  • 0
    You can click accept on the appropriate answer. The tick mark is next to the vote arrows.2011-06-13

4 Answers 4

3

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.

  • 0
    This has to see with the paradox of material implication:http://en.wikipedia.org/wiki/Paradoxes_of_material_implication. 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.2011-06-12
  • 0
    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.2011-06-13
3

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.

  • 0
    @Zev Chonoles: Thanks!2011-06-12
  • 0
    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.2011-06-12
1

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.

0

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.