Existence of the transitive closure for sets

Question

How can I prove that the transitive close of an arbitrary set $X$ exists?

A set $X$ is called transitive if $\in$ is transitiv on it. The transitive closure $\mathrm{tcl}(X)$ of an arbitrary set $X$ is the smallest transitive set (w.r.t. inclusion) which is a superset of $X$.

I guess it would suffice to show that any transitive superset of $X$ exists but I am failing right there.

---

Let me show you my try (note: I know that it fails). Define a function $G(n), n\in \Bbb N$ with

$$G(0)=X,\quad G(n+1)=\bigcup X.$$

This function exists because of the recursive function theorem. From there we can build the set $\mathcal G=\{G(n)\mid n\in \Bbb N\}$ by the axiom of replacement. We then have $\mathrm{tcl}(X)=\bigcup \mathcal G$. This works, because $\in$ is well-founded. Because if $\bigcup \mathcal G$ would not be transitive, this means ther would be an infinite descresing $\in$-sequence (not okay because of axiom of foudnation).

However, as I said, this fails.

• I cannot meaningully define $G$, because I do not realy have any clue what the codomain and domain could be. And I need them to define $G$ as a subset of $\mathrm{Cod}(G)\times \mathrm{Dom}(G)$.
• The part about why $\bigcup\mathcal G$ is transitive is a bit sloppy. But I might be able to make this rigorous. The main problem is the first item.

Answer 1

I like your question, because you found a subtle flaw in the way that people sometimes talk about this theorem.

Let's argue instead like this. We shall use the regularity axiom and argue by $\in$-induction. If there is a set without a transitive closure, then there is an $\in$-minimal such set. So we may assume without loss that every element $a\in X$ has a transitive closure $tc(a)$. By the replacement axiom, therefore, we may form the set $\{X\}\cup\{tc(a)\mid a\in X\}$. The union of this set is transitive and contains $X$ as a subset, and in fact, it is precisely the transitive closure of $X$.

An alternative argument would be to argue like this: $X$ is in some $V_\theta$ in the cumulative hierarchy, and every $V_\theta$ is transitive. So this provides a suitable co-domain for your funtion $G$.

Here is third way to argue. For each natural number $n$, there is a unique sequence of length $n$ that iterates the union operation starting from $X$. This can be proved by induction on $n$, since there cannot be least number $n$ violating this. Thus, by the axiom of replacement, we can take the set of all such sequences. This amounts to having your function $G$, from which one can construct the transitive closure.

Answer 2

You are not using Replacement correctly. What Replacement tells you is that if $\varphi$ can be used to define a function with domain $A$, then $\{(a,\varphi(a))\mid a\in A\}$ is in fact a set, and therefore a function in the semantic sense of the word.

What this tells you is that you don't need to know the codomain, and in fact the domain is easy: $\omega$, that's what recursion tells you.

Indeed, this is one of the few great reasons functions in set theory are just particular sets of ordered pairs, rather than $(f,\operatorname{Dom},\operatorname{Cod})$. If you don't have to carry the domain and codomain with you everywhere you go, you can do things more easily.

So we simply have a function, $F(x)=\bigcup x$, and by the recursion theorem, given any $X$ there is a unique function $G$ such that $G(0)=X$ and $G(n+1)=F(G(n))=\bigcup G(n)$.

As for the proof that $T=\bigcup\cal G$ is transitive: suppose $x\in y\in T$, then there is some $n$ such that $y\in G(n)$ this is by the very definition of $T$ as $\bigcup\{G(n)\mid n\in\omega\}$. But now that means that $x\in G(n+1)$, and therefore $x\in T$ as well.

Finally, as you can see, we did not use Foundation here at all. The well-foundedness used for the recursion theorem is that of $\omega$, which is immediate from it being an ordinal. (Recall that without Foundation ordinals are those transitive sets which are well-ordered by $\in$, and not just "transitive set of transitive sets", this equivalence does in fact use Foundation.)