Metamath Proof Explorer

Theorem cshwcshid

Description: A cyclically shifted word can be reconstructed by cyclically shifting it again. Lemma for erclwwlksym and erclwwlknsym . (Contributed by AV, 8-Apr-2018) (Revised by AV, 11-Jun-2018) (Proof shortened by AV, 3-Nov-2018)

Ref Expression
Hypotheses cshwcshid.1 
|- ( ph -> y e. Word V )
cshwcshid.2 
|- ( ph -> ( # ` x ) = ( # ` y ) )
Assertion cshwcshid 
|- ( ph -> ( ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) -> E. n e. ( 0 ... ( # ` x ) ) y = ( x cyclShift n ) ) )

Proof

Step Hyp Ref Expression
1 cshwcshid.1 
 |-  ( ph -> y e. Word V )
2 cshwcshid.2 
 |-  ( ph -> ( # ` x ) = ( # ` y ) )
3 fznn0sub2 
 |-  ( m e. ( 0 ... ( # ` y ) ) -> ( ( # ` y ) - m ) e. ( 0 ... ( # ` y ) ) )
4 oveq2 
 |-  ( ( # ` x ) = ( # ` y ) -> ( 0 ... ( # ` x ) ) = ( 0 ... ( # ` y ) ) )
5 4 eleq2d 
 |-  ( ( # ` x ) = ( # ` y ) -> ( ( ( # ` y ) - m ) e. ( 0 ... ( # ` x ) ) <-> ( ( # ` y ) - m ) e. ( 0 ... ( # ` y ) ) ) )
6 3 5 imbitrrid 
 |-  ( ( # ` x ) = ( # ` y ) -> ( m e. ( 0 ... ( # ` y ) ) -> ( ( # ` y ) - m ) e. ( 0 ... ( # ` x ) ) ) )
7 6 2 syl11 
 |-  ( m e. ( 0 ... ( # ` y ) ) -> ( ph -> ( ( # ` y ) - m ) e. ( 0 ... ( # ` x ) ) ) )
8 7 adantr 
 |-  ( ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) -> ( ph -> ( ( # ` y ) - m ) e. ( 0 ... ( # ` x ) ) ) )
9 8 impcom 
 |-  ( ( ph /\ ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) ) -> ( ( # ` y ) - m ) e. ( 0 ... ( # ` x ) ) )
10 simpl 
 |-  ( ( y e. Word V /\ m e. ( 0 ... ( # ` y ) ) ) -> y e. Word V )
11 elfzelz 
 |-  ( m e. ( 0 ... ( # ` y ) ) -> m e. ZZ )
12 11 adantl 
 |-  ( ( y e. Word V /\ m e. ( 0 ... ( # ` y ) ) ) -> m e. ZZ )
13 elfz2nn0 
 |-  ( m e. ( 0 ... ( # ` y ) ) <-> ( m e. NN0 /\ ( # ` y ) e. NN0 /\ m <_ ( # ` y ) ) )
14 nn0z 
 |-  ( ( # ` y ) e. NN0 -> ( # ` y ) e. ZZ )
15 nn0z 
 |-  ( m e. NN0 -> m e. ZZ )
16 zsubcl 
 |-  ( ( ( # ` y ) e. ZZ /\ m e. ZZ ) -> ( ( # ` y ) - m ) e. ZZ )
17 14 15 16 syl2anr 
 |-  ( ( m e. NN0 /\ ( # ` y ) e. NN0 ) -> ( ( # ` y ) - m ) e. ZZ )
18 17 3adant3 
 |-  ( ( m e. NN0 /\ ( # ` y ) e. NN0 /\ m <_ ( # ` y ) ) -> ( ( # ` y ) - m ) e. ZZ )
19 13 18 sylbi 
 |-  ( m e. ( 0 ... ( # ` y ) ) -> ( ( # ` y ) - m ) e. ZZ )
20 19 adantl 
 |-  ( ( y e. Word V /\ m e. ( 0 ... ( # ` y ) ) ) -> ( ( # ` y ) - m ) e. ZZ )
21 10 12 20 3jca 
 |-  ( ( y e. Word V /\ m e. ( 0 ... ( # ` y ) ) ) -> ( y e. Word V /\ m e. ZZ /\ ( ( # ` y ) - m ) e. ZZ ) )
22 1 21 sylan 
 |-  ( ( ph /\ m e. ( 0 ... ( # ` y ) ) ) -> ( y e. Word V /\ m e. ZZ /\ ( ( # ` y ) - m ) e. ZZ ) )
23 2cshw 
 |-  ( ( y e. Word V /\ m e. ZZ /\ ( ( # ` y ) - m ) e. ZZ ) -> ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) = ( y cyclShift ( m + ( ( # ` y ) - m ) ) ) )
24 22 23 syl 
 |-  ( ( ph /\ m e. ( 0 ... ( # ` y ) ) ) -> ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) = ( y cyclShift ( m + ( ( # ` y ) - m ) ) ) )
25 nn0cn 
 |-  ( m e. NN0 -> m e. CC )
26 nn0cn 
 |-  ( ( # ` y ) e. NN0 -> ( # ` y ) e. CC )
27 25 26 anim12i 
 |-  ( ( m e. NN0 /\ ( # ` y ) e. NN0 ) -> ( m e. CC /\ ( # ` y ) e. CC ) )
28 27 3adant3 
 |-  ( ( m e. NN0 /\ ( # ` y ) e. NN0 /\ m <_ ( # ` y ) ) -> ( m e. CC /\ ( # ` y ) e. CC ) )
29 13 28 sylbi 
 |-  ( m e. ( 0 ... ( # ` y ) ) -> ( m e. CC /\ ( # ` y ) e. CC ) )
30 pncan3 
 |-  ( ( m e. CC /\ ( # ` y ) e. CC ) -> ( m + ( ( # ` y ) - m ) ) = ( # ` y ) )
31 29 30 syl 
 |-  ( m e. ( 0 ... ( # ` y ) ) -> ( m + ( ( # ` y ) - m ) ) = ( # ` y ) )
32 31 adantl 
 |-  ( ( ph /\ m e. ( 0 ... ( # ` y ) ) ) -> ( m + ( ( # ` y ) - m ) ) = ( # ` y ) )
33 32 oveq2d 
 |-  ( ( ph /\ m e. ( 0 ... ( # ` y ) ) ) -> ( y cyclShift ( m + ( ( # ` y ) - m ) ) ) = ( y cyclShift ( # ` y ) ) )
34 cshwn 
 |-  ( y e. Word V -> ( y cyclShift ( # ` y ) ) = y )
35 1 34 syl 
 |-  ( ph -> ( y cyclShift ( # ` y ) ) = y )
36 35 adantr 
 |-  ( ( ph /\ m e. ( 0 ... ( # ` y ) ) ) -> ( y cyclShift ( # ` y ) ) = y )
37 24 33 36 3eqtrrd 
 |-  ( ( ph /\ m e. ( 0 ... ( # ` y ) ) ) -> y = ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) )
38 37 adantrr 
 |-  ( ( ph /\ ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) ) -> y = ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) )
39 oveq1 
 |-  ( x = ( y cyclShift m ) -> ( x cyclShift ( ( # ` y ) - m ) ) = ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) )
40 39 eqeq2d 
 |-  ( x = ( y cyclShift m ) -> ( y = ( x cyclShift ( ( # ` y ) - m ) ) <-> y = ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) ) )
41 40 adantl 
 |-  ( ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) -> ( y = ( x cyclShift ( ( # ` y ) - m ) ) <-> y = ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) ) )
42 41 adantl 
 |-  ( ( ph /\ ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) ) -> ( y = ( x cyclShift ( ( # ` y ) - m ) ) <-> y = ( ( y cyclShift m ) cyclShift ( ( # ` y ) - m ) ) ) )
43 38 42 mpbird 
 |-  ( ( ph /\ ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) ) -> y = ( x cyclShift ( ( # ` y ) - m ) ) )
44 oveq2 
 |-  ( n = ( ( # ` y ) - m ) -> ( x cyclShift n ) = ( x cyclShift ( ( # ` y ) - m ) ) )
45 44 rspceeqv 
 |-  ( ( ( ( # ` y ) - m ) e. ( 0 ... ( # ` x ) ) /\ y = ( x cyclShift ( ( # ` y ) - m ) ) ) -> E. n e. ( 0 ... ( # ` x ) ) y = ( x cyclShift n ) )
46 9 43 45 syl2anc 
 |-  ( ( ph /\ ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) ) -> E. n e. ( 0 ... ( # ` x ) ) y = ( x cyclShift n ) )
47 46 ex 
 |-  ( ph -> ( ( m e. ( 0 ... ( # ` y ) ) /\ x = ( y cyclShift m ) ) -> E. n e. ( 0 ... ( # ` x ) ) y = ( x cyclShift n ) ) )