I am a student taking an introduction to the theory of computation course. We have been introduced the simple induction. I was wondering is it possible to define a predicate that is either true or false for $n$ but always true for $n + 1$ where $n \in\ \mathbb{N}$? In other words: $$\text{Is there a P(n) such that P(n)} \rightarrow \text{P(n + 1) is true?}$$
I know that the truth table for implication states that there are 3 cases where $P \rightarrow Q$ is true:
- P is true $\rightarrow$ Q is true $= \ true$
- P is false P is true $\rightarrow$ Q $= \ true$
- P is false P is true $\rightarrow$ Q $= \ true$
What predicates could even exist to describe these three cases?
For example if we let $$\text{P(n): n <= n + 1}$$ then obviously that would be always true but this only describe case 1. How do I describe the other two?
Thanks for your time!
Note that if such a predicate is true for some $n$, it must be true for all $m\ge n$, by induction.
Now either $P(n)$ holds for some $n$, or not.
If it does hold for some $n$, let $k$ be the smallest value of $n$ for which $P(n)$ holds. Then $P(n)$ is the predicate which is true precisely if $n \ge k$. (Note that the predicate that is true for all $n$ is included here as the case when $k=0$.)
The only other possibility is that $P(n)$ is false for all $n$.
These are the only predicates $P$ satisfying the desiderata: Either $P(n)$ is the predicate $n\ge k$ for some constant $k$, or $P(n)$ is the predicate that is always false.