All Questions
5 questions
17
votes
7
answers
2k
views
Non-constructive proofs of decidability?
Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
16
votes
2
answers
713
views
Is (Z,+,0,1,P2,P3) decidable?
Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable?
I know that adding just one of P2, P3 to Presburger keeps it decidable, ...
- 428
7
votes
1
answer
262
views
What is known about first order logic of $\mathbb{N}$ with + and a unary predicate?
In "Weak Second-Order Arithmetic and Finite Automata", Büchi claims that the first order theory of $\mathbb{N}$ with + and a predicate for recognizing powers of 2 ($Pw_2$) is expressively ...
- 429
6
votes
2
answers
1k
views
Are omega-consistent extensions of PA always consistent with each other?
The question is as in the title. In the edit history you can find my attempt to formalise the question, but that was a failure, for reasons stated clearly in the comments. Thus, my question is just:
...
- 1,344
5
votes
0
answers
287
views
Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?
Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).
