Stupid question about FLT
Timothy Y. Chow
here goes anyway.
Assume ZFC is consistent. If Fermat's Last Theorem is undecidable then
it is true, right? So if someone tomorrow produces a proof that FLT is
undecidable, then FLT itself will be a corollary. In other words the
person will have proved FLT. However, his proof will not be translatable
into ZFC, for if it were, FLT would be decidable. So our hypothetical
genius will not only have proved FLT, but will also have found a method
of proof that is beyond the capabilities of ZFC. So my question is, is
what I have just said correct?
--
Tim Chow tyc...@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949
Wilson Jose Castrellon
>I have a really stupid question for which I will undoubtedly be flamed, but
>here goes anyway.
There is nothing stupid in the question (except perhaps for the adjective
that some might consider self-referential...); in fact some time ago I heard
from a reliable source that even during the 40s-50s some prominent scholars
still wondered if there would be ways to settle FLT, in case it was proved to
be independent. What you said in the next two lines is correct, and that also
applies to other long standing questions like Poincare's Conjecture, Riemman's
Hypothesis, and about any question that can be refuted by exhibiting a
concrete counterexample, that can be proved to be so by means of a finite
computation.
>Assume ZFC is consistent. If Fermat's Last Theorem is undecidable then
>it is true, right? So if someone tomorrow produces a proof that FLT is
>undecidable, then FLT itself will be a corollary. In other words the
>person will have proved FLT. However, his proof will not be translatable
>into ZFC, for if it were, FLT would be decidable. So our hypothetical
>genius will not only have proved FLT, but will also have found a method
>of proof that is beyond the capabilities of ZFC. So my question is, is
>what I have just said correct?
In a way. If you want to prove that a conjecture is independent of ZFC (or
any other strong system), you are implicitly assuming that ZFC doesn't prove
some sentences, or what is equivalent, it is consistent (an axiomatic system
is inconsistent iff it proves everything).Therefore once you finish the
argument, what you have done is to prove an implication of the form
Consis(ZFC)-->[FLT is independent of ZFC]
in a certain axiomatic system, that could be a weak fragment of arithmetic,
Peano Arithmetic, ZFC itself, or any other system (actually in a finite frag-
ment of any such system, by Godel's Completeness Theorem).
Now you want FLT as a theorem of some axiomatic system, and even more, as a
corollary of [FLT is independent of ZFC], so this last one is also a theorem
of that system. But then that system proves that FLT is independent of ZFC,
so it proves that there are some sentences that ZFC can't prove, therefore
it proves that ZFC is consistent, something beyond the power of ZFC, hence
that system is not ZFC. (this could have been gotten much more easily, but
I believe this way shows it more transparently).
The question of new methods being found is harder to evaluate. I dont know,
would you say that using Consis(ZFC), and putting a computer to search for
consequences of that is a new method? That itself would not be out
of the reach of ZFC. Ruling that out, my answer would be yes: the prover could
have found a finite (or infinite) combinatorial lemma that is implied by
Consis(ZFC), and that implies [FLT is independent of ZFC] (both in Peano
Arithmetic, lets say) and [X is independent of ZFC] for other open X's;
or she could have found a direct proof that A-->[FLT is independent of ZFC]
with A stronger than Consis[ZFC], and A proved independent, etc. Also, that
could have been done by constructing models in a uniform way, the formal de-
tails of which could be handled in ZFC, although some of the things that you
prove are beyond the reach of ZFC.
W.Jose Castrellon G.
>--
>Tim Chow tyc...@math.mit.edu
David Sibley
went sort of as follows.
"If Fermat's Last Theorem is undecidable it's true, right?"
"Yes."
"True in all models of the integers?"
"No. True in all models is equivalent to provable. That's the
Completeness Theorem."
"True in what model then?"
"In the REAL integers."
"What are those?"
-- no answer --
Can someone please straighten this out for me?
David Sibley
sib...@math.psu.edu
Timothy Y. Chow
What my hypothetical genius would have proved would be something like
ZFC |- Con(ZFC)->FLT, or (ZFC+Con(ZFC)) |- FLT. In other words, he would
have proved FLT assuming Con(ZFC). (I should have noticed this since the
first sentence of my question was, "Assume ZFC is consistent.")
We can interpret this in different ways. One is that he has proved FLT
using a "new method" of math---the axiom Con(ZFC), which by Godel's 2nd
incompleteness theorem is not a theorem of ZFC (unless ZFC is inconsistent).
This is suggested by the formulation (ZFC+Con(ZFC)) |- FLT. One reason for
thinking this way is that his proof demonstrates a theorem (namely FLT) that
ZFC cannot prove. A second interpretation says that this is not really a
"new method" because ZFC can "mimic" the proof in a sense---this is
suggested by the formulation ZFC |- Con(ZFC)->FLT. In other words having a
computer churn out theorems of ZFC+Con(ZFC) is a process that can be
mimicked in ZFC.
Note finally that if FLT is not a theorem of ZFC, then neither is [FLT
is independent of ZFC]. So if someone demonstrated that FLT is not a
theorem of ZFC (using the axiom Con(ZFC)) but as conservatives we still
insisted on accepting only proofs from axioms of ZFC, we would be
really left hanging because not only would we be unable to prove FLT;
we would also be unable to prove that FLT is independent of ZFC---assuming
ZFC is consistent of course.
And now we return you to your regular viewing, because my head is spinning
from all this convoluted logic...
G.J. McCaughan
"FLT is undecidable" really means "If M is consistent then M can neither prove nor disprove FLT" where M is whatever system we are using (probably ZFC). A proof
that FLT is undecidable would give a proof that "If M is consistent then FLT is
true", because otherwise there would be a counterexample.
So, if M is consistent then FLT is true; we can prove this in M; so if M is consistent then every model of M makes FLT true. And if M is inconsistent then it hasn't any models. So if M proves FLT undecidable then M proves that every model of M satisfies FLT. (Why isn't this the same as proving FLT? Because M can't prove there are any models at all.)
The mistake is this:
"True in all models is the same as provable. That's the completeness theorem."
There isn't a completeness theorem for any of the systems M that anyone uses. So
FLT might be true in all models but not provable.
--
Adam Costello
>The mistake is this:
>
>"True in all models is the same as provable. That's the completeness theorem."
>
>There isn't a completeness theorem for any of the systems M that anyone uses.
>So FLT might be true in all models but not provable.
That was no mistake. There is a completeness theorem. A sentence is
provable from M iff it is true in all models of M. The problem here is
that FLT is a theorem about the natural numbers, and there is no first-
order axiomatization M of the natural numbers. Any recursive set of
axioms in a first-order language that purports to describe the natural
numbers will always admit some models which aren't exactly like the
natural numbers.
In particular, there are always models containing natural numbers which
are not represented by any terms of the language. In such a model FLT
might be false and still not disprovable because there would be no way to
cite the counterexample.
AMC
Adam Costello
You're "local logician" was correct. The REAL integers are
0, 1, -1, 2, -2, ...
The problem is that the ideas contained in the "..." are not expressible
in a first-order language. No matter how many axioms you give in a
first-order language describing the integers, there will always be models
in which "things" not appearing in the above list manage to sneak into
the set of integers, because they satisfy your axioms.
Note that when I say "No matter how many axioms you give", I still have
to require your set of axioms to be decideable, i.e., there has to be an
effective procedure for determining whether a given sentence is or is not
an axiom. Without this requirement, you could go ahead and choose for
your set of axioms the set of all sentences true for the standard model
of the integers.
AMC
Torkel Franzen
>Assume ZFC is consistent. If Fermat's Last Theorem is undecidable then
>it is true, right?
What role does the assumption that ZFC is consistent play here? "If
Fermat's theorem is undecidable in T then it is true" holds for any T
in which elementary computations can be carried out, consistent or not.
Torkel Franzen
(Adam Costello) writes:
>Any recursive set of
>axioms in a first-order language that purports to describe the natural
>numbers will always admit some models which aren't exactly like the
>natural numbers.
Recursiveness is irrelevant here.
Torkel Franzen
>"True in what model then?"
>"In the REAL integers."
>"What are those?"
>-- no answer --
Naturally your local logician was speechless. The ("REAL") integers are no
different in logic than elsewhere in mathematics. If you are actually
unclear about the integers, the logical apparatus by which nonstandard
models of arithmetic are introduced makes no sense either.
Torkel Franzen
>The mistake is this:
>"True in all models is the same as provable. That's the
>completeness theorem." There isn't a completeness theorem for any of the
>systems M that anyone uses. So FLT might be true in all models but not
>provable.
All models of what? The completeness theorem for first order logic holds,
unsurprisingly, for all first order theories. We don't have a name in
ordinary mathematics for models of e.g. first order arithmetic, since
non-standard models of arithmetic are not natural mathematical objects,
but a statement true in all such structures is provable. Similarly, a
statement in the language of fields true in all fields is provable.
David Sibley
Well, yes, of course I am unclear about the integers. How can anyone
be otherwise? I thought that was the whole point of the Incompleteness
Theorem -- that no matter how clearly I thought I had them pinned down,
there would always be questions that my description could not deal
with, that any idea I have of the integers is bound to be incomplete
(or inconsistent).
David Sibley
sib...@math.psu.edu
Torkel Franzen
No, these are some peculiar philosophical ideas inspired in you by
the incompleteness theorem, and I for one find them barely intelligible.
I don't know what you mean by "incomplete ideas" or "descriptions dealing
with questions". The incompleteness theorem, on the other hand, is easily
understandable. Of course, if I didn't understand arithmetical statements
I wouldn't understand a word of the incompleteness theorem.
Timothy Y. Chow
These are the sorts of ideas that one tends to get from reading too many
popular accounts of Godel's theorems. It seems that you're making the
following assumption:
(*) In order to "understand" or "be clear" about a mathematical concept
one must capture all its properties axiomatically, to the point where
there is exactly one mathematical model of the axiomatic system.
However, results in mathematical logic say (loosely speaking) that
(**) No axiomatic system has the property you want.
Two options are possible here. One is to accept both (*) and (**) and
conclude that the integers cannot be understood clearly. The problem
with this is that proofs in mathematical logic rely on mathematical
ideas (e.g., the integers) just as much as proofs in any other branch
of mathematics. So if the integers are unclear, then so is mathematical
logic---and if mathematical logic is unclear then why accept (**) at all?
The other option is to give up assumption (*). This has the advantage of
being self-consistent---we accept all concepts of mathematics (both things
like the integers and things like first-order languages)---but give up the
notion that mathematical concepts can be captured "perfectly" in an
axiomatic system as per (*). So what did you expect from your local
logician when you asked him what the integers are? Clearly not a bunch of
axioms. Chances are your concept of the integers is just as good as anyone
else's and there is nothing more one can say to clarify the concept to you.
Your local logician knew this and hence had nothing to add. About all he
could have said was, following a certain famous mathematician, "You know,
the integers!"
You will find people who think that all mathematical statements and
concepts are "really" set-theoretical or logical. This betrays an
attitude that somehow we understand concepts in mathematical logic and
set theory more clearly than concepts in other branches of mathematics,
and this is certainly debatable.
John C. Baez
>"If Fermat's Last Theorem is undecidable it's true, right?"
>
>"Yes."
>
>"True in all models of the integers?"
>
>"No. True in all models is equivalent to provable. That's the
>Completeness Theorem."
>
>"True in what model then?"
>
>"In the REAL integers."
>
>"What are those?"
>
>-- [sinister laughter] --
>
>Can someone please straighten this out for me?
(A slightly dramatized (by me) account of something that always amuses
me.)
Forgive me if I get this messed up, since it's been a while since
I've thought about it. We can, for example, describe models of Peano
arithmetic using ZFC. One of these models would be based on the set
{0,S0,SS0,SSS0....} where 0 is the null set and S, the successor
operator, is given by Sx = x U {x}. If we define addition and
multiplication in the "obvious correct way" in ZFC, we have a formal
description in ZFC of a model in PA. This would be one way of thinking
of the REAL (i.e., honest-to-god) natural numbers. One can cook up other nasty
"nonstandard" (i.e. fake) models of the natural numbers as well in ZFC. I have
always found that Boolos' & Jeffrey's book "Logic and Computability"
gives the most elementary descriptions of some nonstandard models of the
integers.
Of course, one can easily become suspicious of whether we really know
what these REAL natural numbers are (i.e., how their properties differ from the
fake ones). First of all, what we can prove using Peano arithmetic
about the REAL natural numbers is precisely equal to what holds in ALL models
of the integers. Rather curious, eh, that our axioms for the natural numbers ,
which are supposed to capture our basic intuitions about the natural numbers,
are only able to prove those things about the REAL natural numbers which also
hold for all the nonstandard ones? Even worse, there is no recursive
enumerable set of additional axioms can be added to the Peano axioms so
that the theorems which can then be proved are precisely those which
hold for the REAL natural numbers. (I.e., there will still be
nonstandard models even if we through in more axioms in any systematic
way.)
Well, that's just life. I can say "One of these three mathematicians
knows everything which is true about the REAL natural numbers, while the
two impostors know everything which is true about two different
nonstandard models of the natural numbers -- you are free to ask them as
many questions as you want to tell which one is the REAL natural
numbers." You can ask each "Is Fermat's last theorem true?" or "Are
there infinitely many twin primes?" and they will each tell you the
answer that's correct in their model of arithmetic, and you must
struggle to guess who is the real one. You are in deep trouble, because
for any theorem you can PROVE in PA, they will all say "Yes, it's true"
to. Now maybe you can prove some other things about about arithemetic
that are true, not using PA, and use these to catch the impostors, who
claim these things don't hold. But there is certainly no computer
program you can write to be certain of winning this game, no matter how
many questions it asks (finitely many questions, or even a recursively
enumberable set of questions). (I am assuimg Peano arithmetic is
consistent here, by the way.)
So one should not be upset at the fact that the logician could not tell
you exactly which were the REAL integers. :-)
John C. Baez
Torkel and I argued a bit about this once (he's a logician and I'm an
illogician, so we took opposite sides), but I want to add that I think
that this is a necessary complement to my little skit about which
mathematician represented the REAL integers. It reminds me a little bit
of the proof technique known as "proof by intimidation." This proceeds
as follows: the professor states a result, declares that it is obvious,
and asks if anyone needs to see a proof. Everyone is too scared, so no
proof is given.
"In the REAL integers."
"What are those?"
"What? You never learned about the integers? Boy, mathematics
education is really on the decline - now they're letting in grad
students who don't even know what the integers are!"
:-)
Neil Rickert
[Nicely written statement about models of arithmethic, and about which
is usually thought of as the `real' model.]
> Rather curious, eh, that our axioms for the natural numbers ,
>which are supposed to capture our basic intuitions about the natural numbers,
>are only able to prove those things about the REAL natural numbers which also
>hold for all the nonstandard ones?
I do have to disagree with you on what axioms "are supposed to capture."
Surely they are meant to capture just that minimal set of properties
which we find important in our use of whatever is axiomatized, in this
case natural numbers. One of the benefits of axiomatization is that it
allows generalization - the same theorems are valid wherever the axioms
are valid, and not just in the originating scenario.
The existence of non-standard models is a demonstration of the power
of axiomatization in encompassing other ideas.
Timothy Y. Chow
>Of course, one can easily become suspicious of whether we really know
>what these REAL natural numbers are (i.e., how their properties differ
>from the fake ones).
I think it helps to emphasize that the issue at stake is essentially a
philosophical one. The question is, what does it take before we can
confidently assert that we "know" what a certain mathematical entity is?
Many of us have some intuition that if there is no systematic method of
distinguishing an entity from similar entities then we do not really
"know" or "have a clear idea of" what it is.
Assuming that modern mathematical logic has accurately captured methods
of mathematical proof, its theorems tell us (roughly speaking) that there
is no such systematic method (for, say, the integers).
Some, clinging to the above-mentioned intuition, conclude that we don't
really have a clear idea of what the integers are. Others counter that
as mathematicians we constantly define and work with entities for which
we have no utopian identification procedure, and mathematical logic is
no exception. So if you really have a problem with accepting the
existence of an entity for which no such utopian procedure exists then
you will get hung up long before you get to the incompleteness theorems.
A: So let M be a model...
B: Excuse me, what is a model?
A: [Gives definition]
B: Can you give me an example?
A: [Gives some standard mathematical concept as an example]
B: But what exactly IS [standard mathematical concept]?
A: [sinister laughter or silence, depending on personality]
Torkel Franzen
>Of course, one can easily become suspicious of whether we really know
>what these REAL natural numbers are (i.e., how their properties differ
>from the fake ones).
For some reason many mathematicians - as you have just demonstrated! -
tend to throw their (mathematical) common sense to the wind as soon as
nonstandard models of arithmetic are at issue. Nonstandard models of
arithmetic differ from the standard model of arithmetic in a very ordinary
mathematical way, and we reason about nonstandard models in a very ordinary
mathematical way. You might as well agonize over how archimedean fields differ
from non-archimedean fields, but in algebra, as opposed to logic,
mathematicians seem to find it easier to stay sober.
G.J. McCaughan
for ZFC and similar theories. As has been pointed out, this was a load of codswallop. I hereby apologise to anyone I may have misled, and will try
to be a bit more careful about checking my facts before posting in future.
I stand by the rest of what I said, if it's any use.
--
W.Jose Castrellon G.
>(Timothy Y. Chow) writes:
>
> >Assume ZFC is consistent. If Fermat's Last Theorem is undecidable then
> >it is true, right?
>
> What role does the assumption that ZFC is consistent play here? "If
>Fermat's theorem is undecidable in T then it is true" holds for any T
>in which elementary computations can be carried out, consistent or not.
Correct. However what you said could be interpreted as (no suggestion that you
actually meant that):
For any T in which elementary computations can be carried out:
T |- [FLT is independent] --> FLT
A few minutes thought didnt produce a proof or disproof of that for the case
where T is Peano Arithmetic. If I use Kreisel's provability predicate in the
formalization of [X is independent], then I can find a polynomial diophantine
equation P such that PA doesnt prove
[ (P has no solutions) is independent] --> (P has no solutions)
Does anybody know if the first implication above is provable in PA, for all
polynomial diophantine equations (in place of FLT) and the standard probability
predicate?
(my guess is, it is not).
W.Jose Castrellon G.
W.Jose Castrellon G.
>(David Sibley) writes:
[brief conversation with Pensylvannia logician deleted]
> [describing PA using ZFC]
. . .
>"nonstandard" (i.e. fake) models of the natural numbers as well in ZFC. I have
>always found that Boolos' & Jeffrey's book "Logic and Computability"
>gives the most elementary descriptions of some nonstandard models of the
>integers.
[ very nice reference, and if I remember well, he gives a very
clear proof of Tennenbaum's or MacAloon's theorem, that loosely
speaking say that no non-standard model can be recursive ]
> . . . Even worse, there is no recursive
>enumerable set of additional axioms can be added to the Peano axioms so
>that the theorems which can then be proved are precisely those which
>hold for the REAL natural numbers. (I.e., there will still be
>nonstandard models even if we through in more axioms in any systematic
>way.)
Let me add that this feature can be strikingly concrete. A couple of years ago
in exploring the limits on the effectiveness of Godel's First Incompleteness
theorem, I found that it is possible to construct a formula p(x,y) in
the language of arithmetic, with only two free varibles, such that whenever
you add to PA any recursively enumerable set of axioms with index (the number
of a computer program that prints them out) e and the resulting theory is
consistent, then all of p(e,0), p(e,1), p(e,2), ... are independent of that
new theory, and not just that, but they are all *strongly independent* of each
other, i.e. the new theory plus any of the continuum many combinations of these
sentences or their negations is still consistent; hence p not only shows the
incompleteness of the new theory, but explicitly describes 2^Aleph_0 ways of
consistently extending it.
>Well, that's just life.
W.Jose Castrellon G.
Grad mailroom.Math.Dept.
The Ohio State University
wjca...@magnus.acs.ohio-state.edu
Adam Costello
Isn't it? I can think of a non-recursive set of axioms which would admit
only models elementarily equivalent to the standard model N, namely the
set Th N.
AMC
Torkel Franzen
(Adam Costello) writes:
>Isn't it? I can think of a non-recursive set of axioms which would admit
>only models elementarily equivalent to the standard model N, namely the
>set Th N.
Yes. However, Th N also has nonstandard models, and I thought that this
was what you meant by "models which aren't exactly like the natural
numbers". Anyway it is a good idea, I believe, to clarify this point.
Dan Bernstein
> The question is, what does it take before we can
> confidently assert that we "know" what a certain mathematical entity is?
The answer is, to define a mathematical entity once and for all takes
nothing beyond a fixed set of axioms and (syntactic) rules for deriving
truths from those axioms. The trick is to find *interesting* entities.
(Of course, we'd have trouble communicating mathematical ideas if we
didn't assign names to things. It's always nice when people don't use
the same names for entities which aren't equivalent. But mathematical
entities exist as syntactic objects even when humans have trouble
agreeing on names for them.)
---Dan
Timothy Y. Chow
>In article <1992Jul19....@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
>> The question is, what does it take before we can
>> confidently assert that we "know" what a certain mathematical entity is?
>
>The answer is, to define a mathematical entity once and for all takes
>nothing beyond a fixed set of axioms and (syntactic) rules for deriving
>truths from those axioms. The trick is to find *interesting* entities.
But this is precisely the point! Consider the "REAL" integers: every
set of axioms and syntactic rules that the "REAL" integers satisfies
also admits nonstandard models. How then do you propose to "define" the
REAL integers with a fixed set of axioms and syntactic rules?
Perhaps you might try to use the fact that in ZFC one can formulate a
proof that any two Peano structures are isomorphic. In that case,
consider nonstandard models of ZFC...
Timothy Y. Chow
>In article <22326.Jul2...@virtualnews.nyu.edu> brn...@nyu.edu (Dan Bernstein) writes:
>>The answer is, to define a mathematical entity once and for all takes
>>nothing beyond a fixed set of axioms and (syntactic) rules for deriving
>>truths from those axioms. The trick is to find *interesting* entities.
>
>But this is precisely the point! Consider the "REAL" integers: every
>set of axioms and syntactic rules that the "REAL" integers satisfies
>also admits nonstandard models. How then do you propose to "define" the
>REAL integers with a fixed set of axioms and syntactic rules?
>
>Perhaps you might try to use the fact that in ZFC one can formulate a
>proof that any two Peano structures are isomorphic. In that case,
>consider nonstandard models of ZFC...
Reading over this I thought it somewhat cryptic, so here's an expansion.
I take "fixed set of axioms and syntactic rules" to mean a first-order
axiomatization. Now it is well-known that there are models that are
elementarily equivalent (i.e., the same first-order sentences are true)
to the "real integers" but which are not isomorphic to the real integers.
So my challenge was to ask for a "definition" of the real integers of the
kind Dan Bernstein wants.
One possible response is to say that we can define the integers and
characterize them uniquely up to isomorphism by means of set theory. But
now, in order to meet Dan Bernstein's criterion, we must define all our
concepts of set theory by means of axioms and syntactic rules. So let's
suppose we do this and come up with ZFC. Well, the problem now is, the
axioms of ZFC can do only so much---there is nothing to stop us from
constructing nonstandard models of ZFC (assuming any models exist at all!)
and we are back to square one. We have a set theory in mind---standard
set theory if you like. We claim to know what it is, yet we cannot
characterize it by means of first-order logic. Either we reject the claim
of knowledge (along with most of mathematics) as illegitimate, or we accept
that it is O.K. in math to talk about objects that cannot be captured in
full by a system of axioms.
Dan Bernstein
> Perhaps you might try to use the fact that in ZFC one can formulate a
> proof that any two Peano structures are isomorphic. In that case,
> consider nonstandard models of ZFC...
Here, I'll tell you what the real integers are, under ZF within a
suitable second-order logic:
If N is a set, and 0 is an element of N, and s is a function on N, and
0 is not in the domain of s, and s is one-to-one, and any subset I of
N with 0 in I and s(i) in I for any i in I must be all of N, then we
say that ``N is an integer set with zero 0 and successor function s.''
There you have it: the integers. Notice that the *syntactic* object
which I've just defined is entirely unique. The fact that there are
several sets satisfying these syntactic properties is about as
astounding and philosophically devastating as the fact that there are
several ways to construct the real numbers.
You may object that ``an integer set'' is not the same as ``the
integers.'' But I claim that it is; you're just getting hung up on the
loaded word ``the.'' In fact you can easily translate all of mathematics
into a language without ``the.'' Nothing changes.
For some reason people don't seem to have this trouble with ``the
reals''; all mathematicians know that ``the reals'' are a syntactic
object, and that they're really working with all real sets modulo a form
of equivalence. Why such difficulties with ``the integers''?
---Dan
W.Jose Castrellon G.
# >brn...@nyu.edu (Dan Bernstein) writes:
# >>The answer is, to define a mathematical entity once and for all takes
# >>nothing beyond a fixed set of axioms and (syntactic) rules for deriving
# >>truths from those axioms. The trick is to find *interesting* entities.
#>But this is precisely the point! Consider the "REAL" integers: every
#>set of axioms and syntactic rules that the "REAL" integers satisfies
#>also admits nonstandard models. How then do you propose to "define" the
#>REAL integers with a fixed set of axioms and syntactic rules?
. . .
[stuff about ZFC deleted]
#Reading over this I thought it somewhat cryptic, so here's an expansion.
#I take "fixed set of axioms and syntactic rules" to mean a first-order
#axiomatization. Now it is well-known that there are models that are
#elementarily equivalent (i.e., the same first-order sentences are true)
#to the "real integers" but which are not isomorphic to the real integers.
#So my challenge was to ask for a "definition" of the real integers of the
#kind Dan Bernstein wants.
#One possible response is to say that we can define the integers and
#characterize them uniquely up to isomorphism by means of set theory. But
#now, in order to meet Dan Bernstein's criterion, we must define all our
#concepts of set theory by means of axioms and syntactic rules. So let's
#suppose we do this and come up with ZFC.
It is possible to uniquely define, up to isomorphism, the natural numbers in
second order logic;so that whenever you are asked a question about the naturals
you know exactly what kind of thing the question is refering to. However,
for practical purposes (i.e. for giving answers to those questions, and
finding methods to answer yet more questions) that idea of the set of natural
numbers might not be the right one to store in your brain, since among other
things second order logic has no complete set of sound deduction rules, and at
this time we know much more model theory for first order languages (which can
be of help for many things: finding new axioms that can be added to an
incomplete first order theory, for instance), and by Godel's First Incomplete-
ness theorem, from that second order definition you will always miss a true
sentence, whatever set of sound deduction rules you use.
After having said this, let me add that, in my opinion, having a definition
that characterizes a structure up to isomorphism is sometimes a desirable
feature, but not a *necessary* one for mathematical practice. I for one
would prefer to have at hand a complete set of deduction rules, and a rich
model theory, to having a definition that categorically characterizes what I
want to study (unless that definition plus the set of deduction rules ensures
completeness, and deduction in the system has polynomial complexity, case in
which I would let a Cray do the job...).
Finally, let me mention that there is a concrete polynomial diophantine equa -
tion in one parameter (and several variables), such that whatever logic you
construct, and whatever set of axioms and rules of deduction you choose:
If
0. You can generate all strings of symbols in the language.
1. Given a string of symbols, you can recognize if it is an axiom or not.
2. Given a string of symbols, you can recognize if that is a valid proof in
your system, or not.
3. And the system proves only true statements.
Then the system can only tell whether that diophantine equation has solutions
or not for *only a finite number* of the parameters. (my apologies, english
is not my first language), i.e. if you plug in the numbers 1,2,3,... in the
parameter, then the system will only be able to decide the (non-)existence of
solutions for only a finite number of the resulting equations. [this can be
proved by standard methods, but there is also a derivation of one (which
provides much more information) in Chaitin's "Algorithmic Information Theory"
(order?)(Information Theoretic Complexity Theory?).]
Gary Martin
But the nonstandard models of Th N all satisfy exactly the same first order
sentences, so FLT is either true in all of them or false in all of them.
"Exactly like" in this context means "elementarily equivalent", not
"isomorphic".
--
Gary A. Martin, Assistant Professor of Mathematics, UMass Dartmouth
Mar...@cis.umassd.edu
Timothy Y. Chow
>In article <1992Jul20....@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
>> Perhaps you might try to use the fact that in ZFC one can formulate a
>> proof that any two Peano structures are isomorphic. In that case,
>> consider nonstandard models of ZFC...
>
>Here, I'll tell you what the real integers are, under ZF within a
>suitable second-order logic:
This approach works---up to a point. I'm not sure I'm adding anything here
to what I've said before, but let me try.
The discussion began with first-order characterizations of the
integers. Now it can be shown that there are nonstandard models of the
integers elementarily equivalent to the standard one. Loosely
speaking, this means that first-order logic is not powerful enough to
single out the standard model from other models.
Well, this might strike us as unsatisfactory. Just what IS the standard
model if we can't distinguish it from nonstandard ones by means of
first-order properties? Let's look at the proof of the result mentioned
above---somehow, in the PROOF, we managed to specify the standard model
of the integers and distinguish it from nonstandard models. How did we
do that? Well, most modern logic texts use set theory as a foundation,
as do most modern mathematical texts. The integers are defined in terms
of SETS, along the lines that Dan Bernstein gives.
Now it seems that we're onto something. The vast majority if not all of
mathematics seems like it can be grounded in set theory. We can define
other mathematical concepts in terms of sets, and then if we can capture
the concepts of set set theory the way Dan Bernstein suggests (i.e.,
syntactically) we will be done. The fact that, using set theory, we can
prove that any two Peano structures are isomorphic might encourage us.
Well, how are we going to axiomatize set theory? Let's try a
first-order axiomatization of ZFC. Will this really capture our notion
of sets? Our experience with trying to axiomatize the integers might
not leave us very optimistic. Sure enough, we find that the situation
is perhaps worse: using usual mathematical methods we cannot even prove
that there EXISTS a model of ZFC, let alone that it is unique! This is
Godel's 2nd incompleteness theorem.
So what this tells us is that our most basic objects in mathematics---sets
---cannot be characterized in the utopian syntactic way that we hoped.
But wait a second, someone will say. Why can't we just take the syntactic
entities of ZFC to BE our sets? We just DEFINE a set to be a syntactic
entity of ZFC. Won't this solve our problems? We don't have to worry about
MODELS of ZFC, which we don't even know exist. We DO have the syntactic
entities, so why not just take those to be our sets. Then math will be
reduced to syntax as per plan.
The problem is this: just what IS ZFC? Remember what we did earlier---we
grounded all of mathematics in set theory. THIS INCLUDES MATHEMATICAL
LOGIC. Pick up a logic text and note that it starts by saying something
like, "An alphabet is a set of symbols..." In other words, our syntactic
entities---axioms, rules, ZFC itself---are defined in terms of sets. Thus
we cannot equate "set" with "syntactic entity of ZFC" without circularity.
We must at the very least distinguish between the sets involved in
constructing ZFC and the sets that ZFC talks about, or we will get horribly
confused by things like Skolem's paradox.
It IS of course O.K. to equate any mathematical entity that was not used to
define ZFC with a syntactic object of ZFC, e.g., the integers. But the
question must be raised, why should we do so? We don't have to if it
doesn't suit our purposes. We don't even have to ground everything in set
theory if we choose not to. Since "set" is just as problematic as
"integers" we could just as well take the integers as primitive. And this
is in fact what many logicians do when they are discussing first-order
axiomatizations of the integers. Dragging in all that set theory is not
necessary and obscures the point under consideration. Now of course with
more complex mathematical objects we would not dream of taking them as
primitive because we generally don't have a clear enough intuition for
them. But the integers are intuitive enough that we can do so without
causing much trouble.
The conclusion is that in mathematics we use entities all the time that
cannot be captured perfectly by first-order axiomatizations. To conclude
that we therefore don't "know" what they are is a philosophical assumption
that I don't think is necessary or helpful.
There is still a way to salvage Dan Bernstein's proposal to ground
everything in syntax---namely, take ZFC to be our primitive object instead
of sets. Then we don't have to worry about distinguishing between sets
involved in ZFC and sets ZFC talks about because there ARE no sets involved
in constructing ZFC. But this seems to me rather artificial, so I prefer
to stick with sets.
Torkel Franzen
mar...@lyra.cis.umassd.edu (Gary Martin) writes:
>"Exactly like" in this context means "elementarily equivalent", not
>"isomorphic".
I might have assumed that the term "exactly like", which has no
standard mathematical definition, here meant "elementarily eqivalent",
had not the original author gone on to say that "in particular, there
are always models containing natural numbers which are not represented
by any terms of the language." So, whatever the original intention,
I believe it should be pointed out, so as not to mislead anybody,
that any consistent first order extension of PA will have models containing
individuals not represented by any terms of the language.
Adam Costello
Okay, I see that you could imagine "non-standard" models of Th N, but since
these models make exactly the same sentences true that N does, this brand
of non-standardness isn't very upsetting. It's the possibility of a
non-standard model that actually disagrees with N about the truth of some
sentences that provokes discussions like the one we're in the middle of.
AMC
Dan Bernstein
> But wait a second, someone will say. Why can't we just take the syntactic
> entities of ZFC to BE our sets? We just DEFINE a set to be a syntactic
> entity of ZFC. Won't this solve our problems? We don't have to worry about
> MODELS of ZFC, which we don't even know exist. We DO have the syntactic
> entities, so why not just take those to be our sets. Then math will be
> reduced to syntax as per plan.
Since that is exactly what mathematicians have always done and will
always continue to do, what are you worried about?
> The problem is this: just what IS ZFC?
Who cares? It's defined well enough for people to be able to prove
things using it (syntactically), and that's what's interesting. (Hell,
for many centuries people found Euclid's axioms interesting enough to
spend lots of time on; and of course you can work with his axioms within
ZFC.) Besides, for whatever unknown reasons, the things we can do in ZFC
seem to be highly effective at modelling the real world (even if they
are ``inconsistent'' in some sense!), so mathematics will always be
funded. There you have it: intellectual challenge and a steady job. What
more could you ask for? (``Pretty pictures,'' say the fractals folks...
oh, never mind.)
> We must at the very least distinguish between the sets involved in
> constructing ZFC and the sets that ZFC talks about,
Yes, of course. Tarski wrote some very clear things about this. When
you're working in mathematical logic, you're studying various syntactic
constructs (like proofs), and it really doesn't matter if you
consistently replace one syntactic symbol (like the word ``set'') with
another one (``frobozz'') when you're writing out those constructs. The
objects of study don't have anything to do with the words you use in
talking about them.
---Dan
Frederick W. Chapman
tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
>Perhaps you might try to use the fact that in ZFC one can formulate a
>proof that any two Peano structures are isomorphic. In that case,
>consider nonstandard models of ZFC...
If I am not mistaken, there are no *KNOWN* models for ZFC, standard or
otherwise! The consistency of ZFC set theory is not known; if a model
for ZFC were to exist, then ZFC would be consistent.
I can't speak for anyone else, but I find the notion that the
consistency of ZFC has not yet been established to be the most
singularly disturbing mathematical news to ever reach my ears, given
that ZFC is intended to serve as a foundation for the rest of
mathematics.
--
o ------------------------------------------------------------------------- o
| Frederick W. Chapman, User Services, Computing Center, Lehigh University |
| Campus Phone: 8-3218 Preferred E-mail Address: fc...@Lehigh.Edu |
| "I do comedy and magic; what you don't find funny -- that's the magic." |
o ------------------------------------------------------------------------- o
Gerald Edgar
>If I am not mistaken, there are no *KNOWN* models for ZFC, standard or
>otherwise!
"Sure. There is a model for ZFC."
"What is it?"
"You know, THE SETS."
--
Gerald A. Edgar Internet: ed...@mps.ohio-state.edu
Department of Mathematics Bitnet: EDGAR@OHSTPY
The Ohio State University telephone: 614-292-0395 (Office)
Columbus, OH 43210 -292-4975 (Math. Dept.) -292-1479 (Dept. Fax)
Jan Johannsen
tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
>In article <1992Jul20....@galois.mit.edu> I wrote:
>>In article <22326.Jul2...@virtualnews.nyu.edu> brn...@nyu.edu (Dan Bernstein) writes:
>>>The answer is, to define a mathematical entity once and for all takes
>>>nothing beyond a fixed set of axioms and (syntactic) rules for deriving
>>>truths from those axioms. The trick is to find *interesting* entities.
>>
>>But this is precisely the point! Consider the "REAL" integers: every
>>set of axioms and syntactic rules that the "REAL" integers satisfies
>>also admits nonstandard models. How then do you propose to "define" the
>>REAL integers with a fixed set of axioms and syntactic rules?
>>
>>Perhaps you might try to use the fact that in ZFC one can formulate a
>>proof that any two Peano structures are isomorphic. In that case,
>>consider nonstandard models of ZFC...
>Reading over this I thought it somewhat cryptic, so here's an expansion.
>I take "fixed set of axioms and syntactic rules" to mean a first-order
>axiomatization. Now it is well-known that there are models that are
>elementarily equivalent (i.e., the same first-order sentences are true)
>to the "real integers" but which are not isomorphic to the real integers.
>So my challenge was to ask for a "definition" of the real integers of the
>kind Dan Bernstein wants.
Following this thread I always wondered why noone ever mentioned the following
possible answer:
Take the axioms for the upper half of a discretely ordered ring (about 15 axioms)
and add the (infinite) \omega-rule of induction:
A(0) A(s0) A(ss0) A(sss0) ....
--------------------------------------
\forall x A(x)
Then every true (first order) sentence about the integers is provable
with this machinery, and vice versa.
Thus we have characterized the integers up to elementary equivalence.
And if anyone out there complains about the non-constructiveness of this
approach, remember the theorem (I forgot the reference) that _recursive_
proofs in this system suffice to do the same thing.
[Stuff deleted]
>--
>Tim Chow tyc...@math.mit.edu
J. Johannsen jnjo...@immd1.uni-erlangen.de
Torkel Franzen
>Okay, I see that you could imagine "non-standard" models of Th N, but since
>these models make exactly the same sentences true that N does, this brand
>of non-standardness isn't very upsetting. It's the possibility of a
>non-standard model that actually disagrees with N about the truth of some
>sentences that provokes discussions like the one we're in the middle of.
Why the quotes? Th N has nonstandard models in the ordinary sense of this
term. As for the questions surrounding incompleteness and the limitations of
first order logic, it is my impression that it is often unclear what people
have in mind. Hence my opinion that it is a good idea to make clear that
"and so on" is not a first order concept in the characterization of the
integers as "0, s(0), s(s(0)), and so on". Those who believe that "we cannot
say" what the natural numbers are, or that there is some problem regarding
what are "the real" natural numbers should try to clarify, for themselves and
for others, why they believe that only first order notions make unambiguous
sense.
Torkel Franzen
mps.ohio-state.edu (Gerald Edgar) writes:
>"You know, THE SETS."
More precisely, the cumulative hierarchy of sets. We learn about the
natural numbers as generated from 0 by repeated application of the successor
function at such an early age, at such a basic level, that it's all but
impossible to make it clearer once we're spouting mathematics or philosophy.
Set theory is a different matter: even today we can point to Zermelo's
"Ueber Grenzzahlen und Mengenbereiche" as a presentation unequaled in
clarity of the cumulative hierarchy of sets as a model of ZFC.
Matthew P Wiener
>If I am not mistaken, there are no *KNOWN* models for ZFC, standard or
>otherwise! The consistency of ZFC set theory is not known; if a model
>for ZFC were to exist, then ZFC would be consistent.
Sure it's known. Start with an inaccessible cardinal ...
>I can't speak for anyone else, but I find the notion that the
>consistency of ZFC has not yet been established to be the most
>singularly disturbing mathematical news to ever reach my ears,
I think most mathematicians consider it one of the most boring questions in
the world. If ZFC were proved inconsistent tomorrow, they'd just laugh at
the set theorists, and get back to doing "real" mathematics. Let someone
else figure out what they are "really" doing. Relativistic quantum physics
has existed in a foundational void for half a century.
>given that ZFC is intended to serve as a foundation for the rest of
>mathematics.
That's leftover propaganda from the beginning of the century. Set theory
has its own vitality, and like any good branch of mathematics, has things
to say about other branches. The fact that the other branches often don't
like what set theory says about them ("Hey wait, what are you doing to my
conjecture? Stop that!") is not the same as being foundational.
Martin Davis tells a wonderful parable to begin his BAMS review of Donald
Monk MATHEMATICAL LOGIC. There was a castle far away in the forests, and
in the deep basements and subbasements, there were thousands of thousands
of spiders, with ancient webs that had been there for unknown eons. One
day, a humungous flood swept through the castle. When it had passed, the
surviving spiders furiously respun their webs as fast as they could. For
you see, they thought their webs were holding the castle up.
Cf Conway's Mathematical Liberation Movement, in his ONAG.
--
-Matthew P Wiener (wee...@sagi.wistar.upenn.edu)
John C. Baez
>I can't speak for anyone else, but I find the notion that the
>consistency of ZFC has not yet been established to be the most
>singularly disturbing mathematical news to ever reach my ears, given
>that ZFC is intended to serve as a foundation for the rest of
>mathematics.
The carefully guarded secret about these "consistency proofs" is that
for you to believe them you must have faith in the consistency of the
system in which you are doing the proof. Suppose you could prove
Con(ZF) in ZF. Well, if you are smart and know Goedel's theorem you
know you're in deep trouble at this point since ZF must be inconsistent.
But even if you weren't so smart you could realize that it's still quite
possible for ZF to be inconsistent, in which case one could prove
EVERYTHING in ZF, e.g., Con(ZF).
Now consider the propositional calculus. There's a consistency proof
for it. However, I claim that this proof isn't worth much if what you
are seeking is reassurance that your ideas on logic aren't screwed up.
For the reasoning used in the proof of consistency of the propositional
calculus, while usually left informal, is no more "self-evidently
consistent" than the propositional calculus itself. It's possible that
our ideas on logic are somehow very deeply confused and that one day
someone will come up with a proof of P & not(P) in the propositional
calculus. Of course, in this case our ideas on logic would be revealed
to be a bunch of baloney - including our proof of the consistency of the
propositional calculus.
For a while I was planning on writing a short story entitled "The
inconsistency of the propositional calculus", that would imagine this
happening.
I used to crave certainty and this sort of thing bugged me. Now I'm
fairly used to it -- as well as the fact (which once seemed disturbing)
that no r.e. set of axioms about the integers will have a unique model
up to elementary equivalence, and NO set of axioms about the integers
will have a unique model up to isomorphism. It irritates Torkel when I
say that this means we're not quite sure what the "real" integers ARE.
I think the sense in which I mean this was most clearly indicated by my
game show in which one tried to figure out which mathematician was using
the real integers and which two were fakes. (What's the name of that
show, anyway? Truth or Consequences?)
Please don't think I'm losing any sleep over this. I like to think of
it this way. I have a notion - "the integers" - and I try to capture
this notion in some axioms and prove some things using the axioms. All
I get is what I pay for, I should not expect the axioms to answer all possible
questions, I should not expect the axioms to be categorical, and I
should not expect to get some sort of guarantee that the axioms are
consistent, other than the empirical fact that nobody has found an
inconsistency yet. This may seem tough but it's certainly no worse than
the rest of life.
Timothy Y. Chow
>In article <1992Jul21.0...@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
>> But wait a second, someone will say. Why can't we just take the syntactic
>> entities of ZFC to BE our sets? We just DEFINE a set to be a syntactic
>> entity of ZFC. Won't this solve our problems? We don't have to worry about
>> MODELS of ZFC, which we don't even know exist. We DO have the syntactic
>> entities, so why not just take those to be our sets. Then math will be
>> reduced to syntax as per plan.
>
>Since that is exactly what mathematicians have always done and will
>always continue to do, what are you worried about?
Is it what mathematicians have done? Texts on set theory will begin with a
bunch of axioms for sets. In general, the term "set" is not defined, much
less defined to be a syntactic entity. In fact, "syntactic entity" is
defined in terms of sets, while sets remain undefined.
Ontological questions like "What IS a set?" are generally restricted to
a preface and are not addressed in mathematics texts. For the purposes
of DOING mathematics, it doesn't really matter what you think a set is,
as long as you can produce correct proofs about sets. This I think you
will agree with. But you go further, concluding from this fact that a
set IS a syntactic entity, i.e., taking a particular ontological stance
on the nature of sets. I recall from an earlier discussion on this
forum that you said something like, "Goldbach's conjecture is the
statement that, in a certain set theory under a suitable logic, ..."
Well, most mathematicians would omit the phrase about set theory and
make the purely mathematical statement that Goldbach's conjecture is
the statement that every even number > 2 is the sum of two primes. For
your approach presupposes a philosophical statement, that sets ARE
syntactic entities, whereas most mathematicians leave such ontological
proclamations alone and just do mathematics.
Nor is the statement that "sets are syntactic entities" trivial, because
in mathematics today it's the other way around. Syntactic entities are
defined in terms of sets. As I said before, take any logic textbook and
note that it begins by saying, "An alphabet is a set of symbols..." In
an earlier article I complained that taking syntactic entities as our
starting point instead of sets seemed artificial. Well, I take that back,
and say now that it is not really artificial; we seem to understand what
an "axiom" or a "string of symbols" is about as well as we understand what
a "set" is. But I do maintain that I see no reason to give up the way we
do things now, i.e., basing everything, including syntactic entities, on
sets.
Earlier in this thread I asked, what does it take before we can say we
"know" what a mathematical entity is. Experience with trying to
capture the properties of the integers (a perfectly respectable
mathematical object) with first-order logic suggests that we cannot
necessarily "define," or characterize uniquely, mathematical objects by
means of first-order axiomatization. But you may say, we can
characterize all other objects in terms of sets, and then take some
first-order axiomatization of set theory. To this I say, what
confidence do we have that first-order logic will succeed with set
theory, something much more complicated than the integers? (In case
you're tempted to say, but sets just ARE syntactic objects of a
first-order logic, see above paragraphs.) We don't have any assurance,
but I say we don't have to worry about this. There is no need to
say that we don't know what a mathematical object "is" just because
its properties cannot be exhausted by a first-order axiomatization.
Note: although I have only talked about first-order axiomatizations,
the philosophical points made here apply for the most part for second-order
and other logics.
Michael Weiss
(John C. Baez) writes:
[discussion of impossibility of proving the consistency of ZF omitted]
I used to crave certainty and this sort of thing bugged me. Now I'm
fairly used to it -- as well as the fact (which once seemed disturbing)
that no r.e. set of axioms about the integers will have a unique model
up to elementary equivalence, and NO set of axioms about the integers
will have a unique model up to isomorphism. It irritates Torkel when I
say that this means we're not quite sure what the "real" integers ARE.
I think the sense in which I mean this was most clearly indicated by my
game show in which one tried to figure out which mathematician was using
the real integers and which two were fakes.
Well... you presumably believe that there are nonstandard models of Peano
arithmetic (say) because you accept the sort of set-theoretic reasoning
used to establish the Compactness theorem of first order logic.
You may say you interpret this reasoning in a purely formal
sense, as another game played on the checkerboard of ZFC. Or you may
prefer a more hedonistic interpretation, where the symbols simply
transcribe a symphony we hear directly with our mathematical ears.
Either way, I assume you would accept the following two theorems
of ZFC on the same philosophical level:
(1) For any consistent extension T of Peano arithmetic, there are
non-isomorphic models of T-- i.e., nonstandard models exist.
(2) There are models of Peano arithmetic that can be imbedded in any
model of Peano arithmetic, and any two such models are
isomorphic.
If I wanted to dot all the i's, I would define a category of models of PA
and state the imbedding and isomorphism properties "canonically", but since
we're among friends, I won't bother.
While the proof of (2) is trivial, I consider it quite adequate
justification for talking about the Real Integers. We can single out a
minimal model of Peano arithmetic, and this model is unique up to
isomorphism in a natural way. What more could one ask for?
Of course, stepping "outside the system", one can see that the model isn't
*really* unique. But if you can do enough set theory to construct
nonstandard models, you can tell which are the honest-to-Kronecker
integers, and which are the fakes.
Torkel Franzen
>Now consider the propositional calculus. There's a consistency proof
>for it. However, I claim that this proof isn't worth much if what you
>are seeking is reassurance that your ideas on logic aren't screwed up.
Hmm..why try to invest consistency proofs with these religious
connotations? Why not just read a consistency proof for a theory as a
proof that the theory is consistent? Such a proof is worth as much or
as little as any other proof in mathematics.
>It irritates Torkel when I
>say that this means we're not quite sure what the "real" integers ARE.
Haha! Actually I'm getting quite used to this kind of thing. It will
always be with us, just like reflections on how we know that anything
exists, or how we can be sure that what you mean by "red" is the same
as what I mean by "red".
>I think the sense in which I mean this was most clearly indicated by my
>game show in which one tried to figure out which mathematician was using
>the real integers and which two were fakes.
The easy way of finding out is to ask the people involved. Of course,
if you restrict the language they are allowed to use in answering you, you
may make it impossible to decide.
For an analogous case, but (I hope) one less apt to put people into a
state of frothing excitement, consider the real numbers vs the rational
numbers. They are indistinguishable as ordered sets if we are only allowed
to use the first order language of ordered sets. Yet most mathematicians
have no difficulty in grasping that the order types of these sets are
different.
Herman Rubin
|>Perhaps you might try to use the fact that in ZFC one can formulate a
|>proof that any two Peano structures are isomorphic. In that case,
|>consider nonstandard models of ZFC...
>If I am not mistaken, there are no *KNOWN* models for ZFC, standard or
>otherwise! The consistency of ZFC set theory is not known; if a model
>for ZFC were to exist, then ZFC would be consistent.
>I can't speak for anyone else, but I find the notion that the
>consistency of ZFC has not yet been established to be the most
>singularly disturbing mathematical news to ever reach my ears, given
>that ZFC is intended to serve as a foundation for the rest of
>mathematics.
I suggest then that you take a good look at what Godel showed.
He showed that any system of axioms adequate for Peano arithmetic
which is consistent has propositions which can be neither proved
nor disproved. One of these propositions is always the consistency.
So you must accept this disturbing news; any remotely useful foundation
will never have its consistency demonstrated. Only relative consistency
can be shown.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hru...@pop.stat.purdue.edu (Internet, bitnet)
{purdue,pur-ee}!pop.stat!hrubin(UUCP)
djvel...@amherst.edu
>
> Following this thread I always wondered why noone ever mentioned the following
> possible answer:
>
> Take the axioms for the upper half of a discretely ordered ring (about 15 axioms)
> and add the (infinite) \omega-rule of induction:
>
> A(0) A(s0) A(ss0) A(sss0) ....
> --------------------------------------
> \forall x A(x)
>
> Then every true (first order) sentence about the integers is provable
> with this machinery, and vice versa.
> Thus we have characterized the integers up to elementary equivalence.
And what exactly does the "..." in the rule above refer to? Your
"characterization" of the integers has the integers hidden in it.
Dan Velleman
Dept. of Mathematics & Computer Science
Amherst College
djvel...@amherst.edu
> In article <1992Jul21.0...@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
>> But wait a second, someone will say. Why can't we just take the syntactic
>> entities of ZFC to BE our sets? We just DEFINE a set to be a syntactic
>> entity of ZFC. Won't this solve our problems? We don't have to worry about
>> MODELS of ZFC, which we don't even know exist. We DO have the syntactic
>> entities, so why not just take those to be our sets. Then math will be
>> reduced to syntax as per plan.
>
> Since that is exactly what mathematicians have always done and will
> always continue to do, what are you worried about?
This is not *at all* what mathematicians have always done. If you took the
syntactic objects to be the sets, then since there are only countably many
syntactic objects, there would only be countably many sets.
Mathematical *reasoning* can be accurately represented syntactically--that's
basically what the completeness theorem says. But that's quite different
from saying that the *objects* of mathematics are syntactic.
You could argue that mathematicians should take their objects to be
syntactic. But that would be quite a change from the way mathematicians
ordinarily do things.
djvel...@amherst.edu
I find the cumulative hierarch of sets very *unclear*--especially in
comparison to the integers. My reaction to the statement, "You know, THE
INTEGERS" would be "Oh yes, of course, I know those." I'm afraid my reaction
to "You know, THE SETS" is "No, I don't know them. I know some of them, and
I have some vague intuitions about others, but at some point the picture gets
too fuzzy for me to be sure what we're talking aobut."
Dan Velleman
Dept. of Mathematics and Computer Science
Amherst College
Torkel Franzen
>I find the cumulative hierarch of sets very *unclear*--especially in
>comparison to the integers. My reaction to the statement, "You know, THE
>INTEGERS" would be "Oh yes, of course, I know those." I'm afraid my
>reaction to "You know, THE SETS" is "No, I don't know them.
Certainly the cumulative hierarchy of sets is unclear if you compare it with
the integers! Who ever claimed otherwise? But the answer to the question
"what sets?" which I mentioned was not "you know, THE SETS", but the
very different answer given by Zermelo.
Kermit Rose
>I have a really stupid question for which I will undoubtedly be flamed, but
>here goes anyway.
>
>Assume ZFC is consistent. If Fermat's Last Theorem is undecidable then
>it is true, right?
^^^^^^^^^^^^^^^
I do not know if this is true or not. Suppose FLT is false, but with only
a finite number of counter examples. Suppose that the smallest
counterexample is so large that it is not possible in practice to discover
it. Perhaps FLT is decidable in principle, but not computable within the
lifetime of humanity. Do we say that FLT is undecidable?
So, if we define undecidable to mean that there ARE NO COUNTEREXAMPLES,
and THERE IS NO WAY TO PROVE the theorem, then I would agree that
undecidable implies true.
>So if someone tomorrow produces a proof that FLT is
>undecidable, then FLT itself will be a corollary. In other words the
>person will have proved FLT. However, his proof will not be translatable
>into ZFC, for if it were, FLT would be decidable. So our hypothetical
>genius will not only have proved FLT, but will also have found a method
>of proof that is beyond the capabilities of ZFC. So my question is, is
>what I have just said correct?
I do not see any flaw your reasoning. However, it suggests that the proof that
FLT is undecidable is impossible.
>--
>Tim Chow tyc...@math.mit.edu
>Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
>30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
>only 1 1/2 tons. ---Popular Mechanics, March 1949
ro...@fsu1.cc.fsu.edu To be sure I see your response, use e-mail.
-----------------------------------------------------------------------
Be of good cheer, for it is much more fun than being depressed.
Dan Bernstein
> Is it what mathematicians have done?
Yes. Oh, sure, you might assign semantics to mathematical concepts, and
when you see how amazingly well math applies to the real world you might
start believing (as I do) that it's all consistent... but when push
comes to shove you demonstrate *everything* syntactically. That's how
modern mathematics works. That's how it's worked since Euclid.
How many mathematicians care whether ZF has a model within some larger
system? Or whether ``the sets'' described by ZF are unique? Very few,
I'd say. All that matters is that the axioms which make up ZF are
useful for producing interesting statements. What a ``set'' is, beyond
the properties assigned to it by ZF, is absolutely, totally irrelevant.
> Texts on set theory will begin with a
> bunch of axioms for sets. In general, the term "set" is not defined, much
> less defined to be a syntactic entity.
Of course it's not ``defined to be a syntactic entity.'' It *is* a
syntactic entity. It's a word. ``Set.'' It has a precise syntactic
meaning (which will vary from text to text, of course): i.e., you're
given certain axioms for set theory which tell you how you're allowed to
push the word ``set'' (together with ``element'') around the page,
within the framework of some appropriate logical system.
> But you go further, concluding from this fact that a
> set IS a syntactic entity,
You might think of sets as having semantics beyond the syntax, but you
can't convince any other mathematician of those semantics without
reducing them to syntax. I'm just trying to make a practical observation
about how math works.
> There is no need to
> say that we don't know what a mathematical object "is" just because
> its properties cannot be exhausted by a first-order axiomatization.
What I am saying is that anyone who talks about a mathematical object
and can't write down axioms for it is a crank. As far as I'm concerned
such objects aren't mathematical.
---Dan
Dan Bernstein
> syntactic objects to be the sets, then since there are only countably many
> syntactic objects, there would only be countably many sets.
You're equating the mathematical term ``the sets'' with some particular
collection which you think of as modelling the sets. What I am saying is
that the word ``set,'' for all mathematical purposes, is a purely
syntactic object which we manipulate according to certain rules. Any
semantics beyond that syntax is irrelevant. This has nothing to do with
the countability of some particular mental model you may have conjured
up of what ``the sets'' really ``are.''
---Dan
Timothy Y. Chow
>You're equating the mathematical term ``the sets'' with some particular
>collection which you think of as modelling the sets. What I am saying is
>that the word ``set,'' for all mathematical purposes, is a purely
>syntactic object which we manipulate according to certain rules.
Aha! The WORD "set" is a syntactic object. There is a world of difference
between the word "set" and a set. Similarly there is a difference between
the phrase "the integers" and the integers. If you alter your claims about
the integers to be claims about the phrase "the integers" then I will have
no objection to what you say.
Bill Taylor
|> >
|> > More precisely, the cumulative hierarchy of sets.
|> > "Ueber Grenzzahlen und Mengenbereiche" as a presentation unequaled in
|> > clarity of the cumulative hierarchy of sets as a model of ZFC.
|>
|> I find the cumulative hierarch of sets very *unclear*
I would partly agree - the cumulative hierarchy is beautifully clear as far
as its LENGTH goes, the backbone of ordinals. (At least provided you dont go
as far as an inaccessible, "whatever that is".)
But the cumulative hierarchy isn't quite so magnificently clear when it comes
to WIDTH; just how many sets are added in at each stage. That's the area
where a lot of fuzzy disagreement occurs between platonist set theorists.
Come to think of it; if you don't fully believe ax.choice is "really" true
for "actual" sets, then maybe the length of the hierarchy isn't all
that clear either, beyond the first nonconstructive ordinal.......
Jan Johannsen
The premiss of the \omega-rule should perhaps be more accurately written as:
A(t) for every term t built up from the constant symbol 0 and the
unary function symbol s
------------------------------------------------------------------------
This is what my dots referred to, a purely syntactic definition.
Where do you see integers here ?
> Dan Velleman
> Dept. of Mathematics & Computer Science
> Amherst College
Jan Johannsen jnjo...@immd1.informatik.uni-erlangen.de
Michael Weiss
[discussion by Dan Bernstein and Timothy Y. Chow on whether formalism is
the "correct" philosophy of mathematics or not-- though they didn't put it
that way-- omitted]
Gee, do you suppose that Peano, Russell, Brouwer, Hilbert, Godel, and co.
would have come to an agreement and settled all these questions if only
they'd had email?
Adam Costello
>
>But this is precisely the point! Consider the "REAL" integers: every
>set of axioms and syntactic rules that the "REAL" integers satisfies
>also admits nonstandard models. How then do you propose to "define" the
>REAL integers with a fixed set of axioms and syntactic rules?
I'm sorry if I begin to sound like a broken record, but please remember
that this is only true if you restrict your axioms to first-order
languages. The REAL integers _can_ be defined (to within isomorphism)
in a second-order language. Of course, this still doesn't get you a
complete number theory. Also, using a second-order language requires
that one already knows what sets are. If these still have to be defined,
then we're back to the same problem. It's inescapable. Set theory is
built on logic, but logic is defined in terms of sets. People obviously
knew and understood both concepts well, before either was formalized.
AMC
Adam Costello
>
>I'm sorry if I begin to sound like a broken record, but please remember
>that this is only true if you restrict your axioms to first-order
>languages. The REAL integers _can_ be defined (to within isomorphism)
>in a second-order language. Of course, this still doesn't get you a
>complete number theory. Also, using a second-order language requires
>that one already knows what sets are. If these still have to be defined,
>then we're back to the same problem. It's inescapable. Set theory is
>built on logic, but logic is defined in terms of sets. People obviously
>knew and understood both concepts well, before either was formalized.
Oops, I didn't realize when I posted this that it had already been
covered quite well (much better than I have done). Unfortunately, rn
is confused and wouldn't let me cancel it. Sorry.
AMC
Timothy Y. Chow
I was tempted to use the word "formalism" in the discussion several times
but refrained because I didn't think it was necessary. Moreover I was not
attempting to refute formalism but trying to show that there are some
difficulties with formalism and it is not the only philosophy of mathematics
around. This is a more modest goal and has a fighting chance of being
attained.
Herman Rubin
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>knew and understood both concepts well, before either was formalized.
This is definitely not so. At least very much of logic does not require
sets. The logic needed in Godel's proof is only part of first-order
intuitionistic logic, and requires no set theory at all.
The sentencial calculus was fairly well understood by Boole, etc., but
that is about all that can be said about understanding either of these
well, at least having an understanding which can be conveyed to others.
There is much better understanding of logic than of set theory. As
someone who has worked with the objects of set theory, it is clear that
much of the power of the field is due to the fact that one works with
them, and knows how to, but they are quite vague. The independence
makes it clear that we will never really see a well-ordering of the
reals, for example.
Kermit Rose
>In article <1992Jul18....@infodev.cam.ac.uk> gj...@cus.cam.ac.uk (G.J. McCaughan) writes:
>>The mistake is this:
>>
>>"True in all models is the same as provable. That's the completeness theorem."
>>
>>There isn't a completeness theorem for any of the systems M that anyone uses.
>>So FLT might be true in all models but not provable.
>
>That was no mistake. There is a completeness theorem. A sentence is
>provable from M iff it is true in all models of M. The problem here is
>that FLT is a theorem about the natural numbers, and there is no first-
>order axiomatization M of the natural numbers. Any recursive set of
>axioms in a first-order language that purports to describe the natural
>numbers will always admit some models which aren't exactly like the
>natural numbers.
>
>In particular, there are always models containing natural numbers which
>are not represented by any terms of the language. In such a model FLT
>might be false and still not disprovable because there would be no way to
>cite the counterexample.
>
>AMC
How does this relate to the proof that the integral domain represented by
the integers is categorical? I had understood that this meant that any
model that satisfied the given axioms was isomorphic to the integers. Is
not the natural numbers isomorphic to a proper subset of this categorical
system?
Kermit Rose
>In article <BrJtH...@cs.psu.edu> sib...@math.psu.edu (David Sibley) writes:
>
>>"If Fermat's Last Theorem is undecidable it's true, right?"
....
>>
>>Can someone please straighten this out for me?
>
>(A slightly dramatized (by me) account of something that always amuses
>me.)
>
>Forgive me if I get this messed up, since it's been a while since
>I've thought about it. We can, for example, describe models of Peano
>arithmetic using ZFC. One of these models would be based on the set
>{0,S0,SS0,SSS0....} where 0 is the null set and S, the successor
>operator, is given by Sx = x U {x}. If we define addition and
>multiplication in the "obvious correct way" in ZFC, we have a formal
>description in ZFC of a model in PA. This would be one way of thinking
>of the REAL (i.e., honest-to-god) natural numbers. One can cook up other nasty
>"nonstandard" (i.e. fake) models of the natural numbers as well in ZFC. I have
>always found that Boolos' & Jeffrey's book "Logic and Computability"
>gives the most elementary descriptions of some nonstandard models of the
>integers.
>
>Of course, one can easily become suspicious of whether we really know
>what these REAL natural numbers are (i.e., how their properties differ from the
>fake ones). First of all, what we can prove using Peano arithmetic
>about the REAL natural numbers is precisely equal to what holds in ALL models
>of the integers. Rather curious, eh, that our axioms for the natural numbers ,
>which are supposed to capture our basic intuitions about the natural numbers,
>are only able to prove those things about the REAL natural numbers which also
>hold for all the nonstandard ones? Even worse, there is no recursive
>enumerable set of additional axioms can be added to the Peano axioms so
>that the theorems which can then be proved are precisely those which
>hold for the REAL natural numbers. (I.e., there will still be
>nonstandard models even if we through in more axioms in any systematic
>way.)
>
>......
>
>So one should not be upset at the fact that the logician could not tell
>you exactly which were the REAL integers. :-)
So, it seems that the REAL integers are the abstract numbers underlying the
numerals that are our model for the integer. Therefore, I suggest that IF
FLT is undecidable, it is only because a proof of it would require a proof
for each of the infinite primes. Clearly if FLT has no counterexamples,
then it is true. If it is undecidable, it cannot be proven false,
therefore it is true. And this would hold in EVERY model of the integers.
I suggest that if FLT is undecidable in one model of the integers, it is
undecidable is ALL models. It is no paradox that if it is undecidable, then
it is true. This is because undecidable simply means unable to prove true or
false. If we cannot (in principle) prove FLT false, this means that it IS
NOT FALSE. Whereas, it might be possible that no method exist to prove FLT
is true. Since we say that FLT is true if it is not false, we say that if
FLT is undecidable, then it is true.
Christopher P Menzel
>I suggest that if FLT is undecidable in one model of the integers, it is
>undecidable is ALL models. It is no paradox that if it is undecidable, then
>it is true. This is because undecidable simply means unable to prove true or
>false. If we cannot (in principle) prove FLT false, this means that it IS
>NOT FALSE.
You seem to be saying that inability to prove the negation of a
sentence implies that the sentence isn't false. But, for example, we
cannot prove (in PA) the negation of the G\"{o}del sentence for PA,
but (reasoning in the usual way in our metatheory) it is false (in the
natural numbers) all the same.
>Whereas, it might be possible that no method exist to prove FLT
>is true. Since we say that FLT is true if it is not false, we say that if
>FLT is undecidable, then it is true.
Correct me if I'm wrong, but I *think* the reason that the
undecidability of FLT implies its truth is simply that any
counterexample to FLT (i.e., a formula of the form a^n + b^n = c^n)
would be provable in PA. Hence, FLT can't be both undecidable and
false.
Chris Menzel
Jan Johannsen
>In article <1992Jul19.2...@mailer.cc.fsu.edu> ro...@fsu1.cc.fsu.edu writes:
>>I suggest that if FLT is undecidable in one model of the integers, it is
>>undecidable is ALL models. It is no paradox that if it is undecidable, then
>>it is true. This is because undecidable simply means unable to prove true or
>>false. If we cannot (in principle) prove FLT false, this means that it IS
>>NOT FALSE.
>You seem to be saying that inability to prove the negation of a
>sentence implies that the sentence isn't false. But, for example, we
>cannot prove (in PA) the negation of the G\"{o}del sentence for PA,
>but (reasoning in the usual way in our metatheory) it is false (in the
>natural numbers) all the same.
Of course the implication not (provable (not A)) -> A
does not hold in general, but it holds for _universal_ sentences,
and of course FLT is a universal sentence (or at least, if you
define exponentiation, a \Pi_1- sentence, for which the same holds).
>>Whereas, it might be possible that no method exist to prove FLT
>>is true. Since we say that FLT is true if it is not false, we say that if
>>FLT is undecidable, then it is true.
>Correct me if I'm wrong, but I *think* the reason that the
>undecidability of FLT implies its truth is simply that any
>counterexample to FLT (i.e., a formula of the form a^n + b^n = c^n)
>would be provable in PA. Hence, FLT can't be both undecidable and
>false.
Yes, and this can be generalized to any universal (or \Pi_1) sentence, since
any counterexample would be an open (or bounded) formula, and all such
formulae are provable in PA iff they are true (in the REAL integers).
>Chris Menzel
J. Johannsen jnjo...@immd1.informatik.uni-erlangen.de
Dan Bernstein
> I was tempted to use the word "formalism" in the discussion several times
> but refrained because I didn't think it was necessary.
``Formalism'' is a loaded term. People called Ramanujan a ``formalist''
when he blindly manipulated the zeta function without realizing that it
had complex zeros. The ``formalism'' of a century ago was ushered out by
rigor.
In any case, the purely syntactic viewpoint which I advocate doesn't
have any difficulties. You may refuse for years to give in and admit
that you're a symbol-pusher too, but I'll be able to take any paper you
publish and keep the entire mathematical content while removing every
appeal to semantics. I win. [chuckle]
---Dan
Michael Weiss
(Timothy Y. Chow) writes:
> I was tempted to use the word "formalism" in the discussion several times
> but refrained because I didn't think it was necessary.
In article <1043.Jul31...@virtualnews.nyu.edu> brn...@nyu.edu (Dan
Bernstein) replies:
``Formalism'' is a loaded term. People called Ramanujan a ``formalist''
when he blindly manipulated the zeta function without realizing that it
had complex zeros. The ``formalism'' of a century ago was ushered out by
rigor.
In any case, the purely syntactic viewpoint which I advocate doesn't
have any difficulties. You may refuse for years to give in and admit
that you're a symbol-pusher too, but I'll be able to take any paper you
publish and keep the entire mathematical content while removing every
appeal to semantics. I win. [chuckle]
"Formalism" has been the standard term for a certain philosophy of
mathematics since Hilbert, at least.
I won't get drawn into an argument about whether formalism is "correct"
(whatever that means). Why don't we just conclusively solve the easy
problems in philosophy first, like the meaning of quantum mechanics, the
mind-body problem, and the nature of good and evil?
Dan appears to believe that he "wins" because Timothy can't prove that
formalism is wrong. Philosophical arguments being what they are, such
victories come cheap.
Anyone who is seriously interested in such issues should do some background
reading. I recommend "The Philosophy of Mathematics", a collection edited
by Benacerraf and Putnam. This dates from c. 1970; most of the essays are
post-Goedel's theorem (the Great Divide for this subject, as Benacerraf and
Putnam point out in their introduction).
Gregory McColm
>In article <1992Jul20....@galois.mit.edu>,
>If I am not mistaken, there are no *KNOWN* models for ZFC, standard or
>otherwise! The consistency of ZFC set theory is not known; if a model
>for ZFC were to exist, then ZFC would be consistent.
>
>I can't speak for anyone else, but I find the notion that the
>consistency of ZFC has not yet been established to be the most
>singularly disturbing mathematical news to ever reach my ears, given
>that ZFC is intended to serve as a foundation for the rest of
>mathematics.
Considering that belief in the consistency of Peano
Arithmetic requires only a little more gullibility than
belief in the consistency of ZFC, one might argue
that there is no "known" model of PA, for then PA
would be known to be consistent. On the other hand,
various platonists claim that the naive Universe of
Sets (you know, V_0 u V_1 u ...) is a model of ZF,
and such belief seems plausible, or at least only
slightly less plausible than the claim that the
integers (whatever they are) (if they are) form a
model of PA.
-----Greg McColm
Torkel Franzen
edu. (Gregory McColm) writes:
>slightly less plausible than the claim that the
>integers (whatever they are) (if they are) form a
>model of PA.
A model of what? Any uncertainty you may feel concerning what "the integers"
are carries over in a routine fashion into an uncertainty concerning what
"PA" is.
Mark Corscadden
|>...
|>In any case, the purely syntactic viewpoint which I advocate doesn't
|>have any difficulties. You may refuse for years to give in and admit
|>that you're a symbol-pusher too, but I'll be able to take any paper you
|>publish and keep the entire mathematical content while removing every
|>appeal to semantics. I win. [chuckle]
|>
|>---Dan
So what happens if I publish a paper concerning neither sets nor manifolds,
say, but concerning the practice of mathematics itself? Suppose that I
"push around some symbols" and manage to prove that there are certain
things which you will never be able to do while you are pushing around
*your* symbols? I'm afraid that you will not be able to remove the
semantics from my paper, because the semantics of my paper describe
all-to-meaningful limits on what you can and cannot do. Assuming that
I pushed my symbols around correctly, you won't be able to violate the
restrictions which are placed upon *your* symbol-pushing activities,
as described by the semantic content of *my* symbol-pushing activities.
Inescapable semantics!
These are known as pushy symbols: you push them around and they push back!
Heh heh.
Mark Corscadden
ma...@smsc.sony.com
work: (408)944-4086
Laurence James Edwards
Granted everything can be reduced to symbol pushing, that seems fairly obvious,
but, I would think the symbols you choose to push and/or the way you push them
have semantic meaning to you, otherwise you wouldn't be pushing them. Don't
mean to be pushy, but thats my opinion (sorry couldn't help myself).
Larry Edwards
edw...@sunrise.stanford.edu
Gregory McColm
There are two problems here. First, do we really believe
that the integers (model <N,+,.,0>) `exists' in some
sense? Realists say YES, materialists say NO.
Nowadays, it is presumably clear what we mean by
the term "integer", but whether this notion represents
a real object, or some commonly accepted fiction, (or
both: a commonly accepted fiction might "become real"
in some sense by virtue of popularity).
From there, we get more problems. Suppose that you
believe that the model of the integers exist. Is PA
true on this model? Remember that this model would be
an infinite object, which undermines any claim that
PA is "obviously" true on it.
On the other hand, suppose that this model does not
exist. Is the assumption "the model exists and
satisfies PA" going to lead to contradictions? Is
the answer to this obvious?
I believe that the model `exists' and satisfies PA;
the point of my note was that a Cartesian approach to
mathematics (ie, use only absolutely true facts) leads
to instant impotence: if one is to move the world,
one must ASSUME a place to stand.
-----Greg McColm
Torkel Franzen
edu. (Gregory McColm) writes:
>From there, we get more problems. Suppose that you
>believe that the model of the integers exist. Is PA
>true on this model?
What is PA? My explanation of the integers is simple: the integers
are 0, s(0), s(s(0)) and so on. Any obscurity or ambiguity that you
find in this explanation carries over to any explanation of what is
meant by "PA".
David Kastrup
> What is PA? My explanation of the integers is simple: the integers
>are 0, s(0), s(s(0)) and so on. Any obscurity or ambiguity that you
>find in this explanation carries over to any explanation of what is
>meant by "PA".
Wow, quite a few less features (axioms) than I need.
At least cyclelessness would be desirable, or else you end up with
a finite set. And some other things would be nice too, as someone
called Peano has figured out quite a while ago.
The above corresponds more or less to the axiom justifying
proofs by complete induction.
Seth Breidbart
(Torkel Franzen) writes:
> My explanation of the integers is simple: the integers
>are 0, s(0), s(s(0)) and so on. Any obscurity or ambiguity that you
>find in this explanation carries over to any explanation of what is
>meant by "PA".
Q: What do you mean by "and so on"?
A: Any number of s's.
Q: "Any number"? What about pi s's?
A: I mean any counting number.
Q: What is a "counting number"?
A: A non-negative integer.
Q: What is an integer?
Seth se...@fid.morgan.com
Torkel Franzen
(Seth Breidbart) writes:
>Q: What do you mean by "and so on"?
Your questions apply equally to an explanation of what is meant by "PA",
which was the point of my comments.
Gregory McColm
And what, precisely do you mean by "and so on"??? You may think
that it is obvious what you mean, but a number of people, from
Aristotle to Brouwer, have had doubts about the murkey depths of
that "and so on".
===================================================================
|
Greg McColm | I see it, but I don't believe it.
Dept of Mathematics |
Univ of S Florida | -----Georg Cantor
mcc...@math.usf.edu |
Torkel Franzen
edu. (Gregory McColm) writes:
>And what, precisely do you mean by "and so on"??? You may think
>that it is obvious what you mean, but a number of people, from
>Aristotle to Brouwer, have had doubts about the murkey depths of
>that "and so on".
Judging by the responses that have appeared, my simple point - as I thought -
is difficult to grasp. To repeat:
Any obscurity or ambiguity that you
find in this explanation carries over to any explanation of what is
meant by "PA".
In other words, I have not claimed that my explanation of what is
meant by "the natural numbers" is clear. On the contrary, it is perfectly
compatible with my claim that that explanation is meaningless,
unintelligible, or a piece of insane raving. What I *am* claiming is
that it is exactly as clear as any explanation you may come up with of
what the phrase "the formal system PA" refers to.
Michael Weiss
system PA" without blushing, one shouldn't gag at "the integers". (Note
that one might accept "the integers" without qualms and still feel nauseous
at "the universe of sets".)
To clarify this point, I offer the following variation on PA:
1. There exists a first post in this thread.
2. For any post in this thread, there is a reply to it.
I believe (2); I'm not so sure about (1).
Brazil
>>edu. (Gregory McColm) writes:
>>
>> >From there, we get more problems. Suppose that you
>> >believe that the model of the integers exist. Is PA
>> >true on this model?
>>
>> What is PA? My explanation of the integers is simple: the integers
>>are 0, s(0), s(s(0)) and so on. Any obscurity or ambiguity that you
>>find in this explanation carries over to any explanation of what is
>>meant by "PA".
>
Don't forget their additive inverses.
/-------------------------------------------------------------------\
/ Believe me I would love to let you know, but..... \
/---------------------------------------------------------------------------\
| I'm not at liberty to tell you anything. |
\---------------------------------------------------------------------------/
\ Brazil : ma...@lily.csv.warwick.ac.uk :))) /
\-------------------------------------------------------------------/