All Questions
Tagged with peano-axioms reverse-math
20
questions
1
vote
1
answer
74
views
Why doesn't $RCA_0$ prove $\Sigma^0_1$-comprehension?
Answer: because that's $ACA_0$, alright, but:
Friedman et al.'s 1983 "Countable algebra and set existence axioms" has [verbatim, including old terminology and dubious notation]:
Lemma 1.6 ($...
- 1,084
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
2
votes
0
answers
57
views
A Peano system with an infinite initial segment
Let $T$ be a binary tree with the lexicographic order. And $f:T→T$ be the successor operation.
We denote the empty sequence in $T$ by $i$.
Also Suppose that:
For all $X⊂T$ if these two conditions hold:...
0
votes
0
answers
59
views
The set of all finite sequences in RCA0
In the book "subsystems of second order arithmetic", page 68, Simpson claimed that the set of all codes of finite sequences (denoted by "Seq") exists by sigma 0-0 comprehension. I ...
3
votes
0
answers
46
views
In RCA0, Prove that for all n, fⁿ(i) exists
I wanted to prove in RCA0 that:
If f:A→A be a function and i∈A, then for all n, fⁿ(i) exists.
To reach that, I proved another theorem. I wrote my proof but I'm not sure it's rigorous. If you read it, ...
0
votes
1
answer
62
views
Does Z₂ Prove the iteration theorem?
iteration theorem:
Let (ℕ,0,S) be the structure of natural numbers. And let W be an arbitrary set and c be an arbitrary member of W and g be a function from W into W. Then, there is a unique function ...
1
vote
0
answers
107
views
What is the importance of Peano categoricity?
We know that Dedekind in 1888 proved that second order peano arithmetic(PA2) is categorical. My question is, why is it important? Does it have any mathematical, philosophical or foundamental ...
1
vote
0
answers
39
views
Peano categoricity is equivalent to weak konig lemma
Peano categoricity (PC) says that:
Every model for second order peano system is isomorphic to standard model.
i.e PC says that every peano system such as
(A, f, i) is isomorphic to (N, S, 0).
Simpson ...
5
votes
1
answer
494
views
What is the difference between "Peano arithmetic," "second-order arithmetic," and "second-order Peano arithmetic?"
I think this needs to be clarified, so it would be helpful to see an answer to this somewhere.
I've seen the following terms:
Peano arithmetic.
Second-order arithmetic.
Second-order Peano arithmetic.
...
- 2,461
1
vote
0
answers
59
views
What subsystem of second-order arithmetic proves the weak Godel’s Theorem?
Godel’s Incompleteness Theorem states that any omega-consistent recursive theory in the language of first-order arithmetic is incomplete. But there is a weaker version of Godel’s Theorem that is ...
- 10.3k
2
votes
0
answers
115
views
What is the omega-completion of $ACA_0$
The omega rule is an infinitary rule of logic which says that from $\phi(0),\phi(1),\phi(2),...$ you can infer $\forall n\phi(n)$. My question is, what is the theory $T$ obtained by adding the omega ...
- 10.3k
0
votes
2
answers
167
views
Is it consistent for $P(\mathbb{N})$ to be present in a low layer of the Constructible Universe?
$ZF+V=L$ implies that $P(\mathbb{N})$, the power set of the set of natural numbers, is a subset of $L_{\omega_1}$. But my question is, is it consistent with $ZF$ if $P(\mathbb{N})$ is a subset of $L_{...
- 10.3k
1
vote
1
answer
144
views
Differences between real numbers in $ACA_0 + \lnot Con(PA)$ and standard real numbers?
Let $M = (\mathbb N_M, 0_M, +_M, \times_M, <_M, D_M)$ be a model of $ACA_0 + \lnot Con(PA)$. We define $\mathbb R_M$ as Dedekind cuts on $D_M$.
What can we say about the differences between $\...
- 10.5k
4
votes
0
answers
131
views
Is there a weak set theory that can prove that the natural numbers is a model of PA?
$ZFC$ proves that $\mathbb N$ is a model of $PA$. Even $ZF$ does. How weak can go?
In particular, is there some weak set theory that proves that $\mathbb N$ is a model of $PA$, but does not proof ...
- 10.5k
4
votes
1
answer
335
views
What is one set of axioms which are sufficient for Calculus?
I am curious to find out what are the "minimum axioms" needed in order to be able to have highschool level math. Another way to explain it: if we were visited by a super intelligent race of aliens (...
- 23.8k