11
$\begingroup$

Note, this is not homework. I have not seen the inside of a classroom in decades.

I decided to brush up on set theory and logic and stumbled on this: Exercise 1-3.7.

Give several examples of a set $\mathcal{X}$ such that each element of $\mathcal{X}$ is a subset of $\mathcal{X}$.

Stoll, Robert R.. Set Theory and Logic (Dover Books on Mathematics) (Kindle Locations 482-483). Dover Publications. Kindle Edition.

This is from the introductory chapter on intuitive set theory. Terms such as predicate and symbols such as $\implies$ and $\iff$ have not yet been introduced. Nor has any formal logic.

So this is my assessment of the situation:

A set is a collection of all entities which satisfy some predicate $P$. That is $\mathcal{X}=\left\{ x\vert P\left[x\right]\right\} $ is a set if $P\left[x\right]$ is always either true or else false.

The statement $\mathcal{Y}$ is a subset of $\mathcal{X}$ may be written symbolically as$\mathcal{Y}\subseteq\mathcal{X}\iff y\in\mathcal{Y}\implies y\in\mathcal{X}$.

Here is an example of a set whose elements are not subsets of the set.

$\mathcal{A}=\left\{ a_{1},a_{2}\right\} $. The subsets of $\mathcal{A}$ are $\emptyset$,$\mathcal{A}$, $\left\{ a_{1}\right\} $ and $\left\{ a_{2}\right\} $, so $a_{1}$ and $a_{2}$ are not subsets of $\mathcal{A}$.

I can write the expression $\mathcal{S}=\left\{ x\vert x\subseteq\mathcal{S}\right\} $, and claim it meets the criteria. But, if I enumerate the elements $\mathcal{S}=\left\{ x_{1},x_{2},\dots\right\} $, the subsets might be understood to be $\mathscr{P}\left[\mathcal{S}\right]=\left\{ \emptyset,\mathcal{S},\left\{ x_{1}\right\} ,\left\{ x_{2}\right\} ,\left\{ x_{1},x_{2}\right\} ,\dots\right\} $. But, since it was predicated that $x_{i}\subseteq\mathcal{S}$, perhaps $\mathscr{P}\left[\mathcal{S}\right]=\left\{ \emptyset,\mathcal{S},x_{1},x_{2},\dots,\left\{ x_{1}\right\} ,\left\{ x_{2}\right\} ,\left\{ x_{1},x_{2}\right\} ,\dots\right\} $.

Assume $\mathcal{S}$ has a finite number of elements, say two, for simplicity. Then $\mathscr{P}\left[\mathcal{S}\right]=\left\{ \emptyset,\mathcal{S},x_{1},x_{2},\left\{ x_{1}\right\} ,\left\{ x_{2}\right\} \right\} $, so the power set of $\mathcal{S}$ has $6$ elements. But the power set of a set of two elements should on have $4$ elements.

That indicates to me that any set satisfying the criteria of the exercise would have to be infinite.

Even if I consider infinite sets, I'm still not comfortable with including the elements as subsets.

Is this a trick question? Or is there some way around this seeming contradiction?

$\endgroup$
3
  • 1
    $\begingroup$ Consider $\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}$ $\endgroup$
    – YCB
    Dec 25, 2017 at 21:17
  • $\begingroup$ As a comment, one thing you do wrong in your answer is the calculation of $\mathcal{P}(S)$. If $|S| = 2$, then $|\mathcal{P}(S)| = 2^2 = 4$. $x_1$ and $x_2$ aren't elements of $\mathcal{P}(S)$. $\endgroup$ Dec 25, 2017 at 21:21
  • 5
    $\begingroup$ You wrote: "The subsets of $\mathcal{A}$ are $\emptyset$,$\mathcal A$, $\left\{ a_1\right\}$ and $\left\{a_2\right\}$, so $a_1$ and $a_2$ are not subsets of $\mathcal A$. How do you know that $a_1$ is not a subset of $\mathcal A?$ We don't know what $a_1$ and $a_2$ are; what if $a_1=\emptyset$ or $a_1=\{a_2\}?$ $\endgroup$
    – bof
    Dec 25, 2017 at 21:26

1 Answer 1

17
$\begingroup$

This isn't a trick question; there's several examples of such sets, both finite and infinite, and they are called transitive sets. First, the simplest examples is $\varnothing$, every element of $\varnothing$ is a subset of $\varnothing$, vacuously. So, next, let us consider the set $1$, which I am going to define as $1 = \{\varnothing\}$. This set has one element, $\varnothing$, and $\varnothing$ is trivially a subset of $1$, so $1$ is also transitive. Next, I define $2 = \{\varnothing, 1\} = 2 = \{\varnothing, \{\varnothing\}\}$. It's another quick calculation that this set is transitive. Similarly, $3 = \{\varnothing, 1, 2\}$ is transitive, as is $4 = \{\varnothing, 1, 2, 3\}$, $n = \{\varnothing, 1, 2, \dots, n - 1\}$. The first infinite example I'll give is $\omega = \{\varnothing, 1, 2, \dots, n, n + 1, \dots \}$. What I've essentially done here is construct the first few ordinal numbers.

$\endgroup$
3
  • 2
    $\begingroup$ Hmmmm, I used to know that. :( $\endgroup$ Dec 25, 2017 at 21:24
  • 4
    $\begingroup$ @StevenHatton And now you know it again :) $\endgroup$ Dec 25, 2017 at 21:24
  • 6
    $\begingroup$ @StevenHatton And there are many other examples of "transitive" sets besides the ordinals, for instance, $\{\emptyset,\{\emptyset\},\{\{\emptyset\}\}\}.$ $\endgroup$
    – bof
    Dec 25, 2017 at 21:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .