All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
3
votes
0
answers
85
views
What is the relation of total functions in second order arithmetic and fast growing hierarchies?
Answer to this questions shows that fast growing hierarchies can grow arbitrarily fast for some definition of 'arbitrary'.
Can second order arithmetic define all these functions (for any ordinal) ...
- 225
3
votes
0
answers
324
views
Is the quantifier-free fragment of Robinson arithmetic essentially undecidable?
It is well known that Robinson arithmetic (Q) is undecidable, and in fact essentially undecidable. Matiyasevich's theorem implies that the quantifier-free fragment of Q is also undecidable. However, I'...
0
votes
1
answer
495
views
Infinite board games: sentences about
As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A..
can a sentence be devised in A which automatically answers the basic ...
- 129
7
votes
2
answers
237
views
On models of $Th_{\Pi_2}(PA)$
Let $M$ be a nonstandard model of $PA$.
Q1. Is there any way to get a submodel $N\subset M$ such that $N\models Th_{\Pi_2}(PA)$, but $N\not\models PA$?
Q2. Especially, what combinatorial principle ...
CommunityBot
- 1
1
vote
0
answers
346
views
approaching the border between absolute convergence and divergence of series
Let us consider absolute convergent series $\ell^{1^+}$ ordered under eventual dominance (mod finite) $<^*$. T. Bartoszynski proved that unbounded number ${\frak b}(\ell^{1^+}, <^*)$ equals ...
- 16.6k
3
votes
0
answers
144
views
A conservativity result of intuitionistic set theory over arithmetic
In their 1985 paper "Arithmetic Transfinite Induction and Recursive Well-Orderings", Friedman and Ščedrov prove that the theory $\mathbf{ZFI}$ is conservative over $\mathbf{HA}^*$ (see here, Theorem ...
- 355
1
vote
0
answers
205
views
Lowest Turing degree that allows a Turing machine to tell whether $\operatorname{Con}(PA)$?
Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...
- 6,403
8
votes
1
answer
334
views
Analog of Tennenbaum's theorem for EFA
EFA can prove the exponential function to be total, but it cannot prove the superexponential function to be total. Is there an analog of Tennenbaum's theorem (which states the PA has no recursive non-...
- 2,464
3
votes
1
answer
120
views
If one adds an inductive subset to a model of $ACA_0$, do we always get a new model of $ACA_0$?
Suppose $(M, \mathcal X) \models ACA_0$. Recall that a subset $A \subseteq M$ is $inductive$ over $M$ if $M$ satisfies all instances of induction in the expanded language with a predicate for $A$. ...
- 17.7k
8
votes
2
answers
730
views
Is every true statement independent of $PA$ equivalent to some consistency statement?
Most true statements independent of PA that I know of is equivalent to some consistency statement. For example
Con(PA), Con(PA + Con(PA)), Con(PA + Con(PA) + Con (PA + Con(PA)), $\dots$
Goodstein's ...
- 741
9
votes
1
answer
1k
views
ERA, PRA, PA, transfinite induction and equivalences
I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exist.
For instance I'm ...
- 1,228
10
votes
1
answer
761
views
Forcing, cuts, and Dedekind-finite cardinalities
Tl;dr version: there are two natural classes of cuts in the nonstandard model of arithmetic consisting of the Dedekind-finite sets (if, in fact, they constitute such a model); both these classes are ...
CommunityBot
- 1
7
votes
1
answer
246
views
Independent/Easy fraction of sentences over PA
Let $S(n)$ be the set of all sentences over PA of length at most $n$ (counting the quantifier symbols, boolean connectives, arithmetic operations and constants, and counting each variable as length $1$...
CommunityBot
- 1
8
votes
0
answers
345
views
What arithmetic is interpretable in Mayberry's Euclidean set theory?
John Mayberry published what he calls a Euclidean set theory in his book The Foundations of Mathematics in the Theory of Sets. It is ZF with the axiom of infinity replaced by an axiom saying "the ...
- 11.2k
8
votes
1
answer
535
views
Is ZFC+(negation of a large cardinal axiom) arithmetically sound?
My knowledge in set theory is very limited, so I apologize if this question is naive or trivial:
Let $A$ to be a large cardinal axiom. $T=ZFC+\neg A$ is a consistent theory. My question is:
Question ...
- 32.5k
1
vote
2
answers
777
views
Can you remove all the extra arithmetic from ZFC (or other theories)?
Let $\mathbb{N}$ be the standard model of the natural numbers. For any statement in the language of arithmetic, we can translate into a statement in the language of set theory by asking if it is true ...
- 11
6
votes
1
answer
172
views
Logical complexity of hard functions conjectures
Let $\phi_1$ and $\phi_2$ be the following statements:
$\phi_1:$ There is a function $f:\{0,1\}^*\to\{0,1\}$ computable in $E$ that has circuit complexity $2^{\Omega(n)}$.
$\phi_2:$ There is a ...
CommunityBot
- 1
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?
- 53
12
votes
2
answers
1k
views
Trouble with models of PA and ZFC
I have a big trouble in my mind, here is my false reasoning:
The Goodstein's theorem is undecidable in (first order) Peano Arithmetic.
There exist a non standard model N of PA where the Goodstein's ...
- 4,713
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:
...
- 870
9
votes
1
answer
874
views
Is there any set theory $T$ such that $T$ plus true arithmetic is complete with respect to statements in set theory?
Is there an effective set theory $T$ such that $T + $$TA$ is consistient and complete. It should at least prove all theorems of $ZF$ true, so that it is a "standard" set theory. In particular, the ...
- 53.3k
5
votes
1
answer
195
views
Can extensions of $Q$ contradict Löb with recursive reflection?
It is an odd and arguably unacceptable situation that $PA$ does not have $\vdash_{PA}(Pr_{PA}\ulcorner A\urcorner\to A)$ for false recursive sentences $A$.
However, it is not clear to me that Löb'...
- 47.8k
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
1
vote
0
answers
113
views
How do I justify these nontheorems in the absence of the Existence Property for $PA$
Let $\Pi$ be the provability predicate for $PA$. I want to conclude that $PA\nvdash\exists x(\alpha(x)\wedge\lnot\Pi\ulcorner \alpha(\overset{.}{x}) \urcorner)$ and $PA\nvdash\exists x(\lnot \alpha(x)\...
- 3,574
2
votes
1
answer
225
views
How does the existence property fail in $PA$?
Who or what is a good reference that explains how the (numerical) existence property fails for $PA$? Alternatively, what is a good example? It e.g. is clear that the disjunction property must fail ...
- 237k
10
votes
2
answers
1k
views
A question about open induction
An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction ...
- 47.8k
4
votes
0
answers
292
views
the strength of saying "each sentence of true arithmetic has a recursive proof"
Let $PA_{\omega}$ be just like $PA$ except that $PA_{\omega}$-proofs can use any number of applications of the recursive $\omega$-rule.
The recursive $\omega$-rule allows the following:
For each ...
- 449
8
votes
0
answers
1k
views
What's Reeb's take on naive integers?
Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
- 16.6k
12
votes
4
answers
931
views
Parameters in arithmetic induction axiom schemas
The induction schema of Peano Arithmetic is standardly given as the universal closure of $\phi(0)\land \forall x (\phi(x)\rightarrow \phi(x+1)) \rightarrow \forall x\phi(x)$. However, since the ...
CommunityBot
- 1
4
votes
1
answer
480
views
$f_{\epsilon_0}$ and provably total functions in $PA$
A total recursive function $f(x)$ is provably total in $PA$ if there's some formula $\phi(x,y)$ such that
$f(x)=y \iff PA\vdash \phi(x,y)$ and
$PA\vdash \forall x \exists y \phi(x,y)$
I know (not in ...
- 2,619
6
votes
3
answers
1k
views
Provability in Second-Order Arithmetic without the Successor Axiom
Consider second-order Peano Arithmetic Z2, i.e. the two-sorted first-order theory with induction and comprehension. Remove the assumption about the totality of the successor relationship (the ...
- 1,228
1
vote
1
answer
238
views
Elementary functions in a formalized PA
I'm having trouble understanding some parts of the paper "Provably computable functions and the fast growing hierarchy" by Buchholz and Wainer (1987).
On page 183 they say that their system has ...
- 7,145
1
vote
1
answer
311
views
Forcing the consistency of $ZF$ from a fragment of $ZF$
Implicit in the technique of forcing is the following relative consistency result:
If $\mathfrak M$$\vDash$$T$, and therefore $T$ is consistent (where $\mathfrak M$ is the ground model) then if $\...
- 6,132
6
votes
1
answer
209
views
Is $PRA$ + $TI({\epsilon_0})$ mutually interpretable with some theory in the language of set theory?
As is well known, the following theory is equiconsistent with $PA$:
$ZFC$ with the axiom of infinity replaced by its negation.
Since this theory is equiconsistent with $PA$, it would seem ...
- 6,132
18
votes
3
answers
2k
views
Is Robinson Arithmetic biinterpretable with some theory in LST?
Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
- 47.8k
2
votes
2
answers
1k
views
Are there non-commutative models of arithmetic which have a prime number structure?
Peano Arithmetic (PA) models have a prime number structure and commutativity of addition and multiplication. Presburger arithmetic (PrA) models of arithmetic have addition without multiplication and ...
- 12.4k
10
votes
0
answers
161
views
Minkowski's lattice theorem in fragments of arithmetic
It is widely remarked that Minkowski's lattice theorem (or, convex body theorem) is a kind of geometrical pigeonhole principle. And it seems it should have a very elementary proof at least for convex ...
- 11.2k
57
votes
2
answers
7k
views
What arithmetic information is contained in the algebraic K-theory of the integers
I'm always looking for applications of homotopy theory to other fields, mostly as a way to make my talks more interesting or to motivate the field to non-specialists. It seems like most talks about ...
CommunityBot
- 1
3
votes
2
answers
353
views
Reference request: Minimal Axiomatizations of PA over (+,x,<=).
Many years ago, when I was still a high school student, I came up with a certain first-order axiomatization of PA over the signature (+, x, ≤). Out of nostalgia, I've decided to clean up what I ...
- 47.8k
2
votes
1
answer
247
views
How can two theories $T$ and $T+\phi$ be mutually interpretable?
Following Koellner in http://plato.stanford.edu/entries/independence-large-cardinals/, "a theory $T_1$ is interpretable in $T_2$ ($T_1 \leq T_2$) when, roughly speaking, there is a translation $\tau$ ...
- 53.3k
4
votes
0
answers
219
views
Construction of model of arithmetic from an arbitrary model
Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that:
$M'\models PA^-$ (or $...
CommunityBot
- 1
1
vote
1
answer
274
views
Natural number properties as uninterpreted functions in first order logic
Can we express the following property of natural numbers as FOL. The property given below is only indicative, I am more interested in knowing how the concepts such as "infinitely many X exists for so ...
CommunityBot
- 1
1
vote
1
answer
186
views
What is difference between length of proof and length of its presentation in Peano Arithmetic?
In this paper http://www.sciencedirect.com/science/article/pii/0304397584901117 page $19$ or $29$ it seems to imply there is a difference between length of proof and length of its presentation in ...
- 39.1k
3
votes
0
answers
198
views
What is the known weakest axiom system has Löb's derivability conditions?
We know that Peano Arithmetic satisfies Löb's derivability conditions, which is required in the proof of Gödel's 2nd incompleteness theorem. Is this the best result? If not, is there any known weaker ...
- 779
9
votes
1
answer
580
views
Interpreting Robinson arithmetic in a very weak set theory
It is known that adjunctive set theory interprets Robinson arithmetic, and that extensionality is not needed for that. (Montagna and Mancini, "A minimal predicative set theory", Notre Dame Journal of ...
- 47.8k
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).
- 39.9k
1
vote
1
answer
629
views
In what sense is the "descending chain principle" for ordinals less than $\epsilon_0$ 'infinitary?
In the introduction to his paper "Assignment of Ordinals to Terms for Primitive Recursive Functionals of Finite Type", W.A. Howard writes:
Gentzen...showed that the consistency of first order (...
- 42.8k
3
votes
1
answer
404
views
Simplest PA theorem whose proof requires encoding of sequences even though the statement itself doesn't
What is the simplest number-theoretic theorem whose proof requires exponentiation or finite sequences/sets (so any proof in Peano Arithmetic would need to use encodings of such things using e.g. Gödel'...
CommunityBot
- 1
3
votes
1
answer
181
views
Least ordinal not embedded in a total order
If $(E,<)$ is a linear order, let $s(E,<)$ denote the least ordinal which doesn't embed in $(E,<)$.
I am trying to prove the following:
If $(M,+,.,0,1)$ is a model of open induction, (or ...
- 237k
3
votes
0
answers
187
views
Reducing Consistency of $PA$ [closed]
By godel translation consistency of $PA$ is equivalent to consistency of $HA$.
I want to know any similar theorems for $PA$.
1.What is the minimal theory $T\subsetneq PA$ such that the proof of $PA\...
CommunityBot
- 1