7
$\begingroup$

I came to think about a subject which I'm almost sure has already be studied, but I would not know how to search for it. What I mean is the "depth" of a set.

For finite depths (what that means will be clear in a moment), it is easy to define:

  • The empty set has depth zero.
  • A non-empty set has a depth of one more than the largest depth of its member sets.

So for example, the set $\{\emptyset\}$ has depth $1$, the sets $\{\emptyset,\{\emptyset\}\}$ and $\{\{\emptyset\}\}$ have both depth $2$, and $\{\{\{\emptyset\}\},\{\emptyset\}\}$ has depth 3.

Now it is obvious that this concept extends to infinite depths. For example, $\omega$ has infinite depth because it contains sets of any finite depth. Now it seems obvious that $\{\omega\}$ should have a larger depth because its element already has an infinite depth. So it may make sense that the possible depths are given by ordinal numbers (a nice side effect would be that each ordinal number would be its own depth). On the other hand, maybe it doesn't really make sense to make that distinction (just like $\omega$ and $\omega+1$ have the same cardinality). So maybe the depth should be measured by cardinal numbers instead. Or maybe the depths form their own class of numbers, distinct both from the class of cardinals and the class of ordinals?

Clearly to make this decision, there needs to be a formal way to decide whether two sets have the same depth. I have no idea how to define it (except for finite depth by the explicit recursion), or if there can be a meaningful definition at all (besides the obvious choice to give all sets of infinite depth the same depth $\infty$). However if the depth can have a meaningful definition for infinite-depth sets, I'm sure this has already be done by someone (although quite possibly under another name; a web search for "depth of sets" didn't seem to find anything relevant).

(PS: I have no idea which of the two "set-theory" tags is appropriate; I just assumed that if I can discover the concept without ever having had a course in set theory, it's probably elementary and thus chose that tag)

$\endgroup$
  • 5
    $\begingroup$ This is precisely the concept of set-theoretic rank. $\endgroup$ – Zhen Lin Aug 2 '13 at 20:50
  • 3
    $\begingroup$ Much like Andres pointed out, the correct system to work with here is ordinal numbers, and not cardinals. It should be hint for this fact because we "measure" the length of something and not its size. $\endgroup$ – Asaf Karagila Aug 3 '13 at 9:01
14
$\begingroup$

As Zhen Lin mentioned in a comment, what you call depth is the (set-theoretic) rank of a set. We define it by $\epsilon$-recursion by $$ \mathrm{rk}(x)=\sup\{\mathrm{rk}(y)+1\mid y\in x\}. $$ Note the use of supremum rather than maximum, since infinite sets (as $\omega$) may not have an element of largest rank.

The cumulative hierarchy is defined by transfinite recursion over all ordinals by

  • $V_0=\emptyset$,
  • $V_{\alpha+1}=\mathcal P(V_\alpha)$, and
  • $V_\lambda=\bigcup_{\beta<\lambda}V_\beta$, for $\lambda$ limit.

These sets are increasing: If $\alpha<\beta$ then $V_\alpha\subsetneq V_\beta$. The rank of a set $x$ is precisely the least $\gamma$ such that $x\in V_{\gamma+1}$.

The axiom of regularity, or foundation, is equivalent to the statement that every set appears in some $V_\alpha$, that is, the universe of sets is $\bigcup_{\alpha\in\mathsf{ORD}}V_\alpha$ or, in terms of ranks, that the rank of every set is well-defined (and an ordinal).

In the absence of regularity, we have sets whose rank is not well-defined. (There are two ways this may happen: We could have "loops", consider, for example, an $x$ such that $x=\{x\}$. Or we could have infinite descending chains: $\dots\in x_3\in x_2\in x_1\in x_0$. The axiom of foundation is precisely the statement that $\in$ is well-founded, that is, there are no such loops or chains.)

This notion is very useful, in the fine-grained version presented here, where we distinguish between ranks with the same cardinality, but different as ordinals. For example, it provides us with a tool to prove facts about all sets by proceeding by induction on their rank.

$\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.