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.

I'm asked to derive the validity of Universal Modus Tollens from the validity of Universal Instantiation and Modus Tollens. I'm new to this deriving/proving stuff, so I'm not sure if I'm doing it right, but here's what I came up with:

Universal instantiation says that if (1) is true:

(1) ∀x, P(x) → Q(x)

Then (2) is true for any particular item y

(2) P(y) → Q(y)

Modus Tollens says that if (2) is true and (3) is true:

(3) ~Q(y)

Then (4) is true:

(4) ~P(y)

Therefore if (1) is true, and (3) is true, then (4) is true. In other words, the following argument is valid:

∀x, P(x) → Q(x)
~Q(y)
∴ ~P(y)

And that's Universal Modus Tollens.

Am I doing this right? Am I making any unwarranted assumptions or unsupported claims? Am I skipping any steps?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Let's do a little logic magic, shall we?

Note: I will assume here "$\implies$" is identical with "$\rightarrow$", and therefore that you are asserting the proposition in (1) rather than merely considering it. See discussion here for a reason why.

Let the set $S$ be the set of those elements, $x$, such that statements such as "$P(x)$" or "$Q(x)$" make sense and for such statements it makes sense to consider the propositions of the form "$P(x) \implies Q(x)$".

Consider then, since:

$$ \tag{1} \forall x \in S,P(x) \implies Q(x), $$

$$ (1) \iff \tag{2} \forall x \in S, (\text{~}P(x) \vee Q(x)) \text{ is true.} $$

Asserting:

$$ \tag{3} \exists y \in S, \text{~}Q(x) \text{ is true}, $$

we get,

$$ \tag{4} (\text{~}Q(x) \text{ is true}) \implies (\text{~}P(x) \text{ is true}). $$

For the sake of brevity, I'm skipping a step here; though it is admittedly trivial.

Therefore,

$$ \tag{5} (1) \wedge (3) \implies \text{~}P(x) \text{ is true}. $$

Q.E.D.

EDIT:

So, to answer your questions:

  1. You have this right.
  2. For most purposes, you have no problem with assumptions.
  3. Finally, you skipped a step between (3) and (4) in your post, which was made explicit by (2) in mine.

On a side note, for future reference, using $\LaTeX$ would probably be a better alternative to inserting mathematical notation in your posts on SE.

TIP: You can tag your equations by using "\tag{n}", where "n" denotes the number or string you want to tag your equation with.

share|improve this answer
    
I edited the 3rd list item, I had referred to the wrong lines. –  ThisIsNotAnId Apr 29 '12 at 17:37

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.