Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Noah Schweber's user avatar
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 ...
Zuhair Al-Johar's user avatar
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:}$ ...
Zuhair Al-Johar's user avatar
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 ...
Amiren's user avatar
  • 1
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-...
user21820's user avatar
  • 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 ...
Dave Pritchard's user avatar
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+\...
Tom Bouley's user avatar
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 ...
E8 Heterotic's user avatar
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 ...
Holo's user avatar
  • 1,676
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 ...
Noah Schweber's user avatar
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}\...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
TomKern's user avatar
  • 429
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 ...
Noah Schweber's user avatar
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 ...
Jozef Mikušinec's user avatar
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 ...
Léreau's user avatar
  • 211
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 ...
Noah Schweber's user avatar
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 ...
Corey Bacal Switzer's user avatar
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(...
James E Hanson's user avatar
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 ...
Léreau's user avatar
  • 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 "...
Noah Schweber's user avatar
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-...
Noah Schweber's user avatar
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 \...
Corey Bacal Switzer's user avatar
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[(\...
Noah Schweber's user avatar
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'...
pathway's user avatar
  • 117
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 ...
Paul Sohn's user avatar
  • 171
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?
Marcus Dubious's user avatar
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 ...
Noah Schweber's user avatar
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, ...
Pace Nielsen's user avatar
  • 18.7k
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 ...
Athar Abdul-Quader's user avatar
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 ...
display llvll's user avatar
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 $\...
Beau Madison Mount's user avatar
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 ...
Christopher King's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Erfan Khaniki's user avatar
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-...
Thomas Klimpel's user avatar
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$. ...
Corey Bacal Switzer's user avatar
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 $\...
Joel David Hamkins's user avatar
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 ...
PostAsAGuest's user avatar
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 ...
Ruizhi Yang's user avatar
4 votes
0 answers
219 views

Construction of model of arithmetic from an arbitrary model

Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that: $M'\models PA^-$ (or $...
Erfan Khaniki's user avatar
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 ...
Matt Brin's user avatar
  • 1,625
43 votes
1 answer
2k 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 ...
Gro-Tsen's user avatar
  • 32.5k
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\...
Erfan Khaniki's user avatar
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 ...
Erfan Khaniki's user avatar
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 ...
user3730940's user avatar
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....
Kaveh's user avatar
  • 5,502
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 ...
user avatar
4 votes
0 answers
126 views

Lascar strong types in fragments of arithmetic

Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.) Definition Given a saturated model ${\cal M}$ ...
Domenico Zambella's user avatar
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}$ ...
stan's user avatar
  • 125