How is strong induction recursive?

Question

I know that strong induction is equivalent to induction, and I know that functions that are defined by inductions are recursive.

So theoretically, strong induction should also give a recursive definition (or even primitive-recursive?).

Suppose that I want to define a set of numbers by strong induction, for example: for all $i$, $2^i\in A$; and if $j,k\in A$ then $2^j3^k\in A$.

How can I show that such $A$ is recursive?

EDIT: I am generally trying to understand how Godel coding works. The definitions usually go about assigning the symbols numbers and then skipping over the part where the set of terms/formulas is recursive; or we define something like the above, for example $\#(r+t)=2^23^{\#r}5^{\#t}$, which is essentially a strong induction argument.

Answer 1

How to show that your $A$ is (primitive) recursive depends on what tools you have available. I'll assume you know about primitive recursion, that you have primitive recursive coding and decoding functions for finite sequences, and that you know that exponentiation is primitive recursive. Then you can define, by primitive recursion, a function $F$ such that $F(n)$ codes the initial segment of length $n$ of the characteristic function of your $A$. $F(0)$ is the code of the empty sequence. $F(n+1)$ is the (code of the result of) result of appending to (the sequence coded by) $F(n)$ a single number $q$, which is $1$ in two situations: (i) if $n$ is of the form $3^i$ or (ii) if $n$ is of the form $2^i3^j$ and $F(n)$ had $1$'s in positions $i$ and $j$; in all other situations, $q$ is $0$. Once you have $F$, you obtain $A$ as the set of $n$ such that the last component (the component in position $n$) of $F(n+1)$ is $1$.

Answer 2

Your definition is a little bit self-contradictory, as $3 \in A$, but $3 \ne 2^i 3^j$, unless $0 \in A$, which it doesn't seem to be. A better definition might be: Let $A$ be the smallest set if integers such that $3^i \in A$ for every $i$ and $2^i3^j \in A$ for all $i,j \in A$ Now it's clear that $A$ is well defined, and it's also clear that $A$ is recursively enumerable, because we can easily write a computer program to list all the elements of it. To show it's recursive, we need an algorithm to determine if $n \in A$ for a given n.

Here's one way you could do it. Given $n$, let $n = 2^i3^jm$, where $m$ is not divisible by 2 or 3. If $m \ne 1$ then $n \notin A$. If $j = 0$ then $n \in A$, otherwise recursively check to see if $i,j \in A$. If they are then $n \in A$. The algorithm will terminate because $i,j \lt n$