# 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

2
votes

0
answers

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 ...

4
votes

1
answer

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 ...

7
votes

4
answers

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 ...

4
votes

1
answer

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 ...

14
votes

1
answer

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
votes

2
answers

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 ...

4
votes

1
answer

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
votes

1
answer

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 ...

-2
votes

1
answer

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 ...

3
votes

1
answer

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 ...

4
votes

0
answers

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-...

1
vote

1
answer

299
views

### What is the set theory synonymous with this order-set theory?

Let $ T$ be a theory written in Mono-sorted first order logic with equality, with extralogical primitives: $<, \in$.
Define: $x \leq y \iff x < y \lor x=y$
Axioms:
$\textbf{Well ordering: }\\\...

10
votes

4
answers

1k
views

### Is this theory synonymous with PA?

Language: Mono-sorted first order logic with equality.
Extralogical Primitives: $<, \in$
Define: $x \leq y \iff x < y \lor x=y$
$\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...

1
vote

1
answer

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 ...

-2
votes

1
answer

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 ...

3
votes

1
answer

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 (...

8
votes

1
answer

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
votes

5
answers

2k
views

### In what sense does the sentence $\operatorname{con}(\mathsf{PA})$ "say" that $\mathsf{PA}$ is consistent?

It seems common amongst logicians to think of "truth" as being relative to a particular structure. Consider, for instance, the first-order theory of groups. The sentence $\forall x\forall y(...

14
votes

1
answer

582
views

### Extensions of $PA+\neg Con(PA)$ with large consistency strength

There is a large hierarchy of theories strengthening $PA$ eg $PA+Con(PA)$, $PA+Con(PA+Con(PA))$,..., second-order arithmetic and $ZFC$, ordered by consistency strength.
Is there an extension of $PA+\...

3
votes

0
answers

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}$:...

6
votes

0
answers

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 ...

14
votes

5
answers

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 ...

1
vote

0
answers

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 ...

2
votes

1
answer

312
views

### Can set theory be interpreted in infinite arithmetic?

Is the following system of infinite arithmetic consistent?
If so, can it interpret $\sf ZFC$?
Language: first order logic
Primitives: $\operatorname{Card}, <, + , \times,\text{^}$
where $\...

10
votes

2
answers

418
views

### The additive structure of clusters of nonstandard models of arithmetic

Given $\frak M$ a countable nonstandard model of $\sf PA$ and let $a\in M$ be a nonstandard element. A "cluster around $a$" is the set of successors and predecessors of $a$, a cluster is a ...

0
votes

0
answers

53
views

### Least number principle for IOpen fragment of Peano Arithmetic

Is it possible to prove the least number principle in IOpen fragment of Peano Arithmetic, i.e. having induction only for Open formulas?

-3
votes

1
answer

584
views

### Analysis I, simpler proof of Tao's construction of the integers [closed]

In chapter 4 of Analysis I by Terence Tao, we have the following note about the set theoretic construction of the integers:
In the language of set theory, what we are doing here is starting with the ...

5
votes

0
answers

156
views

### How to show that $\omega^\omega$ is well-founded in PA?

By induction on $n$ variables I can show that for any meta-natural number $n$, PA proves well-foundedness of $\omega^n$. However it is well known that PA proves well-foundedness of $\omega^\omega$ ...

7
votes

0
answers

104
views

### How tightly are decidability and "induction-completeness" linked?

It is known that there are a number of expansions of the structure $\mathfrak{N}:=(\mathbb{N};+)$ which are decidable (= have computable theories); one such example is the expansion by a predicate ...

2
votes

0
answers

68
views

### Can all the strongly provable theorems of $\sf PA+\neg Con(PA)$ be captured in an effective manner through alternative kind of provability?

If we extend $\sf PA$ with the following axiom asserting its own inconsistency:
Inconsistency: $\exists x: \operatorname {Proof}_{\sf PA} (x, \ulcorner 0=1 \urcorner)$
For short denote this axiom by $\...

2
votes

2
answers

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 ...

2
votes

0
answers

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 ...

2
votes

1
answer

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 ...

1
vote

2
answers

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 ...

12
votes

1
answer

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 ...

11
votes

2
answers

368
views

### Can singular long models require less than PA?

Say that a long model is an $\mathfrak{A}\models\mathsf{I\Sigma_1}$ such that $\mathfrak{A}$ has strictly greater cardinality than each of its proper initial segments (in the case $\vert\mathfrak{A}\...

9
votes

0
answers

192
views

### Is there an Arithmetized Completeness theorem for intuitionistic theories?

For classical theories, Henkin's completeness proof can be arithmetized. This leads to the result that for classical theories $T$ and $S$ if $\sigma$ is a formula enumerating $S$ in $T$ then $S \leq T ...

10
votes

2
answers

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 ...

4
votes

0
answers

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 ...

2
votes

0
answers

76
views

### Which sets of natural numbers are "lambda-analytic"?

Begin with a bit of notation. Let $t = t_0, \ldots, t_d$ be a finite sequence of real numbers. Define
$$\lambda^t(x) = x^{t_0} \log(x)^{t_1} \log(\log(x))^{t_2} \cdots.$$
for all real numbers $x \in ...

1
vote

0
answers

114
views

### Which real functions benefit from the Fundamental Theorem of Interval Analysis?

I'm reading Introduction to Interval Analysis, by Moore, Baker & Cloud and complementing it with Global Optimization using Interval Analysis, by Hansen & Walster.
Theorem 5.1 - Fundamental ...

8
votes

3
answers

1k
views

### Dedekind-Peano axioms, but numbers have at most one successor

One can consider a variant of the Dedekind-Peano axioms
in which one replaces the assumption that every number
has exactly one successor by the assumption that every
number has at most one successor, ...

5
votes

1
answer

138
views

### Does visible nonstandardness imply visible ill-foundedness?

For $X\subseteq\mathfrak{M}\models \mathsf{TA}$, say that $X$ is $\mathfrak{M}$-disruptive iff there is some formula $\varphi$ in the language of arithmetic + a new unary predicate symbol $U$ such ...

2
votes

0
answers

128
views

### Can we extend the projectively extended real line with a single number that stands for division of zero by zero?

If we work within $\hat{\mathbb R} = \mathbb R \cup \{\infty\}$, i.e. one point compactification of the real line.
We extend $<$ relation on $\mathbb R$ to $\hat <$ defined as:
$ x \ \hat{<} \...

6
votes

1
answer

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$ ...

3
votes

1
answer

138
views

### Can we always know if an algebraic rule over the reals is preserved over the extended reals or not?

Recall a prior posting titled Is there an effective way to generalize this approach of affinely extending the number line?, and especially the accepted answer given to it. So we are working in $\sf ...

3
votes

0
answers

199
views

### Self-referential Quinean proof of Löb's Theorem

Given its relevance for Open-source game theory, Dr. Andrew Critch asks the following about provability logic:
We conjecture that Löb’s Theorem can be proven without the use of the
modal fixed point $...

1
vote

1
answer

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 ...

-2
votes

1
answer

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 ...

7
votes

1
answer

227
views

### 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 ...