The 3rd man from the left in the first row is the father of Barkley Rosser, Jr.
I have tried reading Rosser (1936), but I did not really understand the proof. As I understand it, Rosser puts some theorems of the time together to alter a theorem of Gödel's so that it's statement seems more natural. It is a very concise paper. Gödel shows that ω-consistency implies the existence of undecidable propositions. Rosser discarded the ω; he showed that consistency implies the existence of undecidable propositions. I guess there can be consistent systems that are not ω-consistent. Consistency is a syntactical property, and it does not require intuitions about universal quantification over all natural numbers.
Definition: A system is ω-inconsistent if and only if there exists a proposition p(n), with free variable n, such that
- p(0) is provable, p(1) is provable, p(2) is provable, and so on.
- It is provable that not ( for all n, p(n))
Definition: A system is ω-consistent if and only if it is not ω-inconsistent.
References
- Stephen B. Maurer (1985). "Albert Tucker", in Mathematical People: Profiles and Interviews (Ed. by D. J. Albers and G. L. Alexanderson), Birkhauser
- Barkley Rosser (1936) "Extensions of some Theorems of Gödel and Church", The Journal of Symbolic Logic, 1 (3), (September): 87-91.
Robert,
ReplyDeleteThanks for putting up this classic photo. For econmists there are several people in this photo of some interest. One is A.W. Tucker, of the Kuhn-Tucker theorem. He would also be the major professor of John Nash, coined the term "prisoner's dilemma," and was the long time Chairman of the Princeton math department who would later arrange for Nash to lurk about Fine Hall while still pretty out of it, as reported in the book version of _A Beautiful Mind_ (the movie version somehow divided Tucker's role between the character played by Judd Hirsch, who was a takeoff on an earlier dept. chair, Solomon Lefschetz, and Nash's friend, John Milnor).
Another figure of some interest is M.M. Flood, who with Dresher at RAND actually invented the concept of the prisoner's dilemma. They did one of the earliest of economic experiments, a 100-round repeated prisoner's dilemma game in which Armen Alchian and a mathematician whose name I forget now eventually learned to cooperate (the mathematician kept saying "what is the matter with Alchian? Can't he figure this out?"), although they would defect in the final rounds as predicted. This result reportedly upset Nash greatly, who was visiting at RAND at the time, and would lead him to abandon game theory eventually, supposedly, at least for awhile. He could not accept that people would behave so "irrationally" as to cooperate in violation of his equilibrium (which predicts that people defect in a P.D. game).
J. Barkley Rosser, Jr.
«Gödel shows that ω-consistency implies the existence of undecidable propositions.»
ReplyDeleteThat's consistent but not complete :-) his theorems have such a consequence, but its technical importance and its philosophical lack of importance (contrary to myths) depend on the correct formulation, which is not easy.
What the above says is that consistency implies incompleteness. But this is true only in a narrow hilbertian sense, and the reverse also is true, that completeness implies inconsistency.
But making some simplifications, I could say that he proved that if a formal system with the power of arithmetic is reinterpreted as its own proof system, it it possible to prove withing itself either its own consistency or completeness, but not both.
All the elements above are vital constituents of the the theorem, as it was a way to show that one of the elements of Hilbert's finitistic programme could not succeed.
As later logicians proved, Godel's theorem is merely a special case of a rather interesting general result, which says that it is possible to prove both the consistency and completeness of a logical system only by using for the proof a meta-logical system with strictly greater power of induction. So for example it is possible to prove both the consistency and completeness of a system with the power of finitistic induction by using a proof system admitting induction to the transfinites. That is Godel's theorems are just a subset of the Gentzen theorems.
Note that one can prove the completeness of a logical system within itself, at the price of inconsistency. Inconsistency is not such a bad deal -- after all essentially all maths is inconsistent in practice (that is many proofs are buggy :->). The study of awovedly inconsistent logical system is a little known brnahc of maths, and it is called the study of weak logic systems.
I just had a look at the relevant Wikipedia entries and I was astonished that they mostly seem to report the correct story, which is so little known.
Barkley,
ReplyDeleteA belated happy birthday. Mirowski has it that that experiment was conducted on John Williams and Alchian.
Blissex,
The math is advanced for me. I can see the point on insisting that there is no meta-mathematics, just more mathematics. And arguing about that what's syntax/grammar is not semantics. At least, I think these brief comments point to something that I'm probably misrepresenting in Wittgenstein. Even so, I think understanding Gödel early is quite impressive.
Robert,
ReplyDeleteThanks.
Blissex,
That one can prove both consistency and completeness from a higher level system does not imply that one cannot do so from within the system itself. That is what it appears that you are saying.
Barkley Rosser, (Jr.)
Being brought up by logicians, I understand all of this; the most fun way to learn it is through the books of Raymond Smullyan, which also lead you to several of the other key theorems on formal proof systems.
ReplyDelete