# Tagged Questions

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

139 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$ ...
165 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 ...
196 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 ...
128 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 ...
83 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 ...
282 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 ...
221 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).
178 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 (...
453 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 ...
264 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'...
127 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 ...
772 views

### Is platonism regarding arithmetic consistent with the multiverse view in set theory?

A "truth" platonist for arithmetic believes, given a statement in the language of arithmetic, that the problem whether the statement is true has a definite answer. Prof. Hamkins has argued for a ...
156 views

225 views

### End Extension models of $I\Delta_0$

Recently I'm thinking about question below, but I can not prove or disprove it. Is it true that for every model $M\models I\Delta_0$ there exists a model $M'\models PA$ such that $M'$ is end ...
563 views

### Why is there a need for ordinal analysis?

Consider the Peano axioms. There exists a model for them (namely, the natural numbers with a ordering relation $<$, binary function $+$, and constant term $0$). Therefore, by the model existence ...
83 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 ...
234 views

### Semantic reflection

Let $\ulcorner \cdot \urcorner$ be a fixed encoding of formulas by numbers, e.g. let $\ulcorner \varphi \urcorner$ denote the Godel number of $\varphi$. Let $T$ be a first-order arithmetic theory, e....
273 views

### Can there be computable non-standard models of PA in a weaker sense?

By Tennenbaum's theorem, in the usual sense of computability for models, neither addition nor multiplication can be computable in a non-standard model of PA. Weak version: Can addition or ...
105 views

### What are the adequacy conditions for Rosser Provability?

Famously, Rosser introduced a provability predicate $\pi[A]$ that holds iff $\exists x(xP[A]\wedge\forall y(y\le x\to\lnot yP[\lnot A]))$. Supposing $PA$ is consistent, what are the adequacy ...
108 views

### Lascar strong types in fragments of arithmetic

Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.) Definition Given a saturated model ${\cal M}$ ...
148 views

### Non-standard naturals and goodstein sequences [closed]

By the Kirby–Paris theorem, Goodstein's theorem is independent of Peano arithmetic (PA). Therefore there are non-standard models in which every Goodstein sequence terminates. However, Tennenbaum's ...
190 views

### Induction and nonstandard halting times of standard machines

For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: SH(\mathcal{N})=\{n\in\...
132 views

### PA proves that functions are total

Is there a total recursive function $f:N \to N$ such that for no $\Sigma_1$ formula $\phi(x,y)$ which defines it (i.e., defines its graph), is it true that PA proves that "$\phi$ defines a total ...
989 views

### divisible by all standard prime numbers

This question is about prime numbers in nonstandard models of Peano Arithmetic. Every such model looks like N+AxZ, where A is a dense linear order without end points. There are many nonstandard ...
389 views

### Does PA+Con(PA) entail the existence of non-standard models of PA?

Does $\textsf{PA}$+Con($\textsf{PA}$) entail the existence of non-standard models of $\textsf{PA}$? Is there a reasonable way in which to code, inside $\textsf{PA}$, the statement that $\textsf{PA}$ ...
451 views

### Is factorial definable using a $\Delta_0$ formula?

The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula. Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)? If not, why?
261 views

### Is $ACA_0$ + `True Arithmetic exists' interpretable in $ACA$?

Maybe someone here can help me with a question concerning second-order arithmetic. Consider the system $ACA_T := ACA_0 + \exists X \forall x (x \in X \leftrightarrow T(x))$, where $T(x)$ is a $\Pi_1^1$...
979 views

### nonstandard models and mathematical theorems

Is there a first order statement about the natural numbers (not nonstandard analysis) such that the truth of the statement is easier to see in a nonstandard model? In other words, do nonstandard ...
145 views

### Total formulae in a theory equivalent to $\Delta_0$ formulae in the theory?

Let a formula $\phi$ of the language of first-order Peano arithmetic be total in a theory Th that extends PA iff, for any $k_1, \dots, k_n \in \omega$, Th $\vdash \phi(\bar k_1, \dots, \bar k_n)$ or ...
187 views

### Adding consistency statements to Peano arithmetic allows more instances of transfinite induction?

Consider the hierarchy given by $\cal S_0 =$ first-order Peano arithmetic, $\cal S_{\alpha+1}=\cal S_{\alpha} + Con(S_\alpha)$ (a consistency statement for $\cal S_\alpha$), and if $\alpha$ is a limit ...
684 views

### Application of the Riemann hypothesis and the ABC conjecture to independence results

In Old Home Page of Andreas Weiermann Andreas Weiermann has stated the following: Quite recently I submitted a preprint about an application of the Riemann hypothesis and the ABC conjecture to ...
185 views

### Formal systems needed to formalize relative independence results

We know that Con(ZF) implies Con(ZFC+GCH), Con(ZF+neg(AC)) and Con(ZFC+neg(CH)). But what are some weak theories in which these relative independence results are provable? In particular, are they ...
298 views

### Which ordinals can be proof-theoretic ordinals of a reasonable theory?

When talking to a friend recently he asked a question - are there any reasonable first-order theories which have proof theoretic ordinal equal to small or large Veblen ordinal? I have then extended ...
719 views

### Does Nelson try to prove PA inconsistent directly?

Edward Nelson is known for his serious attempts to show that Peano axioms, and sometimes even weaker theories, are inconsistent. I wasn't able to find Nelson's papers anywhere, so I wanted to ask a ...
614 views

### Boolean Valued Models of PA

O.K, a massively naive question. I've never really studied any non-standard models of PA before. I was just wondering if there's ever been any attempt to use the kind of Boolean valued model theory ...
330 views

### An interpretation of not-Con(PA)

Edit After Andreas Blass answer below and comments below the original post I have changed it to accommodate posters' remarks. I hope it is clear and makes more sense now. Let $\mathrm{PA}$ be the ...
296 views

### “Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski]

In his paper "Restricted set-theoretical defintions in arithmetic" Raphael Robinson cites a problem posed by Tarski: Is it possible to give a restricted set-theoretical definition of addition of ...
169 views

### Definability of arithmetic functions and relations

Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand (...
467 views

### The (un)decidability of Robinson-Arithmetic-without-Multiplication?

I asked this over at math.stackexchange, and though a number of people were interested enough to vote up the question, I didn't get an answer -- which makes me wonder whether it isn't quite so trivial/...
303 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 ...
369 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 ...
469 views

### Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?

Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
235 views

### Models of PRA/EFA with induction on $X$ but not $\omega^X$

As I currently understand it, induction on formulas containing $N+1$ first-order quantifiers is required to prove the well-ordering of the ordinal $(\omega \uparrow\uparrow N) < \epsilon_0$, that ...
403 views

### Overspill in models of arithmetic

Assume that $M$ is a non-standard model of complete arithmetic, i.e. of the theory $Th(\mathbb{N})$. Suppose that $R$ and $S$ are proper cuts of $M$. (With a cut, I mean a subset of the universe of $M$...
332 views

### Does the totality of Ackermann's function prove the consistency of $\Sigma_1$-induction?

It is well known that Ackermann's function is not primitive recursive. Therefore, the theories of primitive recursive arithmetic (PRA) and of $\Sigma_1$-induction ($I\Sigma_1$) cannot prove the ...
85 views

### First-order Peano Axioms and order-completeness of $\mathbb{N}$ [closed]

Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo. Notation: We denote the system of first-order Peano Axioms (along with ...