12
$\begingroup$

Does there exist a set containing infinite elements, whose elements themselves are sets containing infinite elements?

I think the answer is no, there is a famous paradox for it but I'm forgetting.

$\endgroup$
7
  • $\begingroup$ The most famous paradox about sets (and the reason Frege abandoned his version of the theory and ZF was formulated) is Russell’s Paradox: “Does the set of all sets that do not contain themselves, contain itself?” Mathematics had to abandon the idea of “the set of all sets” with or without a certain property. $\endgroup$
    – Davislor
    Mar 19, 2018 at 0:02
  • 4
    $\begingroup$ By "infinite elements" do you mean "infinitely many elements"? ($\mathbb{N}$ has infinitely many elements, all of which are finite; $\{\mathbb{N}\}$ has only one element, but that element is infinite.) $\endgroup$
    – ruakh
    Mar 19, 2018 at 0:58
  • 1
    $\begingroup$ and if so, how many such sets are there? I'm guessing 42. $\endgroup$
    – code_monk
    Mar 19, 2018 at 1:58
  • $\begingroup$ Some constructions of reals involve infinite sets of infinite sets (or other collection types). $\endgroup$
    – outis
    Mar 19, 2018 at 8:00
  • $\begingroup$ "There is a famous paradox for it but I'm forgetting." You are almost certainly thinking of Russel's Paradox as @Davislor mentioned. $\endgroup$ Mar 19, 2018 at 14:54

11 Answers 11

27
$\begingroup$

There are many sets with this property. One example is $A=\{S\subseteq\mathbb{N}\mid |S|=\infty\}$, i.e. the set of infinite subsets of the naturals.

$\endgroup$
9
  • 9
    $\begingroup$ And of course by taking the set of infinite subsets of $A$, one gets more levels. It's turtles all the way up. $\endgroup$
    – user296602
    Mar 18, 2018 at 22:22
  • 2
    $\begingroup$ @Freud But you can still have a countably infinite set of countably infinite sets: e.g. the set of all cofinite subsets of $\mathbb{N}$ is an example. $\endgroup$ Mar 18, 2018 at 22:27
  • 4
    $\begingroup$ I object to the use of $\infty$ as a cardinal number. You should write $S\mbox{ is infinite}$ if you want to use that turn of phrase, or use $|S|\ge\aleph_0$ or $|S|=\aleph_0$ if you are talking about cardinals. $\endgroup$ Mar 19, 2018 at 11:14
  • 1
    $\begingroup$ @Freud: Consider for example the set { {integers divisible by 1}, {integers divisible by 2}, {integers divisible by 3}, ... } Plainly that set is countable, and plainly every element is a countably infinite set. If what you want is a countably infinite set of countably infinite sets then just come up with a function that maps natural numbers onto infinite sets and you're done. $\endgroup$ Mar 19, 2018 at 14:05
  • 2
    $\begingroup$ @CiaPan I'm not sure this is simpler ... it just replaces $·$ in the definition by $+$. $\endgroup$ Mar 19, 2018 at 20:35
25
$\begingroup$

There is no paradox here. Indeed, under the usual axioms of set theory (ZFC) there are lots of such sets.

What ZFC disallows is sets which contain themselves, and Russell's paradox (I suspect this might be what you're vaguely remembering) shows that we can't simultaneously have basic set formation axioms and a set of all sets. But there's no problem with infinite sets of infinite sets.

In fact, according to ZFC the "universe of sets" is built entirely from sets of sets of ...! Specifically, ZFC proves that every set $x$ occurs somewhere in the "tower" of sets $V_\alpha$, where

  • $V_0=\emptyset$

  • $V_{\beta+1}=\mathcal{P}(V_\beta)$ (here "$\mathcal{P}(X)$" is the powerset of $X$), and

  • $V_\alpha=\bigcup_{\beta<\alpha} V_\beta$ for $\alpha$ a limit.

Here $\alpha$ is an ordinal. If $\alpha$ is a finite ordinal, $V_\alpha$ will be finite; but once we go into the infinite ordinals we get all sorts of infinite sets, and infinite sets of infinite sets, and etc. So in fact this "sets-of-sets" stuff, which may feel paradoxical at first, is how ZFC interprets the entire mathematical universe!

$\endgroup$
8
  • $\begingroup$ Yeah I thought if a set containing infinite elements, whose elements are sets containing infinite elements as well, at some point the original set would be itself contained within one of the elements/sets of itself. Not sure if I'm explaining it correctly or if my question wasn't worded with enough detail. $\endgroup$
    – Freud
    Mar 18, 2018 at 22:37
  • $\begingroup$ @Freud That's a reasonable worry, but it doesn't actually happen in general. Here's a recipe for cooking up arbitrarily "big" and "deep" examples: for an ordinal $\alpha$, let $I(\alpha)$ be the set of infinite ordinals $<\alpha$. As long as $\alpha\ge\omega+\omega$, $I(\alpha)$ will be an infinite set of infinite sets. $\endgroup$ Mar 18, 2018 at 23:00
  • $\begingroup$ @Hamsterrific An unfortunate typo. Fixed! $\endgroup$ Mar 19, 2018 at 15:04
  • 1
    $\begingroup$ A nit: I don't think ZFC proves the the hierarchy covers all sets because none of the axioms say this is all the sets that exist. If I have an atom it is nowhere in that hierarchy. ZFC certainly proves that all those sets exist, but there might be more. $\endgroup$ Mar 20, 2018 at 2:26
  • $\begingroup$ @RossMillikan You are incorrect: the axiom of regularity winds up doing exactly that. We show that if $a$ is any set not in the cumulative hierarchy, then it has an element which is also not in the cumulative hierarchy, and so the subset of the transitive closure of $a$ consisting of sets not in the cumulative hierarchy is a violation of regularity. $\endgroup$ Mar 20, 2018 at 3:28
7
$\begingroup$

For each $i\in\mathbb{N}$, set $S_i=\{i,i+1, i+2, \ldots\}$. Each $S_i$ is itself a subset of $\mathbb{N}$.

Then, define $$S=\{S_1, S_2, S_3, \ldots\}$$

Now, $S$ is a set with infinitely many elements, each of which is itself a set with infinitely many elements.

$\endgroup$
6
$\begingroup$

How about a set of all lines on the plane, which are themselves sets of points?

Or a set of sets of natural numbers, greater than some natural number: $$\big\{\{1,2,3\dots\},\ \{2,3,4\dots\},\ \{3,4,5\dots\},\ \dots\big\}$$

$\endgroup$
6
$\begingroup$

Example:

$$S=\{n\mathbb{Z}\mid n\in \mathbb{Z}^+\}$$ where $n\mathbb{Z}=\{\dots,-2n,-n,0,n,2n,\dots\}$.

$\endgroup$
4
  • $\begingroup$ You could also define $n \mathbb{Z}$ as the set generated by $n$, $\left< n \right>$, and express this as $$\left\{ \left< n \right> \mid n \in \mathbb{Z}^+\right\}$$ $\endgroup$
    – Davislor
    Mar 19, 2018 at 0:16
  • $\begingroup$ @Davislor, that is true, however I like to reserve that notation for a group generated by one element :) $\endgroup$ Mar 19, 2018 at 15:32
  • $\begingroup$ @cansomeonehelpmeout isn't this a group (by addition)? $\endgroup$ Mar 19, 2018 at 20:38
  • $\begingroup$ @PaŭloEbermann Yes, it is a group. But OP was talking about a set, so i used $n\mathbb{Z}$ to emphasize that. $\endgroup$ Mar 19, 2018 at 21:29
5
$\begingroup$

In standard axiomatic set theory, the answer is certainly yes. For example, you could take the set $$ \{\{0, 1, 2, 3, \ldots\}, \{1, 2, 3,4,\ldots\}, \{2, 3, 4, 5,\ldots\},\ldots\}. $$ In more formal notation you might write this $$ \{ X \subseteq \mathbb N \mid \exists n \in \mathbb N(\forall m \in \mathbb N(m \in X \leftrightarrow m \geq n)) \}. $$

$\endgroup$
1
  • 1
    $\begingroup$ Also notated as $$\bigcup_{k=0}^\infty\left\{ \bigcup_{i=k}^\infty\{i\}\right\}$$ which I think is more comprehensible and better highlights the ‘nested infinities.’ $\endgroup$ Mar 18, 2018 at 23:08
3
$\begingroup$

Take the set of all subsets of the natural numbers that are infinite.

I.e. $$S := \{T \in \mathcal{P}(\mathbb{N}) \mid |T| = + \infty\}$$

The key that this is possible is the axiom in ZF that says that the powerset is a well defined set. Hence, this set makes certainly sense since we use the so called 'set builder notation'

$\endgroup$
3
  • $\begingroup$ Or just the set of all subsets of the natural numbers, full stop. $\endgroup$ Mar 18, 2018 at 22:23
  • $\begingroup$ No singeltons are in it and these are finite. $\endgroup$
    – user370967
    Mar 18, 2018 at 22:24
  • $\begingroup$ Ah, I read the question as asking for some of the elements to be infinite sets. Good point. (I'll leave my comment up, though, in case that's what the OP meant.) $\endgroup$ Mar 18, 2018 at 22:28
2
$\begingroup$

Let $$S_k= \{j\in \Bbb N: j\ge k\}=\{k, k+1,k+2,\cdots\}$$

Then consider

$$S= \{S_k: k\in \Bbb N\}=\{S_1, S_2,\cdots\}$$

S is infinite and each $S_k$ are infinite too.

$\endgroup$
2
$\begingroup$

Here's a very simple example with no intersections between each subset:

$$ S = \left\{S_1,S_2,... \right\} $$

where

$$ S_n = \left\{p_n^1, p_n^2,...\right\} $$

and $p_n$ is the $n$-th prime.

Bonus: it's countable, just like the rationals.

$\endgroup$
2
$\begingroup$

In the Dedekind construction of the reals, the real line is such a set. Basically, each real number can be considered to split the set of rational numbers into a set of rational numbers greater than the real number, and rational numbers less than the real number. We can use this to define every real number in terms of rational numbers. So if you take the set of real numbers, and replace each of them with the set of rational numbers less than them, you have an uncountable set of countable sets.

$\endgroup$
2
$\begingroup$

How about several copies of the natural numbers where one number is missing from each copy:

$$\{\mathbb{N}-\{n\}\; |\; n\in \mathbb{N}\}$$

$\endgroup$

You must log in to answer this question.

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