All Questions
20 questions
5
votes
1
answer
100
views
Mathematical strength of the statement "Heyting Arithmetic admits Markov's rule"
Consider the following theorem about Heyting arithmetic (HA)
For every arithmetical formula $\phi$ whose only free variable is $n$, if $\text{HA} \vdash \forall n. \phi \lor \lnot \phi$ and $\text{HA}...
- 47.8k
3
votes
1
answer
123
views
Kleene normal form theorem for r.e. relations proven in arithmetical theories
After reading the relevant chapters of Classical Recursion Theory (freely available from here), I have the following questions concerning Theorem II.1.10 (Normal form theorem) and Theorem IV.1.9 (...
- 17.7k
11
votes
2
answers
441
views
Are all generalized Scott sets realized as generalized standard systems?
Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so.
The standard system of a nonstandard ...
- 1,228
3
votes
0
answers
283
views
What is the meaning and proof of Harvey Friedman’s ultrafinite incompleteness sentence?
On page 7 of his paper “Adventures in Incompleteness”, Harvey Friedman states the following:
IN ANY LONG ENOUGH SEQUENCE $x_1,...,x_n$ FROM $\{1,2,3\}$, SOME $(x_i,...,x_{2i})$ IS A SUBSEQUENCE OF ...
- 4,597
4
votes
1
answer
377
views
Does ACA prove categoricity of the reals?
$\def\f#1{\text{#1}}$Does $\f{ACA}$ prove that any two internally complete ordered fields are isomorphic?
Here internal completeness is expressed roughly as "every sequence of reals with an upper ...
- 20.7k
3
votes
0
answers
160
views
Is anything known about $\Delta_n$ bounding?
For a class $\Gamma \in \{ \Sigma_n, \Pi_n, \Delta_n \}$ in the arithmetical hierarchy, we can consider the induction, bounding, and least number principles for $\Gamma$:
$\mathsf{I}\Gamma$ is $\big[ ...
- 798
2
votes
1
answer
198
views
Can $\mathsf{RCA}_0$ prove that every nonempty c.e. set $A \subseteq \mathbb{N}$ has a least element?
In other words, can $\mathsf{RCA}_0$ prove that for every function $f\colon \mathbb{N} \to \mathbb{N}$, there is $b \in \mathbb{N}$ such that
$$ \exists k \in \mathbb{N},\ f(k) = b\quad \land\quad \...
- 798
1
vote
0
answers
148
views
Why doesn't $\mathsf{B}\Sigma_2$ hold in $\mathsf{RCA}_0$?
For a formula $\varphi(i,u)$ of arithmetic, the bounding principle for $\varphi$ is the statement
$$\forall m \, \Big( \big( \forall i<m\ \exists u\ \varphi(i,u) \big) \to \big( \exists v\ \forall ...
- 798
11
votes
1
answer
400
views
What is the Turing degree of the monadic theory of the real line?
The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true ...
- 20.7k
8
votes
1
answer
283
views
Paris-Harrington principles parametrized by functions $f:\mathbb N \to \mathbb N$
Recall that the Paris-Harrington Principle, $\mathsf{PH}$, is the statement that for each $e, r, k < \omega$ there is an $N < \omega$ so that given any coloring $c:[N]^e \to r$ there is an $H \...
- 63.9k
1
vote
2
answers
267
views
The "higher topology" of countable Scott sets
Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor ...
- 20.7k
14
votes
0
answers
654
views
Reverse Mathematics of Euclid's theorem
Euclid's theorem that there are infinitely many prime numbers has multiple proofs, ranging from Euclid's original theorem that constructs a new prime from a finite list of such, to Euler's proof that ...
CommunityBot
- 1
2
votes
1
answer
142
views
Does $WKL_0$ plus CON(PA+X) give a binary tree model of PA+X?
In the context of reverse mathematics $WKL_0$ is considered equivalent to Gödel's completeness theorem over $RCA_0$. Does this mean that e.g. $WKL_0$ plus the consistency statement CON(PA+X) gives a ...
- 237k
4
votes
1
answer
347
views
Proving moduli of uniform continuity in RCA_0
Simpson's Subsystems of Second Order Arithmetic (pp. 134ff.) uses RCA$_0$ to prove various theorems of analysis for all continuous functions with a suitable modulus of uniform continuity. And he ...
- 6,287
8
votes
3
answers
2k
views
Does the Feferman-Schutte analysis give a precise characterization of Predicative Second-Order Arithmetic?
A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
- 131
7
votes
1
answer
447
views
The definition of < in Robinson's Q
I recently had to explain how the basic axioms in Simpson's Subsystems of Second Order Arithmetic were interpretable in Robinson's Q. Most of the axioms are actually the same, except that Simpson ...
- 47.8k
12
votes
2
answers
973
views
Z_2 versus second-order PA
These days, Peano Arithmetic ($PA$) refers to the first-order version of the axioms, where induction is only over formulas referring to natural number variables. Peano's original version of the ...
- 35.5k
1
vote
3
answers
996
views
Applicability of Deduction theorem to Primitive recursive arithmetic [closed]
Hello. I already asked the question here. The main point is that I tried to prove in Primitive recursive arithmetic (PRA) the totality of the Ackerman function, and I found, that the single thing ...
CommunityBot
- 1
13
votes
3
answers
1k
views
Reducing ACA₀ proof to First Order PA
According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA.
http://en.wikipedia.org/wiki/Reverse_Mathematics
First of all I have a few questions about the proof:
a - What ...
- 47.8k
8
votes
2
answers
1k
views
Weakest subsystems of second order arithmetic for mathematical logic
It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it?
What about the incompleteness theorems? Is ...
- 2,283