Understanding logic formulae involving $P(n)$

Question

I am given that that $n,m,$ and $k$ are positive natural numbers, and have to find out which of the six statements above are true.

I know that $P(1)$ is not true, because $1$ cannot be written as $5k,$ where $k$ is a natural number; so, I can rule out the first possibility.

But I am not always sure how to even understand the predicate $P(n),$ for instance I don't understand the statement $P(n+1) ⇒ (P(n) \lor P(n+2)).$

Answer 1

It may surprise you but $P(1)$ is actually true.

Let's unfold its definition:

$$P(1)\equiv \exists k:\mathbb N.\ 1 = 5k \lor 1 = 5k+1 $$

So when you take $k=0$ this reduces to $1=5\cdot0\lor 1=5\cdot0+1$; and this second case is indeed true.

---

For the others I recommend that you do the same: unfold the definition. Let's see what happens for the other example you mentioned.

Consider $n:\mathbb N$. Then $P(n+1)\Rightarrow P(n)\lor P(n+2)$ unfolds to $$\big(\exists k_1.\ n+1=5k_1 \lor n+1=5k_1+1\big) \Rightarrow \big(\exists k.\ n=5k \lor n=5k+1\big) \lor \big(\exists k_2.\ n+2=5k_2 \lor n+2=5k_2+1\big) $$

With this you can assume the existence of a $k_1$, and will have to prove that either $P(n)$ or $P(n+2)$ holds for the two distinct cases $n+1=5k_1$ and $n+1=5k_1+1$.

For $n+1=5k_1$ you get that choosing $k_2:=k_1$ is enough since $n+2=5k_2+1$. (I used $P(n+2)$ here.)

For $n+1=5k_1+1$ you get that choosing $k:=k_1$ is enough since $n=5k$. (I used $P(n)$ here.)

Answer 2

I am given that that $n,m,$ and $k$ are positive natural numbers

I am not always sure how to even understand the predicate $P(n),$

The predicate $P(n)$ can be rewritten as $$\exists k{\in}\mathbb N \:\big(n=5k\,\lor \,n-1=5k\big)$$ and then as $$\exists a{\in}\mathbb N\; n=5a\,\lor \,\exists b{\in}\mathbb N\; n-1=5b$$ (after all, $P(x)$ or $Q(x)$ being true of some $x$ is equivalent to $P(y)$ being true of some $y$ or $Q(z)$ being true of some $z$), so it can be read as

• $n$ or $(n-1)$ is a multiple of $5.$

for instance I don't understand the statement $P(n+1) ⇒ (P(n) \lor P(n+2)).$

This is technically a predicate rather than a statement, since its variable $n$ is not bound. According to the previous paragraph, it means that

• if $(n+1)$ or $n$ is a multiple of $5,$ then $n$ or $(n-1)$ or $(n+2)$ or $(n+1)$ is a multiple of $5,$

so clearly is universally true.

I know that $P(1)$ is not true, because $1$ cannot be written as $5k,$ where $k$ is a natural number.

Shouldn't “cannot be written as $5k$” be replaced with “can be written as neither $5k$ nor $5k+1$” ?