Book Review: Naive Set Theory (MIRI research guide)

[-]Vladimir_Nesov10y90

When I first worked through this book, it didn't result in long-term retention of the material (I'm sure some people will be able to manage, just not me, not without meditating on it much longer than it takes to work through or setting up a spaced repetition system). In that respect, Enderton's Elements of Set Theory worked much better. Enderton's book goes into more detail, giving enough time to exercise intuition about standard proofs. At the same time, it's an easier read, which might be helpful if Halmos's text seems difficult.

[-]Tyrrell_McAllister10y70

In general, reading about the same subject from a different author is a great way to learn and retain the material better. This is true even if neither author is objectively "better" than the other. Something about recognizing the same underlying concept expressed in different words helps to fix that concept in the mind.

It's possible to exploit this phenomenon even when you have only one text to work with. One trick I use when working through a math text is to willfully use different notation in my notes next to the text. Using a different notation forces me to make sure that I'm really following the details of the argument. Expressing the same logic in different symbols makes it easier to see through those symbols to the underlying logic.

[-]David_Kristoffersson10y40

The author of the Teach Yourself Logic study guide agrees with you about reading multiple sources:

I very strongly recommend tackling an area of logic (or indeed any new area of mathematics) by reading a series of books which overlap in level (with the next one covering some of the same ground and then pushing on from the previous one), rather than trying to proceed by big leaps.

In fact, I probably can’t stress this advice too much, which is why I am highlighting it here. For this approach will really help to reinforce and deepen understanding as you re-encounter the same material from different angles, with different emphases.

[-]David_Kristoffersson10y40

Thanks for the tip. Two other books on the subject that seem to be appreciated are Introduction to Set Theory by Karel Hrbacek and Classic Set Theory: For Guided Independent Study by Derek Goldrei.

Edit: math.se weighs in: http://math.stackexchange.com/a/264277/255573

[-]Toggle10y70

I finished this book about four months ago, and time is making me increasingly glad that I read it. In particular, its treatment of countable infinities, functions, proof by induction, and the Peano axioms have been worth their weight in gold. When I encounter similar subjects 'out in the wild', I can approach them with relative skill and trust my intuitions in a way that I couldn't before. It's really growing on me.

That said, as a near-introduction to set theory, it was a very difficult read at times. It was a treatment of mathematics far deeper than I had come to expect from my university courses (which were largely in continuous mathematics, according to ancient engineers' tradition). If school has trained you to approach mathematical subjects as a tool the same way it did me, you'll need to adjust your expectations. This book is about virtuosity, not just surveying the tools.

[-]Andrew Quinn7y40

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.

I believe that what you are speaking of here is Halmos's discourse on what are called these days "images and preimages" or "inverse images". I found the subtle difference between these and inverse functions proper annoying when I was learning proof writing, so let me illustrate the concept, so that we have a caveat emptor for the budding mathematician.

Take the sets A = {0, 1} and B = {2}, and define a function f: A -> B as f(x) = 2 for whatever x in A you throw in there.

Then,

f(0) = 2, of course.
f(1) = 2, as well.
f(A) = {2}, which is the image of the whole set A "under" the function f.
f^{-1}(B) = {0, 1}, which is the pre-image of the whole set of B under f. Meaning, "anything I can throw into f, from A, to get something in B".
f^{-1}(2) , however, is meaningless, at least as far as functions go. Functions can only return one thing, so how would you decide whether f^{-1}(2) should give you back 0 or 1?

If you say f^{-1}(2) should give back both, well, now you're not dealing with an inverse function any more, you're dealing with the inverse relation. You can in fact deal with that, with some other tools in the book

These are more general, which is nice, but I've found that in a rigorous environment it won't do to describe them with the same language you use with functions. You really want to toy with these gently, if you can.

[-]gjm10y10

Are you sure that by "one-to-one" Halmos means "bijective"? A more common usage is for it to mean "injective". (But I don't have NST and maybe he has an unusual idiom.)

[-]Tyrrell_McAllister10y30

There is a convention according to which a one-to-one function is injective, while a one-to-one correspondence is an injective function that is also surjective, ie, a bijection. (I don't know whether Halmos uses this convention.)

[-]gjm10y10

Oh yes, for sure, but the context here was a statement that "onto" means surjective while "one-to-one" means bijective. Definitely talking functions. And I would be really surprised if Halmos were using "one-to-one" followed by anything other than "correspondence" to mean bijective.

[-]David_Kristoffersson10y00

You guys must be right. And wikipedia corroborates. I'll edit the post. Thanks.

[-]stoat10y20

Looks to me like Halmos does intend "one-to-one" to mean "injective". What he writes is "A function that always maps distinct elements onto distinct elements is called one-to-one (usually a one-to-one correspondence)." Then he mentions inclusion maps as examples of one-to-one functions.

[-]David_Kristoffersson10y00

My two main sources of confusion in that sentence are:

He says "distinct elements onto distinct elements", which suggests both injection and surjection.
He says "is called one-to-one (usually a one-to-one correspondence)", which might suggest that "one-to-one" and "one-to-one correspondence" are synonyms -- since that is what he usually uses the parantheses for when naming concepts.

I find Halmos somewhat contradictory here.

But I'm convinced you're right. I've edited the post. Thanks.

[-]ThisSpaceAvailable10y20

It is somewhat confusing, but remember that srujectivity is defined with respect to a particular codomain; a function is surjective if its range is equal to its codomain, and thus whether it's surjective depends on what its codomain is considered to be; every function maps its domain onto its range. "f maps X onto Y" means that f is surjective with respect to Y". So, for instance, the exponential function maps the real numbers onto the positive real numbers. It's surjective with respect to positive real numbers*. Saying "the exponential function maps real numbers onto real numbers" would not be correct, because it's not surjective with respect to the entire set of real numbers. So saying that a one-to-one function maps distinct elements onto a set of distinct elements can be considered to be correct, albeit not as clear as saying "to" rather than "onto". It also suffer from a lack of clarity in that it's not clear what the "always" is supposed to range over; are there functions that sometimes do map distinct elements to distinct elements, but sometimes don't?

LESSWRONG
LW

LESSWRONG
LW

23

Book Review: Naive Set Theory (MIRI research guide)

23

23

Naive Set Theory

Summary

Perspective of this review

How I read Naive Set Theory

Chapters

Axiom of extension

Axiom of specification

Unordered pairs

Unions and intersections

Complements and powers

Ordered pairs

Relations

Functions

Families

Inverses and composites

Numbers

The Peano axioms

Arithmetic

Order

Axiom of choice

Zorn's lemma

Well ordering

Transfinite recursion

Ordinal numbers

Sets of ordinal numbers

Ordinal arithmetic

The Schröder-Bernstein theorem

Countable sets

Cardinal arithmetic

Cardinal numbers

Concluding reflections