All Questions
Tagged with definability theories-of-arithmetic
5 questions
1
vote
1
answer
180
views
Natural functions outside $\sf PA$?
Can theories stronger than $\sf PA$ manage to define functions from the naturals to the naturals, that $\sf PA$ cannot? If so, what are examples of those functions?
- 11.3k
7
votes
1
answer
334
views
Why include $0$ and $1$ in the signature of Presburger arithmetic?
I recently became interested in some problems concerning decidability of extensions of Presburger arithmetic. However, being a number-theorist rather than a logician, I am confused by some notational ...
- 1,914
9
votes
0
answers
325
views
Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable?
Assume ZFC. Is there a formula of $\mathcal{L}_\in$ (without parameters) defining a model $\mathcal{M}$ of PA whose domain is a proper class but the complete theory of that model is not definable by ...
21
votes
2
answers
1k
views
Is factorial definable using a $\Delta_0$ formula?
The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?
- 313
0
votes
1
answer
336
views
Definability of arithmetic functions and relations
Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand (...
- 9,730