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$
  • $\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 '18 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 '18 at 0:58
  • 1
    $\begingroup$ and if so, how many such sets are there? I'm guessing 42. $\endgroup$ – code_monk Mar 19 '18 at 1:58
  • $\begingroup$ Some constructions of reals involve infinite sets of infinite sets (or other collection types). $\endgroup$ – outis Mar 19 '18 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$ – Kris Harper Mar 19 '18 at 14:54

11 Answers 11

26
$\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
    $\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 '18 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$ – Noah Schweber Mar 18 '18 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$ – Mario Carneiro Mar 19 '18 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$ – Eric Lippert Mar 19 '18 at 14:05
  • 2
    $\begingroup$ @CiaPan I'm not sure this is simpler ... it just replaces $·$ in the definition by $+$. $\endgroup$ – Paŭlo Ebermann Mar 19 '18 at 20:35
24
$\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$
  • $\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 '18 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$ – Noah Schweber Mar 18 '18 at 23:00
  • $\begingroup$ @Hamsterrific An unfortunate typo. Fixed! $\endgroup$ – Noah Schweber Mar 19 '18 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$ – Ross Millikan Mar 20 '18 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$ – Noah Schweber Mar 20 '18 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$
  • $\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 '18 at 0:16
  • $\begingroup$ @Davislor, that is true, however I like to reserve that notation for a group generated by one element :) $\endgroup$ – cansomeonehelpmeout Mar 19 '18 at 15:32
  • $\begingroup$ @cansomeonehelpmeout isn't this a group (by addition)? $\endgroup$ – Paŭlo Ebermann Mar 19 '18 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$ – cansomeonehelpmeout Mar 19 '18 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
    $\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$ – gen-z ready to perish Mar 18 '18 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$
  • $\begingroup$ Or just the set of all subsets of the natural numbers, full stop. $\endgroup$ – Noah Schweber Mar 18 '18 at 22:23
  • $\begingroup$ No singeltons are in it and these are finite. $\endgroup$ – user370967 Mar 18 '18 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$ – Noah Schweber Mar 18 '18 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$

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.