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$
  • 1
    $\begingroup$ Consider $\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}$ $\endgroup$ – Gödel Dec 25 '17 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$ – Duncan Ramage Dec 25 '17 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 '17 at 21:26
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$
  • 1
    $\begingroup$ Hmmmm, I used to know that. :( $\endgroup$ – Steven Thomas Hatton Dec 25 '17 at 21:24
  • 3
    $\begingroup$ @StevenHatton And now you know it again :) $\endgroup$ – Duncan Ramage Dec 25 '17 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 '17 at 21:29

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.