Transitive closure ($\mathrm{TC}(x)$)

The transitive closure $\mathrm{TC}(x)$ is the least transitive set containing every member of $x$. It is obtained by taking the union of all finite iterates of the union operation starting from $x$. This set-theoretic construction uses the membership binary relation; transitive closure of a relation instead closes an arbitrary binary relation under composition.

The transitive closure is obtained by $x_0=x$, $x_{n+1}=\bigcup x_n$, $t={\bigcup }_{n<\omega }{x}_n$. This is transitive, contains $x$ as a subset, and is contained in any other transitive set containing $x$, by induction. Its graph has a Sigma-one formula in set theory saying there exist $\omega$, a sequence with this recursion, and its range. The bounded definition of omega, function and union predicates keep the matrix bounded. Existence and uniqueness in ZF express failure of $y=\mathrm{TC}(x)$ by the existential assertion that the construction produces some $z\ne y$. Thus the graph is a Delta-one formula modulo ZF, and Delta-one absoluteness makes transitive closure absolute between nested transitive models of ZF.

The least reflexive relation and transitive relation containing $R$. Here $R^0$ is the identity relation. Membership means that a finite sequence of zero or more $R$-steps connects the ordered pair. Adding paths can create reverse connections that were absent in $R$, so initial antisymmetry need not be preserved.

Using the convention that $\mathrm{TC}(x)$ is the least transitive set containing $x$ as a subset, put $x_0=x$, $x_{n+1}=\bigcup x_n$ and $\mathrm{TC}(x)={\bigcup }_{n<\omega }{x}_n$. If $\mathrm{rank}x=\alpha$, every element encountered is an iterated member of an original element and has rank below $\alpha$. Thus the closure has rank at most $\alpha$, while $x\subseteq \mathrm{TC}(x)$ gives the reverse inequality. A convention requiring $x$ itself to be an element instead has rank $\alpha +1$.

For an infinite cardinal number $\kappa$, $H_{\kappa }$ consists of the sets $x$ for which $|\mathrm{tc}(\{x\})|<\kappa$, where $\mathrm{tc}$ is transitive closure. The entire transitive membership ancestry is bounded, not only the size of $x$. These collections are transitive sets. At $\kappa ={\omega }_1$ the elements are the hereditarily countable sets.

The hereditarily small set structure $H_{{\omega }_2}$ fails the Axiom of power set at ${\omega }_1$. Every subset of ${\omega }_1$ belongs to $H_{{\omega }_2}$, but their full power set has cardinality at least ${\aleph }_2$ by the Cantor theorem, so cannot itself be hereditarily smaller than ${\aleph }_2$.

Let $z_0=\omega$ and $z_{n+1}=\mathcal{P}(z_n)$. Call $x$ small when it injects into some $z_n$, and let $\mathbf{HS}$ contain exactly the sets all of whose hereditary members are small. Then every $z_n$ and the set $y=\{z_n:n\in \omega \}$ belong to $\mathbf{HS}$, but $\bigcup y$ does not. Consequently $(\mathbf{HS},\in )$ fails the Axiom of union.

A set is hereditarily countable when its transitive closure is countable. These sets form the transitive set $H_{{\omega }_1}$ and all have rank below ${\omega }_1$.

The transitive set of hereditarily countable sets satisfies every ZFC axiom except the Axiom of power set. For internal definable functions on a countable domain, ambient Axiom schema of replacement gives a countable range of hereditarily countable sets, which belongs to the structure by countable-subset closure. The same closure proves axiom schema of collection and retains countable choice-function graphs. All subsets of $\omega$ are elements, but their uncountable full power set is not an element, so Power Set fails.

A countable well-founded relation that is an extensional relation codes a transitive set through the Mostowski collapse theorem. Adding a distinguished point selects one decoded set. Every hereditarily countable set has such a code by enumerating its transitive membership ancestry. There are only continuum many codes. In ZFC, selecting least codes in a well-order gives an injection of the hereditarily countable sets into a set of size $2^{{\aleph }_0}$.

A set has countable-subset closure when every countable subset of it is one of its elements, including the empty subset. In ZFC, the hereditarily countable sets form the least such set. First realize them as the separated subset of $V_{{\omega }_1}$ with countable transitive closure. Countable unions show closure; well-founded induction proves leastness because each of these sets is a countable collection of earlier members.

A set $x$ is reasonable when every member of $\mathrm{TC}(\{x\})$ is countable. In ZFC this is equivalent to $x$ being hereditarily countable.