Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to solve this simple natural deduction problem:

{∀x(p(x) → q(a)), ∀y¬q(y)} |-nd ¬p(a)

I started out by stating the premisses and the assumption, which is p(a). I used p(a) in the first premise with the (→ - E) rule to get q(a). Here's the problem, i got a q(a) and a ∀y¬q(y) which turns into ¬q(b)? since i already turned x to a.

The question is, can i turn the y to a aswell? If so it should be pretty easy to prove this. Or am i just completely off track?

share|cite|improve this question
Yes, you can infer $\neg q(a)$ from $\forall{y}:\neg q(y)$. – mjqxxxx Oct 22 '12 at 23:01
up vote 0 down vote accepted

You can instantiate a universal quantifier with any constant (whether you've used it before in the deduction or not). For '$\forall$' means all, doesn't it?! So if you are given '$\forall y\neg Q(y)$', then anything you take will satisfy the condition expressed by '$Q$' -- in particular, the thing dubbed '$a$'.

As a footnote, it is probably not a great idea to think in terms of 'turning $x$ into $a$' or the like: what exactly could that mean? You are, to use the standard jargon, instantiating the quantifier -- i.e. moving from a general claim (and it is the whole quantifier/variable apparatus $\forall x ... x ...$ which expresses the generality) to an instance of it. And you do that by-removing-the-initial-quantifier-and-substituting-a-name-for-the-variable(s)-that-it-binds, which is best thought of as a single operation.

share|cite|improve this answer

Your Answer


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.