Let $P(n)$ be a statement and let $P(n) \rightarrow P(n+1)$ is true for natural numbers n, the $P(n)$ is true for

Question

a) For all $n$

b) For all $n>1$

c) For all $n>m$, $m$ being a fixed integer

d) Nothing can be said

We can assume that $P(n+1)=P(n)$

If we substitute $P(n-1)$, $$P(n) = P(n-1)$$

$$\implies P(n-1) = P(n+1)$$

What does this result mean? How is related to the question? The given answer is a very unsatisfying $(d)$, which I think is probably wrong. In any case, I need help understanding it.

Thanks!

Answer 1

Let $P(n)$ be the statement "Pigs can fly and $n+n=2n$"

Answer 2

d) is the correct answer, a key ingredient is missing.

Can you give a single $n$ such that $P(n)$ certainly holds ?

Answer 3

The correct answer is indeed (d): nothing can be said. If we knew that $P(m)$ was true for some natural number $m$, then we could conclude that $P(n)$ is true for all natural numbers $n\ge m$; that’s the principle of mathematical induction. But we don’t know that.

For a concrete example, what if $P(n)$ is the statement $n>n$? It is true that $P(n)$ implies $P(n+1)$ for any natural number $n$: if we assume that $n>n$, we can add $1$ to both sides to deduce that $n+1>n+1$. But of course $P(n)$ is actually false for every natural number $n$.

Answer 4

"d" is indeed the correct answer. Note that all you can obtain from $P(n) \implies P(n+1)$ for $n \in \mathbb{N}$ is the following chain, $$P(1) \implies P(2) \implies P(3) \implies \dots$$ That is to say, $P(1) \implies P(n) \; \forall n \in \mathbb{N}$. Note however that all this shows is that $P(1)$ is sufficient (but not necessary) for $P(n)$ - indeed, $P(1)$ may not even be true.

---

You might try to justify $P(1)$ by the statement $P(n-1) \implies P(n)$, but note that since $n \in \mathbb{N}$, we do not have that $P(0) \implies P(1)$ since $0 \not \in \mathbb{N}$.

The most general thing you can say about this relation is that if there exists a $m$ such that $P(m)$, then $P(n)$ for all $n \geq m$ - however, this isn't the same as (c), since you don't know that such an $m$ exists.

Answer 5

ex falso quodlibet

If $P(N)$ is false, then $P(N) \rightarrow P(N+1)$ is true. So it is possible that $P(N)$ is false for all $N$. So nothing can be said of its being true.