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