**6**

votes

**1**answer

169 views

### Which ordinals can be proof-theoretic ordinals of a reasonable theory?

When talking to a friend recently he asked a question - are there any reasonable first-order theories which have proof theoretic ordinal equal to small or large Veblen ordinal? I have then extended ...

**7**

votes

**1**answer

562 views

### Does Nelson try to prove PA inconsistent directly?

Edward Nelson is known for his serious attempts to show that Peano axioms, and sometimes even weaker theories, are inconsistent. I wasn't able to find Nelson's papers anywhere, so I wanted to ask a ...

**9**

votes

**4**answers

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

**1**

vote

**2**answers

234 views

### An interpretation of not-Con(PA)

Edit After Andreas Blass answer below and comments below the original post I have changed it to accommodate posters' remarks. I hope it is clear and makes more sense now.
Let $\mathrm{PA}$ be the ...

**4**

votes

**1**answer

236 views

### “Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski]

In his paper "Restricted set-theoretical defintions in arithmetic" Raphael Robinson cites a problem posed by Tarski:
Is it possible to give a restricted set-theoretical
definition of addition of ...

**0**

votes

**1**answer

128 views

### Definability of arithmetic functions and relations

Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand ...

**8**

votes

**1**answer

342 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

**1**answer

256 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

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

**12**

votes

**1**answer

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

**5**

votes

**2**answers

155 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

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

**6**

votes

**1**answer

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

**1**

vote

**0**answers

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

**2**

votes

**3**answers

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

**1**

vote

**1**answer

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

**2**

votes

**1**answer

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

**3**

votes

**0**answers

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

**0**

votes

**1**answer

313 views

### Recursive Non-standard Models of Modular Arithmetic? [closed]

Any algebraically closed field (ACF) is a model of Modular arithmetic (MA). (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists ...

**3**

votes

**2**answers

263 views

### Efficient representations of natural numbers via arithmetical expressions

A given natural number $n \in \mathbb{N}$ has many representations
as expressions mixing other natural numbers and the operators and punctuation symbols
$\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' ...

**3**

votes

**3**answers

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

**4**

votes

**1**answer

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

**4**

votes

**2**answers

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

**3**

votes

**2**answers

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

**7**

votes

**3**answers

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

**9**

votes

**3**answers

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

**6**

votes

**1**answer

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

**8**

votes

**3**answers

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

**7**

votes

**1**answer

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

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

**1**

vote

**1**answer

201 views

### Infinite board games: sentences about

As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A..
can a sentence be devised in A which automatically answers the basic ...

**3**

votes

**2**answers

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

**35**

votes

**2**answers

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

**26**

votes

**1**answer

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

**11**

votes

**1**answer

394 views

### Does any lower bound on proofs of FLT improve Shepherdson 1965?

In 1965 Shepherdson proved that FLT is independent of the fragment of PA that uses only open induction and signature $0,S,+\times$. Indeed $2x+1\neq 2y$ is independent of that fragment. Schmerl ...

**12**

votes

**1**answer

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

**1**

vote

**1**answer

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

**4**

votes

**1**answer

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

**0**

votes

**2**answers

709 views

### Gödel, Escher, Bach: b is a power of 10. [closed]

I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...

**2**

votes

**3**answers

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

**0**

votes

**0**answers

283 views

### Definitions for Oddness

In the thread Even Xor Odd Infinities I defined odd models of Modular Arithmetic (MA) as models satisfying the axioms of MA and two first order statements. Even XOR Odd Infinities?
$O1) \forall x(x=0 ...

**9**

votes

**1**answer

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

**12**

votes

**1**answer

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

**4**

votes

**3**answers

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

**5**

votes

**2**answers

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

**27**

votes

**3**answers

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

**2**

votes

**0**answers

70 views

### Seeking name for an order raising operator in Higher Order Arithmetic.

Any class $X$ of order $j$ in HOA is in bijection with the order $j+1$ class built up from singletons $\{x\}$ of natural numbers $x$ just the way that $X$ is built up from the numbers $x$. And of ...

**4**

votes

**0**answers

350 views

### How arithmetical is algebraic exponentiation?

Suppose $K$ is an exponential real closed field, i.e. there is an isomorphism, say exp, between the additive group of $K$ and the multiplicative group of its positive elements.
Assume further that $Z$ ...

**2**

votes

**0**answers

159 views

### Is this fragment of arithmetic on $p^{-\infty} {\mathbb Z}$ decidable?

Let $p$ be a prime number. Consider the abelian group $p^{-\infty} {\mathbb Z} = \bigcup p^{-n} {\mathbb Z}$ consisting of rational numbers whose denominator is a power of $p$, under addition.
View ...

**3**

votes

**1**answer

168 views

### Is there an $E_1$-definition of primality?

Here, $E_1$ denotes the set of arithmetic formulas starting with a bounded existential quantifier, followed by a quantifier-free formula. Is there an $E_1$-formula $\phi$ such that $\phi(n)$ holds
iff ...