Logic: A Study Guide — Naive set theory

I’ve decided to divide the coverage of set theory in the Guide into three different chapters. There will now be two chapters in Part I. A short initial chapter on naive set theory, meaning the bits and pieces of notation, concepts and constructions that are often taken for granted in even very elementary logic books. Mathematicians shouldn’t need the chapter, but it could well be useful for philosophers without much mathematical background. This chapter therefore now comes before the chapters on FOL, model theory, and arithmetic. Then, after those chapters, there will be the main chapter on elementary set theory (a first real encounter at the level of e.g. Enderton’s book or a little more). A later chapter on hard-core set theory (large cardinals, forcing, and the like) belongs in Part III.

So I’ve now inserted the draft chapter on naive set theory (and made a few changes too to other chapters, responding to a few comments and suggestions). Here then is the current version of Part I of Logic: A Study Guide, still lacking its main chapter on set theory, which I hope will follow fairly shortly.

9 thoughts on “Logic: A Study Guide — Naive set theory”

  1. I think there are two different questions; a) whether relations and functions should be identified with sets (their extensions) and b) whether relations and functions are different kinds of thing (or not ‘things’ at all). Section 3.2 of Button’s lovely looking book makes the argument against a) on broadly Benacerrafian grounds. b) seems more controversial to me, but perhaps I wasn’t properly brought up! I’ve always thought of functions as special kinds of relations — ie relations with the functional property that Rab and Rac implies b = c. Perhaps my mind was polluted early on by Quine or someone like that …. I am interested though why there might be reasons to distinguish between a function and the corresponding relation. I wasn’t convinced by the ‘argument from grammar’ in the Gower’s blog post, though there was lots of food for thought in that post. I thought his argument for the different claim that the identification of functions with their set-theoretic extensions/graphs serves no really useful mathematical or conceptual purpose was a good one.

    Since you can quantify over and count functions and relations, I don’t have any problem about saying they are ‘things’. Though sure they are not the same kind of things as individuals. But again maybe I’m just showing my poor upbringing here!

    I found some typos:

    p.13, item (vi) “i.e. we regard properties with the same extension as **the** being the same property”

    p. 14, item (viii) ‘subjective’ should be ‘surjective’

    I wondered why you used fx = y instead of f(x) = y on page 13, item (vii)?

    I thought the section on ‘virtual classes’ was excellent and a really good thing to include.

      1. I think there’s a useful comment on the Gowers post from Tarence Tao. I mean this one which begins:

        My basic rule of thumb to determine whether an object X is “truly” a set, as opposed to merely being modeled or represented by a set, is to ask oneself whether a statement such as “x \in X” could conceivably be useful for doing mathematics; similarly, I would only view X as “truly” being a relation if sentences such as “x X y” could be viewed as useful mathematical statements.

        I also think your answer here is pretty good.

        I think Button’s §3.2, taken as a whole, makes things seem more complicated that is necessary, and (as said before) I think there’s a larger problem with his book in the way he runs naive and informal together.

        And I note that even Gowers happily writes “If f is a function” and “all functions from A to B“, as if we can after all treat functions in a noun-like way, despite the sophistry and misdirection of his “What is squared?” argument earlier.

      2. >> Yes, although I have views on (b), on second thoughts they really shouldn’t intrude here — so I’ll rewrite a bit to focus on (a).

        I’d be very interested to hear you thoughts on b). Perhaps in a new post?

        On the question of identifying functions with relations I suppose there’s a kind of arbitrariness about it similar to the arbitrariness of identifying functions with sets. If f(x) = y, there’s the relation Rxy and also the relation Ryx. The function could be either of those relations (though Quine argued that the latter is more natural).

    1. I thought his argument for the different claim that the identification of functions with their set-theoretic extensions/graphs serves no really useful mathematical or conceptual purpose was a good one.

      What does that say to people who do find it conceptually useful?

      In any case, Gowers pulls back quite a bit in the section Added later.

      1. >> What does that say to people who do find it conceptually useful?

        Yes, fair point. As Gowers says it does make it clearer that a function can be entirely arbitrary.

  2. * I’m not entirely happy with giving such prominence to “naive”. I’m not saying the term should be avoided completely, just that it’s better not to run “informal” and “naive” together, and that if what you mean is informal set theory, it’s better to call it that, reserving “naive” for aspects of early set theory that ran into trouble with paradoxes. (I had a similar issue with Tim Button’s text, as I tried to explain in a comment on your blog post about that book, contrasting his book with the lighter way “naive” was treated by Halmos and by Enderton.)

    * I’m wondering about the level of this section of the Guide since, it seems, the reader is assumed to know little, if anything, about elementary set theory but to understand logical notation and what is meant by φ(x) and “the condition expressed by φ“.

    * Why would “well-brought-up logicians will want to insist that functions and relations are different kinds of thing” or that “neither are strictly speaking things at all”? Saying that functions and relations aren’t objects, but extensions are, seems an odd place for logicians (or anyone) to draw so strong an ontological line — a problem not completely removed by an “in the way”.

    In any case, §3.2 of Button’s book says neither of those things. The Gowers blog post does say them, but I think it’s a terrible and tendentious presentation, full of sophistry and misdirection. Which is strange, since it also says reasonable things about “range” and “codomain”, which seem to have been the post’s main intended points.

    So rather than making “some of the needed points”, it makes dubious and unneeded ones; and what it shows is that some mathematicians have been influenced by questionable stuff from philosophy, have an antipathy to set theory, and imagine (fear?) that when people treat functions and relations as sets they’re doing metaphysics and are trying to say what functions and relations really are.

    All that is really needed here in the Guide — which is after all an introductory section about introductory aspects of set theory — is something like the last paragraph of Button’s §3.2.

    * Re (vii) “The extension (or graph) of a unary relation f” — should it be “unary function f“?

    * Is Halmos “much recommended”? I think it has significant problems (for instance) and that Enderton’s book, for instance, is much better.

    1. Many thanks for this, prompting some thought and re-reading (hence the delay in responding). On the main points:

      1. I’m persuaded that it is best to downplay “naive” (and to be clear that naive-qua-guided-by-informal-ideas-and-not-yet-put-in-regimented/axiomatized-form is to sharply distinguished from naive-qua-assuming-naive-comprehension). So some rewriting definitely needed here.

      2. “Saying that functions and relations aren’t objects, but extensions are, seems an odd place for logicians (or anyone) to draw so strong an ontological line” But exactly the standard Fregean position of course! (“Draw an ontological line” is a bit slippery: does that mean draw a line between what we countenance in our ontology, and what we reject? or does it mean draw a type-distinction within our ontology. For the Fregean, the function/object distinction is of course of the second kind.) But again, I agree that maybe a few comments about elementary readings on sets isn’t the place to get entangled in this sort of issue.

      3. On Tim Gowers, he is indeed interested in conceptual issues, but I wouldn’t have him down as one of those mathematicians who “have been influenced by questionable stuff from philosophy, have an antipathy to set theory”. But I’ll remind myself more carefully of what he says.

      4. I agree that Enderton’s book is particularly good (and that Halmos’s gloss on what he is doing — set theory to be forgotten about after! — verges on the silly). But with respect to his actual light-weight presentation of set theoretic ideas, I think Halmos will still be very useful for some. Again though, I’ll remind myself more carefully of what he says.

      1. Re (2) Many people are now familiar from programming languages with the idea of functions that have functions as arguments or return them as results (which of course goes back at last as far as lambda calculus). How would that work if functions aren’t objects?

        Perhaps there is a level issue again. Perhaps people who’ve absorbed a lot of Frege will see your post as as merely making a type distinction. I don’t know. Still, what you wrote started by saying that “functions and relations are different kinds of thing” (a type distinction) and then went on to say neither are “strictly speaking things at all”. I think that many people will naturally read the statement that they aren’t “things at all” as saying they don’t exist (and that will carry over into the statement that they aren’t objects).

        Much the same goes for the Gowers version:

        … the reason I hate it is that functions and relations are, to any reasonable person, different kinds of things, except that I don’t want to call them things at all, …

        Re (3) The strength of his desire to minimise the role of sets in ‘everyday mathematics’, evidenced by the vehemence of his language about a fairly innocuous case (“of no use whatsoever”), suggests a certain antipathy. (Compare the language in Button or in the Terence Tao comment and your math.stackexchange answer that I linked earlier.)

        And if he hasn’t been influenced by questionable stuff from philosophy, then where does he get the idea that his (ontological) view that functions aren’t relations follows from the sort of ‘grammar’ points he makes, or the tactic of using constructions designed to seem unnatural (such as “My car is a green”), as if hoping people don’t remember cases that might actually occur (“the sea was a deep green, the sky a blue so pale it matched the clouds”)?

        Then consider his claim that his “1 and 3 demonstrate that the grammar of functions is not the same as the grammar of relations.” Here are his 1 and 3:

        1. If f:A \to B and x denotes an element of A, then f(x) denotes an element of B.

        3. If ~ is a relation on A\times B, x is an element of A, and y is an element of B, then x ~ y is a statement.

        Why “denotes” in 1 but not 3? And is something like 1a below supposed to be ungrammatical?

        1a. If f is a function from A \to B, and x is an element of A, then f(x) is an element, b, of B, and f(x) = b is a statement.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top