How to make your own nonstandard model
Mark
The topic's come up a few times, so I thought it might be helpful to show
how you would go about making a non-standard extension of, say, the integers.
The basis of the construction is the ultrafilter. The concept is a little
arcane, though you easily get used to it, so I'll use something slightly
different, more revealing, but rquivalent.
(0) Infinite Binary Sequences (& Ultrafilters)
Consider the set of infinite binary numbers (you can't escape infinity in
this construction). Each number is an infinite sequence of bits (a0, a1, ...)
where a0, a1, ... are 0 or 1. On these bit sequences you can define the
boolean operations & (and), | (or) and ~ (not) bit-wise:
(a0, a1, ...) & (b0, b1, ...) = (a0 & b0, a1 & b1, ...)
(a0, a1, ...) | (b0, b1, ...) = (a0 | b0, a1 | b1, ...)
~(a0, a1, ...) = (~a0, ~a1, ...)
where the bit-wise operations are defined by:
0&0 = 0&1 = 1&0 = 0, 1&1 = 1
1|1 = 1|0 = 0|1 = 1, 0|0 = 0
~0 = 1, ~1 = 0
In this context, an ultrafilter can be defined as a binary valuation, v, of
the sequences defined such that:
v(a) = 0 or 1 for all infinite binary sequences a
v(a) = 1 if a consists of only a finite number of 0's.
and
v(~a) = ~v(a), v(a&b) = v(a)&v(b), v(a|b) = v(a)|v(b).
If you know what ultrafilters are, it should be obvious how you recover the
usual definition from this. The key is you're assigning truth values to
infinite sequences in a consistent manner (so that the boolean algebra is
preserved).
Given two sequences a, b, define the relation a <= b to be true if and only
if every element of a is less than or equal to every element of b. Then one
can state the property: if a <= b then v(a) <= v(b).
Let 0* denote the sequence (0, 0, ...) and 1* the sequence (1, 1, ...).
The properties of v() above entail that v(0*) = 0 and v(1*) = 1.
Here's one of the chief ultrafilter-like properties of the construction:
[Filter Property]
if
v(a) = v(b) = ... = v(y) = 1,
and
a&b&...&y <= z
then
v(z) = 1.
Set A, and B be two sequences of consisting of arbitrary items. Consider the
sequence
q = (q(0), q(1), q(2), ...)
where
q(i) = 1 if A(i) = B(i)
= 0 else
Define the relation "almost equal" A <=> B, if v(q) = 1.
This is an equivalence. Reflexivity amounts to showing that v(*1) = 1.
Symmetry is obvious because the definition is symmetric. Transitivity is a
direct consequence of the Filter Property.
(1) Extending Formal Theories
(a) Formal Theories
A formal theory, T, is mapped to an extended formal theory, T*, using
this ultrafilter construction. In this theory you will have a set of
basic items such as:
(0) Predicates, each predicate, p, with an arity arity(p) >= 0.
(1) Functors, each one, f, likewise with an arity arity(f) >= 0.
(Constants are functors with arity 0).
(2) An unlimited supply of names for variables
Terms are built according to the syntax:
Term: Variable
Functor ( Term, ..., Term )
where the number of sub-terms (if any) is equal
to the functor's arity.
Statements are built according to the syntax:
Statement: Predicate( Term, ..., Term )
with the same matching rule regarding the arity.
Statement & Statement
Statement | Statement
~Statement
(\/ Variable) Statement
(I'm using "\/" to denote the universal quantifier "for all").
Truth values are assigned to variable-free statements when the formal theory
is given an interpretation. If (\/v) S(...v...) is a quantified statement,
then every "v" inside the statement S occurs under the quanfitier (\/v).
A variable-free statement (slight abuse of terminology) is one whose variables
all fall under quantifiers. A free variable is one that doesn't fall under
any quanfitier... thus a variable-free statement is a statement free of free
variables (I'm confusing you on purpose).
(b) Extended Terms
The non-standard extension maps terms to term sequences, and uses the
ultrafilter construction to squash out truth values from statements made out
of these sequences.
Make the following definitions:
v* = (v, v, ... )
where v is a variable, and
f*(t1...tn) = (f(t1(0)...tn(0)), f(t1(1)...tn(1)), f(t1(2)...tn(2)), ...)
where
t1 = (t1(0), t1(1), t1(2), ...)
...
tn = (tn(0), tn(1), tn(2), ...)
n = arity(f)
where f denotes either a functor, and f* the corresponding extended functor.
A similar deinition is made to create an extended predicate P* from a
predicate P.
Define extended Terms by the following:
Extended Term: v*, where v is a variable
Any sequence of constants (c0, c1, ...)
f* ( Extended Term, ..., Extended Term )
where the number of sub-terms (if any) is equal
to the functor f's arity.
This construction is redundant because all the terms that are "almost equal"
to each other (i.e. that stand in the relation <=>) are being counted as being
distinct.
They need to be squashed down first. This can be done because the relation <=>
is a congruence with respect to the set of functors f* and extended predicates,
P*. Namely, if
t1 <=> u1 ... tn <=> un then f*(t1...tn) <=> f*(u1...yn).
This is a direct consequence of the Filter Property. The same thing holds
true of predicates P*. So let's go back and redefine an extended term to
be not just a single sequence but the entire equivalence class of sequences,
and then redefine f* and P* accordingly. Okay, it's done (that was quick).
(c) Extended Statements
Extended statments are formed in precisely the same way that statements
were formed, except now we're using the extended predicates, P*. Under any
interpretation of the standard theory, the extended theory receives its own
interpretation.
Map each variable-free statement, S*, onto a truth value:
Given S*
let T(i) = 1 if S(i) is true
T(i) = 0 otherwise
Consider S* to be true if and only if v(T) = 1.
(2) Embedding Property
Let s be any statement in the formal theory, for example (\/x)~(x + 1 = 0)
You can embed this statement into the extended theory by converting all the
objects of the statement into extended objects:
(\/x)~(*x *+ *1 *= *0)
According to our construction, this is just the constant sequence:
( (\/x)~(x + 1 = 0), (\/x)~(x + 1 = 0), ...)
If the stateemnt is true, then the corresponding sequence, T, becomes 1*. If
it is false, the sequence becomes 0*. Thus, the extended statement is true if
and only if the original statement is true.
So every interpretation of the formal theory is embedded directly into the
extended theory.
Extended objects are built out of the sequence of constants. For example,
omega = (0, 1, 2, 3, ...)
Consider the statement *100 *< omega. This is the sequence:
(100 < 0, 100 < 1, ..., 100 < 100, 100 < 101, 100 < 102, ...)
This maps onto the sequence, T, that consists of 101 0's followed by an
infinite number of 1's. According to the defintion of the valuation, v(T) = 1.
Thus
*100 *< omega
is considered true. The number 100 could have been any natural number, so
omega must be an infinite number and *1 */ omega (in the extended theory of real
numbers) an infinitesimal.
Since the axioms of the formal theory, whatever they may be, are preserved
intact, and since the way we derived extended statements adds nothing new to
what we can do with statements (you don't see any new deduction rules
introduced for example), it must be true that the extended theory (1) makes
equivalent statements about the equivalent objects of the formal theory and
(2) is free of contradictions not already present in the original theory.
(3) Consistency
It's in this way that you can create a consistent account of the
infinitesimals, and even go as far as to create a Leibnitz-inspired account
of the Calculus, this time on a solid logical foundation. Abraham Robinson
was the first to do this in 1960.
The existence of ultrafilters, however, or the equivalent construct presented
above, is an open issue. It is implied by the Axiom of Choice, but is a
somewhat weaker statement than Choice so it fits somewhere in the balance
between what's typically regarded as constructive, and non-constructive.
(4) Commutativity of Embedding
Take any two formal theories, T1, and T2. Extend then by the construction
above to *T1 and *T2 using the SAME ultrafilter. Then the following is true:
any procedure that may have been used to embed T1 into T2
(say, number theory into set theory) will map *T1 into *T2
with exactly the same results.
(a) If c is any term of the formal theory T1, and f(c) the
mapping of the term in T2, then f(*c) = *f(c).
(b) If s is any statement in T1, and f(s) defined likewise,
then f(*s) = *f(s).
So * and f commute.
Thus, if you extend the formal theory of numbers to create infinite
numbers, like omega, and embed the numbers into a formal set theory, then the
very same infinite numbers will appear in the extended set theory. These
numbers will be there independent of whatever infinite cardinals and ordinals
will already be present, kind of like an infinity lying below the first
infinte ordinal. The extended set theory will regard them as finite, since
extended theories never see their terms as being unusual, but from God's
point of view (which we blasphemously claim to hold), they will be infinte.