The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
1answer
168 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
0answers
54 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
3answers
288 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
1answer
315 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
1answer
217 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 ...
2
votes
0answers
94 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
1answer
280 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
2answers
630 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 ...
14
votes
4answers
1k 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 ...
3
votes
3answers
163 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
1answer
228 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 ...
12
votes
1answer
220 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 ...
5
votes
2answers
243 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 ...
13
votes
6answers
967 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?
24
votes
3answers
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)$. ...
7
votes
3answers
350 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 ...
6
votes
1answer
151 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$: ...
9
votes
3answers
238 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 ...
2
votes
3answers
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 ...
8
votes
3answers
257 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
1answer
594 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 ...
28
votes
3answers
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
1answer
772 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 ...
3
votes
2answers
264 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 ...
4
votes
1answer
208 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
2answers
529 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 ...
0
votes
0answers
269 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
1answer
638 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
1answer
565 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
3answers
444 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
2answers
345 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. ...
0
votes
2answers
307 views

Models of the natural numbers in ultrapowers in the universe.

Our question arises from wondering about the systems of natural numbers in models ZFC + Con(ZFC) and ZFC + $\neg$Con(ZFC). In thinking of the systems of natural numbers of these models, we came to ...
5
votes
4answers
468 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 ...
1
vote
3answers
442 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)\ \ \&\ ...
10
votes
5answers
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 ...
3
votes
1answer
354 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 ...
4
votes
1answer
413 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 ...
3
votes
1answer
447 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
1answer
523 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 ...
6
votes
1answer
463 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. ...
12
votes
3answers
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 ...
35
votes
7answers
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 ...
1
vote
2answers
649 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 ...
9
votes
4answers
2k 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 ...
1
vote
1answer
262 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 ...
4
votes
2answers
235 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" ...
0
votes
1answer
528 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
3answers
508 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?) ...