All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
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, ...
- 5,502
6
votes
2
answers
929
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.
...
CommunityBot
- 1
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
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 $...
CommunityBot
- 1
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 ...
- 149k
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 ...
- 3,475
12
votes
2
answers
973
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 ...
- 35.5k
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 ...
CommunityBot
- 1
4
votes
2
answers
743
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 (...
- 48.8k
7
votes
4
answers
912
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,094
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)\ \ \&\ \...
- 73.2k
34
votes
8
answers
8k
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 ...
- 199
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 ...
CommunityBot
- 1
13
votes
3
answers
1k
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 ...
- 47.8k
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 ...
- 6,219
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
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
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 ...
CommunityBot
- 1
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 ...
- 53.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 ...
CommunityBot
- 1
25
votes
2
answers
3k
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 ...
CommunityBot
- 1
5
votes
2
answers
983
views
finite or infinite many quadratic fields embedding into quaternion algebras?
Suppose $H$ is a indefinite quaternion algebra over $\mathbb{Q}$. Are there infinitely many quadratic fields that can be embedded into $H$?
- 65.4k
25
votes
3
answers
3k
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 ...
CommunityBot
- 1
8
votes
2
answers
1k
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 ...
- 2,283
13
votes
7
answers
7k
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 \...
CommunityBot
- 1
42
votes
7
answers
3k
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 ...
CommunityBot
- 1
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 ...
- 44.4k
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 ...
- 44.4k
10
votes
4
answers
5k
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 ...
- 12.4k
3
votes
3
answers
2k
views
"Interesting" properties of sets of natural numbers
On Wikipedia, there is a list of properties of sets of reals, which are in some sense "interesting": just have a look.
I could not find a comparable list of properties of sets of natural numbers (...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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?...
- 44.4k
-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, ...
CommunityBot
- 1
-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?)
...
CommunityBot
- 1