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
68 votes
4 answers
11k views

Nelson's program to show inconsistency of ZF

At the end of the paper Division by three by Peter G. Doyle and John H. Conway, the authors say: Not that we believe there really are any such things as infinite sets, or that the Zermelo-Fraenkel ...
Andreas Thom's user avatar
  • 25.3k
57 votes
2 answers
7k views

What arithmetic information is contained in the algebraic K-theory of the integers

I'm always looking for applications of homotopy theory to other fields, mostly as a way to make my talks more interesting or to motivate the field to non-specialists. It seems like most talks about ...
David White's user avatar
  • 29.4k
54 votes
1 answer
3k views

In the two-person Killing the Hydra game, what is the winning strategy?

My question is which player has a winning strategy in the two-player version of the Killing the Hydra game? In their amazing paper, Kirby, Laurie; Paris, Jeff, Accessible independence results for ...
Joel David Hamkins's user avatar
42 votes
1 answer
2k views

Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?

By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following: We are considering a ...
Gro-Tsen's user avatar
  • 29.9k
41 votes
7 answers
3k views

How would one even begin to try to prove that a simple number-theoretic statement is undecidable?

This question is closely related to this one: Knuth's intuition that Goldbach might be unprovable. It stems from my ignorance about non-standard models of arithmetic. In a comment on the other ...
gowers's user avatar
  • 28.7k
37 votes
3 answers
3k views

Why do stacked quantifiers in PA correspond to ordinals up to $\epsilon_0$?

I am trying to understand why induction up to exactly $\epsilon_0$ is necessary to prove the cut-elimination theorem for first-order Peano Arithmetic; or, as I understand, equivalently, why the length ...
Eliezer Yudkowsky's user avatar
35 votes
8 answers
8k views

Arithmetic fixed point theorem

I want to understand the idea of the proof of the artihmetic fixed point theorem. The theorem is crucial in the proof of Gödel's first Incompletness theorem. First some notation: We work in $NT$, the ...
Martin Brandenburg's user avatar
32 votes
11 answers
10k views

Is PA consistent? do we know it?

1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please). 2) There are proofs (...
32 votes
2 answers
1k views

What is the logical status of the sentence combining the ideas of Löb and Rosser, "this sentence is provable before any proof of its negation"?

Logicians are familiar with the variety of self-referential sentences expressible in the language of arithmetic: The Gödel sentence, "this sentence is not provable", which indeed is not ...
Joel David Hamkins's user avatar
31 votes
2 answers
2k views

Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?

There are many interpretations of arithmetic in set theory. The Zermelo interpretation, for example, begins with the empty set and applies the singleton operator as successor: $$0=\{\ \}$$ $$1=\{0\}$$ ...
Joel David Hamkins's user avatar
31 votes
2 answers
3k views

Do we expect that sufficiently large computable ordinals settle every question of arithmetic?

I came across a post by Ron Maimon on physics.SE that makes what seems to me to be a very interesting conjecture I've never seen before about what it would take to settle every question of arithmetic. ...
Qiaochu Yuan's user avatar
30 votes
2 answers
3k views

Even XOR Odd Infinities?

Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$. (http://en.wikipedia.org/wiki/Peano_axioms#First-...
Russell Easterly's user avatar
29 votes
10 answers
4k views

Defining the standard model of PA so that a space alien could understand

First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on ...
Pace Nielsen's user avatar
27 votes
5 answers
3k views

What is induction up to $\varepsilon_0$?

This is a question asked out of curiosity, and because I can't understand the Wikipedia page. I have often been told that PA cannot prove the validity of induction up to $\varepsilon_0$, which has ...
David E Speyer's user avatar
27 votes
1 answer
650 views

Decidability of equality of expressions built using 1,+,-,*,/,^

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
Zakharia Stanley's user avatar
25 votes
4 answers
3k views

What can be proven in Peano arithmetic but not Heyting arithmetic?

Hi. I'll confess from the start to not being a logician. In fact this question came up not from research but during a discussion with a friend about whether the classical proof that $\sqrt{2}$ is ...
Brad Rodgers's user avatar
  • 2,141
25 votes
3 answers
6k views

Presburger Arithmetic

Presburger arithmetic apparently proves its own consistency. Does anyone have a reference to an exposition of this? It's not clear to me how to encode the statement "Presburger arithmetic is ...
Brendan Cordy's user avatar
25 votes
2 answers
3k views

Is there a known natural model of Peano Arithmetic where Goodstein's theorem fails?

(I've previously asked this question on the sister site here, but got no responses). Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It turns out that this ...
Jason DeVito - on hiatus's user avatar
25 votes
3 answers
3k views

Composite pairs of the form n!-1 and n!+1

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$. Is ...
François G. Dorais's user avatar
23 votes
5 answers
1k views

What is the spectrum of possible cofinality types for cuts in an ordered field? Or in a model of the hyperreals? Or in a nonstandard model of arithmetic?

I am interested to know the full range of possibilities for the cofinality type of cuts in an ordered field and in other structures, such as nonstandard models of arithmetic. Definitions. ...
Joel David Hamkins's user avatar
21 votes
5 answers
2k views

Alternative Arithmetics

Although, beyond any doubts, $ZFC$ is by and large the predominantly accepted theory of sets, there have been a few attempt to establish some serious competitors in town. I just quote two of them (...
Mirco A. Mannucci's user avatar
20 votes
3 answers
2k views

Can FPA really prove its consistency?

I will ask the question first and then explain. QUESTION: FPA can prove its own consistency in the Godelian sense. But can it really prove its consistency? FPA is a multi-sorted first-order theory,...
abo's user avatar
  • 1,844
18 votes
3 answers
1k views

Is Robinson Arithmetic biinterpretable with some theory in LST?

Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
Adam's user avatar
  • 3,247
18 votes
1 answer
692 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"...
Dave Pritchard's user avatar
17 votes
7 answers
2k views

Non-constructive proofs of decidability?

Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
17 votes
3 answers
2k views

Did Edward Nelson accept the incompleteness theorems?

Edward Nelson advocated weak versions of arithmetic (called predicative arithmetic) that couldn't prove the totality of exponentiation. Since his theory extends Robinson arithmetic, the incompleteness ...
BPP's user avatar
  • 665
17 votes
3 answers
2k views

Gödel's Incompleteness Theorem and the complexity of arithmetic

In How complicated can structures be? Jouko Väänänen says: The guiding result of mathematical logic is the Incompleteness Theorem of Gödel, which says that the logical structure of number theory ...
Hans-Peter Stricker's user avatar
17 votes
1 answer
2k views

Existence of a model of ZFC in which the natural numbers are really the natural numbers

I know that, from compactness theorem, one can prove that there are models of first order arithmetic in which there is some "number" which is not a successor of zero, in the sense that it is strictly ...
display llvll's user avatar
17 votes
1 answer
2k 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 + \...
Christopher King's user avatar
16 votes
3 answers
18k views

Non-computable but easily described arithmetical functions

I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted ...
Marc Alcobé García's user avatar
16 votes
2 answers
1k 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?
Yoni Zohar's user avatar
16 votes
2 answers
640 views

Is (Z,+,0,1,P2,P3) decidable?

Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable? I know that adding just one of P2, P3 to Presburger keeps it decidable, ...
ikp's user avatar
  • 418
16 votes
1 answer
798 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 countable non-standard model of PA. Weak version: Can addition or ...
user avatar
16 votes
1 answer
491 views

Are there signatures escaping from Tennenbaum's Theorem?

By Tennenbaum's Theorem all recursive models of $\mathsf{PA}$ are isomorphic to the standard model. And by a result of Wilmer this holds even for models of the theory $\mathsf{IE}_1\subseteq \mathsf{I}...
Fedor Pakhomov's user avatar
15 votes
2 answers
2k 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 ...
AEWARG's user avatar
  • 213
15 votes
2 answers
984 views

How special is first-order $\mathsf{PA}$?

This is a modified version of a question which was asked and bountied at MSE without success. Below, "$\mathsf{PA}$" refers to first-order Peano arithmetic. There are various "...
Noah Schweber's user avatar
15 votes
2 answers
1k views

Could Kronecker accept a proof of Goodstein's theorem?

A famous result of Goodstein asserts that the Goodstein sequence of integers terminates. For a precise statement and a short proof, see https://en.wikipedia.org/wiki/Goodstein%27s_theorem. A well ...
Piotr Hajlasz's user avatar
14 votes
3 answers
2k views

Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
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
14 votes
4 answers
1k 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 ...
King Kong's user avatar
  • 631
14 votes
5 answers
1k 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
  • 191
14 votes
1 answer
573 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
14 votes
1 answer
1k views

Is there a nonstandard model of arithmetic having precisely one inductive truth predicate?

$\newcommand\Tr{\text{Tr}}$My question is whether there can be a nonstandard model of PA having a unique inductive truth predicate. Background. If $\mathcal{N}=\langle N,+,\cdot,0,1,<\rangle$ is ...
Joel David Hamkins's user avatar
14 votes
0 answers
595 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 ...
David Roberts's user avatar
  • 33.8k
13 votes
2 answers
1k 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 ...
Thinniyam Srinivasan Ramanatha's user avatar
13 votes
3 answers
1k views

Reducing ACA₀ proof to First Order PA

According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA. http://en.wikipedia.org/wiki/Reverse_Mathematics First of all I have a few questions about the proof: a - What ...
Lucas K.'s user avatar
  • 1,659
13 votes
1 answer
845 views

What metatheory proves $\mathsf{ACA}_0$ conservative over PA?

Simpson's book shows $\mathsf{ACA}_0$ is conservative over $\mathsf{PA}$ in the natural way by model theory using definable subsets. Of course, $\mathsf{ACA}_0$ being conservative over PA is ...
Colin McLarty's user avatar
13 votes
1 answer
476 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
13 votes
1 answer
380 views

What is the proof-theoretic ordinal of bare $\mathsf{NFU}$?

On the Stanford Encyclopedia of Philosophy article on alternative axiomatic set theories, it is stated without reference that bare $\mathsf{NFU}$ (i.e., $\mathsf{NFU}$ without the axiom of infinity) ...
James Hanson's user avatar
  • 10.3k
12 votes
7 answers
7k views

Are real numbers countable in constructive mathematics?

We are talking about ordinary reals in constructive mathematics. Let represent each real number by infinite converging series: $$r = [\;(a_0,b_0),(a_1,b_1),...,(a_i,b_i),...\;]$$ $$where\quad a_i \...

1
2 3 4 5
7