Let $c$ be a constant such that $$\mathrm{PA}\not\vdash K(x)\ge c$$ for all binary strings $x$, where $K$ is Kolmogorov complexity. Such a $c$ exists by Chaitin's Incompleteness Theorem and the linked Q&A discusses how to find it.

For any $d$, let $x_d$ be the indicator string for the primes among nonnegative integers $\le d$. So for instance, $x_5=001101$ and $x_{9}=0011010100$.

Let $P_{d}(n)$ be the statement $$K(x_{n+d})\ge c.$$

Let $d$ be large and then let $P(n)=P_d(n)$ for all $n$.

• If $d$ is large enough, something like $d\ge c\cdot \mathcal H(1/\log c)$ where $\mathcal H$ is the entropy function, and we heuristically assume the primes are "random modulo the Prime Number Theorem", then heuristically all the $P(n)$ are true.

• By the Pigeonhole Principle, all but finitely many $P(n)$ are true.

• We cannot prove any particular $P(n)$ in PA.

Let $c$ be a constant such that $$\mathrm{PA}\not\vdash K(x)\ge c$$ for all binary strings $x$, where $K$ is Kolmogorov complexity. Such a $c$ exists by Chaitin's Incompleteness Theorem and the linked Q&A discusses how to find it in $\mathrm{PA}+\mathrm{Con}(\mathrm{PA})$.

For any $d$, let $x_d$ be the indicator string for the primes among nonnegative integers $\le d$. So for instance, $x_5=001101$ and $x_{9}=0011010100$.

Let $P_{d}(n)$ be the statement $$K(x_{n+d})\ge c.$$

Let $d$ be large and then let $P(n)=P_d(n)$ for all $n$.

• If $d$ is large enough then heuristically all the $P(n)$ are true.*

• By the Pigeonhole Principle in $\mathrm{PA}+\mathrm{Con}(\mathrm{PA})$ we prove that all but finitely many $P(n)$ are true.

• We cannot prove any particular $P(n)$ in $\mathrm{PA}$.

(*) Heuristics may suggest something like $d\ge c\cdot \mathcal H(1/\log c)$ where $\mathcal H$ is the entropy function, and we heuristically assume the primes are "random modulo the Prime Number Theorem", but the primes are computable so that heuristic is not quite right (thanks @EmilJerabek).

Let $c$ be a constant such that $$\mathrm{PA}\not\vdash K(x)\ge c$$ for all binary strings $x$, where $K$ is Kolmogorov complexity. Such a $c$ exists by Chaitin's Incompleteness Theorem and the linked Q&A discusses how to find it.

For any $d$, let $x_d$ be the indicator string for the primes among nonnegative integers $\le d$. So for instance, $x_5=001101$ and $x_{9}=0011010100$.

Let $P_{d}(n)$ be the statement $$K(x_{n+d})\ge c.$$

Let $d$ be large and then let $P(n)=P_d(n)$ for all $n$.

• If $d$ is large enough then heuristically all the $P(n)$ are true.

• By the Pigeonhole Principle, all but finitely many $P(n)$ are true.

• We cannot prove any particular $P(n)$ in PA.

Let $c$ be a constant such that $$\mathrm{PA}\not\vdash K(x)\ge c$$ for all binary strings $x$, where $K$ is Kolmogorov complexity. Such a $c$ exists by Chaitin's Incompleteness Theorem and the linked Q&A discusses how to find it.

For any $d$, let $x_d$ be the indicator string for the primes among nonnegative integers $\le d$. So for instance, $x_5=001101$ and $x_{9}=0011010100$.

Let $P_{d}(n)$ be the statement $$K(x_{n+d})\ge c.$$

Let $d$ be large and then let $P(n)=P_d(n)$ for all $n$.

• If $d$ is large enough, something like $d\ge c\cdot \mathcal H(1/\log c)$ where $\mathcal H$ is the entropy function, and we heuristically assume the primes are "random modulo the Prime Number Theorem", then heuristically all the $P(n)$ are true.

• By the Pigeonhole Principle, all but finitely many $P(n)$ are true.

• We cannot prove any particular $P(n)$ in PA.