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.
313
questions
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\}$$
...
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. ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 (...
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,...
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 ...
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"...
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 ...
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 ...
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 ...
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 + \...
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 ...
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?
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, ...
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 ...
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}...
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 ...
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 "...
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 ...
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 ...
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 ...
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(...
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+\...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$$ ...
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) ...
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 \...