All Questions
58 questions
12
votes
0
answers
249
views
+50
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
This question is very close to this old MSE question of mine, which is still unanswered.
Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language ...
- 20.7k
5
votes
1
answer
371
views
Are PA and Counting Theory synonymous\bi-interpretable?
The following question is whether $\sf PA$ is synonymous or even bi-interpretable with a theory about counting objects in finite sets.
Counting Theory:
$\textbf{Logic:}$ Bi-sorted first order logic ...
- 11.3k
1
vote
0
answers
90
views
About synonymy relationships around these two theories?
The following question is about patterns of synonymy relationships around two theories, $T^+$ and $\sf PA$.
For purposes of self inclusiveness I'll re-iterate $T$ and its extensions.
$\textbf{Logic:}$ ...
- 11.3k
4
votes
1
answer
515
views
Truth Values of Statements in non-standard models
Excuse me, if the question sounds too naive.
Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...
- 1
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+\...
- 345
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 ...
- 1,676
1
vote
1
answer
221
views
Seeking clarification of ultrapower nonstandard model of arithmetic
I've read that one nonstandard model of arithmetic is:
take $\mathbb{N}^\mathbb{N}$, the set of countably infinite sequences of natural numbers
take a quotent that gives the ultrapower: identify ...
- 1,288
4
votes
0
answers
162
views
Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?
(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.)
Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
- 2,912
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
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
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
16
votes
2
answers
1k
views
How special is first-order $\mathsf{PA}$?
This is a modified version of a question which was asked and bountied at MSE without success.
Below, "$\mathsf{PA}$" refers to first-order Peano arithmetic.
There are various "...
- 20.7k
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
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
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 ...
- 32.5k
11
votes
2
answers
1k
views
Why is there a need for ordinal analysis?
Consider the Peano axioms. There exists a model for them (namely, the natural numbers with a ordering relation $<$, binary function $+$, and constant term $0$). Therefore, by the model existence ...
- 139
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 ...
- 20.7k
10
votes
1
answer
630
views
Is $\mathsf{R}$ axiomatizable by finitely many schemes?
Recall that $\mathsf{R}$ is the theory of arithmetic consisting of the quantifier-free theory of $(\mathbb{N};+,\times,0,1,<)$ together with, for each $k\in\mathbb{N}$, the sentence $$\forall x[(\...
- 20.7k
10
votes
1
answer
807
views
Why can't we embed Tarski's truth in PA?
I recently learned that ZFC can prove $Con(PA)$ because it can give a model of PA, but I'm not given the technical details. (My teacher thinks it is too obvious to even mention.)
What plagues me is ...
- 171
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 ...
- 779
6
votes
2
answers
436
views
Interpreting proper elementarily equivalent end extensions?
Is there a tuple of parameter-free formulas $\Phi$ and a nonstandard $M\models PA$ such that $\Phi^M\models PA$, the induced $M$-definable initial segment embedding $j_\Phi^M:M\rightarrow\Phi^M$ is ...
- 20.7k
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 ...
- 1,441
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
8
votes
3
answers
427
views
Uncountable model of bounded arithmetic with an elementary end extension
Theorem 1.53 (3) in page 227 of Hajek and Pudlak's book, Metamathematics of First-Order Arithmetic, says:
Theorem. If $M$ is a countable model of $I\Delta_{0}$ such that $M$ has a proper elementary ...
- 1,403
22
votes
5
answers
1k
views
What is the spectrum of possible cofinality types for cuts in an ordered field? Or in a model of the hyperreals? Or in a nonstandard model of arithmetic?
I am interested to know the full range of possibilities for the cofinality type of cuts in an ordered field and in other structures, such as nonstandard models of arithmetic.
Definitions. ...
- 237k
5
votes
1
answer
271
views
Can a nonstandard model of $\mathsf{PA}$ be "$\Delta^1_1$-well-ordered?"
This was asked and bountied at MSE with no response:
My question is the following:
Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-...
- 20.7k
8
votes
1
answer
283
views
Paris-Harrington principles parametrized by functions $f:\mathbb N \to \mathbb N$
Recall that the Paris-Harrington Principle, $\mathsf{PH}$, is the statement that for each $e, r, k < \omega$ there is an $N < \omega$ so that given any coloring $c:[N]^e \to r$ there is an $H \...
- 1,882
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
2
votes
1
answer
275
views
Definability in countable nonstandard models of Peano arithmetic
I know that every element of $\mathbb{N}$ is definable the standard model of Peano Arithmetic. Does there exist a countable non-standard model of PA where the same is true?
2
votes
2
answers
281
views
Interpreting peano arithmetic without parameters
I will accept an answer in the form of references to the literature about my question as well as any other information. I am quite ignorant of the area and that will be clear from my question.
I ...
- 1,625
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 ...
8
votes
2
answers
428
views
Models of arithmetic in a signature with exponentiation but not addition and multiplication
Let $\mathcal{L}_{\mathrm{exp}}$ be the language with signature $(0, ^\prime, <, \mathrm{exp})$ (with $0$ interpreted as zero, $^\prime$ as successor, and $\mathrm{exp}(x)$ as $2^x$) and let $\...
- 1,155
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
16
votes
1
answer
1k
views
Is there a nonstandard model of arithmetic having precisely one inductive truth predicate?
$\newcommand\Tr{\text{Tr}}$My question is whether there can be a nonstandard model of PA having a unique inductive truth predicate.
Background. If $\mathcal{N}=\langle N,+,\cdot,0,1,<\rangle$ is ...
- 237k
7
votes
1
answer
572
views
Finding a PA cut in a nonstandard model of PA
For a certain project I am currently working on, I need to be able to find PA cuts in nonstandard models of PA, in desirable intervals. For example, I wonder if the following is true, where $\...
- 237k
7
votes
2
answers
237
views
On models of $Th_{\Pi_2}(PA)$
Let $M$ be a nonstandard model of $PA$.
Q1. Is there any way to get a submodel $N\subset M$ such that $N\models Th_{\Pi_2}(PA)$, but $N\not\models PA$?
Q2. Especially, what combinatorial principle ...
- 1,689
8
votes
1
answer
334
views
Analog of Tennenbaum's theorem for EFA
EFA can prove the exponential function to be total, but it cannot prove the superexponential function to be total. Is there an analog of Tennenbaum's theorem (which states the PA has no recursive non-...
- 2,464
4
votes
3
answers
360
views
End Extension models of $I\Delta_0$
Recently I'm thinking about question below, but I can not prove or disprove it.
Is it true that for every model $M\models I\Delta_0$ there exists a
model $M'\models PA$ such that $M'$ is end ...
- 1,689
6
votes
0
answers
113
views
When can two elementary end extensions of models of PA be uniquely amalgamated?
$\DeclareMathOperator{Cod}{Cod}$
$\DeclareMathOperator{Scl}{Scl}$
$\DeclareMathOperator{Def}{Def}$
$\DeclareMathOperator{Lt}{Lt}$
Background:
All of the background to this question can be found in ...
7
votes
1
answer
597
views
Can an uncountable model of Peano Arithmetic be recursive?
Can an uncountable model of Peano Arithmetic be recursive?
What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...
- 6,403
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
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
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,209
4
votes
1
answer
499
views
Does PA+Con(PA) entail the existence of non-standard models of PA?
Does $\textsf{PA}$+Con($\textsf{PA}$) entail the existence of non-standard models of $\textsf{PA}$?
Is there a reasonable way in which to code, inside $\textsf{PA}$, the statement that $\textsf{PA}$ ...
- 125
2
votes
3
answers
852
views
Can a Decidable Theory Have Non-recursive Models?
Tennenbaums' theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA.
...
- 687
3
votes
3
answers
314
views
Semantic reflection
Let $\ulcorner \cdot \urcorner$ be a fixed encoding of formulas by numbers, e.g.
let $\ulcorner \varphi \urcorner$ denote the Godel number of $\varphi$.
Let $T$ be a first-order arithmetic theory, e....
- 5,502
5
votes
2
answers
663
views
Overspill in models of arithmetic
Assume that $M$ is a non-standard model of complete arithmetic, i.e. of the theory $Th(\mathbb{N})$. Suppose that $R$ and $S$ are proper cuts of $M$. (With a cut, I mean a subset of the universe of $M$...
user49449
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
2
votes
2
answers
1k
views
Are there non-commutative models of arithmetic which have a prime number structure?
Peano Arithmetic (PA) models have a prime number structure and commutativity of addition and multiplication. Presburger arithmetic (PrA) models of arithmetic have addition without multiplication and ...
user10290