Theorem trclfvdecomr 36391

Description: The transitive closure of a relation may be decomposed into a union of the relation and the composition of the relation with its transitive closure. (Contributed by RP, 18-Jul-2020.)

Assertion

Ref	Expression
trclfvdecomr	|- ( R e. V -> ( t+ ` R ) = ( R u. ( ( t+ ` R ) o. R ) ) )

Proof of Theorem trclfvdecomr

Dummy variables m n r are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		elex 3040	. . 3 |- ( R e. V -> R e. _V )
2		oveq1 6315	. . . . 5 |- ( r = R -> ( r ^r n ) = ( R ^r n ) )
3	2	iuneq2d 4296	. . . 4 |- ( r = R -> U_ n e. NN ( r ^r n ) = U_ n e. NN ( R ^r n ) )
4		dftrcl3 36383	. . . 4 |- t+ = ( r e. _V |-> U_ n e. NN ( r ^r n ) )
5		nnex 10637	. . . . 5 |- NN e. _V
6		ovex 6336	. . . . 5 |- ( R ^r n ) e. _V
7	5, 6	iunex 6792	. . . 4 |- U_ n e. NN ( R ^r n ) e. _V
8	3, 4, 7	fvmpt 5963	. . 3 |- ( R e. _V -> ( t+ ` R ) = U_ n e. NN ( R ^r n ) )
9	1, 8	syl 17	. 2 |- ( R e. V -> ( t+ ` R ) = U_ n e. NN ( R ^r n ) )
10		nnuz 11218	. . . . . 6 |- NN = ( ZZ>= ` 1 )
11		2eluzge1 11228	. . . . . . 7 |- 2 e. ( ZZ>= ` 1 )
12		uzsplit 11892	. . . . . . 7 |- ( 2 e. ( ZZ>= ` 1 ) -> ( ZZ>= ` 1 ) = ( ( 1 ... ( 2 - 1 ) ) u. ( ZZ>= ` 2 ) ) )
13	11, 12	ax-mp 5	. . . . . 6 |- ( ZZ>= ` 1 ) = ( ( 1 ... ( 2 - 1 ) ) u. ( ZZ>= ` 2 ) )
14		2m1e1 10746	. . . . . . . . 9 |- ( 2 - 1 ) = 1
15	14	oveq2i 6319	. . . . . . . 8 |- ( 1 ... ( 2 - 1 ) ) = ( 1 ... 1 )
16		1z 10991	. . . . . . . . 9 |- 1 e. ZZ
17		fzsn 11866	. . . . . . . . 9 |- ( 1 e. ZZ -> ( 1 ... 1 ) = { 1 } )
18	16, 17	ax-mp 5	. . . . . . . 8 |- ( 1 ... 1 ) = { 1 }
19	15, 18	eqtri 2493	. . . . . . 7 |- ( 1 ... ( 2 - 1 ) ) = { 1 }
20	19	uneq1i 3575	. . . . . 6 |- ( ( 1 ... ( 2 - 1 ) ) u. ( ZZ>= ` 2 ) ) = ( { 1 } u. ( ZZ>= ` 2 ) )
21	10, 13, 20	3eqtri 2497	. . . . 5 |- NN = ( { 1 } u. ( ZZ>= ` 2 ) )
22		iuneq1 4283	. . . . 5 |- ( NN = ( { 1 } u. ( ZZ>= ` 2 ) ) -> U_ n e. NN ( R ^r n ) = U_ n e. ( { 1 } u. ( ZZ>= ` 2 ) ) ( R ^r n ) )
23	21, 22	ax-mp 5	. . . 4 |- U_ n e. NN ( R ^r n ) = U_ n e. ( { 1 } u. ( ZZ>= ` 2 ) ) ( R ^r n )
24		iunxun 4354	. . . 4 |- U_ n e. ( { 1 } u. ( ZZ>= ` 2 ) ) ( R ^r n ) = ( U_ n e. { 1 } ( R ^r n ) u. U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) )
25		1ex 9656	. . . . . 6 |- 1 e. _V
26		oveq2 6316	. . . . . 6 |- ( n = 1 -> ( R ^r n ) = ( R ^r 1 ) )
27	25, 26	iunxsn 4352	. . . . 5 |- U_ n e. { 1 } ( R ^r n ) = ( R ^r 1 )
28	27	uneq1i 3575	. . . 4 |- ( U_ n e. { 1 } ( R ^r n ) u. U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) ) = ( ( R ^r 1 ) u. U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) )
29	23, 24, 28	3eqtri 2497	. . 3 |- U_ n e. NN ( R ^r n ) = ( ( R ^r 1 ) u. U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) )
30		relexp1g 13166	. . . 4 |- ( R e. V -> ( R ^r 1 ) = R )
31		oveq1 6315	. . . . . . . . . 10 |- ( r = R -> ( r ^r m ) = ( R ^r m ) )
32	31	iuneq2d 4296	. . . . . . . . 9 |- ( r = R -> U_ m e. NN ( r ^r m ) = U_ m e. NN ( R ^r m ) )
33		dftrcl3 36383	. . . . . . . . 9 |- t+ = ( r e. _V |-> U_ m e. NN ( r ^r m ) )
34		ovex 6336	. . . . . . . . . 10 |- ( R ^r m ) e. _V
35	5, 34	iunex 6792	. . . . . . . . 9 |- U_ m e. NN ( R ^r m ) e. _V
36	32, 33, 35	fvmpt 5963	. . . . . . . 8 |- ( R e. _V -> ( t+ ` R ) = U_ m e. NN ( R ^r m ) )
37	1, 36	syl 17	. . . . . . 7 |- ( R e. V -> ( t+ ` R ) = U_ m e. NN ( R ^r m ) )
38	37	coeq1d 5001	. . . . . 6 |- ( R e. V -> ( ( t+ ` R ) o. R ) = ( U_ m e. NN ( R ^r m ) o. R ) )
39		coiun1 36315	. . . . . . 7 |- ( U_ m e. NN ( R ^r m ) o. R ) = U_ m e. NN ( ( R ^r m ) o. R )
40		uz2m1nn 11256	. . . . . . . . 9 |- ( n e. ( ZZ>= ` 2 ) -> ( n - 1 ) e. NN )
41	40	adantl 473	. . . . . . . 8 |- ( ( R e. V /\ n e. ( ZZ>= ` 2 ) ) -> ( n - 1 ) e. NN )
42		eluzp1p1 11208	. . . . . . . . . . 11 |- ( m e. ( ZZ>= ` 1 ) -> ( m + 1 ) e. ( ZZ>= ` ( 1 + 1 ) ) )
43	42, 10	eleq2s 2567	. . . . . . . . . 10 |- ( m e. NN -> ( m + 1 ) e. ( ZZ>= ` ( 1 + 1 ) ) )
44		1p1e2 10745	. . . . . . . . . . 11 |- ( 1 + 1 ) = 2
45	44	fveq2i 5882	. . . . . . . . . 10 |- ( ZZ>= ` ( 1 + 1 ) ) = ( ZZ>= ` 2 )
46	43, 45	syl6eleq 2559	. . . . . . . . 9 |- ( m e. NN -> ( m + 1 ) e. ( ZZ>= ` 2 ) )
47	46	adantl 473	. . . . . . . 8 |- ( ( R e. V /\ m e. NN ) -> ( m + 1 ) e. ( ZZ>= ` 2 ) )
48		oveq2 6316	. . . . . . . . . 10 |- ( m = ( n - 1 ) -> ( R ^r m ) = ( R ^r ( n - 1 ) ) )
49	48	coeq1d 5001	. . . . . . . . 9 |- ( m = ( n - 1 ) -> ( ( R ^r m ) o. R ) = ( ( R ^r ( n - 1 ) ) o. R ) )
50	49	3ad2ant3 1053	. . . . . . . 8 |- ( ( R e. V /\ n e. ( ZZ>= ` 2 ) /\ m = ( n - 1 ) ) -> ( ( R ^r m ) o. R ) = ( ( R ^r ( n - 1 ) ) o. R ) )
51		oveq2 6316	. . . . . . . . 9 |- ( n = ( m + 1 ) -> ( R ^r n ) = ( R ^r ( m + 1 ) ) )
52	51	3ad2ant3 1053	. . . . . . . 8 |- ( ( R e. V /\ m e. NN /\ n = ( m + 1 ) ) -> ( R ^r n ) = ( R ^r ( m + 1 ) ) )
53		relexpsucnnr 13165	. . . . . . . . 9 |- ( ( R e. V /\ m e. NN ) -> ( R ^r ( m + 1 ) ) = ( ( R ^r m ) o. R ) )
54	53	eqcomd 2477	. . . . . . . 8 |- ( ( R e. V /\ m e. NN ) -> ( ( R ^r m ) o. R ) = ( R ^r ( m + 1 ) ) )
55		relexpsucnnr 13165	. . . . . . . . . 10 |- ( ( R e. V /\ ( n - 1 ) e. NN ) -> ( R ^r ( ( n - 1 ) + 1 ) ) = ( ( R ^r ( n - 1 ) ) o. R ) )
56	40, 55	sylan2 482	. . . . . . . . 9 |- ( ( R e. V /\ n e. ( ZZ>= ` 2 ) ) -> ( R ^r ( ( n - 1 ) + 1 ) ) = ( ( R ^r ( n - 1 ) ) o. R ) )
57		eluzelcn 11194	. . . . . . . . . . . 12 |- ( n e. ( ZZ>= ` 2 ) -> n e. CC )
58		npcan1 10065	. . . . . . . . . . . 12 |- ( n e. CC -> ( ( n - 1 ) + 1 ) = n )
59		oveq2 6316	. . . . . . . . . . . 12 |- ( ( ( n - 1 ) + 1 ) = n -> ( R ^r ( ( n - 1 ) + 1 ) ) = ( R ^r n ) )
60	57, 58, 59	3syl 18	. . . . . . . . . . 11 |- ( n e. ( ZZ>= ` 2 ) -> ( R ^r ( ( n - 1 ) + 1 ) ) = ( R ^r n ) )
61	60	eqeq1d 2473	. . . . . . . . . 10 |- ( n e. ( ZZ>= ` 2 ) -> ( ( R ^r ( ( n - 1 ) + 1 ) ) = ( ( R ^r ( n - 1 ) ) o. R ) <-> ( R ^r n ) = ( ( R ^r ( n - 1 ) ) o. R ) ) )
62	61	adantl 473	. . . . . . . . 9 |- ( ( R e. V /\ n e. ( ZZ>= ` 2 ) ) -> ( ( R ^r ( ( n - 1 ) + 1 ) ) = ( ( R ^r ( n - 1 ) ) o. R ) <-> ( R ^r n ) = ( ( R ^r ( n - 1 ) ) o. R ) ) )
63	56, 62	mpbid 215	. . . . . . . 8 |- ( ( R e. V /\ n e. ( ZZ>= ` 2 ) ) -> ( R ^r n ) = ( ( R ^r ( n - 1 ) ) o. R ) )
64	41, 47, 50, 52, 54, 63	cbviuneq12dv 36325	. . . . . . 7 |- ( R e. V -> U_ m e. NN ( ( R ^r m ) o. R ) = U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) )
65	39, 64	syl5eq 2517	. . . . . 6 |- ( R e. V -> ( U_ m e. NN ( R ^r m ) o. R ) = U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) )
66	38, 65	eqtrd 2505	. . . . 5 |- ( R e. V -> ( ( t+ ` R ) o. R ) = U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) )
67	66	eqcomd 2477	. . . 4 |- ( R e. V -> U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) = ( ( t+ ` R ) o. R ) )
68	30, 67	uneq12d 3580	. . 3 |- ( R e. V -> ( ( R ^r 1 ) u. U_ n e. ( ZZ>= ` 2 ) ( R ^r n ) ) = ( R u. ( ( t+ ` R ) o. R ) ) )
69	29, 68	syl5eq 2517	. 2 |- ( R e. V -> U_ n e. NN ( R ^r n ) = ( R u. ( ( t+ ` R ) o. R ) ) )
70	9, 69	eqtrd 2505	1 |- ( R e. V -> ( t+ ` R ) = ( R u. ( ( t+ ` R ) o. R ) ) )

Syntax hints:   -> wi 4   <-> wb 189   /\ wa 376   = wceq 1452   e. wcel 1904   _Vcvv 3031   u. cun 3388   {csn 3959   U_ciun 4269   o. ccom 4843   ` cfv 5589  (class class class)co 6308   CCcc 9555   1c1 9558   + caddc 9560   - cmin 9880   NNcn 10631   2c2 10681   ZZcz 10961   ZZ>=cuz 11182   ...cfz 11810   t+ctcl 13124   ^r crelexp 13160

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1677  ax-4 1690  ax-5 1766  ax-6 1813  ax-7 1859  ax-8 1906  ax-9 1913  ax-10 1932  ax-11 1937  ax-12 1950  ax-13 2104  ax-ext 2451  ax-rep 4508  ax-sep 4518  ax-nul 4527  ax-pow 4579  ax-pr 4639  ax-un 6602  ax-cnex 9613  ax-resscn 9614  ax-1cn 9615  ax-icn 9616  ax-addcl 9617  ax-addrcl 9618  ax-mulcl 9619  ax-mulrcl 9620  ax-mulcom 9621  ax-addass 9622  ax-mulass 9623  ax-distr 9624  ax-i2m1 9625  ax-1ne0 9626  ax-1rid 9627  ax-rnegex 9628  ax-rrecex 9629  ax-cnre 9630  ax-pre-lttri 9631  ax-pre-lttrn 9632  ax-pre-ltadd 9633  ax-pre-mulgt0 9634

This theorem depends on definitions:  df-bi 190  df-or 377  df-an 378  df-3or 1008  df-3an 1009  df-tru 1455  df-ex 1672  df-nf 1676  df-sb 1806  df-eu 2323  df-mo 2324  df-clab 2458  df-cleq 2464  df-clel 2467  df-nfc 2601  df-ne 2643  df-nel 2644  df-ral 2761  df-rex 2762  df-reu 2763  df-rab 2765  df-v 3033  df-sbc 3256  df-csb 3350  df-dif 3393  df-un 3395  df-in 3397  df-ss 3404  df-pss 3406  df-nul 3723  df-if 3873  df-pw 3944  df-sn 3960  df-pr 3962  df-tp 3964  df-op 3966  df-uni 4191  df-int 4227  df-iun 4271  df-br 4396  df-opab 4455  df-mpt 4456  df-tr 4491  df-eprel 4750  df-id 4754  df-po 4760  df-so 4761  df-fr 4798  df-we 4800  df-xp 4845  df-rel 4846  df-cnv 4847  df-co 4848  df-dm 4849  df-rn 4850  df-res 4851  df-ima 4852  df-pred 5387  df-ord 5433  df-on 5434  df-lim 5435  df-suc 5436  df-iota 5553  df-fun 5591  df-fn 5592  df-f 5593  df-f1 5594  df-fo 5595  df-f1o 5596  df-fv 5597  df-riota 6270  df-ov 6311  df-oprab 6312  df-mpt2 6313  df-om 6712  df-1st 6812  df-2nd 6813  df-wrecs 7046  df-recs 7108  df-rdg 7146  df-er 7381  df-en 7588  df-dom 7589  df-sdom 7590  df-pnf 9695  df-mnf 9696  df-xr 9697  df-ltxr 9698  df-le 9699  df-sub 9882  df-neg 9883  df-nn 10632  df-2 10690  df-n0 10894  df-z 10962  df-uz 11183  df-fz 11811  df-seq 12252  df-trcl 13126  df-relexp 13161

This theorem is referenced by:  trclfvdecoml  36392  dmtrclfvRP  36393  frege124d  36424  frege131d  36427