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
    Let me know whether or not you understand the equivalence of (1) and (2) above.2012-11-07
  • 0
    A little explanation on how 1 and 2 are equivalent would be awesome.2012-11-07
  • 0
    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)$.2012-11-07
  • 0
    @Inquest Does the added info in my edit/comment help to clear things up?2012-11-07
  • 0
    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\}$$2012-11-07
  • 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