All Questions
Tagged with theories-of-arithmetic model-theory
73 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
91
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 ...
- 2,167
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
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
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 ...
- 237k
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 ...
- 237k
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
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
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
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
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
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
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
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
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
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 ...
- 2,031
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
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 ...
- 546
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?
- 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[(\...
- 5,831
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 ...
- 20.7k
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
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 ...
- 48.8k
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 ...
- 63.9k
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
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
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 "...
- 17.7k
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-...
- 13.2k
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 \...
- 63.9k
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. ...
- 63.9k
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 $\...
- 63.9k
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 $\...
- 63.9k
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 ...
- 63.9k
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 ...
- 63.9k
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'...
- 82.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 ...
- 73.2k
3
votes
0
answers
301
views
What does second order set theory give us that is new?
There is a natural analogy between the theories PA and ZFC. See the linked question by Gro-Tsen here.
Peano arithmetic (PA) is a first order approximation to the natural numbers. As is well known, ...
- 18.7k
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 ...
- 28.2k
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 ...
- 4,727
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 ...
CommunityBot
- 1
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
3
votes
1
answer
120
views
If one adds an inductive subset to a model of $ACA_0$, do we always get a new model of $ACA_0$?
Suppose $(M, \mathcal X) \models ACA_0$. Recall that a subset $A \subseteq M$ is $inductive$ over $M$ if $M$ satisfies all instances of induction in the expanded language with a predicate for $A$. ...
- 17.7k
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 ...
- 4,713
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 ...
- 47.8k