Hi, charlie99-ga:
The general topic of your Question is often called "non-standard
models" of Peano Arithmetic. In particular we affirm that if PA is
consistent (ie. if it has one model, necessarily infinite), then it
must have a model of every infinite cardinality.
1. A model of a formal first order theory is a set-theoretic
interpretation of the function and predicate symbols of the language
such that all the axioms of the theory are satisfied. So, a model of
Peano's axioms of arithmetic would be a set M on which a constant
(0-ary function) is defined and a successor function s:M->M is defined
in a way that satisfies those axioms.
2. The existence of uncountable models of Peano Arithmetic follows
from the existence of a countable model by the "upward"
Lowenheim-Skolem Theorem. This result says that if a first-order
theory has one infinite model, then it has an infinite model of every
cardinality at least the size of the language of the theory. The
basic idea of the proof is to work with the complete theory of all
closed sentences satisfied in the infinite model, then adjoin an
infinite set of new constants to the language. A model is then
constructed from equivalence classes of closed terms (expressions)
that can be deduced as equivalent, and the model is shown to have the
required infinite cardinality.
[There is also a "downward" Lowenheim-Skolem Theorem, which says that
a first-order theory with an infinite model must have an infinite
model of cardinality equal to the size of its language plus
aleph-zero. This gives rise to Skolem's "paradox", which says that a
consistent set theory (with minimal symbols) in which "uncountable
sets" may be proven to exist, must yet have a countable model. The
resolution of this apparent conflict is that while any subset of the
model is denumerable (finite or countably infinite) from an external
perspective of the model, such an enumeration need not (and will not)
be constructably internal to the model.]
A very concise outline of the proofs of the Lowenheim-Skolem theorems
and the closely related Compactness Theorem is given here:
[Compactness and Lowenheim-Skolem Theorem, by Linton Wang]
http://www.utexas.edu/cola/depts/philosophy/faculty/asher/course/PHL358Fall2003/Handout%2010232003.pdf
A longer description of the results and techniques of proof is here:
[The Lowenheim-Skolem Theorems, by J.R.G. Williams]
http://weka.ucdavis.edu/~ahwiki/pub/Main/RobertWilliams/lstheoremsmain.pdf
A philosophical discussion which touches upon the implications of the
Lowenheim-Skolem theorems may be found here:
[The Löwenheim-Skolem Theorem, by Peter Suber]
http://www.earlham.edu/~peters/courses/logsys/low-skol.htm
As far as giving "an example" of an uncountable model of Peano
Arithmetic is concerned, I must assume some artistic license with what
is meant by "giving" such an example. The proof involves a
construction with an uncountable set, and we will take the real
numbers as the exemplar. Suppose PA is consistent, having in
particular the "standard" model N. Add a new constant to the theory
of N for each real number, say c_r for any real number r. Consider
all the terms that can be constructed in this new language, and create
equivalence classes among them based on whether two terms' equality
can be deduced from the theory of N (as extended with these new
constants). A Zorn's Lemmma/Axiom of Choice-type step is then
required to pass from the incomplete theory represented by these
equivalence classes to a complete theory, and thus to a model which
has the required uncountable cardinality by virtue of the presence of
so many distinct constant terms.
regards, mathtalk-ga |
Request for Answer Clarification by
charlie99-ga
on
16 May 2005 10:54 PDT
What are the set, constant and function corresponding to N, 0 and +1
in the uncountable model that you have defined, and how do we know
that they satisfy Peano?s Axioms, in particular Induction?
|
Clarification of Answer by
mathtalk-ga
on
17 May 2005 07:50 PDT
Hi, charlie99-ga:
I'll be happy to clarify these points of my answer. It might be
expeditious if you gave me some idea of your background in
mathematics, so that the level of detail I provide can be most useful
to you.
thanks,
mathtalk-ga
|
Request for Answer Clarification by
charlie99-ga
on
17 May 2005 08:55 PDT
The more detail the better. I am still waiting for the model. You
defined a set. What is the element instead of zero, the function
instead of successor, and how do we know it satisfies Induction?
|
Clarification of Answer by
mathtalk-ga
on
18 May 2005 06:20 PDT
Hi, charlie99-ga:
That the existence of an uncountable model of Peano Arithmetic follows
from the existence of a countable model is a special case of a general
result, the upward Lowenheim-Skolem Theorem.
In your earlier Request for Clarification you wrote:
"What are the set, constant and function corresponding to N, 0 and +1
in the uncountable model that you have defined, and how do we know
that they satisfy Peano?s Axioms, in particular Induction?"
I'll provide "more details" starting with the nature of the model constructed:
1. "I am still waiting for the model. You defined a set."
Let's elaborate on the construction I sketched. I said that the basic
idea of the proof is to work with a completed theory, as for example
all the sentences satisfied in the given countable model, which we
could assume is the natural numbers N for Peano's axioms. An
uncountably infinite set of new constants are then added to the
language.
We add new axioms which state that no two of these new constants are
equal. It follows from the Compactness Theorem, which states that a
set of axioms is inconsistent if and only if some finite subset of it
is inconsistent, that the new theory with uncountably many constants
is again consistent. In any finite subset of the enlarged axioms,
only finitely many new constants appear, and these may be
"interpreted" as distinct natural numbers, thereby showing their
consistency (relative to the consistency of Peano's axioms).
The meat of the argument is then a "lemma" (itself a result of
independent interest) that every consistent theory has a model.
Because we've added an uncountable number of distinct constants, any
such model for the enlarged theory must be uncountable:
Thm. (Model Completeness) If a set of sentences S is consistent, then
S has a model.
A fairly detailed proof of this may be found here:
[Predicate Logic -- Proofs]
http://john.fremlin.de/schoolwork/logic/logic/node8.html
as his Theorem 5..38 (Model Existence Lemma or Completeness Theorem).
Note also that the construction in that result leads to Corollary
5..43 (Upward Löwenheim-Skolem theorem) further down the page.
The nature of the model that is constructed there from a consistent
theory is a set of equivalence classes of closed terms. Specifically
two closed terms are equivalent in this context when their equality is
deducible from the theory.
So the nature of the set on which the model is based is a certain
partition of the closed terms of a theory that extends Peano
Arithmetic by adjoining uncountably infinitely many distinct
constants.
2. "What is the element instead of zero... ?"
The interpretation of the symbol 0 in this model is the equivalence
class containing the closed term 0.
3. "What is... the function instead of successor... ?"
The interpretation of the successor function in this model is, given
an equivalence class {r} for some closed term r, form the equivalence
class of s(r). That this gives a well-defined function with respect
to these equivalence classes is a consequence of the substitution
principle in predicate logic:
r = t implies s(r) = s(t)
Thus the resulting equivalence class is not dependent on the choice of
the closed term r which represents the "input" equivalence class.
4. "... and how do we know it satisfies Induction [and the rest of PA]?"
There is certainly something to show here. I refer you, at least
initially, to the Web page above, which says (with some changes of
notation for convenience):
"To show that A is a model for S we will show that for any sentence p
[in L] we have [interpretation of p in A is true] iff S' |- p. This is
an easy induction."
Here S' denotes a complete theory that has been constructed as a
consistent extension of S in the earlier part of the proof. S' will
generally also introduce new constant terms, though we do not
necessarily require the distinctness (inequality) of constants
introduced in this phase.
If you wish a more detailed presentation of this proof, I can
recommend some texts. For now I will point out that the proof itself
is inductive, and that it not only uses induction here, and in the
earlier construction of S', but also relies upon the consistency of S
= Peano's axioms in the particular case you are interested in. Not
only do we require the consistency of arithmetic (for induction), but
also the proof inherently appeals to the Axiom of Choice/Zorn's lemma
at each step of the inductive construction of S'.
With regard to uncountable models of Peano's axioms, see the following
node in this Web site:
[Predicate Logic -- Peano Arithmetic]
http://john.fremlin.de/schoolwork/logic/logic/node9.html
and especially this remark:
"Observation 5..50 PA has an infinite model N so by the
Upward-Löwenheim-Skolem theorem PA has an uncountable model which is
therefore not N."
regards, mathtalk-ga
|
Request for Answer Clarification by
charlie99-ga
on
18 May 2005 12:31 PDT
This sounds like you have a set that is something like { 0 = 0+0 = 0*0
. . . , 1 = 0+1 = 1*1 . . . , 2 = 0+2 = 1+1 . . . , . . . , r1, r2,
r3 , . . . } and for the successor function you have 0 . . . => 1 . .
. => 2 . . . and somehow that includes r1, r2, r3, . . . True? The
problem is, how can you reach all of this nondenumerable set counting
through like that? The web page seems to be saying that we can build
any axiom, including Induction, where it is provable in the new model
at each point, but I don?t see how that includes the Induction axiom.
|
Clarification of Answer by
mathtalk-ga
on
18 May 2005 17:48 PDT
The axiom scheme of induction says something quite a bit weaker than
that we can "reach" every element in the model by starting at zero and
applying the successor function. The latter arrangement is of course
exactly what we have in mind by N the "standard model" of Peano
arithmetic.
While "reachability" of every natural number in this fashion clearly
justifies the principle of induction, it is not the only way that the
axiom scheme of induction might be satisfied in a model. Induction is
going to be satisfied if every property expressible in the language
which:
(a) is satisfied by zero
(b) is satisfied by s(x) whenever it is satisfied by x
happens to hold for all x.
It might seem very difficult to guarantee that all instances of the
axiom scheme of induction are satisfied, as indeed it is! But we
essentially cross that bridge at the beginning, when we assume the
consistency of Peano's axioms (or, perhaps more particularly, that N
is a model of those axioms, which implies their consistency).
After that the steps in constructing an uncountable model of PA,
although using induction in a metamathematical sense, are carefully
designed to preserve that consistency.
Step 1: Add to PA the uncountably many new constants c(r), say for
each real r, together with an uncountable number of new axioms that
c(r) and c(s) are unequal for each pair of distinct real numbers r,s.
The enlarged theory is consistent, because if it were inconsistent,
then some finite subset of the theory would be inconsistent (by the
Compactness Theorem). But every finite subset of the enlarged theory
has a valid interpretation in N (because at most finitely many of the
new constants c(r) can appear, and we can simply assign these to
distinct natural numbers in N as necessary, so that both the axioms of
PA and the new axioms involving these c(r) are satisfied in the
interpretation).
Step 2: Use the Model Completeness Theorem (every consistent
first-order theory has a model), or more especially the construction
outlined therein, to produce a model of the enlarged (but still
consistent) theory. Since the enlarged theory has an uncountable
number of distinct constants, any such model must be uncountable.
I don't know if it is helpful or not to think about the "weakness" of
Peano's axioms specifically in the following terms, but I offer the
observation for what it is worth to you. PA doesn't guarantee that a
countable model will be isomorphic to N, nor even that such a
countable model will be elementarily equivalent to N (this is a weak
form of Godel's incompleteness theorem for PA).
There are a few first-order theories which are K-complete in the sense
that for a specific cardinal K (or for all infinite cardinals K), any
two models of the theory of size K are necessarily isomorphic. This
is not the case with PA, as the preceding paragraph suggests.
But the bigger picture here is that no first-order theory with a
denumerable language and an infinite model can fail to have models of
_all_ infinite cardinalities. To set out the proof of this "larger"
fact I've answered your question in terms of the Compactness Theorem
and the Model Completeness Theorem because the proof for PA is
essentially unchanged for any such first-order theory.
regards, mathtalk-ga
|
,
0 Comments
)