All Questions
Tagged with peano-arithmetic or theories-of-arithmetic
334 questions
2
votes
0
answers
192
views
Can PA be acyclically complete?
Any formula $\phi$ in the first order language of arithmetic is to be called acyclic if and only if we can associate with it an acyclic undirected graph whose nodes are the variable symbols occurring ...
- 11.3k
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 ...
- 11.3k
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
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.1k
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
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 ...
- 2,281
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
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 ...
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, ...
- 19.7k
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 ...
- 20.7k
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
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,281
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 $...
- 421
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 ...
- 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
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 ...
- 429
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. ...
- 118k
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 ...
user155516
34
votes
2
answers
2k
views
What is the logical status of the sentence combining the ideas of Löb and Rosser, "this sentence is provable before any proof of its negation"?
Logicians are familiar with the variety of self-referential sentences expressible in the language of arithmetic:
The Gödel sentence, "this sentence is not provable", which indeed is not ...
- 236k
1
vote
0
answers
117
views
Can this type theory interpret second order arithmetic?
Language: multi-sorted first order logic with equality and membership, where for each natural $t$ there is a set $x^t$ of sort $t$. Equality "$=$" only occurs between variables of the same ...
- 11.3k
6
votes
1
answer
278
views
A "negative" standard system
For $\mathcal{M}$ a (countable) nonstandard model of $\mathsf{PA}$, let $\mathsf{SS}(\mathcal{M})$ be the set of sets of natural numbers coded by elements of $\mathcal{M}$. There are various ways to ...
- 20.7k
32
votes
2
answers
3k
views
Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?
There are many interpretations of arithmetic in set theory. The
Zermelo interpretation, for example, begins with the empty set and applies the singleton operator as successor:
$$0=\{\ \}$$
$$1=\{0\}$$
...
- 236k
0
votes
0
answers
152
views
What is the strength of allowing multiple predecessor numbers?
If we have a theory of numbers, pairs of numbers, and sets of those, and axiomatize that the relation $<$ on numbers is both extensional and well founded, then this theory would prove all PA axioms ...
- 11.3k
0
votes
1
answer
150
views
Reflection schema
Peano Arithmetic consists of axioms $P_1, P_2, \ldots P_7$ plus first order classical logic. Let us call this theory $T$. This theory has its unprovable Gödel’s sentence $G$ such that
$$
G\...
- 1
11
votes
0
answers
476
views
Which sentences are "irreducibly" self-referential over $\mathsf{PA}$?
Previously asked at MSE. Below, all sentences/formulas are in the language of arithmetic, and for simplicity we conflate numbers with numerals and sentences with Godel numbers.
Say that a sentence $\...
- 20.7k
7
votes
1
answer
358
views
Proving short consistency: can we do better than brute force search?
This is a minor variation of a question originally asked on MSE by user779130 and bountied by me, without success. Throughout, "length" refers to the number of symbols, not lines, in a proof....
- 20.7k
11
votes
2
answers
967
views
How much induction does a p-adic valuation need?
Recently I learned a nice constructive proof of the irrationality of $\sqrt{2}$, which uses the 2-adic valuation of an integer: the count of how many times a number is divisible by 2. The valuation ...
- 35.5k
3
votes
0
answers
165
views
Why is the proof of decidability of arithmetic (Theorem 2.1) in Hamkins & Lewis (2000) enough?
Recently, I was reading the paper "Infinite Time Turing Machines" by Hamkins & Lewis. And one of the first theorems (Theorem 2.1) is about decidability of arithmetic.
The proof is quite ...
- 31
0
votes
1
answer
256
views
Is there a non-standard model of PA computable with infinitary computation?
By the Tennenbaum's theorem,
there are no non-standard countable models of
Peano Arithmetic that are computable using Turing machines. What about models of infinitary computation like infinite time ...
- 127
4
votes
0
answers
198
views
Is there a simple proof of consistency of EA?
Let $\mathsf{EA}+\mathsf{CE}$ be elementary arithmetic with cut elimination theorem. Is there a simple (1-)consistency proof of $\mathsf{EA}$ over $\mathsf{EA}+\mathsf{CE}$? I think that a naïve ...
- 178
4
votes
1
answer
439
views
Alternative proof of Tennenbaum's theorem
The standard proof of Tennenbaums's theorem uses the existence of recursively enumerable inseparable sets and is presented e.g. in Kaye [1, 2], Smith [3].
In the following, $\mathcal{M}$ will always ...
- 211
5
votes
1
answer
283
views
Which arithmetical sentences have no counterexamples in the sense of Kreisel?
It is a well-known fact that given a first-order sentence $\psi$ in prenex normal form $\forall x_1 \exists y_1 \forall x_2 \exists y_2 \dots \forall x_n \exists y_n \theta(x_1,\dots,x_n,y_1,\dots,y_n)...
- 13.2k
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
2
votes
1
answer
147
views
Representation of the equality relation between hereditarily finite sets in weak set theories
Consider General Set Theory ($ \mathsf { GST } $) axiomatized by the following.
Axiom of Extensionality: The sets $ x $ and $ y $ are the same set if they have the same members:
$$ \forall x \forall ...
- 346
4
votes
1
answer
377
views
Does ACA prove categoricity of the reals?
$\def\f#1{\text{#1}}$Does $\f{ACA}$ prove that any two internally complete ordered fields are isomorphic?
Here internal completeness is expressed roughly as "every sequence of reals with an upper ...
- 2,912
7
votes
0
answers
284
views
Generic behavior of "polynomialish" models of $\mathsf{Q}$
(This question was originally asked and bountied at MSE - with different notation, some more explicit arguments, and topology in place of forcing.)
Suppose $\mathcal{R}=(R_i)_{i\in\mathbb{N}}$ is a ...
- 20.7k
5
votes
0
answers
318
views
$\Sigma_n$-complete sets in the Levy hierarchy
Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes ...
- 1,882
4
votes
0
answers
105
views
Computably saturated Skolem hulls of Morley sequences in $\mathsf{PA}$
Recall that a model $M$ of a first-order theory $T$ (in a computable language $\mathcal{L}$) is computably saturated if for every finite tuple $\bar{a} \in M$ and every computable partial type $\Sigma(...
- 13.2k
0
votes
1
answer
270
views
What is the smallest countable limit ordinal in which 'lost melodies' occur
The question is in the title. This question is in response to the following paragraph found at the end of Prof. Hamkins' answer to my MathOverflow question, Are ITTM's necessary to compute Turing's &...
- 6,132
7
votes
1
answer
341
views
Can this weakish system of arithmetic express multiplication for second-sort numbers?
Consider a 2-sorted first-order logic with equality (for first-sort entities). The first sort consists of numbers, the second sort (which will be capitalized) of unary functions. There is one constant,...
- 1,974
7
votes
0
answers
102
views
How similar can a model of $I\Delta_0$ be to the intersection of all of its definable cuts?
Let $M$ be a model of $I\Delta_0$. Recall that a definable cut is a definable (possibly with parameters) subset $I$ of $M$ that is non-empty, downwards closed, and closed under successor.
If we ...
- 13.2k
3
votes
0
answers
160
views
Is anything known about $\Delta_n$ bounding?
For a class $\Gamma \in \{ \Sigma_n, \Pi_n, \Delta_n \}$ in the arithmetical hierarchy, we can consider the induction, bounding, and least number principles for $\Gamma$:
$\mathsf{I}\Gamma$ is $\big[ ...
- 798
2
votes
1
answer
198
views
Can $\mathsf{RCA}_0$ prove that every nonempty c.e. set $A \subseteq \mathbb{N}$ has a least element?
In other words, can $\mathsf{RCA}_0$ prove that for every function $f\colon \mathbb{N} \to \mathbb{N}$, there is $b \in \mathbb{N}$ such that
$$ \exists k \in \mathbb{N},\ f(k) = b\quad \land\quad \...
- 798
3
votes
0
answers
146
views
Does Robinson arithmetic interpret a Kripke model of the double negation translation of $\mathsf{I}\Delta_0 + \mathrm{Exp}$?
It is a well-known fact that while while Robinson arithmetic can interpret surprisingly strong theories, it cannot interpret $\mathsf{I}\Delta_0 + \mathrm{Exp}$, i.e., Peano arithmetic with induction ...
- 13.2k
6
votes
0
answers
428
views
Proof of Tennenbaum's Theorem by McCarty
Tennenbaum's Theorem in its usual form states that for any countable non-standard model $M$ of PA there is no way to code the elements of $M$ as natural numbers such that either the addition or ...
- 211
13
votes
1
answer
437
views
What is the proof-theoretic ordinal of bare $\mathsf{NFU}$?
On the Stanford Encyclopedia of Philosophy article on alternative axiomatic set theories, it is stated without reference that bare $\mathsf{NFU}$ (i.e., $\mathsf{NFU}$ without the axiom of infinity) ...
- 13.2k
3
votes
1
answer
148
views
Consistency and consistency strength of certain special cuts in $I\Delta_0$
Recall that $I\Delta_0$ is the theory in the language of arithmetic that consists of the axioms of $\mathsf{PA}$ with induction restricted to $\Delta_0$ formulas (i.e., formulas where all quantifiers ...
- 13.2k