# Tagged Questions

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

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

**2**

votes

**3**answers

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

**3**

votes

**0**answers

107 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

301 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

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

**1**

vote

**1**answer

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

**0**

votes

**0**answers

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

**2**

votes

**0**answers

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

**7**

votes

**4**answers

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

**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)\ \ \&\ ...

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

**5**

votes

**2**answers

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

**24**

votes

**3**answers

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

**7**

votes

**4**answers

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

**1**answer

940 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

**2**answers

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