22
$\begingroup$

From Halmos's Naive Set Theory, section 1:

Observe, along the same lines, that inclusion is transitive, whereas belonging is not. Everyday examples, involving, for instance, super-organizations whose members are organizations, will readily occur to the interested reader.

Belonging seems transitive. Can someone explain?

$\endgroup$
  • 12
    $\begingroup$ Well, consider the given example. Bob may be a Boy Scout, hence a member of the Boy Scouts. And the Boy Scouts may be a member of a group of like minded organizations. But Bob himself will not be a member of that broader group. $\endgroup$ – lulu Sep 14 at 0:42
  • 10
    $\begingroup$ Similar example: John Smith, Esq. is a member of the Florida Bar Association, and the Florida Bar Association is a member of the Council of American Bar Associations. Does that necessarily mean John Smith, Esq. is directly a member of the Council of American Bar Associations? $\endgroup$ – Daniel Schepler Sep 14 at 0:46
  • 2
    $\begingroup$ Another is that New York has representation in United States policy which has representation in United Nations policy but New York does not have representation in the UN. $\endgroup$ – John Douma Sep 14 at 0:49
  • 2
    $\begingroup$ I wouldn't say that "all" would change anything. Try this variant: I belong to country X, in that I am a citizen of $X$. $X$ belongs to the United Nations in that $X$ is a member nation of that organization. But I am not a member of the UN. $\endgroup$ – lulu Sep 14 at 12:12
  • 9
    $\begingroup$ To be clear, this all depends on what you mean by "belonging". if you define "belonging" in such a way that it is a synonym of "included in" then of course it is transitive. I don't know if the author gave a formal definition of "belonging" or not, but the examples illustrate sensible, non-transitive uses of the term. $\endgroup$ – lulu Sep 14 at 12:16

10 Answers 10

44
$\begingroup$

The difference between $\subset$ and $\in$ is that the former applies to expressions at the same level of nesting and the latter applies to expressions at one level of nesting apart from each other. So when you chain two $\in$'s together you get something at two levels of nesting, which is not in general comparable to a single $\in$. On the other hand, since $\subset$ doesn't change the level of nesting it doesn't have this problem.

This is the idea behind the example given in other answers of $$ \varnothing\in \{\varnothing\}\in \{\{\varnothing\}\},\qquad \varnothing \not\in \{\{\varnothing\}\}. $$

$\endgroup$
  • $\begingroup$ great answer. I do get the point. Just a minor suggestion if you want to revise your answer is that the nesting levels are not necessarily the same in $\subset$ case. As an example, $A \subset B$ when $A = \left \{ 'apple' \right \} $ and $B= \left \{ 'apple', 'banana' , 'lemon' \right \}$ . In this example , B is one-level above A because B is outside the braces while A is inside. Your answer will still hold given what scheme we choose to express $\subset$ and $\epsilon$ in. $\endgroup$ – New Student Sep 15 at 5:20
  • 4
    $\begingroup$ @NewStudent What do you mean by "$B$ is outside the braces while $A$ is inside" in your example? $\endgroup$ – JiK Sep 15 at 13:43
  • $\begingroup$ @JiK , I am referring to the number of nesting levels A and B are apart. If you notice in this example, B is one level above A. I made an error in my earlier comment when I defined B. B is correctly defined as follows: $B= \left \{ \left \{ 'apple' \right \}, 'banana' , 'lemon' \right \}$ $\endgroup$ – New Student Sep 15 at 20:54
  • 5
    $\begingroup$ @NewStudent If $A = \{ \mathsf{apple} \}$ and $B = \{ \{ \mathsf{apple} \}, \mathsf{banana}, \mathsf{lemon} \}$, then $A \in B$ but $A \nsubseteq B$, because $\mathsf{apple} \in A$ but $\mathsf{apple} \notin B$. $\endgroup$ – wchargin Sep 15 at 21:28
  • 2
    $\begingroup$ @NewStudent The rigorous definition is that $A \subseteq B$ if for every element $x$ that belongs to $A$ (that is, $x \in A$), it is also true that $x\in B$. $\endgroup$ – JiK Sep 16 at 11:07
45
$\begingroup$

A vertex of a triangle belongs to the triangle. A triangle belongs to the set of all triangles. But, a vertex is not itself a triangle.

$\endgroup$
  • 12
    $\begingroup$ I suggest changing the last sentence to read "But a vertex does not belong to the set of all triangles". Or, append "and thus does not belong to the set of all triangles". $\endgroup$ – Greg Martin Sep 15 at 5:09
  • $\begingroup$ Clear example, thanks $\endgroup$ – Stilez Sep 16 at 18:35
  • $\begingroup$ @GregMartin Is that addendum just intended to solidify the meaning of John's answer or is there a difference between the two statements that I'm missing? It seems to me that "X is not a Y" and "X is not in the set of Ys" are equivalent but one is in more conversational language. $\endgroup$ – Jam Sep 17 at 12:48
  • $\begingroup$ @GregMartin I agree that your suggestion is marginally more clear, but I was aiming for a very concise example. For that reason, I prefer the current wording. $\endgroup$ – John Coleman Sep 17 at 13:12
  • $\begingroup$ Greg Martin's suggestion is way clearer, the current wording is a little incomplete. I literally had the exact same thought (as his second suggestion) without reading his comment, word for word, upon seeing your answer. $\endgroup$ – Apollys Sep 17 at 22:20
21
$\begingroup$

$42 \in \mathrm{Even} \in \mathcal{P}(\mathbb{Z})$ but $42 \not\in \mathcal{P}(\mathbb{Z})$ because 42 is not a set of integers.

$\text{Peter} \in \text{Humans} \in \text{Species}$ but $\text{Peter} \not\in \text{Species}$ because Peter is not a species.

$\endgroup$
19
$\begingroup$

Let $y=\{\emptyset\}$. And $x=\{y\}$. Then $\emptyset\in y$ and $y\in x$, but $\emptyset\not\in x$.

$\endgroup$
  • 14
    $\begingroup$ $a\not\in x$, as I had written. $\endgroup$ – Chris Custer Sep 14 at 2:31
  • 1
    $\begingroup$ Problematic example: without additional conditions, you could have $a=y$ (a Quine atom), and then $a\in x$ after all. $\endgroup$ – Andrés E. Caicedo Sep 14 at 17:38
  • 2
    $\begingroup$ @Andrés so I guess I should assume I don't have a "Quine atom". $\endgroup$ – Chris Custer Sep 14 at 18:42
  • 2
    $\begingroup$ Yes, or even better, you could first argue that there are things that are not Quine atoms, and then assume that $a$ is one of them. $\endgroup$ – Andrés E. Caicedo Sep 14 at 18:45
  • 1
    $\begingroup$ @AndrésECaicedo suppose I replace $a$ by $1$, say. Would that clear things up? $\endgroup$ – Chris Custer Sep 14 at 20:09
9
$\begingroup$

Consider the empty set $\phi,$ which has no members. And $x=\{\phi\}$ has one member (namely, $\phi$ is the only member of $x$). And let $y=\{x\}.$

So $\phi \in x$ and $x\in y.$

But $\phi\not\in y,$ because the only member of $y$ is $x,....$ and $x$ is not $\phi$ because $x$ has a member while $\phi$ has none.

$\endgroup$
  • $\begingroup$ $A = \left \{x\right \} $ $ B = \left \{A\right \} $ $ C = \left \{B\right \} $ $means \, B = \left \{\left \{x\right \}\right \} $ $means \, C = \left \{\left \{ \left \{ x \right \}\right \}\right \} $ So $A \subset C$ is true but why not $A \epsilon C$ . Are we talking about nesting of the braces here ? $\endgroup$ – New Student Sep 14 at 4:28
  • $\begingroup$ @NewStudent . In your comment to my answer, by definition of $\subset$, if $A\subset C$ then any member of $A$ is also a member of $C$. But that implies $x,$ a member of $A,$ is equal to the $only$ member of $C,$ which is $B,$.... implying $x=B=\{A\}=\{\{x\}\}.$.... Without the Axiom of Foundation (a.k.a. Regularity) we cannot disprove that $some$ $x$ exists with $x=\{\{x\}\}$ but with a few of the other basic axioms we can prove there are sets (like $\phi$) without this odd-looking property. $\endgroup$ – DanielWainfleet Sep 14 at 6:32
  • 1
    $\begingroup$ @NewStudent yes it amounts to nesting of braces $\endgroup$ – pre-kidney Sep 14 at 20:19
9
$\begingroup$

Belonging is not transitive because we don't want it to be.

Suppose I have sets $A = \{1, 2\}$ and $B = \{3, 4\}$. Now imagine that we write, "Let $C = \{A, B\}$."

When we say "Let $C = \{A, B\}$," what we're saying is that we want $C$ to be a set with exactly two elements: one of the elements is $A$, and the other element is $B$. If we wanted $C$ to have any other elements, we would have said so!

We want to be able to define a set that contains $A$ but doesn't contain $1$. For that reason, when we design the rules of set theory, we choose to design them so that belonging is not transitive.

$\endgroup$
  • $\begingroup$ Your answer is about nesting levels of the curly braces... mentioned in this post in several places. If you ignore the nestling levels, sure thing $1 \epsilon C$ , right ? $\endgroup$ – New Student Sep 14 at 16:48
  • $\begingroup$ @NewStudent Well, it depends on just what you mean by "ignore the nesting levels." If you define a new membership relation $\in^*$ that ignores nesting levels, then yes, $1 \in^* C$. If you use the standard definition $\in$, and my definition of $C$, and you simply choose to ignore nesting levels, then it's false that $1 \in C$, because ignoring something doesn't make it go away. $\endgroup$ – Tanner Swett Sep 14 at 16:54
  • $\begingroup$ “…**and** you simply choose to ignore nesting levels, then it's false that 1∈𝐶...." . Since you used the and actually it will make $1 \epsilon C$ . Paul Halmos defines belonging as contains and subset as inclusion . What is the naive difference between those two since that certainly is the theme of the chapter so far ? $\endgroup$ – New Student Sep 14 at 17:06
  • 1
    $\begingroup$ @NewStudent I like to say that a set is like a list of names of objects (as opposed to a collection of objects, a list of objects, or a collection of names of objects). The statement "$A \in B$" means that the object $A$ is one of the objects whose names are in the list $B$. The statement "$A \subseteq B$" means that all of the names in the list $A$ are also in the list $B$. $\endgroup$ – Tanner Swett Sep 14 at 17:30
  • $\begingroup$ @NewStudent (first comment) I would say, simply, that given how the inclusion relation is defined, you cannot ignore nesting levels. $\endgroup$ – David Z Sep 14 at 22:42
7
$\begingroup$

My dog belongs to me and I belong to the American Mathematical Society... and so....

$\endgroup$
  • 26
    $\begingroup$ I'd say this answer confuses the issue by using two fairly different meanings of the word "belong", one related to ownership and one related to membership. $\endgroup$ – Daniel Schepler Sep 14 at 0:50
  • 9
    $\begingroup$ @Daniel Schelper Or maybe you have one really smart dog! $\endgroup$ – Mike Sep 14 at 1:12
3
$\begingroup$

Based on your response to other answers, your question seems to be "Why do we define the belonging relation ($\in$) in a way that cares about the level of nesting of sets?", i.e. why do we say that $a \notin \{\{a\}\}$?

We could define a relation that ignores nesting, a sort of recursive belonging that works the way you seem to want belonging to work (with $a {\tt\ recursively-belongs-to\ } \{\{a\}\}$), so why don't we use that as the definition of $\in$?

One reason is that we want to be able to use sets for abstraction of concepts to let us ignore details we don't care about. For example, the field of set theory eventually defines the natural numbers as sets: they define $0 = \{\}$, $1 = \{0\}$, and $2 = \{0,1\}$. You shouldn't have to care about that right now, but what if someone asks you whether $0$ belonged to the set $\{1, 2, 3\}$? With non-recursive $\in$, you can immediately answer "no", but what if we had used the recursive belonging relation? In that case the answer would be "yes", because $0 \in 1$ and $1 \in \{1, 2, 3\}$.

Using the current (non-transitive) belonging relation means when we use sets to define composite objects, we can use the resulting things as mathematical objects with their own properties instead of having to care about the details of how they were built out of sets.

$\endgroup$
2
$\begingroup$

Maybe it helps if you draw sets slightly different from the usual way:

image of three-element set

Unlike usually, the set is represented not by the loop, but by a dot connected to a loop (if we are not interested in the content of some specific set, I'll omit the loop). In the image above, we have a set $A$ (the labelled dot in the left, connected to a loop), which has three elements (the dots labelled $1$, $2$, $3$ inside the loop).

Now a subset looks like this:

image of set with subset

You see, all dots encircled by the loop of $B$ are also encircled by the loop of $A$, indicating that this is indeed a subset of $A$. But the dot of $B$ is not encircled by the loop of $A$, which means that $B$ is not an element of $A$.

Now let's add a subset of $B$:

enter image description here

You see, anything inside the circle of $C$ is also inside the circle of $B$, thus $C$ is a subset of $B$. But this necessarily means that anything in $C$ is also in $A$, thus $C$ is also a subset of $A$. That is, the subset relation is transitive.

Now let's look at elements instead:

enter image description here

You see, the dot of $B$ is inside the circle of $A$, so $B$ is an element of $A$. Also, the dot of $C$ is inside the circle of $B$, thus $C$ is in $B$. But the dot of $C$ is not in the circle of $A$, thus $C$ is not in $A$. Since this is obviously possible (I just gave an example), the element relation is not transitive.

Note however that this doesn't mean that you cannot find sets where the relation is transitive, just that generally it isn't. For example, take the following set:

enter image description here

Here $B$ is both element and subset of $A$, that is, the elements of $B$ (in this case, just $C$) are also elements of $A$. Such sets are actually quite important, as they are how natural numbers get defined in set theory (indeed, if $C$ is the empty set, which represents the number $0$, then in the above image $B$ represents the number $1$, and $A$ represents the number $2$).

$\endgroup$
  • $\begingroup$ "Since this is obviously possible ... the element relation is not transitive" Your answer seems to be about nesting levels of the curly braces $\left \{ \right \}$ . When you wrote your statement, it amounts to A = {{C}} so yes $C \not \epsilon A$ because its nested in curly braces a few levels down, but sure it belongs to A. Paul Halmos defines belonging as contains and subset as inclusion . What is the naive difference between those two since that certainly is the theme of the chapter so far ? $\endgroup$ – New Student Sep 14 at 16:42
  • 1
    $\begingroup$ @NewStudent: Apart from the labels, there are no braces in my pictures. I could have reduced the labels to just $A$, $B$, $C$ without changing the content of the pictures. Those braced expressions are just to say what those dots correspond to in the usual way of writing sets. The term “brace nesting level” simply doesn't make sense in the context of my pictures. $\endgroup$ – celtschk Sep 14 at 17:09
  • $\begingroup$ all your pics have loops and braces :-) $\endgroup$ – New Student Sep 14 at 17:43
1
$\begingroup$

Belonging means to be an element of a set, so that $x\in A$ means that $x$ is an element of the set $A$. You can visualise $A$ as a collection of points, and $x$ is one of these points. What you are thinking of, which is correct, is that if $A\subseteq B$, and $x\in A$, then $x\in B$ too. Here, $A\subseteq B$ means $A$ is a subset of $B$, which you can visualise as $B$ being a collection of points which includes all the points of $A$ and possibly more.

However, this is different from saying that $A$ belongs to $B$ unlike perhaps the colloquial meaning of the word. If we were to write $A\in B$, or $A$ belongs to $B$, then we mean as above that $A$ is one point whereby $B$ is a collection of such points including $A$. But here, $A$ is not one point, but a sub-collection of points in $B$. This is an important difference. So although it is true that $x\in A$ and $A\subseteq B$ implies $x\in B$, it is not true that $x\in A$ and $A\in B$ implies $x\in B$, which is the requirement for transitivity.

Indeed, there is also a difference between $\{x\}$ and $x$ for a point $x$. The former refers to the set containing only the point $x$, while the latter refers to the point $x$ itself. This is why $A=\{x\}$, $B=\{\{x\}\}$ is not a counterexample to the claim, for example.


Note: To be pedantic, it's not really rigorous to say for example that $x$ is a point, not a set; for how do you define a "point"? But hopefully the above helps you intuitively understand the difference better.

$\endgroup$
  • $\begingroup$ great post but a few comments 1. Paul Halmos writes belonging as contains and subset as inclusion in section 1. What is the difference here ? subset and $\epsilon$ seem the same thing, no ? 2. Answer to point 1 will help me understand you middle paragraph. 3. when you say “… is not a counterexample to the claim…” , I do not quiet follow. Which “claim” are you talking about ? If its the “claim” in my question heading, then $x \epsilon A$ does not make $x \epsilon B$ but rather $\left \{x \right \} \epsilon B$ is again about nesting levels mentioned elsewhere . $\endgroup$ – New Student Sep 14 at 16: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.