4
votes
0answers
342 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$ ...
3
votes
1answer
162 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 ...
8
votes
1answer
350 views

Does higher order arithmetic interpret the axiom of choice?

By second order arithmetic I mean the axiomatic theory $Z_2$, that is Peano arithmetic extended by second order variables with the full comprehension axiom, and not defined semantically using power ...
4
votes
2answers
801 views

Axiom to exclude nonstandard natural numbers

In Peano Arithmetic, the induction axiom states that there is no proper subset of the natural numbers that contains 0 and is closed under the successor function. This is intended to rule out the ...
3
votes
1answer
307 views

Godel 's Ladder: Undecidable PI_N sentences for N =2, 3, …

After Godel's groundbreaking results, a plethora of $\Pi_1^0$ undecidable arithmetical sentences have been found by many authors. But what about $\Pi_n^0$ for $n=2,3,.....$ ? There are, to my ...
9
votes
2answers
384 views

Z_2 versus second-order PA

These days, Peano Arithmetic ($PA$) refers to the first-order version of the axioms, where induction is only over formulas referring to natural number variables. Peano's original version of the ...
1
vote
3answers
500 views

Applicability of Deduction theorem to Primitive recursive arithmetic [closed]

Hello. I already asked the question here. The main point is that I tried to prove in Primitive recursive arithmetic (PRA) the totality of the Ackerman function, and I found, that the single thing ...
3
votes
2answers
410 views

NNO = (first order) PA

Recall the definition of a Natural Numbers Object in a topos, and the first order axioms for Peano Arithmetic. I am more familiar with the first definition than the second, so I cannot tell from the ...
7
votes
4answers
553 views

Reference Request: Non-Standard Models of PA

I am attempting to write an expository paper on non-standard models of PA that is accesible to students taking an introductory graduate course in mathematical logic (covering Godel's incompleteness ...
5
votes
4answers
479 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 ...
7
votes
1answer
489 views

Nelson natural number objects in a topos (say)

Nelson's predicative arithmetic (survey article) is a very weak system of arithmetic extending Robinson's $Q$ (Wikipedia). We can have natural number objects in a topos, or even a merely finitely ...
2
votes
2answers
532 views

Natural numbers of great kolmogorov complexity

Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, ...
5
votes
2answers
859 views

Set Theory inside Arithmetics via the Ackermann Yoga

Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of $ZF$-Infinity in $PA$ (see for refs this MO question and here for an excellent ...
8
votes
9answers
3k 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 ...
10
votes
2answers
619 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 ...
7
votes
3answers
1k 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 ...
47
votes
3answers
6k 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 ...
5
votes
2answers
550 views

Weakest subsystems of second order arithmetic for mathematical logic

It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it? What about the incompleteness theorems? Is ...
26
votes
8answers
3k 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 ...
6
votes
1answer
476 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. ...
4
votes
7answers
2k 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 ...
24
votes
3answers
2k 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 ...
5
votes
3answers
2k 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 ...
7
votes
4answers
1k views

Incompleteness and nonstandard models of arithmetic

The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome. Reading Peter Smith's "Gödel Without (Too Many) ...
7
votes
1answer
935 views

models of PA which are isomorphic but not elementarily equivalent?

On page 164 of his book Models of Peano Arithmetic, Kaye states Friedman's Theorem: Let $M{\vDash}PA$ be nonstandard and countable, let $a\in M$ and let $n\in {\mathbb N}$. Then there is a proper ...
5
votes
2answers
840 views

A question about open induction

An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction ...
10
votes
3answers
724 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 ...
1
vote
1answer
265 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 ...
0
votes
3answers
522 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?) ...