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 43066

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 43003	. 2 ⊢ r* = (𝑎 ∈ V ↦ ∪ 𝑖 ∈ {0, 1} (𝑎↑_𝑟𝑖))
2		dftrcl3 43047	. 2 ⊢ t+ = (𝑏 ∈ V ↦ ∪ 𝑗 ∈ ℕ (𝑏↑_𝑟𝑗))
3		dfrtrcl3 43060	. 2 ⊢ t* = (𝑐 ∈ V ↦ ∪ 𝑘 ∈ ℕ₀ (𝑐↑_𝑟𝑘))
4		prex 5425	. 2 ⊢ {0, 1} ∈ V
5		nnex 12222	. 2 ⊢ ℕ ∈ V
6		df-n0 12477	. . 3 ⊢ ℕ₀ = (ℕ ∪ {0})
7		uncom 4148	. . 3 ⊢ (ℕ ∪ {0}) = ({0} ∪ ℕ)
8		df-pr 4626	. . . . 5 ⊢ {0, 1} = ({0} ∪ {1})
9	8	uneq1i 4154	. . . 4 ⊢ ({0, 1} ∪ ℕ) = (({0} ∪ {1}) ∪ ℕ)
10		unass 4161	. . . 4 ⊢ (({0} ∪ {1}) ∪ ℕ) = ({0} ∪ ({1} ∪ ℕ))
11		1nn 12227	. . . . . . 7 ⊢ 1 ∈ ℕ
12		snssi 4806	. . . . . . 7 ⊢ (1 ∈ ℕ → {1} ⊆ ℕ)
13	11, 12	ax-mp 5	. . . . . 6 ⊢ {1} ⊆ ℕ
14		ssequn1 4175	. . . . . 6 ⊢ ({1} ⊆ ℕ ↔ ({1} ∪ ℕ) = ℕ)
15	13, 14	mpbi 229	. . . . 5 ⊢ ({1} ∪ ℕ) = ℕ
16	15	uneq2i 4155	. . . 4 ⊢ ({0} ∪ ({1} ∪ ℕ)) = ({0} ∪ ℕ)
17	9, 10, 16	3eqtrri 2759	. . 3 ⊢ ({0} ∪ ℕ) = ({0, 1} ∪ ℕ)
18	6, 7, 17	3eqtri 2758	. 2 ⊢ ℕ₀ = ({0, 1} ∪ ℕ)
19		oveq2 7413	. . . 4 ⊢ (𝑘 = 𝑖 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟𝑖))
20	19	cbviunv 5036	. . 3 ⊢ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) = ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖)
21		ss2iun 5008	. . . 4 ⊢ (∀𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) → ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
22		relexp1g 14979	. . . . . . . 8 ⊢ (𝑑 ∈ V → (𝑑↑_𝑟1) = 𝑑)
23	22	elv 3474	. . . . . . 7 ⊢ (𝑑↑_𝑟1) = 𝑑
24		oveq2 7413	. . . . . . . . 9 ⊢ (𝑗 = 1 → (𝑑↑_𝑟𝑗) = (𝑑↑_𝑟1))
25	24	ssiun2s 5044	. . . . . . . 8 ⊢ (1 ∈ ℕ → (𝑑↑_𝑟1) ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
26	11, 25	ax-mp 5	. . . . . . 7 ⊢ (𝑑↑_𝑟1) ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
27	23, 26	eqsstrri 4012	. . . . . 6 ⊢ 𝑑 ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
28	27	a1i 11	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → 𝑑 ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
29		ovex 7438	. . . . . . 7 ⊢ (𝑑↑_𝑟𝑗) ∈ V
30	5, 29	iunex 7954	. . . . . 6 ⊢ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V
31	30	a1i 11	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V)
32		0nn0 12491	. . . . . . 7 ⊢ 0 ∈ ℕ₀
33		1nn0 12492	. . . . . . 7 ⊢ 1 ∈ ℕ₀
34		prssi 4819	. . . . . . 7 ⊢ ((0 ∈ ℕ₀ ∧ 1 ∈ ℕ₀) → {0, 1} ⊆ ℕ₀)
35	32, 33, 34	mp2an 689	. . . . . 6 ⊢ {0, 1} ⊆ ℕ₀
36	35	sseli 3973	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → 𝑖 ∈ ℕ₀)
37	28, 31, 36	relexpss1d 43032	. . . 4 ⊢ (𝑖 ∈ {0, 1} → (𝑑↑_𝑟𝑖) ⊆ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
38	21, 37	mprg 3061	. . 3 ⊢ ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
39	20, 38	eqsstri 4011	. 2 ⊢ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
40		oveq2 7413	. . . . 5 ⊢ (𝑘 = 𝑗 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟𝑗))
41	40	cbviunv 5036	. . . 4 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
42		relexp1g 14979	. . . . 5 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
43	30, 42	ax-mp 5	. . . 4 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
44	41, 43	eqtr4i 2757	. . 3 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1)
45		1ex 11214	. . . . 5 ⊢ 1 ∈ V
46	45	prid2 4762	. . . 4 ⊢ 1 ∈ {0, 1}
47		oveq2 7413	. . . . 5 ⊢ (𝑖 = 1 → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1))
48	47	ssiun2s 5044	. . . 4 ⊢ (1 ∈ {0, 1} → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
49	46, 48	ax-mp 5	. . 3 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
50	44, 49	eqsstri 4011	. 2 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
51		c0ex 11212	. . . . . 6 ⊢ 0 ∈ V
52	51	prid1 4761	. . . . 5 ⊢ 0 ∈ {0, 1}
53		oveq2 7413	. . . . . 6 ⊢ (𝑘 = 0 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟0))
54	53	ssiun2s 5044	. . . . 5 ⊢ (0 ∈ {0, 1} → (𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘))
55	52, 54	ax-mp 5	. . . 4 ⊢ (𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘)
56		ssid 3999	. . . 4 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
57		unss12 4177	. . . 4 ⊢ (((𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∧ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) → ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) ⊆ (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)))
58	55, 56, 57	mp2an 689	. . 3 ⊢ ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) ⊆ (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
59		iuneq1 5006	. . . . 5 ⊢ ({0, 1} = ({0} ∪ {1}) → ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
60	8, 59	ax-mp 5	. . . 4 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
61		iunxun 5090	. . . 4 ⊢ ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ∪ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
62		oveq2 7413	. . . . . . 7 ⊢ (𝑖 = 0 → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0))
63	51, 62	iunxsn 5087	. . . . . 6 ⊢ ∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0)
64		vex 3472	. . . . . . 7 ⊢ 𝑑 ∈ V
65		nnssnn0 12479	. . . . . . 7 ⊢ ℕ ⊆ ℕ₀
66		inelcm 4459	. . . . . . . 8 ⊢ ((1 ∈ {0, 1} ∧ 1 ∈ ℕ) → ({0, 1} ∩ ℕ) ≠ ∅)
67	46, 11, 66	mp2an 689	. . . . . . 7 ⊢ ({0, 1} ∩ ℕ) ≠ ∅
68		iunrelexp0 43029	. . . . . . 7 ⊢ ((𝑑 ∈ V ∧ ℕ ⊆ ℕ₀ ∧ ({0, 1} ∩ ℕ) ≠ ∅) → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0) = (𝑑↑_𝑟0))
69	64, 65, 67, 68	mp3an 1457	. . . . . 6 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0) = (𝑑↑_𝑟0)
70	63, 69	eqtri 2754	. . . . 5 ⊢ ∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (𝑑↑_𝑟0)
71	45, 47	iunxsn 5087	. . . . . 6 ⊢ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1)
72	43, 41	eqtr4i 2757	. . . . . 6 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
73	71, 72	eqtri 2754	. . . . 5 ⊢ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
74	70, 73	uneq12i 4156	. . . 4 ⊢ (∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ∪ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)) = ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
75	60, 61, 74	3eqtri 2758	. . 3 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
76		iunxun 5090	. . 3 ⊢ ∪ 𝑘 ∈ ({0, 1} ∪ ℕ)(𝑑↑_𝑟𝑘) = (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
77	58, 75, 76	3sstr4i 4020	. 2 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ⊆ ∪ 𝑘 ∈ ({0, 1} ∪ ℕ)(𝑑↑_𝑟𝑘)
78	1, 2, 3, 4, 5, 18, 39, 50, 77	comptiunov2i 43033	1 ⊢ (r* ∘ t+) = t*

Colors of variables: wff setvar class

Syntax hints: = wceq 1533 ∈ wcel 2098 ≠ wne 2934 Vcvv 3468 ∪ cun 3941 ∩ cin 3942 ⊆ wss 3943 ∅c0 4317 {csn 4623 {cpr 4625 ∪ ciun 4990 ∘ ccom 5673 (class class class)co 7405 0cc0 11112 1c1 11113 ℕcn 12216 ℕ₀cn0 12476 t+ctcl 14938 t*crtcl 14939 ↑_𝑟crelexp 14972 r*crcl 42999

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1789 ax-4 1803 ax-5 1905 ax-6 1963 ax-7 2003 ax-8 2100 ax-9 2108 ax-10 2129 ax-11 2146 ax-12 2163 ax-ext 2697 ax-rep 5278 ax-sep 5292 ax-nul 5299 ax-pow 5356 ax-pr 5420 ax-un 7722 ax-cnex 11168 ax-resscn 11169 ax-1cn 11170 ax-icn 11171 ax-addcl 11172 ax-addrcl 11173 ax-mulcl 11174 ax-mulrcl 11175 ax-mulcom 11176 ax-addass 11177 ax-mulass 11178 ax-distr 11179 ax-i2m1 11180 ax-1ne0 11181 ax-1rid 11182 ax-rnegex 11183 ax-rrecex 11184 ax-cnre 11185 ax-pre-lttri 11186 ax-pre-lttrn 11187 ax-pre-ltadd 11188 ax-pre-mulgt0 11189

This theorem depends on definitions: df-bi 206 df-an 396 df-or 845 df-3or 1085 df-3an 1086 df-tru 1536 df-fal 1546 df-ex 1774 df-nf 1778 df-sb 2060 df-mo 2528 df-eu 2557 df-clab 2704 df-cleq 2718 df-clel 2804 df-nfc 2879 df-ne 2935 df-nel 3041 df-ral 3056 df-rex 3065 df-reu 3371 df-rab 3427 df-v 3470 df-sbc 3773 df-csb 3889 df-dif 3946 df-un 3948 df-in 3950 df-ss 3960 df-pss 3962 df-nul 4318 df-if 4524 df-pw 4599 df-sn 4624 df-pr 4626 df-op 4630 df-uni 4903 df-int 4944 df-iun 4992 df-br 5142 df-opab 5204 df-mpt 5225 df-tr 5259 df-id 5567 df-eprel 5573 df-po 5581 df-so 5582 df-fr 5624 df-we 5626 df-xp 5675 df-rel 5676 df-cnv 5677 df-co 5678 df-dm 5679 df-rn 5680 df-res 5681 df-ima 5682 df-pred 6294 df-ord 6361 df-on 6362 df-lim 6363 df-suc 6364 df-iota 6489 df-fun 6539 df-fn 6540 df-f 6541 df-f1 6542 df-fo 6543 df-f1o 6544 df-fv 6545 df-riota 7361 df-ov 7408 df-oprab 7409 df-mpo 7410 df-om 7853 df-2nd 7975 df-frecs 8267 df-wrecs 8298 df-recs 8372 df-rdg 8411 df-er 8705 df-en 8942 df-dom 8943 df-sdom 8944 df-pnf 11254 df-mnf 11255 df-xr 11256 df-ltxr 11257 df-le 11258 df-sub 11450 df-neg 11451 df-nn 12217 df-2 12279 df-n0 12477 df-z 12563 df-uz 12827 df-seq 13973 df-trcl 14940 df-rtrcl 14941 df-relexp 14973 df-rcl 43000

This theorem is referenced by: cortrcltrcl 43067 corclrtrcl 43068

W3C validator