Predicate logic implication

Question

I've been trying to solve this problem but I am not quite sure if I understood it correctly. The question states that:

Assume for all of the question that $P$ is a predicate defined on natural numbers and:

$\forall n \in N: P(n) \implies P(n+1)$

Part A asks: Assume $P(165)$, state whether the following is True, False or could be either:

$P(164)$ -- I put True

$P(166)$ -- True

Part B asks: Assume $\neg$ $P(165)$, state whether the following is True, False or could be either:

$P(164)$ -- False

$P(166)$ -- Either

Part C asks: state whether the following is True, False or could be either:

$P(165) \vee \exists n \in N: n < 165 \wedge \neg P(n) $

And I wasn't quite sure how to tackle C.

Lastly, Part D: Assume for this part that also $P(0)$ and prove or disprove without using induction:

$\exists k \in N: \neg P(k) \wedge \forall n \in N: n < k \implies P(n)$

Answer 1

Part A

What if $P(n)$ stands for "$n>164$"? And what if it stands for "$n>163$"?

---

Part B seems ok

---

Part C

Reat it loud: "Property $P(n)$ is true for $n=165$, or there exists some number $n$ smaller than $165$ such that $P(n)$ is false". You can think in cases: either $P(165)$ or $\lnot P(165)$. What does Part B tell you?

---

Part D

You can assume that $k$ is such that $\lnot P(k)$. Then $k\neq 0$, because $P(0)$. But then $\lnot P(k-1)$ by part $B$, so the second term in the conjunction is false.

Answer 2

Part A

P(164) could be either. 165 could be the first n with P(n)

Part B it's OK

Part C

if $P(165)$ then true

if $\neg P(165)$ then $\neg P(n) \forall n< 165$ this implies that $\exists n \in N: n < 165 \wedge \neg P(n)$

Then Part C is true

Part D Is false If $\neg P(k)$ for some k, but $k-1<k \implies P(k-1) $ but $P(k-1) \implies P(k)$ Then you got $P(k)$ and $\neg P(k)$ is a contradiction

Answer 3

Part A asks: Assume $P(165)$, state whether the following is True, False or could be either:

$P(164)$ -- I put True

That's not correct. The direction of the implication only allows us to infer $P(n)$ for numbers $>165$, and by contraposition it would allow us to infer $\neg P(n)$ for numbers $<165$ if we had $\neg P(165)$. But knowing $P(165)$ tells us nothing about the truth of $P(164)$; both $P(164)$ and $\neg P(164)$ are consistent with the assumptions $P(n) \to P(n+1)$ and $P(165)$.

$P(166)$ -- True

Correct, by direct application of $P(n) \to P(n+1)$ with $n=165$.

Part B asks: Assume $\neg$ $P(165)$, state whether the following is True, False or could be either:

$P(164)$ -- False

Correct, by contraposition on the implication: $\neg P(n+1) \to \neg P(n)$ with $n=164$.

$P(166)$ -- Either

Correct. Neither $P(166)$ nor $\neg P(166)$ would contradict the conjunction of the statements $P(165)$ and $P(n) \implies P(n+1)$, in a similar manner as for A.1.

Part C asks: state whether the following is True, False or could be either:

$P(165) \vee \exists n \in N: n < 165 \wedge \neg P(n) $

And I wasn't quite sure how to tackle C.

Focus on the second disjunct, then do a proof by cases.
$\exists n \in N: n < 165 \wedge \neg P(n)$ could be true without contradicting the assumptions (for example, set $n=164$ like above), in which case the disjunction becomes true.
If $\exists n \in N: n < 165 \wedge \neg P(n)$ is false, then this is equivalent to stating that $\forall n\in n: n < 165 \to P(n)$, hence also $P(164)$, from which we can derive $P(165)$ with the help of the assumptions, so the left disjunct and thereby the formula is true.
Hence C is always true.

Lastly, Part D: Assume for this part that also $P(0)$ and prove or disprove without using induction:

$\exists k \in N: \neg P(k) \wedge \forall n \in N: n < k \implies P(n)$

Induction would immediately tell us that $P(n)$ holds of all $n \in N$ so there will be no $k$ which can fulfill the first conjunct; but without using induction:
Consider the possible values for $k$.
If we try $k=0$, then the first conjunct $\neg P(k)$ would be a direct contradiction to our assumption $P(0)$, so $k=0$ can not satisfy the formula.
For $k>0$, if we want the second conjunct to be true in order to make the formula true, then instantiating $\forall n \in N: n < k \implies P(n)$ with $n=k-1$ gives us $P(k-1)$, which together with $\forall n \in N: P(n) \implies P(n+1)$ implies $P(k)$, which again renders the first conjunct $\neg P(k)$, and hence the quantified formula for that $k$, false.
Since there is no $k$ for which both conjuncts can be true, statement D can only be false.