All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
8
votes
0
answers
198
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\...
- 1,689
4
votes
1
answer
245
views
Induction and nonstandard halting times of standard machines
For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: $$SH(\mathcal{N})=\{n\in\...
- 20.7k
3
votes
2
answers
624
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 ...
user10290
3
votes
2
answers
328
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$' ...
- 151k
11
votes
1
answer
433
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 ...
- 11.2k
2
votes
1
answer
185
views
What are the adequacy conditions for Rosser Provability?
Famously, Rosser introduced a provability predicate $\pi[A]$ that holds iff $\exists x(xP[A]\wedge\forall y(y\le x\to\lnot yP[\lnot A]))$.
Supposing $PA$ is consistent, what are the adequacy ...
- 3,574
8
votes
1
answer
2k
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 ...
- 3,267
1
vote
3
answers
996
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 ...
- 15
7
votes
1
answer
198
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$: ...
- 2,240
4
votes
2
answers
924
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, ...
- 7,853
2
votes
2
answers
980
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 ...
- 995
4
votes
2
answers
292
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" goedelizable?...
- 9,730
2
votes
1
answer
347
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 ...
- 11.2k
4
votes
1
answer
376
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 ...
- 11.2k
4
votes
0
answers
126
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}$ ...
8
votes
1
answer
897
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 ...
- 35.5k
2
votes
3
answers
552
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)\ \ \&\ \...
- 9,730
3
votes
1
answer
746
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 ...
user5810
0
votes
2
answers
998
views
Is division considered the mathematical dual of multiplication? [closed]
I'm doing a bit of research for a tech presentation that touches on the subject of mathematical duality. (To be clear, my presentation is not on mathematics or duality, but mentions duality in passing....
- 121
1
vote
1
answer
274
views
Natural number properties as uninterpreted functions in first order logic
Can we express the following property of natural numbers as FOL. The property given below is only indicative, I am more interested in knowing how the concepts such as "infinitely many X exists for so ...
3
votes
0
answers
343
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 ...
-1
votes
1
answer
679
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, ...
- 9,730
1
vote
0
answers
222
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 ...
- 596
3
votes
1
answer
437
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 ...
- 44.4k
-1
votes
3
answers
1k
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?)
...
- 9,730
7
votes
1
answer
694
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 ...
- 2,762
3
votes
1
answer
405
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 ...
- 7,853
0
votes
0
answers
315
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 ...
- 687
2
votes
2
answers
263
views
FTA in first order setting
When I took model theory is an undergraduate, early on we wrestled with trying to state the fundamental theorem of arithmetic in the first order language of arithmetic. The problem was that we needed ...
- 23
2
votes
0
answers
223
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 $...
- 13.3k
3
votes
0
answers
771
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 ...
- 15.4k
3
votes
0
answers
343
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,595
1
vote
1
answer
365
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 ...
- 9,730
2
votes
0
answers
84
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 ...
- 11.2k