1
$\begingroup$

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?

  • 0
    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)2012-11-07

1 Answers 1

3

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

  • 0
    +1 how can someone read $iff$ in English. I know that is if and only if, but I am looking the way you and the natives read it for example in an oral lecture.2013-08-13