All Questions
Tagged with theories-of-arithmetic model-theory
73 questions
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
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
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
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. ...
- 236k
18
votes
1
answer
3k
views
Existence of a model of ZFC in which the natural numbers are really the natural numbers
I know that, from compactness theorem, one can prove that there are models of first order arithmetic in which there is some "number" which is not a successor of zero, in the sense that it is strictly ...
- 1,514
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
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 ...
- 236k
16
votes
1
answer
831
views
Can there be computable non-standard models of PA in a weaker sense?
By Tennenbaum's theorem, in the usual sense of computability for models,
neither addition nor multiplication can be computable in a countable non-standard model of PA.
Weak version:
Can addition or ...
user5810
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 ...
- 167
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
13
votes
2
answers
1k
views
nonstandard models and mathematical theorems
Is there a first order statement about the natural numbers (not nonstandard analysis) such that the truth of the statement is easier to see in a nonstandard model? In other words, do nonstandard ...
12
votes
2
answers
1k
views
Trouble with models of PA and ZFC
I have a big trouble in my mind, here is my false reasoning:
The Goodstein's theorem is undecidable in (first order) Peano Arithmetic.
There exist a non standard model N of PA where the Goodstein's ...
- 129
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
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
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
11
votes
2
answers
441
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
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
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
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
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
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
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
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
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
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
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
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
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
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
8
votes
0
answers
198
views
Kripke models of $HA$
Let $K$ be a kripke model and $k$ be one of its node, then $\mathcal{M}_k$ is classical structure of $k$.
What is the strongest theory of arithmetic like $T$ such that for
every kripke model $K\...
- 1,689
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
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,441
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
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 $\...
- 236k
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
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
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
6
votes
1
answer
382
views
Formal systems needed to formalize relative independence results
We know that Con(ZF) implies Con(ZFC+GCH), Con(ZF+neg(AC)) and Con(ZFC+neg(CH)). But what are some weak theories in which these relative independence results are provable? In particular, are they ...
- 4,985
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
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
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
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 ...
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
5
votes
3
answers
1k
views
Are there first-order statements that second order PA proves that first order PA does not?
Are there first-order statements that second order PA proves that first order PA does not? Is this known one way or the other? Could you share an example? (edit: to clarify, by 'second order PA' I don'...
- 117
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
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
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
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
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
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