NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/sci/math/14908

Internet Message Format | 1992-11-13 | 13.7 KB

Path: sparky!uunet!utcsri!eecg.toronto.edu!leemike
Newsgroups: sci.math
From: [e-mail] (Michael Lee)
Subject: Re: Logic and Mathematicians (quite long)
Message-ID: <[e-mail]>
Organization: CSRI, University of Toronto
Distribution: sci.math
Date: 13 Nov 92 14:01:26 GMT
Lines: 273

re: zelany's reponse to [e-mail]:
note: `>' represents the statements of [e-mail]
      `|' represents some of zelany's statements

I'm working from zelany's posting (see above).  Hence, if I have
misinterpreted the originator of this thread, feel free to correct
any errors.

>I just had an interesting discussion about the
>fear mathemicians have of logic (and logicians):
>
>Many, if not most, "great" logicians did not
>"solve problems", as one usually does in mathematics,
>in that someone states a problem, and a the you go
>ahead and solve it (positively or negatively);
>furthermore, their solutions are more
>instructive in themselves than the original problems
>where and they not only develop new concepts
>to solve an existing problem (this is commonplace
>in mathematics), but rather invent a new concept which
>they think is interesting IN ITSELF, prove something about it,
>and incidentially some open problem follows as a
>corollary. In fact, more often than not, they do
>not solve problems in the usual sense, but they
>say something about the problem itself, eg, that
>it was mis-posed, mis-conceived, or is meaningless.
>
>Examples: G"odel's Incompleteness Theorems:
>He INVENTED the concepts of undecidability of
>a sentence in a theory and of incompleteness.

In full, Godel's paper, `On Formally Undecidable Propositions
of Principia Mathematica and Related Systens', dealt with the
problem of consistency of a given set of axioms and the transformation
rules of a given system, i.e., these axioms and the transformation
rules do not lead to a theorem which is both true and false.  Suppose
that in a given set of axioms and the corresponding transformation
rules, a theorem and the negation of that theorem can be derived.
Certainly, this result would imply that any formula is deducible
from the hypothetical set of axioms, which would indeed pose serious
problems for the system derived from these axioms - essentially burning
down the entire tree and its entire root system and salting the ground
where it once stood.  Hence the need for a consistent set of axioms
to support the structure of mathematics and the method which can prove
the consistency of a given set of axioms - from this point onwards
when I mention axioms, I also imply a set of transformation rules.  This
method to prove the consistency of a set of axioms in a rigorous fashion
of all classical branches of mathematics was first conceived (I believe)
by Hilbert and was know as Hilbert's program.  Hilbert's program was to
demonstrate, with finistic methods, in a given calculus certain that
contradictory derivations were impossible and hence consistent.
His conception was the construction of an absolute proof which was based
upon the complete formalization of a deductive system.  From Hilbert's
program arose Whitehead's and Russell's `Principia Mathematica' which
purported to be the final solution of the problem of consistency.
Also, we must keep in mind Boole's `The Mathematical Analysis of Logic'
initiating, some would argue, the renaissance of modern logical studies.
The work of Boole, Hilbert, Whitehead and Russell, and others such as
Frege, provide the background and foundation on which Godel based his paper,
as well, the terms, you purported that Godel invented did not come from
nowhere - the terms such as `undecidability' and `incompleteness' had their
roots from the aforementioned background.

I think, I've given enough background.  I won't mention the distinction
between meta-mathematics and mathematics, insofar as to state that
meta-mathematics, as defined by Hilbert, is concerned with meaningful
statements about mathematics, their signs, and their arrangement, relation,
and classes; whereas mathematics is the configuration of symbols or a
system of symbols.  Meta-mathematically, we may ask, `for a given set of
axioms and their set of inference rules, is the set consistent?'.

>The interesting sentence (from the logical, and
>also from G"odels standpoint) is the FIRST
>incompleteness theorem (Why else did G"odel
>entitle his paper "On undeciadable propositions"?
>If he were interested more in consistency,
>he would have titled it "The Unprovability of
>Consistency" or something).

Your suggestion, i.e., the latter title would of implied something Godel
did not prove.  His incompleteness theorem shows that within a
consistent set of arithmetical axioms there is at least one true
arithemetical statement which cannot be derived from the set.  Hence
the apt term `undecideable'.  Furthermore, he showed that it is impossible
to give a meta-mathematical proof of consistency of a system to span
the whole of arithmetic unless the proof utilizes rules of inference
which are different than and exists outside of the transformation rules
which are used to derive the theorems of the system.  Of course, such a
proof would be valuable on its own but would probably violate Hilbert's
program that of finistic proof.  Also, it wouldn't really solve the
question at hand, inference rules more powerful than simple arithmetical
calculus may lead us to doubt the consistency in the reasoning itself
shifting our focus from the consistency of the axioms to the consistency of
the reasoning.  Whatever Godel's initial intent may be, his paper isn't
trying to disprove axiomatic consistency but map-out the boundaries, its
limits.

>From the mathematician's
>viewpoint, the proof is trivial: A simple
>diagonalization argument (in Kreisel's words).

I'm not certain of your term `simple diagonalization.'  From my perspective,
I found the proof difficult to read and understand, I found nothing
trivial about his proof.  He completely arithmetized a formal calculus
and established a one-to-one correspondence between the expressions
of a calculus and a particular subset of integers.  By doing so,
meta-mathematical expressions and their relations to one another is
mirrored through their corresponding integer (Godel's number) and
their arithmetical relations to one another.  On a trivial note, however,
his method is a kin to receiving a unique number from a sequential set upon
entry to a busy deli.  By the given number we can tell how many have been
served, who precedes whom, and by how many, the total number of custumers,
etc.  Hence, we've arithmetized the deli service and can ask arithmetic
questions which directly reflect its operation.  If the triviality of
an idea is based on its most banal application then all of mathematics
fall under the general heading of banality.

>Yet, Hilbert (and others) were very much taken by
>surprise. In a sense, incompleteness says:
>"The concept of consistency is not important"

Why wouldn't he be surprised?  Godel demonstrated that his proposal
on a finistic absolute proof for every deductive system is highly
unlikey.  Godel, also, showed that inifinite bits of true arithmetical
expression can not be formally be deduced from a given set axioms by a
closed set of inference rules.  Yet still, the concept of consistency is
possible along Hilbert's proposal; Godel proof doesn't logically conclude
the impossibility of `consistency' nor does it directly address the
importance, or the lack thereof, of `consistency'.  Although, Godel
didn't say Hilbert's proposal was impossible, he did flesh out its
intractable characteristics.

Suffice to say, consistency for a mathematician or a logician is important;
what would be the point, if it was otherwise?

>The consistency of CH: is a corollary of
>the consistency of V = L. And L is G"odel's
>invention. Also it says (together with Cohen's result),
>that the question of whether CH holds or not
>is meaningless.

I'm not familiar with the above notation; CH you probably represents
continuum hypothesis, as for V = L, I haven't a clue.

|It may say this to Cohen, who allegedly convinced himself to become a
|formalist in the wake of his independence results, but G\"odel's
|opinion most certainly differed.

Didn't Cohen have to say something about Cantor's conjecture of
the continuum hypothesis (the set of all subsets of real numbers
is the same size as the set of all real numbers), i.e., the continuum
hypothesis resides outside the axioms of usual (Zermelo and Fraenkel)
set theory.  Hence, if set theory is the basis of all mathematics, the
continuum hypothesis may be true for some mathematics and false for
others.

>The undecidability of predicate logic from
>Turing's work: The really important part of his
>paper were the "Computable Numbers", not
>the "Application to the Entscheidungsproblem".
>And he MADE UP Turing machines etc. Again,
>easy theorems, difficult concepts requiring
>deep insight.

|You can add Church and Kleene to the same list.

I think you're talking of the first-order predicate logic, which was
shown to be complete by Godel and then undecidable by Church and
Turing by different methods.

>Gentzen's sequent calculus: his invention. Totally
>disconnected from anything that had been done before.
>Required deep insight into the nature of logic
>to come up with. The "problems", eg, Herbrand's
>Theorem, were easy corollaries of the Hauptsatz,
>which, in itself, was easy to prove. But how do
>you come up with the Hauptsatz in the first place?

How is Gentzen's work totaly disconnected from anything?

|Who knows? presumably, the same way you get to the Carnegie Hall...
|It is said that Cohen deliberately chose to attack Hilbert's First
|Problem in order to get the Fields Medal.  However, I rather doubt
|that the same technique would have worked for the average Joe Schmoe.

>I'm not sure myself what I'm trying to get at,
>nor what I'm trying to say, so please take what I say
>cum grano salis. Some questions:
>
>(1) Is this really a difference in the way logic works
>to how mathematics works? (I realize that most of what's
>done in logic is not of the kind described above,
>but more "mathematical", in this sense)

No, most of the stuff you described was some of the stuff of logicism,
formalism, and probably intuitionism about 60 to 50 years ago.  I'm not
sure what the current state of affairs is in now.  I would expect that
the lines between formalism, intuitionism, and logicism have blurred
somewhat since the days of Hilbert, Brouwer, and Russell, the principle
proponents of the three schools.

|This question seems to be more appropriate for sci.math.  I'll add
|some questions of my own: Is Cantor best regarded as primarily a
|mathematician, a logician, or a philosopher?  (So much of his success
|seems to be due to his reading of Spinoza and the Scholastics.)  Is
|the anti-logicist mathematical structuralism exemplified by Bourbaki
|generally thought to be possessed of any genuine mathematical content,
|or is its main contribution purely formalistic in nature?  (One
|seemingly pervasive philosophical doctrine apparently due to Bourbaki

Bourbaki was a pseudo-name used by a group of mathematicians whose
principle members were Weil, Cartan, Eilenberg, Grothendeick; there
probably others but I can't recall their names.

|is the supplanting of absolute numerical identity with mere structural
|congruence, i.e.  isomorphism.)

I think with the Bourbaki group, the proof is in the pudding.  They
published a ton of stuff on algebra completing a new kind of algaebraic
topology and proving the Weil conjectures.  They basically cleaned
up algaebraic topology by framing it axiomatically.

>(2) If yes, is that because logic is a relatively
>young field? Were the mathematical couterparts
>of these results the early results, say the
>invention/discovery of: variables/algebra/the infinite/etc?

|Why is logic a relatively young field?  Aristotle was as much of a
|formal logician as G\"odel & Co.  Perhaps you mean *mathematical*
|logic, as characterized e.g. by Schr\"oder's relation calculus,
|Peirce's quantifiers, Frege's analysis of the proposition as a truth
|function, Sch\"onfinkel's (somewhat complementary) discovery of the
|combinators, Church's formulation of \lambda-calculus, or Tarski's
|definition of satisfaction.  Indeed, in this sense the life work of
|the logicians mentioned can be seen as uniformly stemming from these
|conceptual discoveries.  On the other hand, your own example of Cohen
|seems to give lie to the thesis of relative unimportance of
|problem-solving, -- by far, his most important logical contribution is
|the methodological notion of forcing.  Likewise, diagonalization could
|only have appeared as trivial after Cantor's initial discovery
|thereof.

True, however, I key figure in 20th century mathematics was probably
Godel.  He basically crushed many preconceptions, mathematicians
may have nurtured, and created a good size crack in the shiny armour
of mathematics.  In terms of a mathematician what could be more
exciting or disconcerting than that.

>(3) Are there more recent examples of such fundamental
>findings which cast a problem in a different
>light, maybe made it seem a silly problem to pose
>in the first place?

You'll have to examine the history of mathematics to answer that one, but
I'll hazard a guess that a fundamental finding didn't all of a sudden
transform a problem into utter nonsense.

|I offer Post's problem as a counterexample.  Also, it doesn't seem
|that there could be a solution for "P =? NP" that would render the
|problem silly in retrospect.

>--
>Richard Zach                         Technische Universitaet Wien
>[[e-mail]]     Abteilung fuer Formale Logik 185.2

|cordially,
|mikhail [e-mail]
|" -- I shall speak bluntly, because life is short."

regards,
michael lee