TTMUA Lab
TMUA 2018 · Paper 2 · Question 12 of 20

TMUA 2018 Paper 2 Question 12

Logic and arguments — Negating a statement with nested quantifiers. Try it first; the answer and a full worked solution are below.

TMUA 2018 · Paper 2Logic and argumentsNegating a statement with nested quantifiers8 options
Consider the following statement:

For any positive integer N there is a positive integer K such that N(Km+1) − 1 is not prime for any positive integer m.

Which one of the following is the negation of this statement?

  1. AFor any positive integer N there is a positive integer K such that there is a positive integer m for which N(Km+1)−1 is prime.
  2. BFor any positive integer N there is a positive integer K such that there is a positive integer m for which N(Km+1)−1 is not prime.
  3. CFor any positive integer N there is a positive integer K such that for any positive integer m, N(Km+1)−1 is not prime.
  4. DFor any positive integer N, any positive integer K and any positive integer m, N(Km+1)−1 is not prime.
  5. EThere is a positive integer N such that for any positive integer K there is a positive integer m for which N(Km+1)−1 is not prime.
  6. FThere is a positive integer N such that for any positive integer K there is a positive integer m for which N(Km+1)−1 is prime.
  7. GThere is a positive integer N such that for any positive integer K and any positive integer m, N(Km+1)−1 is prime.
  8. HThere is a positive integer N and a positive integer K for which there is no positive integer m for which N(Km+1)−1 is prime.
Show the answer and worked solution
answer · F
  1. AFor any positive integer N there is a positive integer K such that there is a positive integer m for which N(Km+1)−1 is prime.
  2. BFor any positive integer N there is a positive integer K such that there is a positive integer m for which N(Km+1)−1 is not prime.
  3. CFor any positive integer N there is a positive integer K such that for any positive integer m, N(Km+1)−1 is not prime.
  4. DFor any positive integer N, any positive integer K and any positive integer m, N(Km+1)−1 is not prime.
  5. EThere is a positive integer N such that for any positive integer K there is a positive integer m for which N(Km+1)−1 is not prime.
  6. FThere is a positive integer N such that for any positive integer K there is a positive integer m for which N(Km+1)−1 is prime.
  7. GThere is a positive integer N such that for any positive integer K and any positive integer m, N(Km+1)−1 is prime.
  8. HThere is a positive integer N and a positive integer K for which there is no positive integer m for which N(Km+1)−1 is prime.
Strip the statement to its quantifiers: ∀ N ∃ K ∀ m, N(Km+1)−1 is not prime. Negating flips each quantifier in turn and finally the property, giving ∃ N ∀ K ∃ m, N(Km+1)−1 is prime. Read back into words that is "there is an N such that for any K there is an m for which N(Km+1)−1 is prime". The tempting near-misses keep "not prime" or flip only some of the quantifiers.