Metamath Proof Explorer

Theorem wrdind

Description: Perform induction over the structure of a word. (Contributed by Mario Carneiro, 27-Sep-2015) (Revised by Mario Carneiro, 26-Feb-2016) (Proof shortened by AV, 12-Oct-2022)

Ref Expression
Hypotheses wrdind.1 
|- ( x = (/) -> ( ph <-> ps ) )
wrdind.2 
|- ( x = y -> ( ph <-> ch ) )
wrdind.3 
|- ( x = ( y ++ <" z "> ) -> ( ph <-> th ) )
wrdind.4 
|- ( x = A -> ( ph <-> ta ) )
wrdind.5 
|- ps
wrdind.6 
|- ( ( y e. Word B /\ z e. B ) -> ( ch -> th ) )
Assertion wrdind 
|- ( A e. Word B -> ta )

Proof

Step Hyp Ref Expression
1 wrdind.1 
 |-  ( x = (/) -> ( ph <-> ps ) )
2 wrdind.2 
 |-  ( x = y -> ( ph <-> ch ) )
3 wrdind.3 
 |-  ( x = ( y ++ <" z "> ) -> ( ph <-> th ) )
4 wrdind.4 
 |-  ( x = A -> ( ph <-> ta ) )
5 wrdind.5 
 |-  ps
6 wrdind.6 
 |-  ( ( y e. Word B /\ z e. B ) -> ( ch -> th ) )
7 lencl 
 |-  ( A e. Word B -> ( # ` A ) e. NN0 )
8 eqeq2 
 |-  ( n = 0 -> ( ( # ` x ) = n <-> ( # ` x ) = 0 ) )
9 8 imbi1d 
 |-  ( n = 0 -> ( ( ( # ` x ) = n -> ph ) <-> ( ( # ` x ) = 0 -> ph ) ) )
10 9 ralbidv 
 |-  ( n = 0 -> ( A. x e. Word B ( ( # ` x ) = n -> ph ) <-> A. x e. Word B ( ( # ` x ) = 0 -> ph ) ) )
11 eqeq2 
 |-  ( n = m -> ( ( # ` x ) = n <-> ( # ` x ) = m ) )
12 11 imbi1d 
 |-  ( n = m -> ( ( ( # ` x ) = n -> ph ) <-> ( ( # ` x ) = m -> ph ) ) )
13 12 ralbidv 
 |-  ( n = m -> ( A. x e. Word B ( ( # ` x ) = n -> ph ) <-> A. x e. Word B ( ( # ` x ) = m -> ph ) ) )
14 eqeq2 
 |-  ( n = ( m + 1 ) -> ( ( # ` x ) = n <-> ( # ` x ) = ( m + 1 ) ) )
15 14 imbi1d 
 |-  ( n = ( m + 1 ) -> ( ( ( # ` x ) = n -> ph ) <-> ( ( # ` x ) = ( m + 1 ) -> ph ) ) )
16 15 ralbidv 
 |-  ( n = ( m + 1 ) -> ( A. x e. Word B ( ( # ` x ) = n -> ph ) <-> A. x e. Word B ( ( # ` x ) = ( m + 1 ) -> ph ) ) )
17 eqeq2 
 |-  ( n = ( # ` A ) -> ( ( # ` x ) = n <-> ( # ` x ) = ( # ` A ) ) )
18 17 imbi1d 
 |-  ( n = ( # ` A ) -> ( ( ( # ` x ) = n -> ph ) <-> ( ( # ` x ) = ( # ` A ) -> ph ) ) )
19 18 ralbidv 
 |-  ( n = ( # ` A ) -> ( A. x e. Word B ( ( # ` x ) = n -> ph ) <-> A. x e. Word B ( ( # ` x ) = ( # ` A ) -> ph ) ) )
20 hasheq0 
 |-  ( x e. Word B -> ( ( # ` x ) = 0 <-> x = (/) ) )
21 5 1 mpbiri 
 |-  ( x = (/) -> ph )
22 20 21 syl6bi 
 |-  ( x e. Word B -> ( ( # ` x ) = 0 -> ph ) )
23 22 rgen 
 |-  A. x e. Word B ( ( # ` x ) = 0 -> ph )
24 fveqeq2 
 |-  ( x = y -> ( ( # ` x ) = m <-> ( # ` y ) = m ) )
25 24 2 imbi12d 
 |-  ( x = y -> ( ( ( # ` x ) = m -> ph ) <-> ( ( # ` y ) = m -> ch ) ) )
26 25 cbvralvw 
 |-  ( A. x e. Word B ( ( # ` x ) = m -> ph ) <-> A. y e. Word B ( ( # ` y ) = m -> ch ) )
27 simprl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> x e. Word B )
28 fzossfz 
 |-  ( 0 ..^ ( # ` x ) ) C_ ( 0 ... ( # ` x ) )
29 simprr 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( # ` x ) = ( m + 1 ) )
30 nn0p1nn 
 |-  ( m e. NN0 -> ( m + 1 ) e. NN )
31 30 ad2antrr 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( m + 1 ) e. NN )
32 29 31 eqeltrd 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( # ` x ) e. NN )
33 fzo0end 
 |-  ( ( # ` x ) e. NN -> ( ( # ` x ) - 1 ) e. ( 0 ..^ ( # ` x ) ) )
34 32 33 syl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( ( # ` x ) - 1 ) e. ( 0 ..^ ( # ` x ) ) )
35 28 34 sseldi 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( ( # ` x ) - 1 ) e. ( 0 ... ( # ` x ) ) )
36 pfxlen 
 |-  ( ( x e. Word B /\ ( ( # ` x ) - 1 ) e. ( 0 ... ( # ` x ) ) ) -> ( # ` ( x prefix ( ( # ` x ) - 1 ) ) ) = ( ( # ` x ) - 1 ) )
37 27 35 36 syl2anc 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( # ` ( x prefix ( ( # ` x ) - 1 ) ) ) = ( ( # ` x ) - 1 ) )
38 29 oveq1d 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( ( # ` x ) - 1 ) = ( ( m + 1 ) - 1 ) )
39 nn0cn 
 |-  ( m e. NN0 -> m e. CC )
40 39 ad2antrr 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> m e. CC )
41 ax-1cn 
 |-  1 e. CC
42 pncan 
 |-  ( ( m e. CC /\ 1 e. CC ) -> ( ( m + 1 ) - 1 ) = m )
43 40 41 42 sylancl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( ( m + 1 ) - 1 ) = m )
44 37 38 43 3eqtrd 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( # ` ( x prefix ( ( # ` x ) - 1 ) ) ) = m )
45 fveqeq2 
 |-  ( y = ( x prefix ( ( # ` x ) - 1 ) ) -> ( ( # ` y ) = m <-> ( # ` ( x prefix ( ( # ` x ) - 1 ) ) ) = m ) )
46 vex 
 |-  y e. _V
47 46 2 sbcie 
 |-  ( [. y / x ]. ph <-> ch )
48 dfsbcq 
 |-  ( y = ( x prefix ( ( # ` x ) - 1 ) ) -> ( [. y / x ]. ph <-> [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph ) )
49 47 48 bitr3id 
 |-  ( y = ( x prefix ( ( # ` x ) - 1 ) ) -> ( ch <-> [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph ) )
50 45 49 imbi12d 
 |-  ( y = ( x prefix ( ( # ` x ) - 1 ) ) -> ( ( ( # ` y ) = m -> ch ) <-> ( ( # ` ( x prefix ( ( # ` x ) - 1 ) ) ) = m -> [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph ) ) )
51 simplr 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> A. y e. Word B ( ( # ` y ) = m -> ch ) )
52 pfxcl 
 |-  ( x e. Word B -> ( x prefix ( ( # ` x ) - 1 ) ) e. Word B )
53 52 ad2antrl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( x prefix ( ( # ` x ) - 1 ) ) e. Word B )
54 50 51 53 rspcdva 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( ( # ` ( x prefix ( ( # ` x ) - 1 ) ) ) = m -> [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph ) )
55 44 54 mpd 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph )
56 32 nnge1d 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> 1 <_ ( # ` x ) )
57 wrdlenge1n0 
 |-  ( x e. Word B -> ( x =/= (/) <-> 1 <_ ( # ` x ) ) )
58 57 ad2antrl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( x =/= (/) <-> 1 <_ ( # ` x ) ) )
59 56 58 mpbird 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> x =/= (/) )
60 lswcl 
 |-  ( ( x e. Word B /\ x =/= (/) ) -> ( lastS ` x ) e. B )
61 27 59 60 syl2anc 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( lastS ` x ) e. B )
62 oveq1 
 |-  ( y = ( x prefix ( ( # ` x ) - 1 ) ) -> ( y ++ <" z "> ) = ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" z "> ) )
63 62 sbceq1d 
 |-  ( y = ( x prefix ( ( # ` x ) - 1 ) ) -> ( [. ( y ++ <" z "> ) / x ]. ph <-> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" z "> ) / x ]. ph ) )
64 48 63 imbi12d 
 |-  ( y = ( x prefix ( ( # ` x ) - 1 ) ) -> ( ( [. y / x ]. ph -> [. ( y ++ <" z "> ) / x ]. ph ) <-> ( [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph -> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" z "> ) / x ]. ph ) ) )
65 s1eq 
 |-  ( z = ( lastS ` x ) -> <" z "> = <" ( lastS ` x ) "> )
66 65 oveq2d 
 |-  ( z = ( lastS ` x ) -> ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" z "> ) = ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) )
67 66 sbceq1d 
 |-  ( z = ( lastS ` x ) -> ( [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" z "> ) / x ]. ph <-> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) / x ]. ph ) )
68 67 imbi2d 
 |-  ( z = ( lastS ` x ) -> ( ( [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph -> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" z "> ) / x ]. ph ) <-> ( [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph -> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) / x ]. ph ) ) )
69 ovex 
 |-  ( y ++ <" z "> ) e. _V
70 69 3 sbcie 
 |-  ( [. ( y ++ <" z "> ) / x ]. ph <-> th )
71 6 47 70 3imtr4g 
 |-  ( ( y e. Word B /\ z e. B ) -> ( [. y / x ]. ph -> [. ( y ++ <" z "> ) / x ]. ph ) )
72 64 68 71 vtocl2ga 
 |-  ( ( ( x prefix ( ( # ` x ) - 1 ) ) e. Word B /\ ( lastS ` x ) e. B ) -> ( [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph -> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) / x ]. ph ) )
73 53 61 72 syl2anc 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( [. ( x prefix ( ( # ` x ) - 1 ) ) / x ]. ph -> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) / x ]. ph ) )
74 55 73 mpd 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) / x ]. ph )
75 wrdfin 
 |-  ( x e. Word B -> x e. Fin )
76 75 ad2antrl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> x e. Fin )
77 hashnncl 
 |-  ( x e. Fin -> ( ( # ` x ) e. NN <-> x =/= (/) ) )
78 76 77 syl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( ( # ` x ) e. NN <-> x =/= (/) ) )
79 32 78 mpbid 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> x =/= (/) )
80 pfxlswccat 
 |-  ( ( x e. Word B /\ x =/= (/) ) -> ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) = x )
81 80 eqcomd 
 |-  ( ( x e. Word B /\ x =/= (/) ) -> x = ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) )
82 27 79 81 syl2anc 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> x = ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) )
83 sbceq1a 
 |-  ( x = ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) -> ( ph <-> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) / x ]. ph ) )
84 82 83 syl 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ( ph <-> [. ( ( x prefix ( ( # ` x ) - 1 ) ) ++ <" ( lastS ` x ) "> ) / x ]. ph ) )
85 74 84 mpbird 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ ( x e. Word B /\ ( # ` x ) = ( m + 1 ) ) ) -> ph )
86 85 expr 
 |-  ( ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) /\ x e. Word B ) -> ( ( # ` x ) = ( m + 1 ) -> ph ) )
87 86 ralrimiva 
 |-  ( ( m e. NN0 /\ A. y e. Word B ( ( # ` y ) = m -> ch ) ) -> A. x e. Word B ( ( # ` x ) = ( m + 1 ) -> ph ) )
88 87 ex 
 |-  ( m e. NN0 -> ( A. y e. Word B ( ( # ` y ) = m -> ch ) -> A. x e. Word B ( ( # ` x ) = ( m + 1 ) -> ph ) ) )
89 26 88 syl5bi 
 |-  ( m e. NN0 -> ( A. x e. Word B ( ( # ` x ) = m -> ph ) -> A. x e. Word B ( ( # ` x ) = ( m + 1 ) -> ph ) ) )
90 10 13 16 19 23 89 nn0ind 
 |-  ( ( # ` A ) e. NN0 -> A. x e. Word B ( ( # ` x ) = ( # ` A ) -> ph ) )
91 7 90 syl 
 |-  ( A e. Word B -> A. x e. Word B ( ( # ` x ) = ( # ` A ) -> ph ) )
92 eqidd 
 |-  ( A e. Word B -> ( # ` A ) = ( # ` A ) )
93 fveqeq2 
 |-  ( x = A -> ( ( # ` x ) = ( # ` A ) <-> ( # ` A ) = ( # ` A ) ) )
94 93 4 imbi12d 
 |-  ( x = A -> ( ( ( # ` x ) = ( # ` A ) -> ph ) <-> ( ( # ` A ) = ( # ` A ) -> ta ) ) )
95 94 rspcv 
 |-  ( A e. Word B -> ( A. x e. Word B ( ( # ` x ) = ( # ` A ) -> ph ) -> ( ( # ` A ) = ( # ` A ) -> ta ) ) )
96 91 92 95 mp2d 
 |-  ( A e. Word B -> ta )