Say you prove a statement $P(n)$ by induction, for all $n$ in $\mathbb{N}$.
Does the set {$P(k): k \in \mathbb{N}$ s.t. P(k) is true} have the same cardinality as the set of all natural numbers? Is there a bijection here?
For some reason I can't find much. Google is pulling up a lot of "use induction to prove the union of $n$ countably infinite sets is countably infinite" which isn't quite what I'm asking, I think.
Thank you for any help!
Not necessarily.
Suppose $P(k)=P$ for all $k$ (in other words, the statement $P(k)$ does not vary with $k$). If $P$ is true, it is of course trivial to show that $P(k)$ is true for any $k$. Moreover, the set $\{ P(k)|k \in \mathbb{N} \land P(k) \}$ is just $\{ P \}$, which obviously has cardinality smaller than $\mathbb{N}$.
Of course, this is a very unusual case, and typically $P(m) \not = P(n)$ for $m \not = n$, in which case the function $f(k) = P(k)$ is a bijection between $\mathbb{N}$ and $\{ P(k)|k \in \mathbb{N} \land P(k) \}$, and thus they will have the same cardinality in that case. But as I showed above, this is not necessarily the case.