# Questions tagged [theories-of-arithmetic]

Theories of arithmetic in first-order logic, such as Peano arithmetic, second-order arithmetic, Heyting arithmetic, and their subsystems and extensions. Models of Peano arithmetic.

120 questions
Filter by
Sorted by
Tagged with
54 views

### $\Pi^0_1$ sentences modulo "schematic entailment"

Let $\mathfrak{P}$ be the preorder of $\Delta^0_0$ (= only bounded quantifiers) formulas with one free variable in the language of arithmetic with a symbol for each primitive recursive function, under ...
• 19.4k
109 views

### Does this hierarchy of fragments of $I \Sigma_1$ collapse?

Does anyone know whether the following hierarchy of fragments of $\mathrm{I} \Sigma_1$ (or rather $\mathrm{I} \Pi_1$) collapses or not? Let $\Sigma^b_n$ denote formulas in the language of arithmetic ...
448 views

### A conservative extension of Peano Arithmetic

Ulrich Kohlenbach makes the following intriguing comment here: "In the 70s S. Feferman introduced a mathematically strong system S=restricted(PA^omega)+QF-AC+mu for classical mathematics (and in ...
• 15.4k
464 views

### Truth Values of Statements in non-standard models

Excuse me, if the question sounds too naive. Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...
487 views

### Is there a theory between HA and PA that doesn't have Markov's rule?

A theory $T$ admits Markov's rule when For every formula $\phi(n)$, if $$T \vdash \forall n \in \mathbb N. \phi(n) \lor \lnot \phi(n)$$ and $$T \vdash \lnot \lnot \exists n \in \mathbb N. \phi(n)$$ ...
• 5,841
406 views

### Models of second-order arithmetic closed under relative constructibility

I know little to nothing about second-order arithmetic and its subsystems. However, I would like to understand when a model of (a subsystem of) second-order arithmetic ($\mathsf{Z}_2$) is downward ...
• 2,134
235 views

### What is the theory of statements with a provably *bounded* realizer (according to PA)?

$\let\T\mathrm\def\kr{\mathrel{\mathbf r}}$This is a follow up to Kleene realizability in Peano arithmetic. We can summarize the results from Emil Jeřábek's answer as follows: \begin{gather*} T_1 = \{ ...
• 5,841
250 views

### Why include $0$ and $1$ in the signature of Presburger arithmetic?

I recently became interested in some problems concerning decidability of extensions of Presburger arithmetic. However, being a number-theorist rather than a logician, I am confused by some notational ...
• 1,762
207 views

### Would this alteration safeguard the resulting theory from inconsistency?

If we replace "Emergence" axiom in the theory $T$ presented at posting "What is the set theory synonymous with this order-set theory?" with the following axiom, call the resulting ...
• 9,362
162 views

### Would this alteration of $T$ affect its synonymy with PA?

If we replace the single axiom "Emergence" in the axiomatic system $T$ presented at posting [What is the set theory synonymous with this order-set theory], by the following schema. Would the ...
• 9,362
144 views

### Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?

(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.) Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
• 2,732
1 vote
299 views

• 9,362
1 vote
212 views

### Seeking clarification of ultrapower nonstandard model of arithmetic

I've read that one nonstandard model of arithmetic is: take $\mathbb{N}^\mathbb{N}$, the set of countably infinite sequences of natural numbers take a quotent that gives the ultrapower: identify ...
• 1,258
367 views

### Defining the set of natural numbers in the first order Peano arithmetic [closed]

The question seems simple, but I'm not sure: let's consider a first order Peano Arithmetic and its standard model $N = \{ 0,1,2,3,... \}$ of natural numbers. A question: how can we define the whole ...
• 19
108 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 (...
• 31
569 views

### Con(PA) via non-well-foundedness?

Lumsdaine made the following interesting comment: if Con(PA) fails in a non-standard model, it means it contains a “proof of non-standard length” of a contradiction from PA. With a little work, one ...
• 15.4k
2k views

• 345
198 views

### Independence and truth in PA

By $\textbf{PA}$ I will mean the usual first-order Peano Arithmetic. I will denote an element of $\mathbb{N}$ by $n$, and by $[n]$ I will denote the corresponding term in the language of $\textbf{PA}$:...
• 2,743
400 views

### Can Set Theory be turned into Infinite Arithmetic?

The following system I'd label as "Infinite Arithmetic" is simply an endeavor to extend second order arithmetic to the infinite ordinal world, and extending with it the representation of ...
• 9,362
2k views

### How is it possible for PA+¬Con(PA) to be consistent?

I'm having some trouble understanding how a certain first-order theory isn't just straight-up inconsistent. Let $PA$ be the axioms of (first-order) Peano arithmetic and let $C$ be the following ...
• 157
1 vote
117 views

### Is set theory interpretable in infinite primitive recursive arithmetic?

In A Formalization of the Theory of Ordinal Numbers, Takeuti interprets $\sf ZFC$ in a first order theory extending first order arithmetic to the infinite ordinal realm, while at the same time ...
• 9,362
312 views

• 9,362
280 views

### Can we use remote provability to prove the first incompleteness theorem sans $\omega$-consistency?

Let $\mathcal g_1$ denote the usual Godel sentence defined as: $$\mathcal g_1 \iff \neg\exists x:\operatorname {Proof}_T(x, \ulcorner \mathcal g_1 \urcorner)$$ Lets suppose that $\sf T$ is ...
• 9,362
118 views

### Can PA be acyclically complete?

Any formula $\phi$ in the first order language of arithmetic is to be called acyclic if and only if we can associate with it an acyclic undirected graph whose nodes are the variable symbols occurring ...
• 9,362
192 views

### Do these two provability theories over PA differ in consistency strength?

This posting is related to the answer to this question. Lets extend the language of $\sf PA$ with a monadic symbol "$\vdash$", add to the formula formation rules, the rule: if $(\phi)$ is a ...
• 9,362
1 vote
216 views

### Does strong provability imply syntactical provability?

This posting is related to the answer to this question. Lets extend the language of $\sf PA$ with a monadic symbol "$\vdash$", add to the formula formation rules, the rule: if $(\phi)$ is a ...
• 9,362
472 views

### Is there a useful measure of density of decidable sentences in PA?

Essential undecidability of PA says every complete extension of PA includes a non r.e. set of new "axioms," all undecidable in PA.  In that sense lots of sentences of PA are undecidable in ...
• 10.8k
368 views

577 views

### Is diamond consistent with 2nd order PA?

If $T$ is a theorem of ZF which says something only about reals, then one may want to prove $T$ using a theory like 2nd order PA or related theories like ZFC$^-$ or GBC$^-$ (minus accounts for the ...
• 2,321
254 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,529
76 views

• 9,362
179 views

### Interpretation of $ZFC^-$ in 2nd order Peano arithmetic

Let $Z_2^-$ be the 2nd order Peano arithmetic without the schema of Countable Choice. It has been known, since 1960s at least, that $ZFC^-$ (without the power set) admits an interpretation in $Z_2$ ...
• 2,321
138 views

• 421
1 vote
199 views

### Is there an effective way to generalize this approach of affinely extending the number line?

The general approach here is a follow up of the approach outlined in a prior posting on extending the projectively extended real line. In particular arithmetic operators break down to ternery ...
• 9,362
338 views

### Is this extension of the projectively extended real line, consistent?

This posting has been Edited. The edited material shall be noted. The projectively extended real line $\hat {\mathbb R}= \mathbb R \cup \{\infty\}$ is one system which allows division by zero! Yet it ...
• 9,362
### What is known about first order logic of $\mathbb{N}$ with + and a unary predicate?
In "Weak Second-Order Arithmetic and Finite Automata", Büchi claims that the first order theory of $\mathbb{N}$ with + and a predicate for recognizing powers of 2 ($Pw_2$) is expressively ...