Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.
Naive Set Theory
Halmos Naive Set Theory is a classic and dense little book on axiomatic set theory, from a "naive" perspective.
Which is to say, the book won't dig to the depths of formality or philosophy, it focuses on getting you productive with set theory. The point is to give someone who wants to dig into advanced mathematics a foundation in set theory, as set theory is a fundamental tool used in a lot of mathematics.
Is it a good book? Yes.
Would I recommend it as a starting point, if you would like to learn set theory? No. The book has a terse presentation which makes it tough to digest if you aren't already familiar with propositional logic, perhaps set theory to some extent already and a bit of advanced mathematics in general. There are plenty of other books that can get you started there.
If you do have a somewhat fitting background, I think this should be a very competent pick to deepen your understanding of set theory. The author shows you the nuts and bolts of set theory and doesn't waste any time doing it.
Perspective of this review
I will first refer you to Nate's review, which I found to be a lucid take on it. I don't want to be redundant and repeat the good points made there, so I want to focus this review on the perspective of someone with a bit weaker background in math, and try to give some help to prospective readers with parts I found tricky in the book.
What is my perspective? While I've always had a knack for math, I only read about 2 months of mathematics at introductory university level, and not including discrete mathematics. I do have a thorough background in software development.
Set theory has eluded me. I've only picked up fragments. It's seemed very fundamental but school never gave me a good opportunity to learn it. I've wanted to understand it, which made it a joy to add Naive Set Theory to the top of my reading list.
How I read Naive Set Theory
Starting on Naive Set Theory, I quickly realized I wanted more meat to the explanations. What is this concept used for? How does it fit in to the larger subject of mathematics? What the heck is the author expressing here?
I supplemented heavily with wikipedia, math.stackexchange and other websites. Sometimes, I read other sources even before reading the chapter in the book. At two points, I laid down the book in order to finish two other books. The first was Gödel's Proof, which handed me some friendly examples of propositional logic. I had started reading it on the side when I realized it was contextually useful. The second was Concepts of Modern Mathematics, which gave me much of the larger mathematical context that Naive Set Theory didn't.
Consequently, while reading Naive Set Theory, I spent at least as much time reading other sources!
A bit into the book, I started struggling with the exercises. It simply felt like I hadn't been given all the tools to attempt the task. So, I concluded I needed a better introduction to mathematical proofs, ordered some books on the subject, and postponed investing into the exercises in Naive Set Theory until I had gotten that introduction.
In general, if the book doesn't offer you enough explanation on a subject, search the Internet. Wikipedia has numerous competent articles, math.stackexchange is overflowing with content and there's plenty additional sources available on the net. If you get stuck, do try playing around with examples of sets on paper or in a text file. That's universal advice for math.
I'll follow with some key points and some highlights of things that tripped me up while reading the book.
Axiom of extension
The axiom of extension tells us how to distinguish between sets: Sets are the same if they contain the same elements. Different if they do not.
Axiom of specification
The axiom of specification allows you to create subsets by using conditions. This is pretty much what is done every time set builder notation is employed.
Puzzled by the bit about Russell's paradox at the end of the chapter? http://math.stackexchange.com/questions/651637/russells-paradox-in-naive-set-theory-by-paul-halmos
The axiom of pairs allows one to create a new set that contains the two original sets.
Unions and intersections
The axiom of unions allows one to create a new set that contains all the members of the original sets.
Complements and powers
The axiom of powers allows one to, out of one set, create a set containing all the different possible subsets of the original set.
Getting tripped up about the "for some" and "for every" notation used by Halmos? Welcome to the club:
Using natural language rather than logical notation is commmon practice in mathematical textbooks. You'd better get used to it:
The existential quantifiers tripped me up a bit before I absorbed it. In math, you can freely express something like "Out of all possible x ever, give me the set of x that fulfill this condition". In programming languages, you tend to have to be much more... specific, in your statements.
Cartesian products are used to represent plenty of mathematical concepts, notably coordinate systems.
Halmos is using some dated terminology and is in my eyes a bit inconsistent here. In modern usage, we have: injective, surjective, bijective and functions that are none of these. Bijective is the combination of being both injective and surjective. Replace Halmos' "onto" with surjective, "one-to-one" with injective, and "one-to-one correspondence" with bijective.
He also confused me with his explanation of "characteristic function" - you might want to check another source there.
This chapter tripped me up heavily because Halmos mixed in three things at the same time on page 36: 1. A confusing way of talking about sets. 2. Convoluted proof. 3. n-ary cartesian product.
Families are an alternative way of talking about sets. An indexed family is a set, with an index and a function in the background. A family of sets means a collection of sets, with an index and a function in the background. For Halmos build-up to n-ary cartesian products, the deal seems to be that he teases out order without explicitly using ordered pairs. Golf clap. Try this one for the math.se treatment: http://math.stackexchange.com/questions/312098/cartesian-products-and-families
Inverses and composites
The inverses Halmos defines here are more general than the inverse functions described on wikipedia. Halmos' inverses work even when the functions are not bijective.
The axiom of infinity states that there is a set of the natural numbers.
The Peano axioms
The peano axioms can be modeled on the the set-theoretic axioms. The recursion theorem guarantees that recursive functions exist.
The principle of mathematical induction is put to heavy use in order to define arithmetic.
Partial orders, total orders, well orders -- are powerful mathematical concepts and are used extensively.
Some help on the way:
Also, keep in mind that infinite sets like subsets of w can muck up expectations about order. For example, a totally ordered set can have multiple elements without a predecessor.
Axiom of choice
The axiom of choice lets you, from any collection of non-empty sets, select an element from every set in the collection. The axiom is necessary to do these kind of "choices" with infinite sets. In finite cases, one can construct functions for the job using the other axioms. Though, the axiom of choice often makes the job easier in finite cases so it is used where it isn't necessary.
Zorn's lemma is used in similar ways to the axiom of choice - making infinite many choices at once - which perhaps is not very strange considering ZL and AC have been proven to be equivalent.
robot-dreams offers some help in following the massive proof in the book.
A well-ordered set is a totally ordered set with the extra condition that every non-empty subset of it has a smallest element. This extra condition is useful when working with infinite sets.
The principle of transfinite induction means that if the presence of all strict predecessors of an element always implies the presence of the element itself, then the set must contain everything. Why does this matter? It means you can make conclusions about infinite sets beyond w, where mathematical induction isn't sufficient.
Transfinite recursion is an analogue to the ordinary recursion theorem, in a similar way that transfinite induction is an analogue to mathematical induction - recursive functions for infinite sets beyond w.
In modern lingo, what Halmos calls a "similarity" is an "order isomorphism".
The axiom of substitution is called the axiom (schema) of replacement in modern use. It's used for extending counting beyond w.
Sets of ordinal numbers
The counting theorem states that each well ordered set is order isomorphic to a unique ordinal number.
The misbehavior of commutativity in arithmetic with ordinals tells us a natural fact about ordinals: if you tack on an element in the beginning, the result will be order isomorphic to what it is without that element. If you tack on an element at the end, the set now has a last element and is thus not order isomorphic to what you started with.
The Schröder-Bernstein theorem
The Schröder-Bernstein theorem states that if X dominates Y, and Y dominates X, then X ~ Y (X and Y are equivalent).
Cantor's theorem states that every set always has a smaller cardinal number than the cardinal number of its power set.
Read this chapter after Cardinal numbers.
Cardinal arithmetic is an arithmetic where just about all the standard operators do nothing (beyond the finite cases).
Read this chapter before Cardinal arithmetic.
The continuum hypothesis asserts that there is no cardinal number between that of the natural numbers and that of the reals. The generalized continuum hypothesis asserts that, for all cardinal numbers including aleph-0 and beyond aleph-0, the next cardinal number in the sequence is the power set of the previous one.
I am at the same time humbled by the subject and empowered by what I've learned in this episode. Mathematics is a truly vast and deep field. To build a solid foundation in proofs, I will now go through one or two books about mathematical proofs. I may return to Naive Set Theory after that. If anyone is interested, I could post my impressions of other mathematical books I read.
I think Naive Set Theory wasn't the optimal book for me at the stage I was. And I think Naive Set Theory probably should be replaced by another introductory book on set theory in the MIRI research guide. But that's a small complaint on an excellent document.
If you seek to get into a new field, know the prerequisites. Build your knowledge in solid steps. Which I guess, sometimes requires that you do test your limits to find out where you really are.
The next book I start on from the research guide is bound to be Computability and Logic.
View more: Next