All Questions
Tagged with peano-axioms computability
32
questions
2
votes
0
answers
76
views
Are the models of PA recursively enumerable?
Is there a Turing machine (TM from now on) which lists every model of PA (without the induction axiom schema, so just addition and multiplication)? More specifically, can such a TM list all infinite ...
1
vote
2
answers
70
views
Modern reference on PA degrees?
I'm currently trying to work my way around some papers from Jockush et al, and PA degrees come up frequently. I'd be interested in a modern reference/survey summarizing the main results on the subject,...
- 461
3
votes
1
answer
97
views
Are there examples of statements not provable in PA that do not require fast growing (not prf) functions?
Goodstein's theorem is an example of a statement that is not provable in PA. The Goodstein function, $\mathcal {G}:\mathbb {N} \to \mathbb {N}$, defined such that $\mathcal {G}(n)$ is the length of ...
- 1,027
0
votes
0
answers
59
views
Non recursive provably total functions
It is provable that every primitive recursive function is total in 1st order PA. Some non primitive recursive functions are also provably total in PA.
Can we show that a function is totally provable ...
user1203803
0
votes
1
answer
47
views
Meaning of Provable recursiveness
Is there any difference between provably total function and provable recursiveness of a function in first order PA ?
From provably total I mean that the totality of the function itself is provable in ...
user1203803
4
votes
1
answer
126
views
Representability of Goodstein function in PA
I have a doubt concerning the representability of Goodstein's function in Peano Arithmetic ($PA$). Specifically, the function
$G(n) =$ “The length of the Goodstein sequence starting from $n$”
is ...
- 473
2
votes
0
answers
72
views
Understanding the system $\textbf{ACA}_0'$ and and exercise $6.26$ of Hirschfeldt
The system $\textbf{ACA}_0' $ is the theory $ \textbf{ACA}_0 $ plus the statement $\forall n\,\forall X \,\exists X^{(n)}$. I'm not entirely sure what the proper way to express this as a second order ...
- 1,926
1
vote
0
answers
43
views
Formula $f(x) = y$ with $f$ a computable function can be expressed in PA
I remember reading somewhere (although I can't find a source) that for any computable function $f: \mathbb{N} \to \mathbb{N}$ (that is, a function such that we can write an algorithm that computes $f(...
- 785
5
votes
0
answers
154
views
Can ZFC decide more values of the Busy Beaver function than PA?
This is related to a previous question. In that question, I asked whether ZFC can define the Busy Beaver function. I was told even Peano Arithmetic(PA) can define it, and also that PA can't decide ...
- 21.4k
4
votes
1
answer
448
views
Provably total functions in $\mathsf{Q}$
I was interested in the relations between induction and recursion, and so a natural question (to my mind, anyway), was how much we can prove without appealing to induction, i.e. which functions are ...
- 5,537
2
votes
1
answer
445
views
How does one prove that Peano Arithmetic can represent all partially computable functions?
I'm interested in establishing that for any partially computable $k$-ary function $f$ there exists a formula $\Phi$ with $k+1$ free variables such that
If $f(x_1, \dots, x_k) = y$, then $\Phi(x_1, \...
- 1,249
3
votes
1
answer
71
views
Length of a Deduction
Suppose we have a sentence whose number of of symbols is less than $n$. Assume that this sentence is provable in Peano Arithmetic (with the first-order induction scheme).
Also, suppose that we want ...
- 31
9
votes
1
answer
200
views
What Turing degrees can truth in $\mathbb{N}$ have for different languages?
Tarski’s theorem implies that set of Gödel numbers of statements in the language of Peano arithmetic which are true in $\mathbb{N}$, the standard model of arithmetic, is not a recursive set. In fact ...
- 10.3k
0
votes
1
answer
196
views
What is the smallest ordinal not computable by using artihmetical truth as an oracle?
Kleene's $O$ is a way to use natural numbers as notations for recursive ordinals. I’m wondering what happens if you modify the definition of Kleene’s $O$ to allow for arithmetical truth as an oracle. ...
- 10.3k
3
votes
1
answer
82
views
If the relation $f(x_1, ..., x_n)=y$ is $\Sigma_1$, then is its negation also $\Sigma_1$?
If the relation $f(x_1, ..., x_n)=y$ is $\Sigma_1$, then is its negation also $\Sigma_1$?
The above question (ore more like the imperative to prove it in the affirmative) is Exercise 1. on page 54 of ...
- 117