#transitive set

First off, I want to assert that the class of ordinal numbers (because there are too many ordinal numbers to fit into a set) is well-ordered by inclusion. I don't feel like proving this statement. Onwards we go.

Where we left off last time, we had defined the ordinal numbers, and noticed that an ordinal number is well-ordered by ∈. So it should be no surprise that every ordinal number is a transitive set, because orderings are transitive, and our ordering in question is precisely inclusion.

In fact, any transitive set well-ordered by ∈ is an ordinal number. Basically, we have to show that the ∈-image of our transitive set is the set itself. So let's call our transitive set α. We want to show that F defined on α is just the identity function. We'll do this proof by transfinite induction (similar flavour to strong induction).

So first notice that since our ordering mechanism is just inclusion, the segment of any t ∈ α is just t. See, segt = {x ∈ α | x ∈ t} = t. So for our inductive step, suppose F(s) = s. We show for any t with s < t, that F(t) = t.

F(t) = {F(s) | s ∈ t} = {s | s ∈ t} = t. Whoop de whoop. We've done it. So basically we can create ordinal numbers be just creating transitive sets that are well-ordered by inclusion. Since the class of ordinals are well-ordered by inclusion, it follows that any transitive set of ordinal numbers is itself an ordinal. Like I said, they breed each other!

Something that's useful to remember when doing proofs with ordinals is that F(t) is the range of F on the segment of t. Therefore, any element x of F(t) is F(s) for some s < t. We use this fact specifically to prove things like F(t) cannot be an element of F(t), or s < t iff F(s) is an element of F(t).

We have the concept of transitivity for relations: R is transitive if it's the case that given aRb and bRc, it's the case that aRc. Defining what it means for a set to be transitive kind of is in line with this idea, only we use ∈ for the relation.

Specifically, a set A is transitive if x ∈ a and a ∈ A implies that x ∈ A. Remember, a is an element of A, but a is also a set itself. For A to be transitive, all the elements of a must be in A: the elements of elements.

Confusing? Yeah, a little. There isn't too much to say about transitivity, but it's a handy little property to have. Some alternate formulations are: ∪A ⊆ A; and A ⊆ PA. Let's see why these conditions are equivalent to the original definition of transitivity.

Suppose A is transitive, We'll show ∪A ⊆ A. Let x ∈ ∪A. Then, there is a ∈ A with x ∈ a. By transitivity, a ∈ A. So ∪A ⊆ A.

Suppose ∪A ⊆ A. We'll show A ⊆ PA. Let a ∈ A. Then, for every x ∈ a, x ∈ A. Then, we have a ⊆ A. So a ∈ PA, and A ⊆ PA. In fact, that gives us another slightly different way of having transitivity: A is transitive if a ∈ A → a ⊆ A.

Suppose A ⊆ PA. We show A is transitive. Let x ∈ a and a ∈ A. Then, a ∈ PA so a ⊆ A. Then, x ∈ A, so A is transitive.

Cute, huh? I guess what's important is that every natural number is transitive. Extending further, ω, the set of natural numbers, is also transitive.