Does anyone know a reference discussing/describing the coding of sets and finite sequences in Elementary Arithmetic (EA, also know as $I\Delta_0(exp)$)?

All I know is that $\#\emptyset=0, \#\{n_1,…,n_m\}=2^{n_1}+…+2^{n_m}$, and for finite sequences, we have $\#(n_0,…,n_{m-1})=\#\{\langle i,n_i \rangle : i < m\}$.

A book would be appreciated since they tend to have more descriptions/examples but even a paper describing this would be fine.

Thank you for reading.

  • $\begingroup$ Your notation is not clear. The first expression appears to just be the ordinary binary representation of an integer. But you use $\{,\}$ and $(,)$ and $\langle, \rangle$ brackets and it isn't clear if these are meant to be somehow different. $\endgroup$
    – lulu
    Mar 25 at 15:48
  • $\begingroup$ $\{,\}$ is for sets, $(, )$ is for sequences and $\langle , \rangle$ is for pairs. $\endgroup$
    – Ingolfur
    Mar 25 at 15:51
  • $\begingroup$ Ok...what are $\#\{1,2\}$, $\#(1,2)$, and $\#\langle1,2\rangle$? $\endgroup$
    – lulu
    Mar 25 at 15:54
  • $\begingroup$ a) 2+4=6 As for the others, I am not sure how to compute them. This is the reason why I am asking for references: to learn more. What I wrote in the question is all the information I was given about this. $\endgroup$
    – Ingolfur
    Mar 25 at 16:01
  • 1
    $\begingroup$ I don't believe these are universally defined notations, so absent a definition, or a link to a definition, I don't think there's much anyone can say. $\endgroup$
    – lulu
    Mar 25 at 16:02


You must log in to answer this question.

Browse other questions tagged .