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.

If I want to prove something along the lines of:

If there exists a j which satisfies the conditions: 1)... 2)... 3)... then Something awesome happens.

I proved the forward direction of this (its an iff proof)

I want to prove the reverse direction

How do I do it using contrapositive?

I understand that a contrapositive of

X > Y is ~Y>~X.

So, in my case, I should have:

something awesome > existence equivalent to ~existence > ~ something awesome.

But, what is ~existence? How do i connect the 3 conditions with ~existence?

share|improve this question
    
Suppose I say if there exists j such that j is prime, j is not 2 and j is in the interval [1,100] then blah happens. I have showed the forward direction. I want to show reverse direction using contrapositive. So, _blah_>existence of j; contrapositive is (j does not exist) > blah does not happen. What is j does not exist with respect to the 3 conditions on j (prime, >2 and in the interval) –  Inquest Nov 7 '12 at 1:21

1 Answer 1

up vote 4 down vote accepted

For proving $iff$, letting $P_j$ denot "$p$ is prime," i.e., to prove:

$$\exists j(Pj \land j\neq 2 \land j\in[1, 100]) \iff (\text{blah happens}),$$

and given that you've established/proved the forward direction ($\implies$), if you want to prove the reverse implication

$$(\text{blah happens}) \implies \exists j(Pj \land j\neq 2 \land j\in[1, 100])$$

by proving its contrapositive,

then you would need to establish that $$\lnot \exists j(Pj \land j\neq2 \land j\in[1,100]) \implies \lnot \text{(blah happens)},\tag{1}$$

or equivalently

$$\forall j (\lnot Pj \lor j = 2 \lor j\notin[1,100]) \implies \lnot \text{(blah happens)}.\tag{2}$$


EDIT as requested by the OP:

To understand why $(1)$ and $(2)$ are equivalent, with the understanding that each represents the contrapositive of $$(\text{blah happens}) \implies \exists j(Pj \land j\neq 2 \land j\in[1, 100]) $$

We start from $(1)$:

$$\lnot \exists j(Pj \land j\neq2 \land j\in[1,100]) \implies \lnot \text{(blah happens)}.\tag{1}$$

We switch to the universal quantifier while moving the negation inward gives us the equivalent statement:

$$\forall j[\lnot(Pj \land j\neq2 \land j\in[1,100])] \implies \lnot \text{(blah happens)}.\tag{1.a}$$

Then by DeMorgan's law $(1.a)$ is equivalent to $(1.b)$:

$$\forall j[(\lnot Pj \lor (\lnot (j\neq2) \lor (\lnot(j\in[1,100]))] \implies \lnot \text{(blah happens)},\tag{1.b}$$

which you can see is equivalent to $(2)$:

$$\forall j[(\lnot Pj \lor (j = 2) \lor (j\notin[1,100])] \implies \lnot \text{(blah happens)}\tag{2}$$

share|improve this answer
    
Let me know whether or not you understand the equivalence of (1) and (2) above. –  amWhy Nov 7 '12 at 2:02
    
A little explanation on how 1 and 2 are equivalent would be awesome. –  Inquest Nov 7 '12 at 5:38
    
Re: $(1) \to (1.a)$ Good to know: When you negate an existential quantifier, e.g. to assert $\lnot \exists x (B(x)$, you can assert the universal quantifier (by moving negation inward, so to speak), applied to the negation of the quantified statement, e.g. you can assert $\forall x (\lnot B(x)).$ And by DeMorgan's, $\lnot (Bx \land Cx) \iff \lnot Bx \lor \lnot Cx.$ (Side note: if you negate a universal quantifier, you can assert the existential quantifier if you negate the quantified statement that follows. E.g. $\lnot \forall x Bx \iff \exists x (\lnot Bx)$. –  amWhy Nov 7 '12 at 14:36
    
@Inquest Does the added info in my edit/comment help to clear things up? –  amWhy Nov 7 '12 at 14:47
    
One additional note in case any statement about $j$ appears in "blah happens": if, e.g., "blah happens" = "$j$ explodes" = $E_j$, you need to extend the scope of the quantifier to include that conclusion by enclosing the entire statement in parentheses, with the "for all j" preceding it: $$\forall j\{[(\lnot Pj \lor (j = 2) \lor (j\notin[1,100])] \implies \lnot E_j\}$$ –  amWhy Nov 7 '12 at 21:22

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.