Metamath Proof Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >  efgcpbllemb Structured version   Unicode version

Theorem efgcpbllemb 15387
 Description: Lemma for efgrelex 15383. Show that is an equivalence relation containing all direct extensions of a word, so is closed under . (Contributed by Mario Carneiro, 1-Oct-2015.)
Hypotheses
Ref Expression
efgval.w Word
efgval.r ~FG
efgval2.m
efgval2.t splice
efgred.d
efgred.s Word ..^
efgcpbllem.1 concat concat concat concat
Assertion
Ref Expression
efgcpbllemb
Distinct variable groups:   ,,   ,   ,,,,,   ,,,,,,,,   ,,,,,,   ,,,,   ,,,,,,,,,   ,,,,,,,   ,,   ,,   ,,,,,,,,,,   ,,,,
Allowed substitution hints:   (,,,,,,,,)   (,,,,,,,,)   (,,,,,,)   (,,,)   (,,,,,,,,)   (,,,,)   ()   (,,,,,,,,,,)   (,,)

Proof of Theorem efgcpbllemb
Dummy variables are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 efgval.w . . 3 Word
2 efgval.r . . 3 ~FG
3 efgval2.m . . 3
4 efgval2.t . . 3 splice
51, 2, 3, 4efgval2 15356 . 2
6 efgcpbllem.1 . . . . . . 7 concat concat concat concat
76relopabi 5000 . . . . . 6
87a1i 11 . . . . 5
9 efgred.d . . . . . . . . 9
10 efgred.s . . . . . . . . 9 Word ..^
111, 2, 3, 4, 9, 10, 6efgcpbllema 15386 . . . . . . . 8 concat concat concat concat
1211simp2bi 973 . . . . . . 7
1312adantl 453 . . . . . 6
1411simp1bi 972 . . . . . . 7
1514adantl 453 . . . . . 6
161, 2efger 15350 . . . . . . . 8
1716a1i 11 . . . . . . 7
1811simp3bi 974 . . . . . . . 8 concat concat concat concat
1918adantl 453 . . . . . . 7 concat concat concat concat
2017, 19ersym 6917 . . . . . 6 concat concat concat concat
211, 2, 3, 4, 9, 10, 6efgcpbllema 15386 . . . . . 6 concat concat concat concat
2213, 15, 20, 21syl3anbrc 1138 . . . . 5
2314ad2antrl 709 . . . . . 6
241, 2, 3, 4, 9, 10, 6efgcpbllema 15386 . . . . . . . 8 concat concat concat concat
2524simp2bi 973 . . . . . . 7
2625ad2antll 710 . . . . . 6
2716a1i 11 . . . . . . 7
2818ad2antrl 709 . . . . . . 7 concat concat concat concat
2924simp3bi 974 . . . . . . . 8 concat concat concat concat
3029ad2antll 710 . . . . . . 7 concat concat concat concat
3127, 28, 30ertrd 6921 . . . . . 6 concat concat concat concat
321, 2, 3, 4, 9, 10, 6efgcpbllema 15386 . . . . . 6 concat concat concat concat
3323, 26, 31, 32syl3anbrc 1138 . . . . 5
3416a1i 11 . . . . . . . . 9
35 fviss 5784 . . . . . . . . . . . . . 14 Word Word
361, 35eqsstri 3378 . . . . . . . . . . . . 13 Word
37 simpll 731 . . . . . . . . . . . . 13
3836, 37sseldi 3346 . . . . . . . . . . . 12 Word
39 simpr 448 . . . . . . . . . . . . 13
4036, 39sseldi 3346 . . . . . . . . . . . 12 Word
41 ccatcl 11743 . . . . . . . . . . . 12 Word Word concat Word
4238, 40, 41syl2anc 643 . . . . . . . . . . 11 concat Word
43 simplr 732 . . . . . . . . . . . 12
4436, 43sseldi 3346 . . . . . . . . . . 11 Word
45 ccatcl 11743 . . . . . . . . . . 11 concat Word Word concat concat Word
4642, 44, 45syl2anc 643 . . . . . . . . . 10 concat concat Word
471efgrcl 15347 . . . . . . . . . . . 12 Word
4847simprd 450 . . . . . . . . . . 11 Word
4948ad2antrr 707 . . . . . . . . . 10 Word
5046, 49eleqtrrd 2513 . . . . . . . . 9 concat concat
5134, 50erref 6925 . . . . . . . 8 concat concat concat concat
5251ex 424 . . . . . . 7 concat concat concat concat
5352pm4.71d 616 . . . . . 6 concat concat concat concat
541, 2, 3, 4, 9, 10, 6efgcpbllema 15386 . . . . . . 7 concat concat concat concat
55 df-3an 938 . . . . . . 7 concat concat concat concat concat concat concat concat
56 anidm 626 . . . . . . . 8
5756anbi1i 677 . . . . . . 7 concat concat concat concat concat concat concat concat
5854, 55, 573bitri 263 . . . . . 6 concat concat concat concat
5953, 58syl6bbr 255 . . . . 5
608, 22, 33, 59iserd 6931 . . . 4
611, 2, 3, 4efgtf 15354 . . . . . . . . . 10 splice
6261simprd 450 . . . . . . . . 9
6362adantl 453 . . . . . . . 8
64 ffn 5591 . . . . . . . 8
65 ovelrn 6222 . . . . . . . 8
6663, 64, 653syl 19 . . . . . . 7
67 simplr 732 . . . . . . . . . 10
6862ad2antlr 708 . . . . . . . . . . 11
69 simprl 733 . . . . . . . . . . 11
70 simprr 734 . . . . . . . . . . 11
7168, 69, 70fovrnd 6218 . . . . . . . . . 10
7250adantr 452 . . . . . . . . . . 11 concat concat
7337adantr 452 . . . . . . . . . . . . . . . . 17
7436, 73sseldi 3346 . . . . . . . . . . . . . . . 16 Word
7540adantr 452 . . . . . . . . . . . . . . . . 17 Word
76 swrdcl 11766 . . . . . . . . . . . . . . . . 17 Word substr Word
7775, 76syl 16 . . . . . . . . . . . . . . . 16 substr Word
78 ccatcl 11743 . . . . . . . . . . . . . . . 16 Word substr Word concat substr Word
7974, 77, 78syl2anc 643 . . . . . . . . . . . . . . 15 concat substr Word
803efgmf 15345 . . . . . . . . . . . . . . . . . 18
8180ffvelrni 5869 . . . . . . . . . . . . . . . . 17
8281ad2antll 710 . . . . . . . . . . . . . . . 16
8370, 82s2cld 11833 . . . . . . . . . . . . . . 15 Word
84 ccatcl 11743 . . . . . . . . . . . . . . 15 concat substr Word Word concat substr concat Word
8579, 83, 84syl2anc 643 . . . . . . . . . . . . . 14 concat substr concat Word
86 swrdcl 11766 . . . . . . . . . . . . . . 15 Word substr Word
8775, 86syl 16 . . . . . . . . . . . . . 14 substr Word
8844adantr 452 . . . . . . . . . . . . . 14 Word
89 ccatass 11750 . . . . . . . . . . . . . 14 concat substr concat Word substr Word Word concat substr concat concat substr concat concat substr concat concat substr concat
9085, 87, 88, 89syl3anc 1184 . . . . . . . . . . . . 13 concat substr concat concat substr concat concat substr concat concat substr concat
91 ccatcl 11743 . . . . . . . . . . . . . . . . 17 substr Word Word substr concat Word
9277, 83, 91syl2anc 643 . . . . . . . . . . . . . . . 16 substr concat Word
93 ccatass 11750 . . . . . . . . . . . . . . . 16 Word substr concat Word substr Word concat substr concat concat substr concat substr concat concat substr
9474, 92, 87, 93syl3anc 1184 . . . . . . . . . . . . . . 15 concat substr concat concat substr concat substr concat concat substr
95 ccatass 11750 . . . . . . . . . . . . . . . . 17 Word substr Word Word concat substr concat concat substr concat
9674, 77, 83, 95syl3anc 1184 . . . . . . . . . . . . . . . 16 concat substr concat concat substr concat
9796oveq1d 6096 . . . . . . . . . . . . . . 15 concat substr concat concat substr concat substr concat concat substr
981, 2, 3, 4efgtval 15355 . . . . . . . . . . . . . . . . . 18 splice
9967, 69, 70, 98syl3anc 1184 . . . . . . . . . . . . . . . . 17 splice
100 splval 11780 . . . . . . . . . . . . . . . . . 18 Word splice substr concat concat substr
10167, 69, 69, 83, 100syl13anc 1186 . . . . . . . . . . . . . . . . 17 splice substr concat concat substr
10299, 101eqtrd 2468 . . . . . . . . . . . . . . . 16 substr concat concat substr
103102oveq2d 6097 . . . . . . . . . . . . . . 15 concat concat substr concat concat substr
10494, 97, 1033eqtr4rd 2479 . . . . . . . . . . . . . 14 concat concat substr concat concat substr
105104oveq1d 6096 . . . . . . . . . . . . 13 concat concat concat substr concat concat substr concat
106 lencl 11735 . . . . . . . . . . . . . . . . . . 19 Word
10774, 106syl 16 . . . . . . . . . . . . . . . . . 18
108 nn0uz 10520 . . . . . . . . . . . . . . . . . 18
109107, 108syl6eleq 2526 . . . . . . . . . . . . . . . . 17
110 elfznn0 11083 . . . . . . . . . . . . . . . . . 18
111110ad2antrl 709 . . . . . . . . . . . . . . . . 17
112 uzaddcl 10533 . . . . . . . . . . . . . . . . 17
113109, 111, 112syl2anc 643 . . . . . . . . . . . . . . . 16
11442adantr 452 . . . . . . . . . . . . . . . . . 18 concat Word
115 ccatlen 11744 . . . . . . . . . . . . . . . . . 18 concat Word Word concat concat concat
116114, 88, 115syl2anc 643 . . . . . . . . . . . . . . . . 17 concat concat concat
117 ccatlen 11744 . . . . . . . . . . . . . . . . . . . 20 Word Word concat
11874, 75, 117syl2anc 643 . . . . . . . . . . . . . . . . . . 19 concat
119 elfzuz3 11056 . . . . . . . . . . . . . . . . . . . . . 22
120119ad2antrl 709 . . . . . . . . . . . . . . . . . . . . 21
121107nn0zd 10373 . . . . . . . . . . . . . . . . . . . . 21
122 eluzadd 10514 . . . . . . . . . . . . . . . . . . . . 21
123120, 121, 122syl2anc 643 . . . . . . . . . . . . . . . . . . . 20
124 lencl 11735 . . . . . . . . . . . . . . . . . . . . . . 23 Word
12575, 124syl 16 . . . . . . . . . . . . . . . . . . . . . 22
126125nn0cnd 10276 . . . . . . . . . . . . . . . . . . . . 21
127107nn0cnd 10276 . . . . . . . . . . . . . . . . . . . . 21
128126, 127addcomd 9268 . . . . . . . . . . . . . . . . . . . 20
129111nn0cnd 10276 . . . . . . . . . . . . . . . . . . . . . 22
130129, 127addcomd 9268 . . . . . . . . . . . . . . . . . . . . 21
131130fveq2d 5732 . . . . . . . . . . . . . . . . . . . 20
132123, 128, 1313eltr3d 2516 . . . . . . . . . . . . . . . . . . 19
133118, 132eqeltrd 2510 . . . . . . . . . . . . . . . . . 18 concat
134 lencl 11735 . . . . . . . . . . . . . . . . . . 19 Word
13588, 134syl 16 . . . . . . . . . . . . . . . . . 18
136 uzaddcl 10533 . . . . . . . . . . . . . . . . . 18 concat concat
137133, 135, 136syl2anc 643 . . . . . . . . . . . . . . . . 17 concat
138116, 137eqeltrd 2510 . . . . . . . . . . . . . . . 16 concat concat
139 elfzuzb 11053 . . . . . . . . . . . . . . . 16 concat concat concat concat
140113, 138, 139sylanbrc 646 . . . . . . . . . . . . . . 15 concat concat
1411, 2, 3, 4efgtval 15355 . . . . . . . . . . . . . . 15 concat concat concat concat concat concat concat concat splice
14272, 140, 70, 141syl3anc 1184 . . . . . . . . . . . . . 14 concat concat concat concat splice
143 wrd0 11732 . . . . . . . . . . . . . . . 16 Word
144143a1i 11 . . . . . . . . . . . . . . 15 Word
145 ccatcl 11743 . . . . . . . . . . . . . . . 16 substr Word Word substr concat Word
14687, 88, 145syl2anc 643 . . . . . . . . . . . . . . 15 substr concat Word
147 ccatrid 11749 . . . . . . . . . . . . . . . . . 18 concat substr Word concat substr concat concat substr
14879, 147syl 16 . . . . . . . . . . . . . . . . 17 concat substr concat concat substr
149148oveq1d 6096 . . . . . . . . . . . . . . . 16 concat substr concat concat substr concat concat substr concat substr concat
150 ccatass 11750 . . . . . . . . . . . . . . . . 17 concat substr Word substr Word Word concat substr concat substr concat concat substr concat substr concat
15179, 87, 88, 150syl3anc 1184 . . . . . . . . . . . . . . . 16 concat substr concat substr concat concat substr concat substr concat
152 ccatass 11750 . . . . . . . . . . . . . . . . . . 19 Word substr Word substr Word concat substr concat substr concat substr concat substr
15374, 77, 87, 152syl3anc 1184 . . . . . . . . . . . . . . . . . 18 concat substr concat substr concat substr concat substr
154111, 108syl6eleq 2526 . . . . . . . . . . . . . . . . . . . . . 22
155 eluzfz1 11064 . . . . . . . . . . . . . . . . . . . . . 22
156154, 155syl 16 . . . . . . . . . . . . . . . . . . . . 21
157125, 108syl6eleq 2526 . . . . . . . . . . . . . . . . . . . . . 22
158 eluzfz2 11065 . . . . . . . . . . . . . . . . . . . . . 22
159157, 158syl 16 . . . . . . . . . . . . . . . . . . . . 21
160 ccatswrd 11773 . . . . . . . . . . . . . . . . . . . . 21 Word substr concat substr substr
16175, 156, 69, 159, 160syl13anc 1186 . . . . . . . . . . . . . . . . . . . 20 substr concat substr substr
162 swrdid 11772 . . . . . . . . . . . . . . . . . . . . 21 Word substr
16375, 162syl 16 . . . . . . . . . . . . . . . . . . . 20 substr
164161, 163eqtrd 2468 . . . . . . . . . . . . . . . . . . 19 substr concat substr
165164oveq2d 6097 . . . . . . . . . . . . . . . . . 18 concat substr concat substr concat
166153, 165eqtrd 2468 . . . . . . . . . . . . . . . . 17 concat substr concat substr concat
167166oveq1d 6096 . . . . . . . . . . . . . . . 16 concat substr concat substr concat concat concat
168149, 151, 1673eqtr2rd 2475 . . . . . . . . . . . . . . 15 concat concat concat substr concat concat substr concat
169 ccatlen 11744 . . . . . . . . . . . . . . . . 17 Word substr Word concat substr substr
17074, 77, 169syl2anc 643 . . . . . . . . . . . . . . . 16 concat substr substr
171 swrd0len 11769 . . . . . . . . . . . . . . . . . 18 Word substr
17275, 69, 171syl2anc 643 . . . . . . . . . . . . . . . . 17 substr
173172oveq2d 6097 . . . . . . . . . . . . . . . 16 substr
174170, 173eqtr2d 2469 . . . . . . . . . . . . . . 15 concat substr
175 hash0 11646 . . . . . . . . . . . . . . . . 17
176175oveq2i 6092 . . . . . . . . . . . . . . . 16
177107, 111nn0addcld 10278 . . . . . . . . . . . . . . . . . 18
178177nn0cnd 10276 . . . . . . . . . . . . . . . . 17
179178addid1d 9266 . . . . . . . . . . . . . . . 16
180176, 179syl5req 2481 . . . . . . . . . . . . . . 15
18179, 144, 146, 83, 168, 174, 180splval2 11786 . . . . . . . . . . . . . 14 concat concat splice concat substr concat concat substr concat
182142, 181eqtrd 2468 . . . . . . . . . . . . 13 concat concat concat substr concat concat substr concat
18390, 105, 1823eqtr4d 2478 . . . . . . . . . . . 12 concat concat concat concat
1841, 2, 3, 4efgtf 15354 . . . . . . . . . . . . . . 15 concat concat concat concat concat concat concat concat splice concat concat concat concat
185184simprd 450 . . . . . . . . . . . . . 14 concat concat concat concat concat concat
186 ffn 5591 . . . . . . . . . . . . . 14 concat concat concat concat concat concat concat concat
18772, 185, 1863syl 19 . . . . . . . . . . . . 13 concat concat concat concat
188 fnovrn 6221 . . . . . . . . . . . . 13 concat concat concat concat concat concat concat concat concat concat
189187, 140, 70, 188syl3anc 1184 . . . . . . . . . . . 12 concat concat concat concat
190183, 189eqeltrd 2510 . . . . . . . . . . 11 concat concat concat concat
1911, 2, 3, 4efgi2 15357 . . . . . . . . . . 11 concat concat concat concat concat concat concat concat concat concat
19272, 190, 191syl2anc 643 . . . . . . . . . 10 concat concat concat concat
1931, 2, 3, 4, 9, 10, 6efgcpbllema 15386 . . . . . . . . . 10 concat concat concat concat
19467, 71, 192, 193syl3anbrc 1138 . . . . . . . . 9
195 vex 2959 . . . . . . . . . . 11
196 vex 2959 . . . . . . . . . . 11
197195, 196elec 6944 . . . . . . . . . 10
198 breq2 4216 . . . . . . . . . 10
199197, 198syl5bb 249 . . . . . . . . 9
200194, 199syl5ibrcom 214 . . . . . . . 8
201200rexlimdvva 2837 . . . . . . 7
20266, 201sylbid 207 . . . . . 6
203202ssrdv 3354 . . . . 5
204203ralrimiva 2789 . . . 4
205 fvex 5742 . . . . . . 7 Word
2061, 205eqeltri 2506 . . . . . 6
207 erex 6929 . . . . . 6
20860, 206, 207ee10 1385 . . . . 5
209 ereq1 6912 . . . . . . 7
210 eceq2 6942 . . . . . . . . 9
211210sseq2d 3376 . . . . . . . 8
212211ralbidv 2725 . . . . . . 7
213209, 212anbi12d 692 . . . . . 6
214213elabg 3083 . . . . 5
215208, 214syl 16 . . . 4
21660, 204, 215mpbir2and 889 . . 3
217 intss1 4065 . . 3
218216, 217syl 16 . 2
2195, 218syl5eqss 3392 1
 Colors of variables: wff set class Syntax hints:   wi 4   wb 177   wa 359   w3a 936   wceq 1652   wcel 1725  cab 2422  wral 2705  wrex 2706  crab 2709  cvv 2956   cdif 3317   wss 3320  c0 3628  csn 3814  cpr 3815  cop 3817  cotp 3818  cint 4050  ciun 4093   class class class wbr 4212  copab 4265   cmpt 4266   cid 4493   cxp 4876   crn 4879   wrel 4883   wfn 5449  wf 5450  cfv 5454  (class class class)co 6081   cmpt2 6083  c1o 6717  c2o 6718   wer 6902  cec 6903  cc0 8990  c1 8991   caddc 8993   cmin 9291  cn0 10221  cz 10282  cuz 10488  cfz 11043  ..^cfzo 11135  chash 11618  Word cword 11717   concat cconcat 11718   substr csubstr 11720   splice csplice 11721  cs2 11805   ~FG cefg 15338 This theorem is referenced by:  efgcpbl  15388 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1555  ax-5 1566  ax-17 1626  ax-9 1666  ax-8 1687  ax-13 1727  ax-14 1729  ax-6 1744  ax-7 1749  ax-11 1761  ax-12 1950  ax-ext 2417  ax-rep 4320  ax-sep 4330  ax-nul 4338  ax-pow 4377  ax-pr 4403  ax-un 4701  ax-cnex 9046  ax-resscn 9047  ax-1cn 9048  ax-icn 9049  ax-addcl 9050  ax-addrcl 9051  ax-mulcl 9052  ax-mulrcl 9053  ax-mulcom 9054  ax-addass 9055  ax-mulass 9056  ax-distr 9057  ax-i2m1 9058  ax-1ne0 9059  ax-1rid 9060  ax-rnegex 9061  ax-rrecex 9062  ax-cnre 9063  ax-pre-lttri 9064  ax-pre-lttrn 9065  ax-pre-ltadd 9066  ax-pre-mulgt0 9067 This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1328  df-ex 1551  df-nf 1554  df-sb 1659  df-eu 2285  df-mo 2286  df-clab 2423  df-cleq 2429  df-clel 2432  df-nfc 2561  df-ne 2601  df-nel 2602  df-ral 2710  df-rex 2711  df-reu 2712  df-rab 2714  df-v 2958  df-sbc 3162  df-csb 3252  df-dif 3323  df-un 3325  df-in 3327  df-ss 3334  df-pss 3336  df-nul 3629  df-if 3740  df-pw 3801  df-sn 3820  df-pr 3821  df-tp 3822  df-op 3823  df-ot 3824  df-uni 4016  df-int 4051  df-iun 4095  df-iin 4096  df-br 4213  df-opab 4267  df-mpt 4268  df-tr 4303  df-eprel 4494  df-id 4498  df-po 4503  df-so 4504  df-fr 4541  df-we 4543  df-ord 4584  df-on 4585  df-lim 4586  df-suc 4587  df-om 4846  df-xp 4884  df-rel 4885  df-cnv 4886  df-co 4887  df-dm 4888  df-rn 4889  df-res 4890  df-ima 4891  df-iota 5418  df-fun 5456  df-fn 5457  df-f 5458  df-f1 5459  df-fo 5460  df-f1o 5461  df-fv 5462  df-ov 6084  df-oprab 6085  df-mpt2 6086  df-1st 6349  df-2nd 6350  df-riota 6549  df-recs 6633  df-rdg 6668  df-1o 6724  df-2o 6725  df-oadd 6728  df-er 6905  df-ec 6907  df-map 7020  df-pm 7021  df-en 7110  df-dom 7111  df-sdom 7112  df-fin 7113  df-card 7826  df-pnf 9122  df-mnf 9123  df-xr 9124  df-ltxr 9125  df-le 9126  df-sub 9293  df-neg 9294  df-nn 10001  df-n0 10222  df-z 10283  df-uz 10489  df-fz 11044  df-fzo 11136  df-hash 11619  df-word 11723  df-concat 11724  df-s1 11725  df-substr 11726  df-splice 11727  df-s2 11812  df-efg 15341
 Copyright terms: Public domain W3C validator