Prerequisites for Reading Halmos Naive Set Theory

I'm David. I'chiliad reading through the books in the MIRI enquiry guide and volition write a review for each as I finish them. Past mode of inspiration from how Nate did it.

Naive Set Theory

Halmos Naive Set Theory is a classic and dense piffling volume on axiomatic set theory, from a "naive" perspective.

Which is to say, the volume won't dig to the depths of formality or philosophy, it focuses on getting y'all productive with set up theory. The point is to give someone who wants to dig into advanced mathematics a foundation in set theory, as ready theory is a central tool used in a lot of mathematics.

Summary

Is information technology a good book? Yep.

Would I recommend information technology as a starting bespeak, if you would like to larn set theory? No. The volume has a terse presentation which makes information technology tough to digest if y'all aren't already familiar with propositional logic, perhaps set theory to some extent already and a bit of advanced mathematics in general. In that location are enough of other books that tin get you started at that place.

If you do have a somewhat fitting background, I recollect this should exist a very competent pick to deepen your understanding of set theory. The author shows you the basics and bolts of set theory and doesn't waste any time doing it.

Perspective of this review

I volition first refer you to Nate'southward review, which I found to be a lucid have on it. I don't want to be redundant and repeat the good points fabricated there, so I want to focus this review on the perspective of someone with a scrap weaker background in math, and try to requite 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 simply read about 2 months of mathematics at introductory university level, and not including detached mathematics. I practise have a thorough background in software development.

Fix theory has eluded me. I've simply picked upwardly fragments. It's seemed very fundamental just schoolhouse never gave me a expert opportunity to larn information technology. I've wanted to empathise information technology, which made it a joy to add Naive Set up Theory to the top of my reading listing.

How I read Naive Set Theory

Starting on Naive Fix 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 field of study of mathematics? What the heck is the writer expressing here?

I supplemented heavily with wikipedia, math.stackexchange and other websites. Sometimes, I read other sources fifty-fifty earlier reading the chapter in the book. At two points, I laid down the book in lodge to cease two other books. The commencement 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 information technology 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 try the task. So, I concluded I needed a better introduction to mathematical proofs, ordered some books on the bailiwick, and postponed investing into the exercises in Naive Set Theory until I had gotten that introduction.

Capacity

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 alluvion with content and there'due south enough additional sources available on the net. If you become stuck, practise try playing around with examples of sets on paper or in a text file. That'due south 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 incorporate the same elements. Different if they practise not.

Axiom of specification

The precept of specification allows you lot to create subsets by using atmospheric condition. This is pretty much what is done every time set builder note is employed.

Puzzled past the bit about Russell's paradox at the end of the chapter? http://math.stackexchange.com/questions/651637/russells-paradox-in-naive-prepare-theory-by-paul-halmos

Unordered pairs

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 gear up that contains all the members of the original sets.

Complements and powers

The axiom of powers allows one to, out of ane set, create a set containing all the different possible subsets of the original set.

Getting tripped upward about the "for some" and "for every" notation used by Halmos? Welcome to the guild:
http://math.stackexchange.com/questions/887363/axiom-of-unions-and-its-apply-of-the-existential-quantifier
http://math.stackexchange.com/questions/1368073/society-of-evaluation-in-conditions-in-set-theory

Using natural language rather than logical note is commmon practice in mathematical textbooks. You'd better get used to it:
http://math.stackexchange.com/questions/1368531/why-in that location-is-no-sign-of-logic-symbols-in-mathematical-texts

The existential quantifiers tripped me up a scrap before I absorbed it. In math, y'all can freely express something like "Out of all possible x always, give me the set of x that fulfill this condition". In programming languages, you tend to accept to be much more... specific, in your statements.

Ordered pairs

Cartesian products are used to correspond plenty of mathematical concepts, notably coordinate systems.

Relations

Equivalence relations and equivalence classes are of import concepts in mathematics.

Functions

Halmos is using some dated terminology and is in my eyes a flake inconsistent here. In modernistic usage, we accept: injective, surjective, bijective and functions that are none of these. Bijective is the combination of beingness 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" - yous might want to check another source there.

Families

This chapter tripped me up heavily because Halmos mixed in three things at the same time on page 36: 1. A confusing mode of talking about sets. 2. Convoluted proof. 3. due north-ary cartesian production.

Families are an alternative way of talking about sets. An indexed family is a set up, with an index and a role in the groundwork. A family of sets means a collection of sets, with an index and a role in the background. For Halmos build-upward to north-ary cartesian products, the deal seems to exist that he teases out order without explicitly using ordered pairs. Golf game clap. Try this one for the math.se handling: http://math.stackexchange.com/questions/312098/cartesian-products-and-families

Inverses and composites

The inverses Halmos defines here are more full general than the inverse functions described on wikipedia. Halmos' inverses work even when the functions are non bijective.

Numbers

The axiom of infinity states that at that place is a set of the natural numbers.

The Peano axioms

The peano axioms tin exist modeled on the the set-theoretic axioms. The recursion theorem guarantees that recursive functions exist.

Arithmetic

The principle of mathematical induction is put to heavy use in gild to define arithmetics.

Society

Fractional orders, total orders, well orders -- are powerful mathematical concepts and are used extensively.

Some help on the way:
http://math.stackexchange.com/questions/1047409/sole-minimal-element-why-not-also-the-minimum
http://math.stackexchange.com/questions/367583/example-of-fractional-order-thats-not-a-total-order-and-why
http://math.stackexchange.com/questions/225808/is-my-understanding-of-antisymmetric-and-symmetric-relations-correct
http://math.stackexchange.com/questions/160451/difference-between-supremum-and-maximum

Besides, keep in mind that infinite sets like subsets of w can muck up expectations about order. For example, a totally ordered prepare can have multiple elements without a predecessor.

Axiom of option

The axiom of choice lets you, from any drove of non-empty sets, select an chemical element from every gear up in the collection. The axiom is necessary to practice these kind of "choices" with infinite sets. In finite cases, ane tin construct functions for the job using the other axioms. Though, the axiom of pick frequently makes the job easier in finite cases so it is used where it isn't necessary.

Zorn'south lemma

Zorn's lemma is used in similar means to the axiom of option - 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.

Well ordering

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 actress status is useful when working with space sets.

The principle of transfinite induction ways that if the presence of all strict predecessors of an element always implies the presence of the element itself, and then the ready must contain everything. Why does this matter? Information technology ways you can brand conclusions about space sets beyond w, where mathematical induction isn't sufficient.

Transfinite recursion

Transfinite recursion is an analogue to the ordinary recursion theorem, in a similar style that transfinite induction is an analogue to mathematical induction - recursive functions for infinite sets beyond w.

In modernistic lingo, what Halmos calls a "similarity" is an "order isomorphism".

Ordinal numbers

The axiom of substitution is chosen the precept (schema) of replacement in modern utilise. It'south used for extending counting across due west.

Sets of ordinal numbers

The counting theorem states that each well ordered set is society isomorphic to a unique ordinal number.

Ordinal arithmetic

The misbehavior of commutativity in arithmetics with ordinals tells us a natural fact nearly ordinals: if you tack on an element in the offset, the result will be lodge isomorphic to what information technology is without that element. If you tack on an chemical element at the end, the set at present has a last element and is thus non order isomorphic to what yous started with.

The Schröder-Bernstein theorem

The Schröder-Bernstein theorem states that if Ten dominates Y, and Y dominates X, then X ~ Y (Ten and Y are equivalent).

Countable sets

Cantor's theorem states that every set always has a smaller primal number than the cardinal number of its ability ready.

Key arithmetic

Read this chapter afterward Fundamental numbers.

Cardinal arithmetic is an arithmetic where just about all the standard operators do nothing (beyond the finite cases).

Primal numbers

Read this affiliate earlier Central arithmetics.

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 side by side central number in the sequence is the power set of the previous ane.

Concluding reflections

I am at the same time humbled by the field of study 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 volition at present go through 1 or two books near mathematical proofs. I may return to Naive Ready Theory after that. If anyone is interested, I could mail service 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 Prepare Theory probably should be replaced by another introductory book on set theory in the MIRI inquiry guide. Merely that'due south 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 yous actually are.

The side by side book I first on from the inquiry guide is bound to exist Computability and Logic.

fernandezitimpookind.blogspot.com

Source: https://www.lesswrong.com/posts/FvA2qL6ChCbyi5Axk/book-review-naive-set-theory-miri-research-guide

Share this post