All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
8
votes
1
answer
1k
views
Can the "real" Peano Arithmetic be inconsistent?
Assuming $\text{PA}$ is consistent. Then $\text{PA} + \neg\text{Con}(\text{PA})$ is consistent and have a model, say $M$. We know $M$ must be nonstandard, in which case, there is a nonstandard proof ...
- 237k
14
votes
1
answer
646
views
Extensions of $PA+\neg Con(PA)$ with large consistency strength
There is a large hierarchy of theories strengthening $PA$ eg $PA+Con(PA)$, $PA+Con(PA+Con(PA))$,..., second-order arithmetic and $ZFC$, ordered by consistency strength.
Is there an extension of $PA+\...
- 237k
5
votes
2
answers
2k
views
How many models of Peano arithmetic are isomorphic to the standard model and how many models of Peano arithmetic are non-standard?
I am currently writing a paper on non-standard models of Peano arithmetic and I am having trouble finding references or information that discuss the relative sizes of how many models of Peano ...
- 237k
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 ...
- 1,446
10
votes
2
answers
600
views
Is diamond consistent with 2nd order PA?
If $T$ is a theorem of ZF which says something only about reals, then one may want to prove $T$ using a theory like 2nd order PA or related theories like ZFC$^-$ or GBC$^-$ (minus accounts for the ...
- 237k
15
votes
5
answers
2k
views
In what sense does the sentence $\operatorname{con}(\mathsf{PA})$ "say" that $\mathsf{PA}$ is consistent?
It seems common amongst logicians to think of "truth" as being relative to a particular structure. Consider, for instance, the first-order theory of groups. The sentence $\forall x\forall y(...
- 63.9k
8
votes
1
answer
588
views
Con(PA) via non-well-foundedness?
Lumsdaine made the following interesting
comment:
if Con(PA) fails in a non-standard model, it means it contains a
“proof of non-standard length” of a contradiction from PA. With a
little work, one ...
- 35.5k
29
votes
10
answers
4k
views
Defining the standard model of PA so that a space alien could understand
First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on ...
- 16.6k
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 ...
- 18.7k
3
votes
0
answers
206
views
Independence and truth in PA
By $\textbf{PA}$ I will mean the usual first-order Peano Arithmetic. I will denote an element of $\mathbb{N}$ by $n$, and by $[n]$ I will denote the corresponding term in the language of $\textbf{PA}$:...
- 3,065
6
votes
0
answers
407
views
Can Set Theory be turned into Infinite Arithmetic?
The following system I'd label as "Infinite Arithmetic" is simply an endeavor to extend second order arithmetic to the infinite ordinal world, and extending with it the representation of ...
- 11.3k
15
votes
5
answers
3k
views
How is it possible for PA+¬Con(PA) to be consistent?
I'm having some trouble understanding how a certain first-order theory isn't just straight-up inconsistent.
Let $PA$ be the axioms of (first-order) Peano arithmetic and let $C$ be the following ...
- 12.9k
8
votes
2
answers
560
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 ...
- 47.8k
1
vote
0
answers
129
views
Is set theory interpretable in infinite primitive recursive arithmetic?
In A Formalization of the Theory of Ordinal Numbers, Takeuti interprets $\sf ZFC$ in a first order theory extending first order arithmetic to the infinite ordinal realm, while at the same time ...
- 20.7k
2
votes
1
answer
329
views
Can set theory be interpreted in infinite arithmetic?
Is the following system of infinite arithmetic consistent?
If so, can it interpret $\sf ZFC$?
Language: first order logic
Primitives: $\operatorname{Card}, <, + , \times,\text{^}$
where $\...
- 237k
10
votes
2
answers
436
views
The additive structure of clusters of nonstandard models of arithmetic
Given $\frak M$ a countable nonstandard model of $\sf PA$ and let $a\in M$ be a nonstandard element. A "cluster around $a$" is the set of successors and predecessors of $a$, a cluster is a ...
- 237k
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. ...
- 387
0
votes
0
answers
73
views
Least number principle for IOpen fragment of Peano Arithmetic
Is it possible to prove the least number principle in IOpen fragment of Peano Arithmetic, i.e. having induction only for Open formulas?
- 19
-3
votes
1
answer
638
views
Analysis I, simpler proof of Tao's construction of the integers [closed]
In chapter 4 of Analysis I by Terence Tao, we have the following note about the set theoretic construction of the integers:
In the language of set theory, what we are doing here is starting with the ...
- 237k
6
votes
0
answers
192
views
How to show that $\omega^\omega$ is well-founded in PA?
By induction on $n$ variables I can show that for any meta-natural number $n$, PA proves well-foundedness of $\omega^n$. However it is well known that PA proves well-foundedness of $\omega^\omega$ ...
- 101
7
votes
0
answers
110
views
How tightly are decidability and "induction-completeness" linked?
It is known that there are a number of expansions of the structure $\mathfrak{N}:=(\mathbb{N};+)$ which are decidable (= have computable theories); one such example is the expansion by a predicate ...
- 20.7k
2
votes
0
answers
75
views
Can all the strongly provable theorems of $\sf PA+\neg Con(PA)$ be captured in an effective manner through alternative kind of provability?
If we extend $\sf PA$ with the following axiom asserting its own inconsistency:
Inconsistency: $\exists x: \operatorname {Proof}_{\sf PA} (x, \ulcorner 0=1 \urcorner)$
For short denote this axiom by $\...
- 11.3k
2
votes
2
answers
294
views
Can we use remote provability to prove the first incompleteness theorem sans $\omega$-consistency?
Let $\mathcal g_1$ denote the usual Godel sentence defined as: $$ \mathcal g_1 \iff \neg\exists x:\operatorname {Proof}_T(x, \ulcorner \mathcal g_1 \urcorner)$$
Lets suppose that $\sf T$ is ...
- 11.3k
12
votes
1
answer
482
views
Is there a useful measure of density of decidable sentences in PA?
Essential undecidability of PA says every complete extension of PA includes a non r.e. set of new "axioms," all undecidable in PA. In that sense lots of sentences of PA are undecidable in ...
- 11.2k
2
votes
1
answer
194
views
Do these two provability theories over PA differ in consistency strength?
This posting is related to the answer to this question.
Lets extend the language of $\sf PA$ with a monadic symbol "$\vdash$", add to the formula formation rules, the rule:
if $(\phi)$ is a ...
- 237k
1
vote
2
answers
231
views
Does strong provability imply syntactical provability?
This posting is related to the answer to this question.
Lets extend the language of $\sf PA$ with a monadic symbol "$\vdash$", add to the formula formation rules, the rule:
if $(\phi)$ is a ...
- 11.3k
11
votes
2
answers
379
views
Can singular long models require less than PA?
Say that a long model is an $\mathfrak{A}\models\mathsf{I\Sigma_1}$ such that $\mathfrak{A}$ has strictly greater cardinality than each of its proper initial segments (in the case $\vert\mathfrak{A}\...
- 20.7k
9
votes
0
answers
210
views
Is there an Arithmetized Completeness theorem for intuitionistic theories?
For classical theories, Henkin's completeness proof can be arithmetized. This leads to the result that for classical theories $T$ and $S$ if $\sigma$ is a formula enumerating $S$ in $T$ then $S \leq T ...
- 481
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 ...
- 35.5k
11
votes
2
answers
442
views
Are all generalized Scott sets realized as generalized standard systems?
Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so.
The standard system of a nonstandard ...
- 1,228
3
votes
0
answers
283
views
What is the meaning and proof of Harvey Friedman’s ultrafinite incompleteness sentence?
On page 7 of his paper “Adventures in Incompleteness”, Harvey Friedman states the following:
IN ANY LONG ENOUGH SEQUENCE $x_1,...,x_n$ FROM $\{1,2,3\}$, SOME $(x_i,...,x_{2i})$ IS A SUBSEQUENCE OF ...
- 4,597
5
votes
1
answer
485
views
Extensions of the Ackermann interpretation to nonstandard theories of arithmetic
In their paper, " On Interpretations of Arithmetic and Set Theory" (Notre Dame Journal of Formal Logic, Vol. 8, No. 4 (2007), pp. 497-510) in section 7, "Fragments of Arithmetic and Set ...
- 2,031
2
votes
0
answers
79
views
Which sets of natural numbers are "lambda-analytic"?
Begin with a bit of notation. Let $t = t_0, \ldots, t_d$ be a finite sequence of real numbers. Define
$$\lambda^t(x) = x^{t_0} \log(x)^{t_1} \log(\log(x))^{t_2} \cdots.$$
for all real numbers $x \in ...
- 13.3k
1
vote
0
answers
118
views
Which real functions benefit from the Fundamental Theorem of Interval Analysis?
I'm reading Introduction to Interval Analysis, by Moore, Baker & Cloud and complementing it with Global Optimization using Interval Analysis, by Hansen & Walster.
Theorem 5.1 - Fundamental ...
- 875
43
votes
1
answer
3k
views
Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?
By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...
- 2,031
8
votes
3
answers
1k
views
Dedekind-Peano axioms, but numbers have at most one successor
One can consider a variant of the Dedekind-Peano axioms
in which one replaces the assumption that every number
has exactly one successor by the assumption that every
number has at most one successor, ...
- 237k
5
votes
1
answer
148
views
Does visible nonstandardness imply visible ill-foundedness?
For $X\subseteq\mathfrak{M}\models \mathsf{TA}$, say that $X$ is $\mathfrak{M}$-disruptive iff there is some formula $\varphi$ in the language of arithmetic + a new unary predicate symbol $U$ such ...
- 47.8k
2
votes
0
answers
137
views
Can we extend the projectively extended real line with a single number that stands for division of zero by zero?
If we work within $\hat{\mathbb R} = \mathbb R \cup \{\infty\}$, i.e. one point compactification of the real line.
We extend $<$ relation on $\mathbb R$ to $\hat <$ defined as:
$ x \ \hat{<} \...
- 11.3k
-2
votes
1
answer
369
views
Is this extension of the projectively extended real line, consistent?
This posting has been Edited. The edited material shall be noted.
The projectively extended real line $\hat {\mathbb R}= \mathbb R \cup \{\infty\}$ is one system which allows division by zero! Yet it ...
- 11.3k
10
votes
2
answers
2k
views
The different Branches of Arithmetic
... "and then the
different branches of Arithmetic--
Ambition, Distraction, Uglification,
and Derision."
(Alice in Wonderland, chapter IX: the Mock Turtle's story)
As a child I wondered for ...
- 12.9k
6
votes
1
answer
232
views
Interpretation of $ZFC^-$ in 2nd order Peano arithmetic
Let $Z_2^-$ be the 2nd order Peano arithmetic without the schema of Countable Choice. It has been known, since 1960s at least, that $ZFC^-$ (without the power set) admits an interpretation in $Z_2$ ...
- 2,167
3
votes
1
answer
140
views
Can we always know if an algebraic rule over the reals is preserved over the extended reals or not?
Recall a prior posting titled Is there an effective way to generalize this approach of affinely extending the number line?, and especially the accepted answer given to it. So we are working in $\sf ...
- 11.3k
3
votes
0
answers
210
views
Self-referential Quinean proof of Löb's Theorem
Given its relevance for Open-source game theory, Dr. Andrew Critch asks the following about provability logic:
We conjecture that Löb’s Theorem can be proven without the use of the
modal fixed point $...
CommunityBot
- 1
1
vote
1
answer
213
views
Is there an effective way to generalize this approach of affinely extending the number line?
The general approach here is a follow up of the approach outlined in a prior posting on extending the projectively extended real line. In particular arithmetic operators break down to ternery ...
- 20.7k
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 ...
- 4,713
7
votes
1
answer
262
views
What is known about first order logic of $\mathbb{N}$ with + and a unary predicate?
In "Weak Second-Order Arithmetic and Finite Automata", Büchi claims that the first order theory of $\mathbb{N}$ with + and a predicate for recognizing powers of 2 ($Pw_2$) is expressively ...
CommunityBot
- 1
32
votes
2
answers
3k
views
Do we expect that sufficiently large computable ordinals settle every question of arithmetic?
I came across a post by Ron Maimon on physics.SE that makes what seems to me to be a very interesting conjecture I've never seen before about what it would take to settle every question of arithmetic. ...
- 7,545
10
votes
5
answers
2k
views
What is the canonical way to extend Peano's axioms to the set of all integers?
My first idea on how to do this would be:
$0\in\mathbf Z$
$\forall x\in\mathbf Z,Sx\in\mathbf Z\land Px\in\mathbf Z$
$P$ and $S$ are injective
$\forall x\in\mathbf Z,PSx=SPx=x$
some induction axiom ...
- 406
16
votes
1
answer
532
views
Are there signatures escaping from Tennenbaum's Theorem?
By Tennenbaum's Theorem all recursive models of $\mathsf{PA}$ are isomorphic to the standard model. And by a result of Wilmer this holds even for models of the theory $\mathsf{IE}_1\subseteq \mathsf{I}...
- 5,831
8
votes
1
answer
545
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$ ...
- 47.8k