# Metamath Proof Explorer

## Theorem tz9.1

Description: Every set has a transitive closure (the smallest transitive extension). Theorem 9.1 of TakeutiZaring p. 73. See trcl for an explicit expression for the transitive closure. Apparently open problems are whether this theorem can be proved without the Axiom of Infinity; if not, then whether it implies Infinity; and if not, what is the "property" that Infinity has that the other axioms don't have that is weaker than Infinity itself?

(Added 22-Mar-2011) The following article seems to answer the first question, that it can't be proved without Infinity, in the affirmative: Mancini, Antonella and Zambella, Domenico (2001). "A note on recursive models of set theories."Notre Dame Journal of Formal Logic, 42(2):109-115. (Thanks to Scott Fenton.) (Contributed by NM, 15-Sep-2003)

Ref Expression
Hypothesis tz9.1.1 ${⊢}{A}\in \mathrm{V}$
Assertion tz9.1 ${⊢}\exists {x}\phantom{\rule{.4em}{0ex}}\left({A}\subseteq {x}\wedge \mathrm{Tr}{x}\wedge \forall {y}\phantom{\rule{.4em}{0ex}}\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to {x}\subseteq {y}\right)\right)$

### Proof

Step Hyp Ref Expression
1 tz9.1.1 ${⊢}{A}\in \mathrm{V}$
2 omex ${⊢}\mathrm{\omega }\in \mathrm{V}$
3 fvex ${⊢}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\in \mathrm{V}$
4 2 3 iunex ${⊢}\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\in \mathrm{V}$
5 sseq2 ${⊢}{x}=\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\to \left({A}\subseteq {x}↔{A}\subseteq \bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\right)$
6 treq ${⊢}{x}=\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\to \left(\mathrm{Tr}{x}↔\mathrm{Tr}\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\right)$
7 sseq1 ${⊢}{x}=\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\to \left({x}\subseteq {y}↔\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\subseteq {y}\right)$
8 7 imbi2d ${⊢}{x}=\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\to \left(\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to {x}\subseteq {y}\right)↔\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to \bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\subseteq {y}\right)\right)$
9 8 albidv ${⊢}{x}=\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\to \left(\forall {y}\phantom{\rule{.4em}{0ex}}\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to {x}\subseteq {y}\right)↔\forall {y}\phantom{\rule{.4em}{0ex}}\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to \bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\subseteq {y}\right)\right)$
10 5 6 9 3anbi123d ${⊢}{x}=\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\to \left(\left({A}\subseteq {x}\wedge \mathrm{Tr}{x}\wedge \forall {y}\phantom{\rule{.4em}{0ex}}\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to {x}\subseteq {y}\right)\right)↔\left({A}\subseteq \bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\wedge \mathrm{Tr}\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\wedge \forall {y}\phantom{\rule{.4em}{0ex}}\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to \bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\subseteq {y}\right)\right)\right)$
11 eqid ${⊢}{\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}={\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}$
12 eqid ${⊢}\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)=\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)$
13 1 11 12 trcl ${⊢}\left({A}\subseteq \bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\wedge \mathrm{Tr}\bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\wedge \forall {y}\phantom{\rule{.4em}{0ex}}\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to \bigcup _{{z}\in \mathrm{\omega }}\left({\mathrm{rec}\left(\left({w}\in \mathrm{V}⟼{w}\cup \bigcup {w}\right),{A}\right)↾}_{\mathrm{\omega }}\right)\left({z}\right)\subseteq {y}\right)\right)$
14 4 10 13 ceqsexv2d ${⊢}\exists {x}\phantom{\rule{.4em}{0ex}}\left({A}\subseteq {x}\wedge \mathrm{Tr}{x}\wedge \forall {y}\phantom{\rule{.4em}{0ex}}\left(\left({A}\subseteq {y}\wedge \mathrm{Tr}{y}\right)\to {x}\subseteq {y}\right)\right)$