**35**

votes

**7**answers

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

**29**

votes

**3**answers

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

**27**

votes

**3**answers

1k 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)$.
...

**15**

votes

**4**answers

2k views

### What is induction up to epsilon_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 $\epsilon\_0$, which has been ...

**13**

votes

**6**answers

1k 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?

**12**

votes

**2**answers

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

**12**

votes

**1**answer

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

**12**

votes

**1**answer

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

**12**

votes

**1**answer

365 views

### Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?

Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...

**10**

votes

**5**answers

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

**9**

votes

**4**answers

3k views

### Historically first uses of mathematical induction

I'm interested in find out what were some of the first uses of mathematical induction in the literature.
I am aware that in order to define addition and multiplication axiomatically, mathematical ...

**9**

votes

**3**answers

252 views

### Uncountable model of bounded arithmetic with an elementary end extension

Theorem 1.53 (3) in page 227 of Hajek and Pudlak's book, Metamathematics of First-Order Arithmetic, says:
Theorem. If $M$ is a countable model of $I\Delta_{0}$ such that $M$ has a proper elementary ...

**9**

votes

**1**answer

653 views

### Is an ultrafinitist Hilbert's program doomed?

Hilbert's program is popularly understood as an attempt to justify infinitary mathematics with a finitary consistency proof. Godel's Second Theorem is usually considered as showing this is not ...

**8**

votes

**3**answers

288 views

### If an oracle Turing machine halts with every infinite arithmetic oracle, can it fail to halt with some non-arithmetic oracle?

Let $e$ be an index of an oracle Turing machine program and $k$ be some natural number. Let us say that a subset of $\mathbb N$ is arithmetic if it is definable in the model $\langle \mathbb ...

**8**

votes

**1**answer

302 views

### The (un)decidability of Robinson-Arithmetic-without-Multiplication?

I asked this over at math.stackexchange, and though a number of people were interested enough to vote up the question, I didn't get an answer -- which makes me wonder whether it isn't quite so ...

**7**

votes

**3**answers

398 views

### Elementary end extensions of models of Peano Arithmetic in uncountable languages

A well-known theorem of Mills asserts that there is a model of Peano Arithmetic $M$ in an uncountable language such that $M$ has no elementary end extension (e.e.e.). I ask whether every complete ...

**7**

votes

**1**answer

602 views

### Has Ribet's theorem been proved using only finite powers of primes?

Ribet proved the Serre epsilon conjecture using $p$-adic Galois representations (http://math.berkeley.edu/~ribet/Articles/invent_100.pdf). Can someone show how to replace all use of $p$-adics in ...

**7**

votes

**1**answer

245 views

### The definition of < in Robinson's Q

I recently had to explain how the basic axioms in Simpson's Subsystems of Second Order Arithmetic were interpretable in Robinson's Q. Most of the axioms are actually the same, except that Simpson ...

**7**

votes

**1**answer

221 views

### Forcing, cuts, and Dedekind-finite cardinalities

Tl;dr version: there are two natural classes of cuts in the nonstandard model of arithmetic consisting of the Dedekind-finite sets (if, in fact, they constitute such a model); both these classes are ...

**6**

votes

**1**answer

158 views

### A well-behaved $A$ that is almost contained in every element of some filter for a countable arithmetically closed family $\mathfrak X$

The question has relevance for constructing Scott sets with certain extra desirable properties.
Suppose that $\mathfrak X$ is a countable arithmetically closed family of subsets of $\mathbb N$: ...

**6**

votes

**1**answer

236 views

### Does the totality of Ackermann's function prove the consistency of $\Sigma_1$-induction?

It is well known that Ackermann's function is not primitive recursive. Therefore, the theories of primitive recursive arithmetic (PRA) and of $\Sigma_1$-induction ($I\Sigma_1$) cannot prove the ...

**6**

votes

**1**answer

477 views

### How to locate the paper that established Robinson Arithmetic?

If I'm not mistaken, it was in his seminal paper “An Essentially Undecidable Axiom System”, published in
Proceedings of the International Congress of Mathematics (1950), 729–730,
where R.M. ...

**5**

votes

**4**answers

480 views

### parameters in arithmetic induction axiom schemas

The induction schema of Peano Arithmetic is standardly given as the universal closure of $\phi(0)\land \forall x (\phi(x)\rightarrow \phi(x+1)) \rightarrow \forall x\phi(x)$. However, since the ...

**5**

votes

**2**answers

355 views

### First-order vs second-order provability

Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except ∀x(Sx≠0) is replaced with ∃x(Sx=0). Let MA2 be the second-order variation, with second-order induction.
...

**5**

votes

**2**answers

147 views

### Models of PRA/EFA with induction on $X$ but not $\omega^X$

As I currently understand it, induction on formulas containing $N+1$ first-order quantifiers is required to prove the well-ordering of the ordinal $(\omega \uparrow\uparrow N) < \epsilon_0$, that ...

**4**

votes

**2**answers

239 views

### Goedelizability and decidability of a property of Peano formulas

Sorry for not knowing the answers to these elementary questions:
Is the property of formulas of the first-order language of Peano arithmetic of "defining a finite set of natural numbers" ...

**4**

votes

**3**answers

458 views

### Provability in Second-Order Arithmetic without the Successor Axiom

Consider second-order Peano Arithmetic Z2, i.e. the two-sorted first-order theory with induction and comprehension. Remove the assumption about the totality of the successor relationship (the ...

**4**

votes

**2**answers

287 views

### Overspill in models of arithmetic

Assume that $M$ is a non-standard model of complete arithmetic, i.e. of the theory $Th(\mathbb{N})$. Suppose that $R$ and $S$ are proper cuts of $M$. (With a cut, I mean a subset of the universe of ...

**4**

votes

**1**answer

229 views

### ERA, PRA, PA, transfinite induction and equivalences

I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exist.
For instance I'm ...

**4**

votes

**2**answers

269 views

### Does the Feferman-Schutte analysis give a precise characterization of Predicative Second-Order Arithmetic?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...

**4**

votes

**1**answer

424 views

### Implication of Polignac's conjecture on prime distribution in models of PA

Polignac's conjecture (PC) is that there exists infinitely many pairs of consecutive prime numbers that are a distance $d$ apart for some natural number $d$. The twin prime conjecture is the ...

**4**

votes

**1**answer

233 views

### Interpreting the Galois theory of finite extensions of $\mathbb{Q}$ in PA

Any finite extension of the rationals, along with its Galois group, can be interpreted in Peano arithmetic by straightforward means. For a fixed bound $n$ in the degree this is uniform in the ...

**3**

votes

**3**answers

181 views

### Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA

In models of PA with restricted induction power (for example, only $I\Sigma_n$ is present), the failure of higher induction scheme is characterised by the existence of definable cuts (like $\Sigma_2$ ...

**3**

votes

**1**answer

355 views

### Axiomatizations of complete theories

This question was motivated by this recent question by Ricky Demer.
In his paper $\Pi^0_1$ classes and Boolean combinations of recursively enumerable sets, Carl Jockusch showed that there is no ...

**3**

votes

**1**answer

456 views

### Turing degrees of nonstandard models of PA

Since the theorems of (PA + "there is a nonstandard number") are recursively enumerable, by the
Low Basis Theorem, WKL0's proof of the completeness theorem gives a nonstandard model of PA of [low ...

**3**

votes

**2**answers

660 views

### Neither Even Nor Odd Natural Numbers

Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. In Even XOR Odd Infinities? I asked if this statement ...

**3**

votes

**2**answers

269 views

### Reference request: Minimal Axiomatizations of PA over (+,x,<=).

Many years ago, when I was still a high school student, I came up with a certain first-order axiomatization of PA over the signature (+, x, ≤). Out of nostalgia, I've decided to clean up what I ...

**3**

votes

**1**answer

532 views

### Derivability conditions for Robinson arithmetic

Two pieces of hearsay I have encountered about Robinson's Q:
Q fails to satisfy the Löb derivability conditions;
Pudlák criticised the Löb derivability conditions and suggested rival, weaker ...

**3**

votes

**0**answers

106 views

### Peano (Dedekind) categoricity

What is the smallest fragment of second order logic such that $Th(\mathbb{N})$ in that logic is categorical (only one model, namely natural numbers, up to isomorphism). For example, can we do this in ...

**2**

votes

**3**answers

1k views

### Why Does Induction Prove Multiplication is Commutative?

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom:
$$\forall x \forall y \forall ...

**2**

votes

**3**answers

342 views

### Can a Decidable Theory Have Non-recursive Models?

Tennenbaums' theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA.
...

**2**

votes

**1**answer

222 views

### Elementary proof of bounds on factor polynomials

The question Getting a bound on the coefficients of the factor polynomial got very nice answers on Gelfond's theorem. But for work on proof theory of arithmetic I want a proof in arithmetic. The ...

**1**

vote

**2**answers

666 views

### What is cardinality of the set of true undecidable minimal sentences in a formal theory of aritmetic

Let T be a true theory of arithmetic to which the incompleteness theorems apply. Consider two sentences in the language of T to be equivalent if they are provably equivalent over T. How many ...

**1**

vote

**3**answers

445 views

### Generalizations of PA and its standard and non-standard models

Consider Peano's axioms — in its first-order version and without addition and multiplication — with its single injective function $S$:
$(\forall x) \neg Sx = 0$
$\Big(\phi(0)\ \ \&\ ...

**1**

vote

**1**answer

328 views

### Transfinite induction vs induction in mathematics

What are the nontrivial theorems one can prove about natural numbers which need transfinite induction? By "need transfinite induction" I mean one can show that the statement is not provable in ...

**1**

vote

**1**answer

798 views

### Are there non-commutative models of arithmetic which have a prime number structure?

Peano Arithmetic (PA) models have a prime number structure and commutativity of addition and multiplication. Presburger arithmetic (PrA) models of arithmetic have addition without multiplication and ...

**1**

vote

**1**answer

266 views

### Naturally definable sets of natural numbers (3)

[This shall be the last of a series of questions, see Naturally definable sets of natural numbers (2)]
I cannot explain why I have been so stubborn not to see the most straight-forward definition for ...

**1**

vote

**0**answers

57 views

### First-order Peano Axioms and order-completeness of $\mathbb{N}$ [closed]

Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo.
Notation: We denote the system of first-order Peano Axioms (along with ...

**0**

votes

**1**answer

537 views

### Naturally definable sets of natural numbers (2): Can the circle be broken?

(follow-up to: Naturally definable sets of natural numbers)
Every formula $\Psi(x)$ in the first-order language of Peano arithmetic defines a set of natural numbers. Some of these sets are finite, ...

**0**

votes

**3**answers

523 views

### Naturally definable sets of natural numbers

(This is a follow-up question from over there: Natural models of graphs.)
(And it has a follow-up question over there: Naturally definable sets of natural numbers (2): Can the circle be broken?)
...