Epsilon-induction and the cumulative hierarchy

The axiom of foundation says that every non-empty set must contain an element that it is disjoint with. One implication of this is that no set can contain itself. (Why? Suppose ∃x (x ∈ x). Then you can pair x with itself to form {x}. {x} is non-empty, so it must contain an element that it’s disjoint with. But its only element is x, and that element is not disjoint with {x}. In particular, they both have as an element x.)

Another implication of foundation is that there can be no infinite descending sequence of sets. A sequence of sets is a function f whose domain is ω. For each k ∈ ω we write f(k) as fk. Suppose that f is a function with the property that for each n ∈ ω, fn+1 ∈ fn. Then by the axiom of replacement, there would exist the set {f0, f1, f2, …}. Each element of this set contains the following element, so none of the elements are disjoint with the entire set. So the sequence we started with could not exist.

This allows us to prove a pretty powerful and surprising result about set theory. The result: For any sentence Φ, if Φ holds of at least one set, then there must exist a set X such that Φ(X) holds, but Φ doesn’t hold for any element of X.

Formally:

(∃A Φ(A)) → ∃X (Φ(X) ∧ ∀Y ∈ X (¬Φ(Y))).

Suppose this was false. Then Φ would be satisfied by at least one set, and every set that satisfied Φ would contain an element that satisfied Φ. We can use this to build an infinite descending sequence of sets. Take any set that satisfies Φ and call it X0. Since X0 satisfies Φ, it must contain at least one element that satisfies Φ. Define X1 to be any such element. X1 satisfies Φ as well, so it must contain at least one element that satisfies Φ, which we’ll call X2. And so on forever. Since no set can contain itself, Xn+1 is always distinct from Xn. We can use recursion and then replacement to construct the set {X0, X1, X2, …}, which is an infinite descending sequence of sets. Contradiction!

This peculiar principle turns out to be useful to prove some big results, and the proofs are always a little funny and enjoyable to me. I’m not aware of any name for it, so I’ll call it the “far-from-the-tree” principle: for any property that holds of at least one set, there’s a set that has that property, none of whose elements have the property. I’ll now show two big results that are proven by this principle.

Everything’s in the Cumulative Hierarchy

The cumulative hierarchy is constructed recursively as follows:

V0 = ∅
Vα+1 = 𝒫(Vα), for each ordinal α
Vλ = U{Vβ : β < λ}, for each limit ordinal λ

V0 = ∅
V1 = {∅}
V2 = {∅, {∅}}
V3 = {∅, {∅}, {{∅}}, {∅, {∅}}}

One can prove that Vα is transitive for each ordinal α (in other words, that every element of Vα is also a subset of Vα). Also, due to the nature of the power-set operation, for any two ordinals α < β, Vα ⊆ Vβ.

Now, the reason the cumulative hierarchy is interesting is that we can prove that every set is on some level of the hierarchy. We do so with the far-from-the-tree principle:

Suppose that there was a set X that wasn’t on the hierarchy. This means that ∀α, X ∉ Vα. We use the far-from-tree principle with the property of “not being on the hierarchy” to conclude that there must be a set Y such that Y is not on the hierarchy, but every element of Y is on the hierarchy. So for each element y ∈ Y there’s some ordinal αy such that y ∈ Vαy. Take the highest such ordinal, and now we have a level of the hierarchy that every element of Y is on. Now just go up by one level! Since every element of Y was in the previous level, the set consisting of each of those elements (i.e. Y) is in the power set of that level. So Y actually is on the hierarchy! Contradiction.

This shows that any set you choose shows up on some level of the cumulative hierarchy. Incidentally, the rank of a set is defined as the first level that the set appears on, and one can prove that for each ordinal α, rank(α) = α.

∈-Induction

∈-induction is a really strong principle of induction, because it is induction over all sets, not just the natural numbers or the ordinals. The principle of ∈-induction is the following:

Suppose that for every set X, if Φ(x) holds for every x ∈ X, then Φ(X) holds.
Then Φ holds of every set.

Suppose that this principle was false. Then it’s true that for every set X, if Φ(x) holds for every x ∈ X, then Φ(X) holds, but false that Φ holds of every set. So there’s some set Y such that ¬Φ(Y). We use the far-from-the-tree principle with the property “¬Φ”. This tells us that there’s some set Z such that ¬Φ(Z), but Φ(z) for every z in Z. But we already said that if Φ(z) for every z in Z, then Φ(Z)! Contradiction.

I hope you like these applications as much as I do. They feel to me like very strong and surprising results, especially given how simply they can be proved.

8 thoughts on “Epsilon-induction and the cumulative hierarchy

  1. There’s the fun fact that Regularity implies LEM while Induction doesn’t.
    In any case, I think I’ve posted twice on some of your articles before, some older ones, but somehow the system doesn’t seem to pick them up. And generally the internal linking and the Calendar on the side seem buggy here.

    1. Huh, thanks for letting me know! I don’t recall getting any notifications about comments from you before. Not sure what happened there. What’s the problem with internal linking and the calendar?

      Also, I didn’t know that regularity implies LEM! Do you know the proof of this?

  2. I just left you a lengthy comment but now I don’t see it posted or that it’s awaiting moderation. I’ll check back in tomorrow to find out what you see.

    1. I’ll not rewrite the rant about Constructive Set Theory and equivalent proofs, but you can check out the Wikipedia article on the topic that I’ve curated a bit in the last months.

      And instead of describing the issues I found a third time, here’s a png
      https://i.imgur.com/Tg5KB5Y.png
      So e.g. if I click the first article on low hanging fruits, I get to a similarly titled but different article, and the Calendar does what it wants. Also, at the bottom I added a screencap of my last post just a few minutes ago, which it shows me as being posted at 8am (it was about 15:07 or so).

    2. Very strange. I’m not sure why some of your comments aren’t showing up. One thing is that somebody’s first comment must be approved by me before it shows up, but once I’ve approved one of your comments the rest should show up automatically. I do see the problem with the low hanging policy fruits page, I had two separate pages with the same URL, and all the links to the page made later were directed to the page made earlier. I’m still not sure what the problem is with the calendar. Thanks for pointing out these problems!

      Also, I’ve checked out your youtube channel and really like what I’ve seen so far. I enjoyed the video you made on the continuum hypothesis and its implications for order of integration, and might write about that result in the future!

      1. Maybe it’s an issue of waiting too long while typing in an open reply box and the connection on either side being cut for some time. So that once I eventually click “Post Comment”, the text in the browser doesn’t actually get tied to your comment section. I had been browsing around with open tabs for links to post with my comment after all. I’ll keep track of the behaviour if I write another comment and keep you posted on the results.

        It seems your progression with set theory seems to overlap in time pretty much with mine. As for your future posts, what I’d be interested in is what literature you consumed over the last years. Curiously, you posted about Epsilon-Induction, but you didn’t read the Wikipedia article on the subject, where I added the LEM thingy too, so I know 🙂

  3. But to cut it short, one can guess that the “for all x there exists y such that” (they don’t intersect) form of the Regularity axiom might be dangerous constructively. This particular sequence of quantifiers has a functional character f does map x to y and thus cheap existence of a set, unlike induction. Like with Diaconescu’s theorem, I recall the proof just sets up some concisely defined set, inhabitat-claims of which then correspond with decidability of a disjunction. I think maybe you can track down the proof following the Stanford Encyclopedia article on Constructive Set Theory.
    I’ll make a video on the Powerset axiom in that context in a month or so.

    And this time I’ll safe my text before posting 🙂

Leave a Reply