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 44312

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 44249	. 2 ⊢ r* = (𝑎 ∈ V ↦ ∪ 𝑖 ∈ {0, 1} (𝑎↑_𝑟𝑖))
2		dftrcl3 44293	. 2 ⊢ t+ = (𝑏 ∈ V ↦ ∪ 𝑗 ∈ ℕ (𝑏↑_𝑟𝑗))
3		dfrtrcl3 44306	. 2 ⊢ t* = (𝑐 ∈ V ↦ ∪ 𝑘 ∈ ℕ₀ (𝑐↑_𝑟𝑘))
4		prex 5395	. 2 ⊢ {0, 1} ∈ V
5		nnex 12216	. 2 ⊢ ℕ ∈ V
6		df-n0 12482	. . 3 ⊢ ℕ₀ = (ℕ ∪ {0})
7		uncom 4111	. . 3 ⊢ (ℕ ∪ {0}) = ({0} ∪ ℕ)
8		df-pr 4585	. . . . 5 ⊢ {0, 1} = ({0} ∪ {1})
9	8	uneq1i 4117	. . . 4 ⊢ ({0, 1} ∪ ℕ) = (({0} ∪ {1}) ∪ ℕ)
10		unass 4124	. . . 4 ⊢ (({0} ∪ {1}) ∪ ℕ) = ({0} ∪ ({1} ∪ ℕ))
11		1nn 12221	. . . . . . 7 ⊢ 1 ∈ ℕ
12		snssi 4744	. . . . . . 7 ⊢ (1 ∈ ℕ → {1} ⊆ ℕ)
13	11, 12	ax-mp 5	. . . . . 6 ⊢ {1} ⊆ ℕ
14		ssequn1 4138	. . . . . 6 ⊢ ({1} ⊆ ℕ ↔ ({1} ∪ ℕ) = ℕ)
15	13, 14	mpbi 232	. . . . 5 ⊢ ({1} ∪ ℕ) = ℕ
16	15	uneq2i 4118	. . . 4 ⊢ ({0} ∪ ({1} ∪ ℕ)) = ({0} ∪ ℕ)
17	9, 10, 16	3eqtrri 2790	. . 3 ⊢ ({0} ∪ ℕ) = ({0, 1} ∪ ℕ)
18	6, 7, 17	3eqtri 2789	. 2 ⊢ ℕ₀ = ({0, 1} ∪ ℕ)
19		oveq2 7404	. . . 4 ⊢ (𝑘 = 𝑖 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟𝑖))
20	19	cbviunv 4996	. . 3 ⊢ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) = ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖)
21		ss2iun 4968	. . . 4 ⊢ (∀𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) → ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
22		relexp1g 15039	. . . . . . . 8 ⊢ (𝑑 ∈ V → (𝑑↑_𝑟1) = 𝑑)
23	22	elv 3459	. . . . . . 7 ⊢ (𝑑↑_𝑟1) = 𝑑
24		oveq2 7404	. . . . . . . . 9 ⊢ (𝑗 = 1 → (𝑑↑_𝑟𝑗) = (𝑑↑_𝑟1))
25	24	ssiun2s 5006	. . . . . . . 8 ⊢ (1 ∈ ℕ → (𝑑↑_𝑟1) ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
26	11, 25	ax-mp 5	. . . . . . 7 ⊢ (𝑑↑_𝑟1) ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
27	23, 26	eqsstrri 3983	. . . . . 6 ⊢ 𝑑 ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
28	27	a1i 11	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → 𝑑 ⊆ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
29		ovex 7429	. . . . . . 7 ⊢ (𝑑↑_𝑟𝑗) ∈ V
30	5, 29	iunex 7949	. . . . . 6 ⊢ ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V
31	30	a1i 11	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V)
32		0nn0 12496	. . . . . . 7 ⊢ 0 ∈ ℕ₀
33		1nn0 12497	. . . . . . 7 ⊢ 1 ∈ ℕ₀
34		prssi 4779	. . . . . . 7 ⊢ ((0 ∈ ℕ₀ ∧ 1 ∈ ℕ₀) → {0, 1} ⊆ ℕ₀)
35	32, 33, 34	mp2an 702	. . . . . 6 ⊢ {0, 1} ⊆ ℕ₀
36	35	sseli 3932	. . . . 5 ⊢ (𝑖 ∈ {0, 1} → 𝑖 ∈ ℕ₀)
37	28, 31, 36	relexpss1d 44278	. . . 4 ⊢ (𝑖 ∈ {0, 1} → (𝑑↑_𝑟𝑖) ⊆ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
38	21, 37	mprg 3082	. . 3 ⊢ ∪ 𝑖 ∈ {0, 1} (𝑑↑_𝑟𝑖) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
39	20, 38	eqsstri 3982	. 2 ⊢ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
40		oveq2 7404	. . . . 5 ⊢ (𝑘 = 𝑗 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟𝑗))
41	40	cbviunv 4996	. . . 4 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
42		relexp1g 15039	. . . . 5 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗) ∈ V → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗))
43	30, 42	ax-mp 5	. . . 4 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)
44	41, 43	eqtr4i 2788	. . 3 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1)
45		1ex 11176	. . . . 5 ⊢ 1 ∈ V
46	45	prid2 4722	. . . 4 ⊢ 1 ∈ {0, 1}
47		oveq2 7404	. . . . 5 ⊢ (𝑖 = 1 → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1))
48	47	ssiun2s 5006	. . . 4 ⊢ (1 ∈ {0, 1} → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
49	46, 48	ax-mp 5	. . 3 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
50	44, 49	eqsstri 3982	. 2 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
51		c0ex 11173	. . . . . 6 ⊢ 0 ∈ V
52	51	prid1 4721	. . . . 5 ⊢ 0 ∈ {0, 1}
53		oveq2 7404	. . . . . 6 ⊢ (𝑘 = 0 → (𝑑↑_𝑟𝑘) = (𝑑↑_𝑟0))
54	53	ssiun2s 5006	. . . . 5 ⊢ (0 ∈ {0, 1} → (𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘))
55	52, 54	ax-mp 5	. . . 4 ⊢ (𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘)
56		ssid 3958	. . . 4 ⊢ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
57		unss12 4140	. . . 4 ⊢ (((𝑑↑_𝑟0) ⊆ ∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∧ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘) ⊆ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) → ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) ⊆ (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)))
58	55, 56, 57	mp2an 702	. . 3 ⊢ ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)) ⊆ (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
59		iuneq1 4966	. . . . 5 ⊢ ({0, 1} = ({0} ∪ {1}) → ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
60	8, 59	ax-mp 5	. . . 4 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)
61		iunxun 5051	. . . 4 ⊢ ∪ 𝑖 ∈ ({0} ∪ {1})(∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ∪ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖))
62		oveq2 7404	. . . . . . 7 ⊢ (𝑖 = 0 → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0))
63	51, 62	iunxsn 5048	. . . . . 6 ⊢ ∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0)
64		vex 3458	. . . . . . 7 ⊢ 𝑑 ∈ V
65		nnssnn0 12484	. . . . . . 7 ⊢ ℕ ⊆ ℕ₀
66		inelcm 4419	. . . . . . . 8 ⊢ ((1 ∈ {0, 1} ∧ 1 ∈ ℕ) → ({0, 1} ∩ ℕ) ≠ ∅)
67	46, 11, 66	mp2an 702	. . . . . . 7 ⊢ ({0, 1} ∩ ℕ) ≠ ∅
68		iunrelexp0 44275	. . . . . . 7 ⊢ ((𝑑 ∈ V ∧ ℕ ⊆ ℕ₀ ∧ ({0, 1} ∩ ℕ) ≠ ∅) → (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0) = (𝑑↑_𝑟0))
69	64, 65, 67, 68	mp3an 1482	. . . . . 6 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟0) = (𝑑↑_𝑟0)
70	63, 69	eqtri 2785	. . . . 5 ⊢ ∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (𝑑↑_𝑟0)
71	45, 47	iunxsn 5048	. . . . . 6 ⊢ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1)
72	43, 41	eqtr4i 2788	. . . . . 6 ⊢ (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟1) = ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
73	71, 72	eqtri 2785	. . . . 5 ⊢ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘)
74	70, 73	uneq12i 4119	. . . 4 ⊢ (∪ 𝑖 ∈ {0} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ∪ ∪ 𝑖 ∈ {1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖)) = ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
75	60, 61, 74	3eqtri 2789	. . 3 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) = ((𝑑↑_𝑟0) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
76		iunxun 5051	. . 3 ⊢ ∪ 𝑘 ∈ ({0, 1} ∪ ℕ)(𝑑↑_𝑟𝑘) = (∪ 𝑘 ∈ {0, 1} (𝑑↑_𝑟𝑘) ∪ ∪ 𝑘 ∈ ℕ (𝑑↑_𝑟𝑘))
77	58, 75, 76	3sstr4i 3987	. 2 ⊢ ∪ 𝑖 ∈ {0, 1} (∪ 𝑗 ∈ ℕ (𝑑↑_𝑟𝑗)↑_𝑟𝑖) ⊆ ∪ 𝑘 ∈ ({0, 1} ∪ ℕ)(𝑑↑_𝑟𝑘)
78	1, 2, 3, 4, 5, 18, 39, 50, 77	comptiunov2i 44279	1 ⊢ (r* ∘ t+) = t*

Colors of variables: wff setvar class

Syntax hints: = wceq 1560 ∈ wcel 2142 ≠ wne 2957 Vcvv 3454 ∪ cun 3902 ∩ cin 3903 ⊆ wss 3904 ∅c0 4285 {csn 4582 {cpr 4584 ∪ ciun 4949 ∘ ccom 5651 (class class class)co 7396 0cc0 11073 1c1 11074 ℕcn 12210 ℕ₀cn0 12481 t+ctcl 14998 t*crtcl 14999 ↑_𝑟crelexp 15032 r*crcl 44245

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1815 ax-4 1829 ax-5 1930 ax-6 1987 ax-7 2028 ax-8 2144 ax-9 2152 ax-10 2175 ax-11 2191 ax-12 2212 ax-ext 2734 ax-rep 5227 ax-sep 5246 ax-nul 5256 ax-pow 5322 ax-pr 5390 ax-un 7718 ax-cnex 11129 ax-resscn 11130 ax-1cn 11131 ax-icn 11132 ax-addcl 11133 ax-addrcl 11134 ax-mulcl 11135 ax-mulrcl 11136 ax-mulcom 11137 ax-addass 11138 ax-mulass 11139 ax-distr 11140 ax-i2m1 11141 ax-1ne0 11142 ax-1rid 11143 ax-rnegex 11144 ax-rrecex 11145 ax-cnre 11146 ax-pre-lttri 11147 ax-pre-lttrn 11148 ax-pre-ltadd 11149 ax-pre-mulgt0 11150

This theorem depends on definitions: df-bi 209 df-an 400 df-or 859 df-3or 1099 df-3an 1100 df-tru 1563 df-fal 1573 df-ex 1800 df-nf 1804 df-sb 2091 df-mo 2566 df-eu 2596 df-clab 2741 df-cleq 2754 df-clel 2837 df-nfc 2911 df-ne 2958 df-nel 3062 df-ral 3077 df-rex 3087 df-reu 3368 df-rab 3415 df-v 3456 df-sbc 3745 df-csb 3853 df-dif 3907 df-un 3909 df-in 3911 df-ss 3921 df-pss 3924 df-nul 4286 df-if 4481 df-pw 4557 df-sn 4583 df-pr 4585 df-op 4589 df-uni 4866 df-int 4906 df-iun 4951 df-br 5101 df-opab 5163 df-mpt 5182 df-tr 5208 df-id 5542 df-eprel 5547 df-po 5555 df-so 5556 df-fr 5600 df-we 5602 df-xp 5653 df-rel 5654 df-cnv 5655 df-co 5656 df-dm 5657 df-rn 5658 df-res 5659 df-ima 5660 df-pred 6288 df-ord 6349 df-on 6350 df-lim 6351 df-suc 6352 df-iota 6477 df-fun 6523 df-fn 6524 df-f 6525 df-f1 6526 df-fo 6527 df-f1o 6528 df-fv 6529 df-riota 7353 df-ov 7399 df-oprab 7400 df-mpo 7401 df-om 7847 df-2nd 7971 df-frecs 8262 df-wrecs 8293 df-recs 8342 df-rdg 8381 df-er 8678 df-en 8928 df-dom 8929 df-sdom 8930 df-pnf 11218 df-mnf 11219 df-xr 11220 df-ltxr 11221 df-le 11222 df-sub 11416 df-neg 11417 df-nn 12211 df-2 12280 df-n0 12482 df-z 12569 df-uz 12840 df-seq 14015 df-trcl 15000 df-rtrcl 15001 df-relexp 15033 df-rcl 44246

This theorem is referenced by: cortrcltrcl 44313 corclrtrcl 44314

W3C validator