276: Transitive Closure of Subset Is Transitive Set That Contains Subset

<The previous article in this series | The table of contents of this series | The next article in this series>

A description/proof of that transitive closure of subset is transitive set that contains subset

---

Topics

About: set

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Description
• 2: Proof

---

Starting Context

• The reader knows a definition of set.
• The reader knows a definition of transitive closure of subset.
• The reader admits the transfinite recursion theorem.

---

Target Context

• The reader will have a description and a proof of the proposition that the transitive closure of any subset is a transitive set that contains the subset.

---

Orientation

There is a list of definitions discussed so far in this site.

There is a list of propositions discussed so far in this site.

---

Main Body

---

1: Description

For any subset, $S$, the natural numbers set, $N$, the formula for the transitive closure, $\varphi (x,y)$, the transitive closure of $S$, $\bar{S}$, is a transitive set that contains $S$.

---

2: Proof

$N$ is a well-ordered set. The formula, $y=S\cup \cup \cup imax$, is a legitimate formula, as $y$ is uniquely determined for any $x$ that is any function from any subset of $N$. So, the transfinite recursion theorem can be applied to them, and the constructed function, $f$, satisfies $f(n)=S\cup \cup \cup imaf{|}_{segn}$.

$f(n^{+})=S\cup \cup \cup imaf{|}_{seg{n}^{+}}$. $f(n)\in imaf{|}_{seg{n}^{+}}$, because $n\in seg{n}^{+}$ and $f(n)=f{|}_{seg{n}^{+}}(n)$. For any $p\in f(n)$, $p\in \cup imaf{|}_{seg{n}^{+}}$, and for any $p^{\prime }\in p$, $p^{\prime }\in \cup \cup imaf{|}_{seg{n}^{+}}$. So, $p^{\prime }\in f(n^{+})$, so, $p\subseteq f(n^{+})$.

For any $p\in \bar{S}=\cup imaf$, $p\in f(n)$ for an $n$. So, by the previous paragraph, $p\subseteq f(n^{+})$. So, for any $p^{\prime }\in p$, $p^{\prime }\in f(n^{+})\subseteq \cup imaf=\bar{S}$.

$S\subseteq \bar{S}$, because $\bar{S}=\cup imaf$ while $f(n)=S\cup \cup \cup imaf{|}_{segn}$.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>