Questions tagged [nonstandard-models]

For questions specifically concerning models of arithmetic (which could be Peano Arithmetic, the first-order theory of the natural numbers, or some other system) which differs from the standard model by the existence of nonstandard numbers.

Filter by
Sorted by
Tagged with
21
votes
4answers
3k views

How does Gödel Completeness fail in second-order logic?

So a while ago I saw a proof of the Completeness Theorem, and the hard part of it (all logically valid formulae have a proof) went thusly: Take a theory $K$ as your base theory. Suppose $\varphi$ ...
17
votes
3answers
4k views

What is an example of a non standard model of Peano Arithmetic?

According to here, there is the "standard" model of Peano Arithmetic. This is defined as $0,1,2,...$ in the usual sense. What would be an example of a nonstandard model of Peano Arithmetic? What would ...
17
votes
2answers
579 views

What lessons have mathematicians drawn from the existence of non-standard models?

So, as someone whose knowledge of mathematics has always come from studying it with an eye towards philosophical/foundational issues and studying it with other philosophers (who are not primarily ...
15
votes
1answer
404 views

Tennenbaum's theorem without overspill

While trying to clean up Wikipedia's proof sketch for Tennenbaum's theorem (there is no computable non-standard model of Peano Arithmetic), the following strategy occurred to me. Since it seems to be ...
15
votes
1answer
170 views

Exponentiation and a weak fragment of arithmetic

The title is slightly misleading, since the theory I'm looking at is an extension of PA; however, the question is "morally" about very weak arithmetic. Specifically, consider the following theory PA':...
12
votes
1answer
338 views

Gödel's way of teaching non-standard models to Takeuti.

In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way: It went as follows. Let T be a theory with a nonstandard model. By ...
9
votes
3answers
623 views

How does induction fail in computable nonstandard models?

Tennenbaum's theorem does not apply to Robinson Arithmetic ($Q$). There is a computable, nonstandard model of $Q$ "consisting of integer-coefficient polynomials with positive leading coefficient, plus ...
9
votes
2answers
177 views

Relationship between nonstandard analysis and nonstandard models of arithmetic

So I've been reading through some introductory texts on nonstandard analysis, basically through the ultrafilter construction of hyperreals and the transfer principle. It seems that much of the time, ...
8
votes
1answer
210 views

Is the standard model for the language of number theory elementarily equivalent to one with a nonstandard element?

On page 89 in A Friendly Introduction to Mathematical Logic, the author writes that the standard model $\mathfrak{N}$ for $\mathcal{L}_{NT}$ is elementarily equivalent to a model $\mathfrak{A}$ that ...
7
votes
3answers
495 views

Primes in nonstandard models of PA

What is known about prime numbers in nonstandard models of PA? Restricted to true natural numbers the sets are identical, but does there always exist nonstandard primes? Can we explicitly define one ...
7
votes
4answers
363 views

Why aren't there any first-order sentences which have the property of being true in all non-standard models of PA and false in the standard one?

I'd like to know where the following result comes from (that is, whether there is a more general result from which it follows or else how it can be proven): There is no first-order sentence which is ...
7
votes
2answers
100 views

Why do models of ZF which are not $\omega$-models have non-standard formulas whose length is “infinitely large natural numbers”?

In his popular book Set Theory: An Introduction to Independence Proofs, Kunen gives the following definitions on the bottom of page 145: Let $\mathcal{A} = \lbrace A, E \rbrace$ be a structure for ...
7
votes
2answers
229 views

Can additional predicates “eliminate” nonstandard models of true arithmetic?

For languages $\mathcal{L} \subseteq \mathcal{L}',$ say that a set of sentences $\Delta$ in $\mathcal{L}'$ eliminates a model $M$ of $\mathcal{L}$ if no matter how the symbols of $\mathcal{L}' \...
7
votes
3answers
212 views

How can induction work on non-standard natural numbers?

When we consider the Peano axioms minus the induction scheme, we can have strange, but still quite understandable models in which there are "parallel strands" of numbers, as I imagine in the ...
6
votes
2answers
242 views

Explicit countable elementary extension of $\mathbb{N}$

I would like to see an explicit example of a non-trivial elementary extension of the structure $(\mathbb{N}, +, \cdot, 0, 1)$ where $\mathbb{N}$ includes zero. Most of all I am interested in countable ...
6
votes
2answers
607 views

nonstandard topology?

It is possible to have nonstandard models of PA where the natural numbers are different. The definition of a topology requires a notion of finiteness. What happens if we use a nonstandard model of ...
6
votes
4answers
234 views

Showing that the hyperintegers are uncountable

In class, we constructed the hyperintegers as follows: Let $N$ be a normal model of the natural number with domain $\mathbb{N}$ in the language $\{0, 1, +, \cdot, <, =\} $. Also let $F$ be a fixed ...
6
votes
3answers
673 views

Prime numbers on a non-standard model

I can't imagine how this is possible: Let $\mathcal{M}$ be a nonstandard model of arithmetic. Show that: There is an element $a\in M$ such that for all prime numbers $p$, we have that $\mathcal{M} \...
6
votes
2answers
348 views

Is the axiom of induction constructively verifiable for a non-standard model of arithmetic?

There exist models of the natural numbers which include infinite numbers. Such models are called non-standard models of arithmetic. Just like the standard model $\mathbb{N}$, the non-standard models ...
5
votes
1answer
211 views

The satisfaction relation is undefinable, but does it still “exist”?

In Jech's book "Set Theory" chapter 13, he shows how the satisfaction relation $\models_{n}$ for $\Sigma_n$ formulas can be formalized in ZF. As he pointed out previously, the full satisfaction ...
5
votes
1answer
65 views

On an explicit model for $\mathbf Q$ with the negation of the axiom of induction

I've been thinking for a while about non standard models of Robinson Arithmetic (here on out referred to as $\mathbf Q$), specifically ones in which induction ($\mathbf{AI}$) fails. This could happen ...
5
votes
1answer
246 views

The order-theoretic structure of the ordinal numbers in non-standard models

I have read the following. Proposition. Let $T$ denote the first-order theory of $\mathbb{N}$ in the language of arithmetic. Then any countable non-standard model of $T$ is order isomorphic to a ...
5
votes
1answer
509 views

How do we know that certain concrete nonstandard models of the natural numbers satisfy the Peano axioms?

It is easy to come up with objects that do not satisfy the Peano axioms. For example, let $\Bbb{S} = \Bbb N \cup \{Z\}$, and $SZ = S0$. Then this clearly violates the axiom that says that $Sa=Sb\to ...
5
votes
1answer
399 views

Is there a consistent arithmetically definable extension of PA that proves its own consistency?

Gödel's second incompleteness applies, for instance, to r.e. extensions of PA. I am wondering if it applies more generally to arithmetically definable extensions of PA. I see that there is a complete ...
5
votes
1answer
120 views

Nonstandard models of PA with a decidable order relation.

There this exercise in Models of Peano Arithmetic (Kaye 1991, p.157), which asks to define a recursive binary relation on $\mathbb{N}^2$, such that $M \upharpoonright < $ is isomorphic to $(\mathbb{...
5
votes
0answers
102 views

Can all $\mathsf{Q}$-provably recursive functions be “frequently termlike”?

Now asked at MO. Motivated by this question, I'd like to ask whether in a precise sense there are no "interesting" functions which are provably recursive in Robinson's arithmetic $\mathsf{Q}...
5
votes
0answers
110 views

Information about $ZFC + (\neg CH)$

$\underline{\text{Some Background}}$: A classic axiomatic system of set theory in modernity is $ZFC$. Results from modern mathematical logic guarantee the existence of statements undecidable given ...
4
votes
1answer
58 views

Understanding non-standard arithmetic models.

I am reading Enderton's Logic Book and I can't understand the proof that there is a non-standard arithmetic model. The proof is typical using the compactness theorem: First we expand $\mathcal{L}$ ...
4
votes
1answer
78 views

Are there countable non-standard models of true arithmetic formulated in the uncountable “full (first-order) language of arithmetic”?

Fix the standard language of arithmetic as, for example, $L_A ≔ ⟨0,1,+,×,<⟩$. Define the full (first-order) language of arithmetic, notation $L_\text{full}$, as the first-order language with the ...
4
votes
2answers
334 views

Are we in a nonstandard model of arithmetic?

My question is: is $\mathbb{N}$ a nonstandard model of arithmetic for someone else? Let $\mathbb{N}^*$ be a nonstandard model of Peano Arithmetic. Then that consists of a copy of $\mathbb{N}$ ...
4
votes
1answer
158 views

What do non-standard cardinalities look like?

The Von Neumann universe $V$ satisfies ZFC, and there are other models within $V$ that are non-standard and satisfy ZFC. If we look at one of these non-standard models $M$ with a non-standard model of ...
4
votes
1answer
322 views

Model of concatenation theory with left-cancellation but no right-cancellation

The theory of concatenation (TC) can be equivalently expressed as the following assumptions: Closure of strings under concatenation $+$. Existence of an empty string $e$, namely $e+x = x = x+e$ for ...
4
votes
2answers
256 views

Non-standard integers?

Edit: Realized almost immediately that this was a stupid question - see comment below. Was about to delete it when an answer appeared that seems like saving... Context: I just saw a presentation of ...
4
votes
1answer
137 views

Infinite set of standard primes as the set of standard prime divisors of a nonstandard number

Suppose $(N, +, \cdot, 0, 1, <, =)$ is a proper elementary substructure of $(N^*, +^*, \cdot^*, 0^*, 1^*, =^*, <^*)$. Show that there exists some (infinite) $b$, where $b ∈ N^*$, such that for ...
4
votes
2answers
86 views

Can proper elementarily equivalent end extensions ever be definable?

Suppose $M\models PA$. Can there be a tuple of formulas $\Psi$ (possibly with parameters from $M$) such that: $\Psi^M\equiv M$ (or more precisely, $\Psi$ is an interpretation of an $\{0,1,+,\cdot,<...
4
votes
1answer
63 views

Bound for Non-standard Model of PA

For some non-standard model $M \models PA$, I recently proved that there is some $a \in M$ such that for all quantifier-free formulas $\varphi(x)$, if $M \models (\exists \, x) \varphi(x)$, then $M \...
4
votes
0answers
84 views

Is there a least standard model of Peano Arithmetics?

Here's the informal part: I'm trying to get a better intuition about the differences between the standard model and the non-standard ones. Some people seem to be really good at imagining what non-...
4
votes
0answers
39 views

Automorphism group of poset of models of Peano Arithmetic.

Suppose we put a poset structure on the set of countable models of Peano Arithmetic as follows: for models 𝑃 and 𝑄, let 𝑃≤𝑄 if 𝑃 is isomorphic to a submodel of 𝑄. As described, this is just a ...
4
votes
1answer
119 views

Where is the (original) proof of Klaus Potthoff's Theorem about the order type of arithmetic models?

I am looking for a complete proof, respectively for the complete original proof of the following theorem, which is attributed to Klaus Potthoff: If $\mathfrak{M}$ is a nonstandard model of PA, then ...
3
votes
3answers
148 views

Can a countable model of arithmetic have mutually non-definable numbers?

Let $M$ be a countable model of arithmetic (that satisfies PA). Can we have two numbers $c_1, c_2 \in M$ such that $c_1$ can not be defined in terms of $c_2$, and $c_2$ can not be defined in terms of $...
3
votes
2answers
352 views

Non-standard model of arithmetic - why is adding new constants to the model acceptable?

I have a question about the following proof of existence of a model of non-standard arithmetic (taken from wikipedia): The existence of non-standard models of arithmetic can be demonstrated by an ...
3
votes
2answers
363 views

First order axiomatization of $\mathbb{R}$

Recently I've been trying to come to terms with the seemingly contradictory facts that (1) $\mathbb{R}$ is the only Dedekind complete ordered field up to isomorphism, and (2) $^*\mathbb{R}$, the ...
3
votes
1answer
119 views

Are there Countable $\omega$- models of ZFC?

By the $\text{L-S}_\downarrow$ theorem we know that there must exist a countable model of ZFC. Suppose that there is an $\omega$ model of ZFC, then would $\text{ L-S}_\downarrow$ theorem entail that ...
3
votes
2answers
227 views

embdedding standard models of PA into nonstandard models

Maybe it's well known to experts, but is there always an embedding $f$ of the standard model of Peano arithmetic into a nonstandard model? By Peano arithmetic I mean its first-order version, with the ...
3
votes
1answer
89 views

Do the properties of the hyperreal numbers change depending on the ultrafilter used?

One of the more common constructions of the hyperreals is $\mathbb{R}^{*} := \mathbb{R}^{\omega}/\mathcal{U}$ where $\mathcal{U}$ is some ultrafilter containing the filter of sequences in $\mathbb{R}^{...
3
votes
1answer
124 views

Any non-standard halting oracles stronger than $\mathbb N$?

Let $M$ be some model of PA. Let $H_M$ be the set of codes of standard turing machines $X$ such that $M \models X \text{ halts}$. For example, $H_\mathbb N$ corresponds to the regular halting oracle (...
3
votes
2answers
177 views

Can the transfer principle apply to second-order logic if we transfer sets and relations to hyper-sets and hyper-relations?

The transfer principle doesn't apply to second-order logic. For example, if I take a standard statement. $$\text{A lower bounded set of Reals has a greatest lower bound}$$ Is false for the hyperreals:...
3
votes
1answer
37 views

No single axiom stating non-Archimedeanity [duplicate]

An ordered field $K$ with the ordering $<$ is Archimedean if for any $x \in K$ there exists $n \in \mathbb{N}$ (where $\mathbb{N}$ is the copy of the natural numbers in $K$) such that $|x|<n$. ...
3
votes
1answer
53 views

Is the union of non-standard analogs of a family of sets a proper subset of the non-standard analog of the union of those sets?

The book on formal logic I'm using for self-study builds the foundation for non-standard analysis (to illustrate the usage of non-standard models) using the following construction. Consider the real ...
3
votes
1answer
69 views

Is there an overview of possible order types of fragments of first-order arithmetic?

I know, that there aren't many results on order types of arithmetic fragments. E.g. there are some basic results which one can find in texts of Kaye and Bovykin. But does anyone know, if there is ...