39
votes
Accepted
What is an example of a non standard model of Peano Arithmetic?
Peano arithmetic is a first-order theory, and therefore if it has an infinite model---and it has---then it has models of every cardinality.
Not only that, because it has a model which is pointwise ...
- 388k
25
votes
Accepted
How does Gödel Completeness fail in second-order logic?
The property that "every consistent theory has a model" does not hold for second-order logic.
Consider, for example the second-order Peano axioms, which are well known to have only $\mathbb N$ as ...
16
votes
Accepted
"Natural" non-standard models of Peano.
Certainly the good money is on the (current) nonexistence of such an example. But that's boring. Here are a couple positive observations, although - in my opinion - each falls short of an actual ...
- 237k
13
votes
Accepted
How can addition be non-recursive?
Tennenbaum's theorem doesn't claim that your TM doesn't work inside the model (if its operation is suitably arithmetized in well-known ways).
It says that there cannot exists a TM that works outside ...
12
votes
How does Gödel Completeness fail in second-order logic?
First of all, even in the first-order case that "proof" doesn't work: how do you get $M$? You need the assumption that, if $K'$ is consistent, then it has a model; but this is exactly what you are ...
- 237k
11
votes
How does Gödel Completeness fail in second-order logic?
Take the language of arithmetic, augmented by a single constant symbol $c$. Now add to the Peano [second-order] axioms the following schema, $0<c$, $s(0)<c$ and so on.
If this theory is ...
- 388k
11
votes
Explicit countable elementary extension of $\mathbb{N}$
Unfortunately, Tennenbaum's theorem (https://en.wikipedia.org/wiki/Tennenbaum%27s_theorem) shows that any such extension is non-computable. So there isn't really an explicit example.
That said, if ...
- 237k
10
votes
Accepted
How does induction fail in computable nonstandard models?
Here's an even simpler one: "Every number is either even or odd." That is, $$\forall x\exists y(x=y+y \mbox{ or } x=y+y+1).$$ The polynomial $x$ is a counterexample.
Ignoring the specific model and ...
- 237k
10
votes
Accepted
The satisfaction relation is undefinable, but does it still "exist"?
Option 2 is exactly what is going on. For each meta-language natural number $n$, we can write down a formula in the language of set theory that formalizes $\vDash_n$. However, we cannot define a ...
- 323k
8
votes
What is an example of a non standard model of Peano Arithmetic?
It should be mentioned that one of the most concrete nonstandard models of PA was developed by Skolem in the 1930s in ZF (without the axiom of choice, unlike the constructions mentioned in the other ...
- 38.2k
8
votes
Accepted
Non-standard model of arithmetic - why is adding new constants to the model acceptable?
There's nothing mysterious or underhand going on here. Though there is an important point in the background, which is simply this:
In a standard formal language (like the language of Peano ...
- 53.1k
8
votes
Why do models of ZF which are not $\omega$-models have non-standard formulas whose length is "infinitely large natural numbers"?
For every natural $n$, $\phi_n$ is a sentence, where $\phi_0$ is $\forall x\,(x=x)$ and $\phi_{n+1}$ is $(\phi_n\land\phi_n)$. By recursion, there is a sentence in the theory that codes this claim and ...
- 78.2k
8
votes
Which models of PA can be standard in some model of ZFC?
This is a surprisingly subtle question!
Right off the bat, we have an obvious observation: if $\mathcal{M}$ is a "potential $\omega$" (= is isomorphic to the $\omega$ of some model of $\...
- 237k
7
votes
What is an example of a non standard model of Peano Arithmetic?
This is a historical footnote to the nice accepted answer above. More precisely, the method in the yellow box in
seems to be already hinted at in Kurt Gödel's review in Zentralblatt, Band 7, Heft 5, ...
- 1,258
7
votes
Accepted
Are the algebraic numbers recursive?
Let me preface this by saying that I'm very surprised by your claim that Tennenbaum "almost certainly" applies to $MA$. Do you have any evidence for this? Also, what precisely does "nonstandard model" ...
- 237k
7
votes
Accepted
Are we in a nonstandard model of arithmetic?
Your question is not ill-posed and in fact admits a rather precise answer in the context of Joel David Hamkins' multiverse. The technical details of this may be beyond the level of this question but ...
- 38.2k
7
votes
Accepted
Is the standard model for the language of number theory elementarily equivalent to one with a nonstandard element?
In the notes, I don't see the claim that $c$ is larger than all other numbers of $\mathfrak{A}$. The number $c$ in $\mathfrak{A}$ is larger than $0$, $S(0)$, $S(S(0))$, etc., - so $c$ is greater than ...
- 80.6k
7
votes
Accepted
On an explicit model for $\mathbf Q$ with the negation of the axiom of induction
Great question!
In my opinion, the simplest nonstandard model of $Q$ consists of polynomials (in one variable). Specifically, let $\mathfrak{P}$ be the set consisting of all integer-coefficient ...
- 237k
7
votes
Accepted
Understanding non-standard arithmetic models.
$c^{\mathfrak{M}}$ is not a greatest element of $\mathfrak{M}$. For example, $S(c^{\mathfrak{M}})$ is larger than it.
- 72.3k
7
votes
How would you express, in ZFC, that the number of countable models of Th($\mathbb{N}$), up to isomorphism, is at most $2^{\aleph_0}$?
Here is one way to express this in the language of set theory: There is a set $X$ of cardinality $2^{\aleph_0}$ such that for every $\mathfrak{A}$, if $\mathfrak{A}$ is a countable model of $\mathrm{...
- 72.3k
7
votes
"Natural" non-standard models of Peano.
This answer is a remark on "all methods I've seen of constructing non-standard models never in any sense uniquely specify any non-standard model". It shows that you can uniquely specify a ...
- 9,185
6
votes
Accepted
Is there a consistent arithmetically definable extension of PA that proves its own consistency?
Here is the answer I had made over on MathOverflow:
Surprisingly, the answer is yes! Well, let me say that the answer
is yes for what I find to be a reasonable way to understand what
you've asked.
...
- 43.5k
6
votes
Accepted
Nonstandard Model of PA where the carrier set is N and Tennenbaum
If you're just asking why PA has nonstandard models with carrier set $\mathbb{N}$, this is an immediate consequence of the Lowenheim-Skolem theorem: if $\mathcal{M}\models PA$ is nonstandard, let $c\...
- 237k
6
votes
Accepted
Are there Countable $\omega$- models of ZFC?
Well, by the LS theorem, we know that if there is any model of ZFC then there is a countable model. In fact, it says there is a countable elementary submodel of the original model. By the same token, ...
- 55.5k
6
votes
Accepted
Are there countable non-standard models of true arithmetic formulated in the uncountable "full (first-order) language of arithmetic"?
No, there are not. For instance, there exists a sequence of $\omega_1$ functions $f_\alpha:\mathbb{N}\to\mathbb{N}$ (for $\alpha<\omega_1$) such that if $\alpha<\beta$ then $f_\alpha(n)<f_\...
- 323k
6
votes
Accepted
(Request for) simple constructive proof of existence of nonstandard model of PA
Ultrapowers are certainly important and worth understanding, but in my opinion - especially if we're looking at nonstandard models of arithmetic in particular - they are not optimally constructive.
...
- 237k
6
votes
Why isn't there a contradiction between compactness and the Archimedean property when we create non-standard models of real numbers?
Not only that the Archimedean property is not a first-order property, if we add $\Bbb N$ as a predicate to the language, making it a first-order property (by saying $\forall x\exists n(x<n\land n\...
- 388k
5
votes
Is the axiom of induction constructively verifiable for a non-standard model of arithmetic?
Well, "constructively verifable" means different things in different contexts. But I am going to take it here as "true without the axiom of choice".
So first of all, the compactness theorem holds for ...
- 388k
5
votes
Can additional predicates "eliminate" nonstandard models of true arithmetic?
Here's an improvement on (1), with just a single predicate $S,$ but as @ElliotGlazer pointed out, it's not a solution to (2), since there isn't a single sentence $\varphi$ that eliminates some ...
- 9,338
5
votes
Accepted
What do non-standard cardinalities look like?
Option 2 is correct: $M$ doesn't see the bijection that exists externally (= in $V$).
Specifically, let's take $P$ to be $M$'s actual version of $\mathbb{N}$ (I think this is what you had in mind ...
- 237k
Only top scored, non community-wiki answers of a minimum length are eligible