Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [peano-arithmetic]

Peano arithmetic (or Peano axioms) is a set of axioms for the natural numbers proposed by Giuseppe Peano in 1889.

-1
votes
0answers
56 views

Hyperlogarithmic Axioms [on hold]

I am trying to define a minimal set of axioms allowing the recursive construction of $\mathbb{N}$ and the definition of a binary logarithm function, its inverse, and its corresponding commutative ...
9
votes
0answers
350 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 ...
10
votes
1answer
331 views

Looking for “Set theory for a small universe” by Ketonen

In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...
16
votes
1answer
371 views

What non-standard model of arithmetic does Hofstadter reference in GEB?

Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...
2
votes
0answers
60 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) ...
2
votes
0answers
76 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'...
5
votes
1answer
339 views

Can an uncountable model of Peano Arithmetic be recursive?

Can an uncountable model of Peano Arithmetic be recursive? What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...
5
votes
1answer
327 views

What is the consistency strength of this theory?

Language: first-order logic Primitives: $=, S, \in $ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation). Axioms: those of identity ...
11
votes
2answers
226 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 ...
7
votes
2answers
164 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 ...
1
vote
0answers
258 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 ...
3
votes
0answers
91 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 ...
1
vote
0answers
157 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 { ...
8
votes
1answer
188 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-...
3
votes
1answer
80 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$. ...
7
votes
2answers
429 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 ...
0
votes
0answers
154 views

Indirect attempts at showing that Peano Arithmetic proves Fermat's Last Theorem

So, Peano Arithmetic almost definitely proves Fermat's Last Theorem (see What is known about the relationship between Fermat's last theorem and Peano Arithmetic?). That being said, constructing an ...
11
votes
1answer
532 views

What is known about the relationship between Fermat's last theorem and Peano Arithmetic?

As far as I know, whether Fermat's Last Theorem is provable in Peano Arithmetic is an open problem. What is known about this problem? In particular, what is known about the arithmetic systems $PA + \...
7
votes
1answer
192 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$...
7
votes
0answers
205 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 ...
6
votes
1answer
317 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 ...
2
votes
2answers
650 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 ...
7
votes
2answers
504 views

On a theorem of Zhang Jinwen about models of arithmetic

In the paper ''A Nonstandard Model of Arithmetic Constructed by means of Forcing Method'', Zhang Jinwen states the following in his abstract: The first nonstandard model of arithmetic was given by ...
6
votes
1answer
153 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 ...
11
votes
2answers
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 ...
5
votes
1answer
127 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'...
2
votes
1answer
98 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 ...
1
vote
0answers
104 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)\...
2
votes
1answer
134 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 ...
6
votes
2answers
382 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: ...
4
votes
0answers
234 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 ...
4
votes
1answer
198 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 ...
1
vote
1answer
121 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 ...
1
vote
1answer
249 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 $\...
3
votes
1answer
253 views

Extensions of the Ackermann interpretation to nonstandard theories of arithmetic

In their paper, " On Interpretations of Arithmetic and Set Theory" (Notre Dame Journal of Formal Logic, Vol. 8, No. 4 (2007), pp. 497-510) in section 7, "Fragments of Arithmetic and Set Theory", Kaye ...
5
votes
1answer
144 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 ...
2
votes
1answer
297 views

Is the statement “All numbers are counting numbers” independent of $PA$?

In his paper, "Completed versus Incomplete Infinity in Arithmetic" (look under "www.math.princeton.edu/$\sim$nelson/papers.html" under the subheading "Infinity"), the late Edward Nelson defines the ...
10
votes
0answers
144 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 ...
9
votes
1answer
712 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 ...
2
votes
1answer
195 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$ ...
4
votes
0answers
199 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 $...
2
votes
2answers
230 views

Interpreting peano arithmetic without parameters

I will accept an answer in the form of references to the literature about my question as well as any other information. I am quite ignorant of the area and that will be clear from my question. I ...
1
vote
1answer
160 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 ...
3
votes
0answers
138 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 ...
8
votes
1answer
367 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 ...
5
votes
0answers
252 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).
1
vote
1answer
282 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 (...
5
votes
0answers
704 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 ...
3
votes
1answer
306 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'...
3
votes
1answer
144 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 ...