Skip to main content

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.

Filter by
Sorted by
Tagged with
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 ...
Noah Schweber's user avatar
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 ...
Lukas Holter Melgaard's user avatar
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 ...
Mikhail Katz's user avatar
  • 15.4k
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 ...
Amiren's user avatar
  • 1
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)$$ ...
Christopher King's user avatar
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 ...
Lorenzo's user avatar
  • 2,134
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 = \{ ...
Christopher King's user avatar
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 ...
Jakub Konieczny's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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-...
user21820's user avatar
  • 2,732
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: }\\\...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Dave Pritchard's user avatar
-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 ...
Viipuri's user avatar
  • 19
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 (...
CBuch's user avatar
  • 31
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 ...
Mikhail Katz's user avatar
  • 15.4k
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(...
Joe's user avatar
  • 301
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+\...
Tom Bouley's user avatar
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}$:...
jg1896's user avatar
  • 2,743
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 ...
Zuhair Al-Johar's user avatar
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 ...
E8 Heterotic's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 $\...
Zuhair Al-Johar's user avatar
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 ...
Holo's user avatar
  • 1,645
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?
Viipuri's user avatar
  • 19
-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 ...
HJE's user avatar
  • 23
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$ ...
SmileLee's user avatar
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 ...
Noah Schweber's user avatar
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 $\...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Colin McLarty's user avatar
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}\...
Noah Schweber's user avatar
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 ...
Spencer Woolfson's user avatar
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 ...
Vladimir Kanovei's user avatar
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 ...
Keshav Srinivasan's user avatar
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 ...
Marty's user avatar
  • 13.1k
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 ...
Lost in Traslations's user avatar
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, ...
James Propp's user avatar
  • 19.4k
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 ...
Noah Schweber's user avatar
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{<} \...
Zuhair Al-Johar's user avatar
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$ ...
Vladimir Kanovei's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 $...
Martín S's user avatar
  • 421
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 ...
Zuhair Al-Johar's user avatar
-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 ...
Zuhair Al-Johar's user avatar
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 ...
TomKern's user avatar
  • 429