Metamath Proof Explorer

Theorem swrdrn3

Description: Express the range of a subword. Stronger version of swrdrn2 . (Contributed by Thierry Arnoux, 13-Dec-2023)

Ref Expression
Assertion swrdrn3 
|- ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ran ( W substr <. M , N >. ) = ( W " ( M ..^ N ) ) )

Proof

Step Hyp Ref Expression
1 simpr 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ i e. ( 0 ..^ ( N - M ) ) ) -> i e. ( 0 ..^ ( N - M ) ) )
2 fzssz 
 |-  ( 0 ... ( # ` W ) ) C_ ZZ
3 simpl3 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ i e. ( 0 ..^ ( N - M ) ) ) -> N e. ( 0 ... ( # ` W ) ) )
4 2 3 sseldi 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ i e. ( 0 ..^ ( N - M ) ) ) -> N e. ZZ )
5 fzssz 
 |-  ( 0 ... N ) C_ ZZ
6 simpl2 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ i e. ( 0 ..^ ( N - M ) ) ) -> M e. ( 0 ... N ) )
7 5 6 sseldi 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ i e. ( 0 ..^ ( N - M ) ) ) -> M e. ZZ )
8 fzoaddel2 
 |-  ( ( i e. ( 0 ..^ ( N - M ) ) /\ N e. ZZ /\ M e. ZZ ) -> ( i + M ) e. ( M ..^ N ) )
9 1 4 7 8 syl3anc 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ i e. ( 0 ..^ ( N - M ) ) ) -> ( i + M ) e. ( M ..^ N ) )
10 simpr 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> j e. ( M ..^ N ) )
11 simpl2 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> M e. ( 0 ... N ) )
12 5 11 sseldi 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> M e. ZZ )
13 12 zcnd 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> M e. CC )
14 simpl3 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> N e. ( 0 ... ( # ` W ) ) )
15 2 14 sseldi 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> N e. ZZ )
16 15 zcnd 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> N e. CC )
17 13 16 pncan3d 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> ( M + ( N - M ) ) = N )
18 17 oveq2d 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> ( M ..^ ( M + ( N - M ) ) ) = ( M ..^ N ) )
19 10 18 eleqtrrd 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> j e. ( M ..^ ( M + ( N - M ) ) ) )
20 15 12 zsubcld 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> ( N - M ) e. ZZ )
21 fzosubel3 
 |-  ( ( j e. ( M ..^ ( M + ( N - M ) ) ) /\ ( N - M ) e. ZZ ) -> ( j - M ) e. ( 0 ..^ ( N - M ) ) )
22 19 20 21 syl2anc 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> ( j - M ) e. ( 0 ..^ ( N - M ) ) )
23 simpr 
 |-  ( ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) /\ i = ( j - M ) ) -> i = ( j - M ) )
24 23 oveq1d 
 |-  ( ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) /\ i = ( j - M ) ) -> ( i + M ) = ( ( j - M ) + M ) )
25 24 eqeq2d 
 |-  ( ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) /\ i = ( j - M ) ) -> ( j = ( i + M ) <-> j = ( ( j - M ) + M ) ) )
26 fzossz 
 |-  ( M ..^ N ) C_ ZZ
27 26 10 sseldi 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> j e. ZZ )
28 27 zcnd 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> j e. CC )
29 28 13 npcand 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> ( ( j - M ) + M ) = j )
30 29 eqcomd 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> j = ( ( j - M ) + M ) )
31 22 25 30 rspcedvd 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j e. ( M ..^ N ) ) -> E. i e. ( 0 ..^ ( N - M ) ) j = ( i + M ) )
32 eqcom 
 |-  ( y = ( W ` j ) <-> ( W ` j ) = y )
33 simpr 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j = ( i + M ) ) -> j = ( i + M ) )
34 33 fveq2d 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j = ( i + M ) ) -> ( W ` j ) = ( W ` ( i + M ) ) )
35 34 eqeq2d 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j = ( i + M ) ) -> ( y = ( W ` j ) <-> y = ( W ` ( i + M ) ) ) )
36 32 35 bitr3id 
 |-  ( ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) /\ j = ( i + M ) ) -> ( ( W ` j ) = y <-> y = ( W ` ( i + M ) ) ) )
37 9 31 36 rexxfrd 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( E. j e. ( M ..^ N ) ( W ` j ) = y <-> E. i e. ( 0 ..^ ( N - M ) ) y = ( W ` ( i + M ) ) ) )
38 eqid 
 |-  ( i e. ( 0 ..^ ( N - M ) ) |-> ( W ` ( i + M ) ) ) = ( i e. ( 0 ..^ ( N - M ) ) |-> ( W ` ( i + M ) ) )
39 fvex 
 |-  ( W ` ( i + M ) ) e. _V
40 38 39 elrnmpti 
 |-  ( y e. ran ( i e. ( 0 ..^ ( N - M ) ) |-> ( W ` ( i + M ) ) ) <-> E. i e. ( 0 ..^ ( N - M ) ) y = ( W ` ( i + M ) ) )
41 37 40 bitr4di 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( E. j e. ( M ..^ N ) ( W ` j ) = y <-> y e. ran ( i e. ( 0 ..^ ( N - M ) ) |-> ( W ` ( i + M ) ) ) ) )
42 wrdf 
 |-  ( W e. Word V -> W : ( 0 ..^ ( # ` W ) ) --> V )
43 42 3ad2ant1 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> W : ( 0 ..^ ( # ` W ) ) --> V )
44 43 ffnd 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> W Fn ( 0 ..^ ( # ` W ) ) )
45 elfzuz 
 |-  ( M e. ( 0 ... N ) -> M e. ( ZZ>= ` 0 ) )
46 45 3ad2ant2 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> M e. ( ZZ>= ` 0 ) )
47 fzoss1 
 |-  ( M e. ( ZZ>= ` 0 ) -> ( M ..^ N ) C_ ( 0 ..^ N ) )
48 46 47 syl 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( M ..^ N ) C_ ( 0 ..^ N ) )
49 elfzuz3 
 |-  ( N e. ( 0 ... ( # ` W ) ) -> ( # ` W ) e. ( ZZ>= ` N ) )
50 49 3ad2ant3 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( # ` W ) e. ( ZZ>= ` N ) )
51 fzoss2 
 |-  ( ( # ` W ) e. ( ZZ>= ` N ) -> ( 0 ..^ N ) C_ ( 0 ..^ ( # ` W ) ) )
52 50 51 syl 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( 0 ..^ N ) C_ ( 0 ..^ ( # ` W ) ) )
53 48 52 sstrd 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( M ..^ N ) C_ ( 0 ..^ ( # ` W ) ) )
54 44 53 fvelimabd 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( y e. ( W " ( M ..^ N ) ) <-> E. j e. ( M ..^ N ) ( W ` j ) = y ) )
55 swrdval2 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( W substr <. M , N >. ) = ( i e. ( 0 ..^ ( N - M ) ) |-> ( W ` ( i + M ) ) ) )
56 55 rneqd 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ran ( W substr <. M , N >. ) = ran ( i e. ( 0 ..^ ( N - M ) ) |-> ( W ` ( i + M ) ) ) )
57 56 eleq2d 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( y e. ran ( W substr <. M , N >. ) <-> y e. ran ( i e. ( 0 ..^ ( N - M ) ) |-> ( W ` ( i + M ) ) ) ) )
58 41 54 57 3bitr4rd 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ( y e. ran ( W substr <. M , N >. ) <-> y e. ( W " ( M ..^ N ) ) ) )
59 58 eqrdv 
 |-  ( ( W e. Word V /\ M e. ( 0 ... N ) /\ N e. ( 0 ... ( # ` W ) ) ) -> ran ( W substr <. M , N >. ) = ( W " ( M ..^ N ) ) )