Peano arithmetic (or Peano axioms) is a set of axioms for the natural numbers proposed by Giuseppe Peano in 1889.

learn more… | top users | synonyms

7
votes
0answers
130 views

Kripke models of $HA$

Let $K$ be a kripke model and $k$ be one of its node, then $\mathcal{M}_k$ is classical structure of $k$. What is the strongest theory of arithmetic like $T$ such that for every kripke model $K\...
5
votes
0answers
107 views

Lascar strong types in fragments of arithmetic

Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.) Definition Given a saturated model ${\cal M}$ ...
4
votes
0answers
221 views

Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?

Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).
4
votes
0answers
385 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
0answers
165 views

Construction of model of arithmetic from an arbitrary model

Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that: $M'\models PA^-$ (or ...
3
votes
0answers
451 views

What's Reeb's take on naive integers?

Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
3
votes
0answers
146 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 ...
3
votes
0answers
323 views

example just slightly better than the greedy construction

Roth's theorem provides an estimate for the largest size of a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ (a set of integers is nonaveraging if it does not contain any nontrivial three-...
3
votes
0answers
661 views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
2
votes
0answers
73 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 ...
2
votes
0answers
191 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 $...
0
votes
0answers
83 views

What is the known weakest axiom system has Löb's derivability conditions?

We know that Peano Arithmetic satisfies Löb's derivability conditions, which is required in the proof of Gödel's 2nd incompleteness theorem. Is this the best result? If not, is there any known weaker ...
0
votes
0answers
295 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 ...