Every Countable Model of PA is Recursive?

Question

I am interested in any obvious flaws in the following argument.

Assume we have a countable model of Peano arithmetic in a meta-theory like ZFC. Assume this model has a set of ordered triplets, $\mathbb{A}$, that defines addition. $\mathbb{A}$ is countable because the model is countable. Assume we have a bijection between $\mathbb{A}$ and the standard natural numbers, $\aleph_0$. Using this bijection, we can index each element, $a_i \in \mathbb{A}$, with a standard natural number. We now have an indexed set of ordered triplets, $[a_i, b_i, c_i]$ such that $a_i + b_i = c_i$.

Define the function $ADD(x,y)$. This function searches $\mathbb{A}$ in index order until it finds $a_i = x$ and $b_i=y$. It then returns $c_i$. Clearly, $ADD(x,y)$ finds $c_i$ in a finite number of steps. This proves addition is recursive in our model. A similar argument proves multiplication is recursive.

---

I changed the meta-theory to be ZFC since I may need choice to prove $\mathbb{A}$ can be well ordered.

There seems to be two main objections. The first is that my proof leads to contradictions. This is an attempt to prove a contradiction to Tennebaum's theorem. If this proof is valid it can be used to prove anything including the idea that every set of natural numbers is recursive. Initially, I was trying to prove every finite set of natural numbers is recursive. This is enought to derive a contradiction. I was able to simplify the proof when I realized the set could be countable instead of finite.

The second objection is $\mathbb{A}$ is not a recursive set. This is not accurate. One can argue that addition as defined by $\mathbb{A}$ is not recursive. This is irrelevent to my argument. I make no assumptions about how $\mathbb{A}$ defines addition. I only assume $\mathbb{A}$ exists and is countable. I think the fact there is an injection from $\mathbb{A}$ to the standard natural numbers is enough for my proof to go through.

Answer 1

The flaw is the same as in this argument:

Let $A \subseteq \mathbb{N}$ be an infinite set of natural numbers that is not computably enumerable. Then $A$ is countably infinite; let $f \colon \mathbb{N} \to A$ be a bijection. We can enumerate $A$ as $f(0), f(1), f(2), \ldots$. This gives a procedure for enumerating $A$, so $A$ is computably enumerable, which is a contradiction.

The bijection $f$ in that argument will not be computable, and so the procedure given is not effective. It is true that every countable set is in bijection with the natural numbers, but the bijections are rarely computable.