Let $L$ be the first-order language with binary function symbol $+$, unary function symbol $E$. Let $T$ be the set of sentences over this language that are true in the natural numbers, with $+$ interpreted in the usual way, and $E(n$) interpreted as $2^n$. Is the set $T$ recursive?
3
-
$\begingroup$ Also asked here: math.stackexchange.com/questions/349383/… $\endgroup$– Andrés E. CaicedoCommented Apr 2, 2013 at 22:04
-
$\begingroup$ See these related questions: mathoverflow.net/questions/103896/beyond-presburger-arithmetic/…, mathoverflow.net/questions/106551/…. $\endgroup$– Joel David HamkinsCommented Apr 2, 2013 at 22:22
-
$\begingroup$ Does anybody know a book / other resources about omega structures? $\endgroup$– Martin ThomaCommented Feb 26, 2015 at 10:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
As Marty explained in this answer, this question is the central topic of the paper On the expansion $\langle \mathbb{N},+,2^x\rangle$ of Presburger arithmetic, by Françoise Point, based on a joint proceedings paper with G. Cherlin on a result credited to Alexei L. Semenov.
answered Apr 2, 2013 at 22:26