I have a countably infinite set $A$ with elements $\{a_0, a_1, ... \}$. I've also been given $P(n) := (b = a_n) \lor P(n+1)$ and that $P(0)$ is true. I could expand this out to a chain of "ors" for every element of A.
To my understanding this is the same as $\exists a \in A, a = b $. However what is the formal step to transform my chain of ors to the exists statement?
Branching off Noah's comment, your logic can only apply if $A$ is finite. So let $\left| A \right|=n+1$. So $A = \{a_0,a_1,\dots a_n\}$
For $0 \le m \le n-1$, the truth of $P(m)$ implies the truth of $P(m+1)$ if and only if $b\neq a_m$ But then if $b \neq a_m$ for all $m$, and $P(0)$ being true is given, then we see that $P(n)$ must be true. Because $P(n+1)$ is not defined, we must have that $b = a_n$. Otherwise, there exists some $m$ where $b = a_m$, and this shows exactly what you were trying to say.
Letting $A$ be countably infinite does bring up a problem, as Noah had previously mentioned. His choice of the phrase where the sequence may never "bottom out" is a very accurate description of what could happen. It may seem like you are guaranteed to eventually obtain a value $i$ such that $a_i = b$, but on the contrary. Look at the case of letting $A = \mathbb{N}$. In this scenario, $A = \{0,1,2,3,4,5,6,7,\dots\}$ and if $b\in \mathbb{N}$ then $P(0)$ is true, as the $(b+1)^\text{th}$ term will be what we are looking for. The converse of this isn't necessarily true, however; if we are given $P(0)$ is true, one could try to argue that $b\in \mathbb{N}$ but it won't be possible. Recall that in the proof for the finite set, eventually we were forced to find a value because the next step $P(n+1)$ was not defined. We aren't given that fact to use this time, so we may find our value in this sequence at the $n$th term. Or we might have to go on to the next one. And the next. And the next...But no where does it say we eventually must come to a stop. We aren't able to ever stop falling down the line of the sequence and we would be stuck in an endless loop of checking a term and moving on to the next term when we don't find what we want. We don't "bottom out".