Show Book List

 

Melvin Fitting

Incompleteness in the land of sets

Gödel's incompleteness theorems can either be expressed in terms of integers, or in terms of set theory. In Incompleteness in the Land of Sets Melvin Fitting shows that links between the two approaches provide new insights into the theorems.

If you start with the empty set φ you can generate its power set {φ} an the power set of that,{φ,{φ}}. Repeatedly doing this generates the hierarchially finite sets, which have a natural representation as binary integers. But the natural numbers can also be generated by taking φ to be zero and defining each new number as the set of numbers generated so far. The book uses these two ways of linking numbers and sets to provide a useful way of looking at representation of numbers, or of logical statements, in terms of sets. It goes on to give a proof of Tarski's theorem and then to look at computability and axiomatics. This leads to a demonstration of Gödel's first incompleteness theorem.Up to this point the book wouldn't be too hard to follow for someone for someone knowing a bit of mathematical logic. The final three chapters delve deeper into the incompleteness theorems, looking at the relationship between soundness, provability and truth and at whether the proofs are constructive. There is also a look at how Rosser removed the need to assume ω-completeness and at Gödel's second incompleteness theorem. These chapters need a bit more work, but they do make some deep results accessible to the reader in a concise and pretty much self-contained book.

Amazon.com info
Paperback 156 pages  
ISBN: 1904987346
Salesrank: 1519002
Weight:0.5 lbs
Published: 2007 College Publications
Marketplace:New from $26.83:Used from $16.81
Buy from Amazon.com
Amazon.co.uk info
Paperback 156 pages  
ISBN: 1904987346
Salesrank: 2006986
Weight:0.5 lbs
Published: 2007 College Publications
Amazon price £15.00
Marketplace:New from £12.19:Used from £20.77
Buy from Amazon.co.uk
Amazon.ca info
Paperback 156 pages  
ISBN: 1904987346
Salesrank: 1778891
Weight:0.5 lbs
Published: 2007 College Publications
Amazon price CDN$ 29.39
Marketplace:New from CDN$ 22.91:Used from CDN$ 34.45
Buy from Amazon.ca





Product Description
Russell's paradox arises when we consider those sets that do not belong to themselves. The collection of such sets cannot constitute a set. Step back a bit. Logical formulas define sets (in a standard model). Formulas, being mathematical objects, can be thought of as sets themselves-mathematics reduces to set theory. Consider those formulas that do not belong to the set they define. The collection of such formulas is not definable by a formula, by the same argument that Russell used. This quickly gives Tarski's result on the undefinability of truth. Variations on the same idea yield the famous results of Gödel, Church, Rosser, and Post. This book gives a full presentation of the basic incompleteness and undecidability theorems of mathematical logic in the framework of set theory. Corresponding results for arithmetic follow easily, and are also given. Gödel numbering is generally avoided, except when an explicit connection is made between set theory and arithmetic. The book assumes little technical background from the reader. One needs mathematical ability, a general familiarity with formal logic, and an understanding of the completeness theorem, though not its proof. All else is developed and formally proved, from Tarski's Theorem to Gödel's Second Incompleteness Theorem. Exercises are scattered throughout.