I am reading Paul Halmos's Naive Set Theory. Everything seems pretty fair and easy to me at the intuitive level but I am very lost at the technical level. I have one very basic question and one question where I cannot see a deduction.

What's the difference between $B= \left\{ x \in A : P(x)\right\} $ and $B= \left\{ x : x\in A \wedge P(x)\right\} $? Why is the latter not allowed, even though it still is FOL? Why does the latter not avoid Russell's paradox? Does this difference give us the idea that it is meaningful to ask whether or not $B \in A$? Is there where ZFC states that everything is a set? If yes, how? Excuse my ignorance but apologies in advance if these are unrelated questions.

Second question: Paul Halmos arrives at $B \not \in A$ for $P(x):=x \not \in x$ and goes on to state that nothing is contained in everything, given that the universe of discourse $A$ was arbitrary. I fail to see the conclusion.

P.S. This book does not give a rigorous definition of a set or the symbol "$\in$" in the start and most sources I have looked up are not very enlightening.

  • $\begingroup$ If you are going to be a working mathematician and not a set theorist, you dont need to worry about this distinction. I suggest understanding Russel's paradox and then see how ZFC handles it compared to NBG (wikipedia). I also found these details confusing in Halmos. $\endgroup$ – Rachmaninoff Feb 13 '15 at 7:03
  • $\begingroup$ And you may want to know that $\in$ is just a relation between any sets. Look at first-order languages (wikipedia). $\endgroup$ – Rachmaninoff Feb 13 '15 at 7:06
  • $\begingroup$ Well, frequently, many proofs refer to Zorn's lemma or some other equivalent. I just thought that the foundations ought not to be murky if I ever am going to get to use them myself. $\endgroup$ – Coward Feb 13 '15 at 7:41
  • $\begingroup$ I don't think Halmos is the best place to study about Zorn's lemma. He tries so hard to avoid ordinals that the result is terrifying. $\endgroup$ – Asaf Karagila Feb 13 '15 at 7:55
  • 1
    $\begingroup$ Broad enough to be practical, and very precise, and covers logic and model theory? No, I don't know anything like that. Try Enderton's book(s) on these topics, they seem to be very good. Discovering Modern Set Theory by Just and Weese is also a reasonable introductory book. $\endgroup$ – Asaf Karagila Feb 13 '15 at 11:04

What's the difference between $B= \left\{ x \in A : P(x)\right\} $ and $B= \left\{ x : x\in A \wedge P(x)\right\} $? Why is the latter not allowed, even though it still is FOL? Why does the latter not avoid Russell's paradox?

Hint: The set-builder notation may be clouding the issue. (It is not a part of FOL.) Note that you can easily obtain a contradiction from: $$\exists s: \forall x :[ x\in s \iff x\notin x] $$ You won't, however, obtain a contradiction from: $$\exists s:\forall x:[x\in s \iff [x\in A \land x\notin x]]$$ Note, too, that this will be the case for any binary relation $R$. You will get a contradiction from: $$\exists s: \forall x :[ R(x, s) \iff \neg R(x,x)] $$

But not from: $$\exists s:\forall x:[R(x,s) \iff [R(x,A) \land \neg R(x,x)]]$$

  • $\begingroup$ No contradiction? The book I referred to arrives at $B\not\in A$ for $P(x):=x\not\in x$ and goes on to state that nothing is contained in everything, given that $A$ was arbitrary. Doesn't that contradict the Axiom of Existence? $\endgroup$ – Coward Feb 16 '15 at 6:29
  • 1
    $\begingroup$ @Coward $B\notin A$ would be the correct conclusion. (Likewise $s\notin A$ or $\neg R(s,A)$ in my example.) "Nothing is contained in everything" is cute, but I prefer: No set includes everything. Or, every set excludes at least one thing. More formally:$$\neg \exists s: \forall x :x\in s $$ Or equivalently: $$\forall s: \exists x: x\notin s $$ $\endgroup$ – Dan Christensen Feb 16 '15 at 16:12

I haven't read Halmos's book on this, but I"m taking set theory right now, and the two seem identical . Written in the formal language of logic, they would stated as $\forall x((x\in B \rightarrow (x\in A \land P(x))\land (x\in A \land P(x))\rightarrow x\in B)$ I.e., the things in B are exactly the things in A for which P(x) holds.

Comprehension requires $A$ to be a set for this to work, $A$ cannot be the whole universe. Basically, it says that if you already have a set, then we can make a new set out that is a subset of the original set, the identifying characteristic being that some logical formula is true for those elements.

$\in $ just means "Is a member/element of"

Edit: A "set" in set theory is a very abstract term. It's basically anything that fits the axioms. You can take as a model of set theory $L$, which is the definable universe...in that model, pretty much everything is $\emptyset$, and powersets and unions and stuff of it.

Edit 2: Basically, set theory lives alongside the logical language that considers of the "standard" logical symbols of $\land,\lor,\lnot ,\rightarrow,\forall,\exists $ along with one additional symbol, $\in$. A set just "is", it doesn't have a concrete definition. The only things we can say about sets without the axiom is the relationship $\in$, which is a binary relationship: $x\in y$ says $x$ is an element of $y$, this is a logical statement, and has a truth value: true or false, depending on whether or not $x$ really is a member of $y$.

Different books/authors take as different axioms for set theory, they are generally equivalent. For instance, there's the axiom of the empty set, this asserts that the empty set exists. Formally, we would say $$\exists x\forall y(\lnot (y\in x))$$ This asserts the existance of the set $x$ with the property that for every single set in our universe $y$, $y$ is not an element of $x$.

Then, for convenience, we assign this set a label: $\emptyset$. This label is NOT in the language or the theory, it's just the choice of the particular $x$ for which this property holds.

Now, what tells us that there is only one such $x$? For that we need a second axiom, extensionality....this axiom states that two sets are equal if and only if their members exactly line up/are equal to each other. That justifies the label $\emptyset$, for there really is only one set with this property.

Subset another shorthand notation that's not in the language itself. $x\subseteq y$ is another logical statement that is either true or false, depending. It is a shorthand for the following logical statement: $$\forall z(z\in x \rightarrow z\in y)$$ I.e., all the elements of x are also elements of y.

Remember, in set theory, EVERYTHING in the universe is a set. So elements of sets are themselves sets. Here's an example of how something can be both an element and a subset: $\emptyset \in \{ \emptyset \}$ but we also have $\emptyset \subseteq \{ \emptyset \}$

  • $\begingroup$ Is the universe of discourse another abstract term in these axioms? What's a set, really? How is B a member of A when it is being considered as a subset? :/ $\endgroup$ – Coward Feb 13 '15 at 6:55
  • $\begingroup$ I'll edit the answer with more details on this $\endgroup$ – Alan Feb 13 '15 at 7:00
  • $\begingroup$ If $\in$ is a relation between sets, then how is the idea that $\pi$ is a real number made precise? $\left\{\pi\right\}\in\mathbb{R}$? But then Russell's paradox $x\not\in x$ becomes $\left\{ x\right\} \not\in\left\{ x\right\}$ which contradicts axiom of extensionality. $\endgroup$ – Coward Feb 13 '15 at 7:52
  • $\begingroup$ $\pi\in\mathbb R$ not $\{\pi\}\in \mathbb R$. This is a distinction you probably should know. In ZFC, finite numbers can be constucted using the empty set and the power set operation. We use the axiom of infinity to construct the natural numbers, then use equivalence relations to define integers and rationals and reals. So $\pi$ is a set constructed in this way. $\endgroup$ – Rachmaninoff Feb 15 '15 at 5:56
  • $\begingroup$ The real numbers is just a set of sets, eh? What's in the set $\pi$? $\endgroup$ – Coward Feb 16 '15 at 6:22

Although you're reading Halmos's book "Naive Set Theory." There's nothing really "naive" about your two sets

B = {x belonging to A: P(x)} and B = {x: x belongs to A and P(x)} as given.

Both your sets claim to separate from an arbitrary set A those sets which have the property P (or satisfies the formula P(x)). This done using the "Restricted" comprehension Axiom or Axiom of Specification

It is not un-natural to question as to whether or not the set A contains sets which are "not" members of themselves. After all, A is some arbitrary set. Perhaps A contains sets which are members of themselves and maybe sets which are not members of themselves or perhaps some other properties. At any rate, if A does contain such sets (i.e., sets which are not members of themselves), then we can use the Axiom of Specification to collect such elements in to one comprehensive set, namely, your sets B where P(x) is the set-theoretic formula x is not a member of x.

Thus, B = {x: x belongs to A and x is not a member of x}

           = {x belongs to A: **x is not a member of x**}

Let's think about this a little

From this arbitrary set A we used the Axiom of Specification to "separate" out those sets in A (if any) that are not members of themselves. It is possible that B was an element in this arbitrary set A from the start? (or it wasn't). Since we don't know, let's investigate.

If B was an element in A from the start, then the Axiom of specification selected it in forming B (i.e., B is a member in A) or it wasn't selected at all (i.e., B is not a member in A).

So if B was selected by Axiom of Specification as an element in A, then we have these two possibilities

      (B is a member of B) and (B is not a member in B)

Consider the possibilities separately:

If B is a member of B, then our assumption that B belongs to A yields B is not a member of B which is clearly a contradiction.

On the other hand, if B is not a member of B, then our assumption that B belongs to A, yields B is a member of B, again, a contradiction is reached.

Thus in both cases (under the assumption that B is a member in A) contradictions were obtained. Thus, it must follow that our assumption is false. Therefore, it must be that B is not a member of A as we wanted to show.

In other words, the Axiom of Specification avoids selecting from a Given set A the very set B (as an element in A beforehand). If it did, then then one can derive the "Set of all Sets"

But what we learned most of all from this is that there is no set which contains every set (i.e., a set of all sets does not exists in ZFC). In other words, according to Halmos

                 "nothing contains Everything"

PS: I hope this discussion sheds some insight to the answers to your questions.

  • $\begingroup$ It surely does. $\endgroup$ – Coward Feb 3 '17 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.