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 sselid
 |-  ( ( ( 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 )