Collection of Maths Problems

Writing formal propositions

Task number: 2782

• Variant 1

  All natural numbers are even.

• Resolution

  \(\forall x\in \mathbb N\ \exists y\in \mathbb N: x=2y\).

  Negation: \(\exists x\in \mathbb N\ \forall y\in \mathbb N: x\ne 2y\).

  In words: there exists a natural number that is not even.
  (Or: not all, but only some natural numbers are even.)

• Variant 2

  Every prime number is odd.

• Hint

  To characterize the prime numbers \(p\), use for example \(\forall x,y\in \mathbb N: p=xy \Rightarrow (x=1 \lor y=1)\).

• Resolution

  \(\forall p\in \mathbb N: (\forall x,y\in \mathbb N: p=xy \Rightarrow (x=1 \lor y=1)) \Rightarrow (\exists k\in \mathbb N: p=2k-1)\).

  We may collect the quantifiers at the beginning. The variable \(k\) does not depend on the variables \(x,y\), so it is possible to change their order as well.

  \(\forall p,x,y\in \mathbb N\ \exists k\in \mathbb N: (p=xy \Rightarrow (x=1 \lor y=1)) \Rightarrow ( p=2k-1)\).

  The negation is \(\exists p,x,y\in \mathbb N\ \forall k\in \mathbb N: (p=xy \Rightarrow (x=1 \lor y=1)) \land (p\ne 2k-1)\).

  In words: there exists some prime number that is not odd.

• Variant 3

  Some natural number is divisible by all primes.

• Hint

  To express the attribute „to be a prime number“ you may introduce a predicate \(prime(p)\).

• Resolution

  \(\exists n\in \mathbb N\ \forall p\in \mathbb N: prime(p) \Rightarrow p|n\)

  Negation: \(\forall n\in \mathbb N\ \exists p\in \mathbb N: prime(p) \land \neg(p|n)\)

  In words: for any given natural number there exists some prime number that does not divide it.

• Variant 4

  Between \(n\) and \(2n\) we can always find some prime number.

• Resolution

  \(\forall n\ \exists p\in \mathbb N: prime(p) \land n< p \land p< 2n\)

  Negation: \(\exists n\ \forall p\in \mathbb N: prime(p) \Rightarrow (n\ge p \lor p\ge 2n)\)

  In words: there exists some number \(n\) such that every prime is smaller than \(n\) or greater than \(2n\).