All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
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
6
votes
1
answer
988
views
Nonstandard models of PA of large cardinal size
It is easy to overlook the fact that the existence of a given large cardinal provides us with a true arithmetical statement that would otherwise be false if the large cardinal notion were not ...
- 2,762
11
votes
1
answer
2k
views
Uncountable nonstandard models of PA
Standard techniques (no pun intended) can be used to show that countable nonstandard models of Peano Arithmetic are order isomorphic to $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$. Once we have used ...
- 2,762
2
votes
2
answers
262
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
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
4
votes
1
answer
876
views
Derivability conditions for Robinson arithmetic
Two pieces of hearsay I have encountered about Robinson's Q:
Q fails to satisfy the Löb derivability conditions;
Pudlák criticised the Löb derivability conditions and suggested rival, weaker ...
- 2,283
18
votes
3
answers
1k
views
Computable nonstandard models for weak systems of arithmetic
By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of ...
user5810
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$?
- 709
14
votes
3
answers
2k
views
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
17
votes
3
answers
3k
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 ...
- 9,720
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 ...
- 6,556
68
votes
4
answers
12k
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 ...
- 25.5k
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 ...
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 ...
- 1,465
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 ...
- 63.1k
12
votes
1
answer
1k
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 Mathematicians (1950), 1952:729–730,
where R.M. ...
- 2,992
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 \...
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 ...
- 44.4k
16
votes
3
answers
19k
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 ...
- 1,465
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 ...
- 29k
9
votes
4
answers
3k
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) Tears",...
- 1,465
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
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
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 ...
user2529
10
votes
2
answers
1k
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 ...
- 6,199
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 ...
- 1,659
17
votes
7
answers
2k
views
Non-constructive proofs of decidability?
Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
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 (...
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,720
-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,720
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,720
-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,720
26
votes
3
answers
7k
views
Presburger Arithmetic
Presburger arithmetic apparently proves its own consistency. Does anyone have a reference to an exposition of this? It's not clear to me how to encode the statement "Presburger arithmetic is ...
- 464
27
votes
5
answers
4k
views
What is induction up to $\varepsilon_0$?
This is a question asked out of curiosity, and because I can't understand the Wikipedia page.
I have often been told that PA cannot prove the validity of induction up to $\varepsilon_0$, which has ...
- 156k