Is this sequence and its range definable in PA?

Question

Fix a base $b \geq 2$, and consider the sequence $1, 22, 333,$ etc, where we interpret those symbols in base $b$. So, for example, given $b=2$, we have the sequence $1$, $1010_2$, $111111_2$, etc. For every such base $b$, is both the sequence of values, and the range of same sequence, definable by a first-order formula in Peano Arithmetic (PA)? If so, can I see such a definition, possibly with abbreviations if necessary?

Answer 1

For this sort of question, arithmetic is incredibly powerful.

If a sequence is arithmetically definable, then so is its range: consider the expression "There is some $n$ such that the $n$th term of the sequence is $x$." Your sequences, meanwhile, are quite clearly computable, so we can use the general fact due to Post that "computable = $\Delta^0_1$" - so in particular, every computable sequence is arithmetically definable.

Actually producing a definition in terms of just addition and multiplication will be a bit tedious, though. This is because your sequences depend heavily on exponentiation and approximate logarithms; for example, to determine the $n=3,b=2$ term, we need to $(i)$ figure out that $3$ has length $2$ in base $2$ and $(ii)$ then compute $3\cdot 2^0+3\cdot 2^2+3\cdot 2^4.$ This will extensively use Godel's $\beta$-function. In general, you'll get a definition that looks like $$(n,b)\leadsto \sum_{1\le k\le n}n\cdot b^{k\cdot len_b(n)}$$ where $len_b(n)$ is the length of $n$ expressed in base $b$. For exponentiation, length, and finite summation, you'll need to use the $\beta$-function (or some appropriate equivalent).

---

Note that, contra your phrasing, I've used the phrase "arithmetically definable" rather than "definable in $\mathsf{PA}$." This is because definability lives in the realm of languages and structures, not theories: theories are for proving, not defining. That said, there is a reasonable notion of "definability relative to a theory" - this is representability. Roughly speaking, if $T$ is a theory of arithmetic, then a function $f$ is $T$-representable iff there is some formula $\varphi(x,y)$ such that $T$ proves that $\varphi$ defines a function and for each $n$ we have $T\vdash\varphi(\underline{n},\underline{f(n)})$ (where "$\underline{k}$" is the numeral corresponding to $k$). Essentially, representability means that each specific value is determined by the theory. Godel (essentially) showed that every computable function is representable in $\mathsf{PA}$, or indeed much less, so the above application of Post's theorem still applies.