# Deriving Universal Modus Tollens

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?

-

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:

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.

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

I apologize for being late to the game, but here goes:

$[(P\rightarrow&space;Q)\wedge&space;\sim&space;Q]&space;\rightarrow&space;\sim&space;P$

Since $\\&space;(P\rightarrow&space;Q)&space;\Leftrightarrow&space;(\sim&space;P\vee&space;Q)$ due to the identity rule, then $\\&space;((\sim&space;P&space;\vee&space;Q)&space;\wedge&space;\sim&space;Q)&space;\rightarrow&space;\sim&space;P$. Now distribute $\\&space;((\sim&space;P&space;\vee&space;Q)&space;\wedge&space;\sim&space;Q)$ to get $\\&space;((\sim&space;P&space;\wedge&space;\sim&space;Q)\vee&space;(Q&space;\wedge&space;\sim&space;Q))$.

$\\(Q&space;\wedge&space;\sim&space;Q))$ is a contradiction, or a negation law. Thus $\\(Q&space;\wedge&space;\sim&space;Q))\Leftrightarrow&space;False$.

So we now have $\\((\sim&space;P&space;\wedge&space;\sim&space;Q)\vee&space;False)&space;\rightarrow&space;\sim&space;P$.

we can now use the identity law of $\\&space;(P&space;\vee&space;contradition)&space;\Leftrightarrow&space;P$, assuming $\\False&space;\Leftrightarrow&space;contradiction$. Thus $\\((\sim&space;P&space;\wedge&space;\sim&space;Q)&space;\vee&space;False)&space;\Leftrightarrow&space;(\sim&space;P&space;\wedge&space;\sim&space;Q)$

$\\(\sim&space;P&space;\wedge&space;\sim&space;Q)\rightarrow&space;\sim&space;P$ is the definition of Decomposing a conjunction in the laws of Tautology. Please refer to page 7 of the following link: http://sites.millersville.edu/bikenaga/math-proof/truth-tables/truth-tables.pdf

-