I like nonstandard arithmetic...

Here's a thread, a primer for the uninitiated.

0/

What is "nonstandard arithmetic"? What is meant by "nonstandard"?

The "nonstandard" refers to the use of non-standard models, literally, models that are not the usual ones standard. So for arithmetic, we mean nonstandard models of Peano Arithmetic (PA).

1/

The standard model of PA is the one we're all familiar with. It's the natural numbers (and I prefer to include 0 as a natural number, FYI, ... see the first post of this thread), with addition and multiplication.

But what's a nonstandard model of PA?

2/

A nonstandard model contains the natural numbers, since their unique existence is implied by the axioms of PA. But it also contains additional elements. We call the natural number analogues the "standard elements", and the others the "nonstandard elements".

3/

One thing we know is that nonstandard elements must be greater than all the standard elements. This follows from natural induction on the proposition

P(n) := *n < m

where *n is the standard element that corresponds to the number n, and m is any nonstandard element.

4/

So, nonstandard elements are a bit like "infinity", since they are greater than any natural number. But they aren't the kind of infinity that you write with a symbol like ∞. These numbers are a kind of "infinity" that requires a different sort of intuition.

5/

Case in point: Because the nonstandard model is still a model of PA, it must satisfy the axiom schema of induction that is part of PA. This schema says that for any predicate P(n) in the language of PA, if we can show P(0) and ∀n. P(n) => P(n+1) then we have ∀n. P(n).

6/

Induction makes sense for natural numbers, right? You start at P(0), and you apply the proof of ∀n. P(n) => P(n+1) enough times to get to the desired P(x).

So, how could it make sense when dealing with infinity? You can't apply a proof "infinitely many times"??

7/

Ha, but you can! It's a nonstandard model, so the axiom schema of induction must hold. ANY predicate in the language of PA will work by induction, in a nonstandard model.

Induction that goes all the way to infinity...

It's like, induction on steroids.

8/

Actually, there's a neat principle that lets us transfer our intuition from standard to nonstandard models.

It's called the Transfer Principle, and it says that any closed formula in the language of PA is true of natural numbers iff it is true in the nonstandard model.

9/

This has tons of implications. The first one, which I should have already mentioned, is that for every nonstandard number n, there is larger nonstandard number, n+1.

(It's like the old playground favorite, "infinity + 1".)

But that's not all ...

10/

You can add nonstandard numbers. You can multiply them. You can add/multiply them by standard numbers too. In each case (except multiplying by 0) you get nonstandard numbers.

These satisfy all the properties you expect from arithmetic: commutativity, distributivity, etc.

11/

If you take a nonstandard number n, it's not 0, so it must have a predecessor n-1. This n-1 must also be nonstandard. So you can count down: n, n-1, n-2, n-3, ... and never reach a standard number.

12/

Ok, cool.

What does a nonstandard model actually look like, though?

This is a bit more complicated. I will show you one "construction" of a non-standard model.

13/

I'm going to use the compactness theorem of first-order logic to "construct" a nonstandard model. The compactness theorem says that if you have a set of statements in first-order logic, such that any finite subset is satisfiable, then the whole set is satisfiable.

14/

So we take the set of statements to be all the axioms of PA, plus all statements of the form "c > n" where c is a new constant symbol, and n is any natural number (0, 1, 2, 3, ...) (which can be expressed as a term, one way or another). Call this set of statements PA'.

15/

Any finite subset of PA' is satisfied by the standard model while interpreting c as a sufficiently large number. Therefore, by compactness, all the statements are jointly satisfied by some model, call it M.

16/

In this model, the symbol c must be interpreted by some element that is greater than every natural number. Therefore it is a nonstandard element, and M is a nonstandard model.

17/

So, we have a nonstandard model, it exists in some sense. But sadly this "construction" is not constructive. We don't have a set of

Sadly, no constructive model of nonstandard arithmetic can exist, if we restrict ourselves to the standard interpretation of logic.

18/

Otherwise, we could use the nonstandard model to solve the halting problem: just construct a standard Turing machine and run it for a nonstandard number of steps ... which we can do by induction. Then we would know if it halted...

But that's impossible.

19/

I will continue / follow-up another day, because there's a lot more I wanted to talk about but it's getting very late:

- ultrafilters
- nonstandard analysis
- cheap nonstandard analysis
- how to *actually* make constructive nonstandard models
- what's it for?

20/20?