corcltrcl - Mathbox for Richard Penner

	Mathbox for Richard Penner		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > Mathboxes > corcltrcl		Structured version Visualization version GIF version

Theorem corcltrcl 43980

Description: The composition of the reflexive and transitive closures is the reflexive-transitive closure. (Contributed by RP, 17-Jun-2020.)

**Assertion**
Ref	Expression
corcltrcl	⊢ (r* ∘ t+) = t*

Proof of Theorem corcltrcl Dummy variables 𝑎 𝑏 𝑐 𝑑 𝑖 𝑗 𝑘 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		dfrcl4 43917	. 2 ⊢ r* = (𝑎 ∈ V ↦ ∪ 𝑖 ∈ {0, 1} (𝑎↑_𝑟𝑖))
2		dftrcl3 43961	. 2 ⊢ t+ = (𝑏 ∈ V ↦ ∪ 𝑗 ∈ ℕ (𝑏↑_𝑟𝑗))
3		dfrtrcl3 43974	. 2 ⊢ t* = (𝑐 ∈ V ↦ ∪ 𝑘 ∈ ℕ₀ (𝑐↑_𝑟𝑘))
4		prex 5382	. 2 ⊢ {0, 1} ∈ V
5		nnex 12151	. 2 ⊢ ℕ ∈ V
6		df-n0 12402	. . 3 ⊢ ℕ₀ = (ℕ ∪ {0})
7		uncom 4110	. . 3 ⊢ (ℕ ∪ {0}) = ({0} ∪ ℕ)
8		df-pr 4583	. . . . 5 ⊢ {0, 1} = ({0} ∪ {1})
9	8	uneq1i 4116	. . . 4 ⊢ ({0, 1} ∪ ℕ) = (({0} ∪ {1}) ∪ ℕ)
10		unass 4124	. . . 4 ⊢ (({0} ∪ {1}) ∪ ℕ) = ({0} ∪ ({1} ∪ ℕ))
11		1nn 12156	. . . . . . 7 ⊢ 1 ∈ ℕ
12		snssi 4764	. . . . . . 7 ⊢ (1 ∈ ℕ → {1} ⊆ ℕ)
13	11, 12	ax-mp 5	. . . . . 6 ⊢ {1} ⊆ ℕ
14		ssequn1 4138	. . . . . 6 ⊢ ({1} ⊆ ℕ ↔ ({1} ∪ ℕ) = ℕ)
15	13, 14	mpbi 230	. . . . 5 ⊢ ({1} ∪ ℕ) = ℕ
16	15	uneq2i 4117	. . . 4 ⊢ ({0} ∪ ({1} ∪ ℕ)) = ({0} ∪ ℕ)
17	9, 10, 16	3eqtrri 2764	. . 3 ⊢ ({0} ∪ ℕ) = ({0, 1} ∪ ℕ)
18	6, 7, 17	3eqtri 2763	. 2 ⊢ ℕ₀ = ({0, 1} ∪ ℕ)
19		oveq2 7366	. . . 4 ⊢ (𝑘 = 𝑖 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟𝑖))
20	19	cbviunv 4994	. . 3 ⊢ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) = ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖)
21		ss2iun 4965	. . . 4 ⊢ (∀𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) → ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
22		relexp1g 14949	. . . . . . . 8 ⊢ (𝑑 ∈ V → (𝑑↑_𝑟1) = 𝑑)
23	22	elv 3445	. . . . . . 7 ⊢ (𝑑↑_𝑟1) = 𝑑
24		oveq2 7366	. . . . . . . . 9 ⊢ (𝑗 = 1 → (𝑑↑_𝑟𝑗) = (𝑑↑_𝑟1))
25	24	ssiun2s 5004	. . . . . . . 8 ⊢ (1 ∈ ℕ → (𝑑↑_𝑟1) ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
26	11, 25	ax-mp 5	. . . . . . 7 ⊢ (𝑑↑_𝑟1) ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
27	23, 26	eqsstrri 3981	. . . . . 6 ⊢ 𝑑 ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
28	27	a1i 11	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → 𝑑 ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
29		ovex 7391	. . . . . . 7 ⊢ (𝑑↑_𝑟𝑗) ∈ V
30	5, 29	iunex 7912	. . . . . 6 ⊢ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V
31	30	a1i 11	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V)
32		0nn0 12416	. . . . . . 7 ⊢ 0 ∈ ℕ₀
33		1nn0 12417	. . . . . . 7 ⊢ 1 ∈ ℕ₀
34		prssi 4777	. . . . . . 7 ⊢ ((0 ∈ ℕ₀ ∧ 1 ∈ ℕ₀) → {0, 1} ⊆ ℕ₀)
35	32, 33, 34	mp2an 692	. . . . . 6 ⊢ {0, 1} ⊆ ℕ₀
36	35	sseli 3929	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → 𝑖 ∈ ℕ₀)
37	28, 31, 36	relexpss1d 43946	. . . 4 ⊢ (𝑖 ∈ {0, 1} → (𝑑↑_𝑟𝑖) ⊆ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
38	21, 37	mprg 3057	. . 3 ⊢ ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
39	20, 38	eqsstri 3980	. 2 ⊢ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
40		oveq2 7366	. . . . 5 ⊢ (𝑘 = 𝑗 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟𝑗))
41	40	cbviunv 4994	. . . 4 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
42		relexp1g 14949	. . . . 5 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
43	30, 42	ax-mp 5	. . . 4 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
44	41, 43	eqtr4i 2762	. . 3 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1)
45		1ex 11128	. . . . 5 ⊢ 1 ∈ V
46	45	prid2 4720	. . . 4 ⊢ 1 ∈ {0, 1}
47		oveq2 7366	. . . . 5 ⊢ (𝑖 = 1 → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1))
48	47	ssiun2s 5004	. . . 4 ⊢ (1 ∈ {0, 1} → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
49	46, 48	ax-mp 5	. . 3 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
50	44, 49	eqsstri 3980	. 2 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
51		c0ex 11126	. . . . . 6 ⊢ 0 ∈ V
52	51	prid1 4719	. . . . 5 ⊢ 0 ∈ {0, 1}
53		oveq2 7366	. . . . . 6 ⊢ (𝑘 = 0 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟0))
54	53	ssiun2s 5004	. . . . 5 ⊢ (0 ∈ {0, 1} → (𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘))
55	52, 54	ax-mp 5	. . . 4 ⊢ (𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘)
56		ssid 3956	. . . 4 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
57		unss12 4140	. . . 4 ⊢ (((𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∧ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) → ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) ⊆ (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)))
58	55, 56, 57	mp2an 692	. . 3 ⊢ ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) ⊆ (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
59		iuneq1 4963	. . . . 5 ⊢ ({0, 1} = ({0} ∪ {1}) → ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
60	8, 59	ax-mp 5	. . . 4 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
61		iunxun 5049	. . . 4 ⊢ ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ∪ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
62		oveq2 7366	. . . . . . 7 ⊢ (𝑖 = 0 → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0))
63	51, 62	iunxsn 5046	. . . . . 6 ⊢ ∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0)
64		vex 3444	. . . . . . 7 ⊢ 𝑑 ∈ V
65		nnssnn0 12404	. . . . . . 7 ⊢ ℕ ⊆ ℕ₀
66		inelcm 4417	. . . . . . . 8 ⊢ ((1 ∈ {0, 1} ∧ 1 ∈ ℕ) → ({0, 1} ∩ ℕ) ≠ ∅)
67	46, 11, 66	mp2an 692	. . . . . . 7 ⊢ ({0, 1} ∩ ℕ) ≠ ∅
68		iunrelexp0 43943	. . . . . . 7 ⊢ ((𝑑 ∈ V ∧ ℕ ⊆ ℕ₀ ∧ ({0, 1} ∩ ℕ) ≠ ∅) → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0) = (𝑑↑_𝑟0))
69	64, 65, 67, 68	mp3an 1463	. . . . . 6 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0) = (𝑑↑_𝑟0)
70	63, 69	eqtri 2759	. . . . 5 ⊢ ∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (𝑑↑_𝑟0)
71	45, 47	iunxsn 5046	. . . . . 6 ⊢ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1)
72	43, 41	eqtr4i 2762	. . . . . 6 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
73	71, 72	eqtri 2759	. . . . 5 ⊢ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
74	70, 73	uneq12i 4118	. . . 4 ⊢ (∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ∪ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)) = ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
75	60, 61, 74	3eqtri 2763	. . 3 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
76		iunxun 5049	. . 3 ⊢ ∪ 𝑘 ∈ ({0, 1} ∪ ℕ)(𝑑↑_𝑟𝑘) = (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
77	58, 75, 76	3sstr4i 3985	. 2 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ⊆ ∪ 𝑘 ∈ ({0, 1} ∪ ℕ)(𝑑↑_𝑟𝑘)
78	1, 2, 3, 4, 5, 18, 39, 50, 77	comptiunov2i 43947	1 ⊢ (r* ∘ t+) = t*

Colors of variables: wff setvar class

Syntax hints: = wceq 1541 ∈ wcel 2113 ≠ wne 2932 Vcvv 3440 ∪ cun 3899 ∩ cin 3900 ⊆ wss 3901 ∅c0 4285 {csn 4580 {cpr 4582 ∪ ciun 4946 ∘ ccom 5628 (class class class)co 7358 0cc0 11026 1c1 11027 ℕcn 12145 ℕ₀cn0 12401 t+ctcl 14908 t*crtcl 14909 ↑_𝑟crelexp 14942 r*crcl 43913

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1796 ax-4 1810 ax-5 1911 ax-6 1968 ax-7 2009 ax-8 2115 ax-9 2123 ax-10 2146 ax-11 2162 ax-12 2184 ax-ext 2708 ax-rep 5224 ax-sep 5241 ax-nul 5251 ax-pow 5310 ax-pr 5377 ax-un 7680 ax-cnex 11082 ax-resscn 11083 ax-1cn 11084 ax-icn 11085 ax-addcl 11086 ax-addrcl 11087 ax-mulcl 11088 ax-mulrcl 11089 ax-mulcom 11090 ax-addass 11091 ax-mulass 11092 ax-distr 11093 ax-i2m1 11094 ax-1ne0 11095 ax-1rid 11096 ax-rnegex 11097 ax-rrecex 11098 ax-cnre 11099 ax-pre-lttri 11100 ax-pre-lttrn 11101 ax-pre-ltadd 11102 ax-pre-mulgt0 11103

This theorem depends on definitions: df-bi 207 df-an 396 df-or 848 df-3or 1087 df-3an 1088 df-tru 1544 df-fal 1554 df-ex 1781 df-nf 1785 df-sb 2068 df-mo 2539 df-eu 2569 df-clab 2715 df-cleq 2728 df-clel 2811 df-nfc 2885 df-ne 2933 df-nel 3037 df-ral 3052 df-rex 3061 df-reu 3351 df-rab 3400 df-v 3442 df-sbc 3741 df-csb 3850 df-dif 3904 df-un 3906 df-in 3908 df-ss 3918 df-pss 3921 df-nul 4286 df-if 4480 df-pw 4556 df-sn 4581 df-pr 4583 df-op 4587 df-uni 4864 df-int 4903 df-iun 4948 df-br 5099 df-opab 5161 df-mpt 5180 df-tr 5206 df-id 5519 df-eprel 5524 df-po 5532 df-so 5533 df-fr 5577 df-we 5579 df-xp 5630 df-rel 5631 df-cnv 5632 df-co 5633 df-dm 5634 df-rn 5635 df-res 5636 df-ima 5637 df-pred 6259 df-ord 6320 df-on 6321 df-lim 6322 df-suc 6323 df-iota 6448 df-fun 6494 df-fn 6495 df-f 6496 df-f1 6497 df-fo 6498 df-f1o 6499 df-fv 6500 df-riota 7315 df-ov 7361 df-oprab 7362 df-mpo 7363 df-om 7809 df-2nd 7934 df-frecs 8223 df-wrecs 8254 df-recs 8303 df-rdg 8341 df-er 8635 df-en 8884 df-dom 8885 df-sdom 8886 df-pnf 11168 df-mnf 11169 df-xr 11170 df-ltxr 11171 df-le 11172 df-sub 11366 df-neg 11367 df-nn 12146 df-2 12208 df-n0 12402 df-z 12489 df-uz 12752 df-seq 13925 df-trcl 14910 df-rtrcl 14911 df-relexp 14943 df-rcl 43914

This theorem is referenced by: cortrcltrcl 43981 corclrtrcl 43982

W3C validator