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
- 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, \(\phi (x, y)\), the transitive closure of \(S\), \(\overline S\), is a transitive set that contains \(S\).
2: Proof
\(N\) is a well-ordered set. The formula, \(y = S \cup \cup \cup ima \text{ }x\), 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 ima \text{ }f\vert_{seg \text{ }n}\).
\(f (n^+) = S \cup \cup \cup ima \text{ }f\vert_{seg \text{ }n^+}\). \(f (n) \in ima \text{ }f\vert_{seg \text{ }n^+}\), because \(n \in seg \text{ }n^+\) and \(f (n) = f\vert_{seg \text{ }n^+} (n)\). For any \(p \in f (n)\), \(p \in \cup ima \text{ }f\vert_{seg \text{ }n^+}\), and for any \(p' \in p\), \(p' \in \cup \cup ima \text{ }f\vert_{seg \text{ }n^+}\). So, \(p' \in f (n^+)\), so, \(p \subseteq f (n^+)\).
For any \(p \in \overline S = \cup ima \text{ }f\), \(p \in f (n)\) for an \(n\). So, by the previous paragraph, \(p \subseteq f (n^+)\). So, for any \(p' \in p\), \(p' \in f (n^+) \subseteq \cup ima \text{ }f = \overline S\).
\(S \subseteq \overline S\), because \(\overline S = \cup ima \text{ }f\) while \(f (n) = S \cup \cup \cup ima \text{ }f\vert_{seg \text{ }n}\).
