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

Theorem efgsdm 15290
Description: Elementhood in the domain of  S, the set of sequences of extensions starting at an irreducible word. (Contributed by Mario Carneiro, 27-Sep-2015.)
Hypotheses
Ref Expression
efgval.w  |-  W  =  (  _I  ` Word  ( I  X.  2o ) )
efgval.r  |-  .~  =  ( ~FG  `  I )
efgval2.m  |-  M  =  ( y  e.  I ,  z  e.  2o  |->  <. y ,  ( 1o 
\  z ) >.
)
efgval2.t  |-  T  =  ( v  e.  W  |->  ( n  e.  ( 0 ... ( # `  v ) ) ,  w  e.  ( I  X.  2o )  |->  ( v splice  <. n ,  n ,  <" w ( M `  w ) "> >. )
) )
efgred.d  |-  D  =  ( W  \  U_ x  e.  W  ran  ( T `  x ) )
efgred.s  |-  S  =  ( m  e.  {
t  e.  (Word  W  \  { (/) } )  |  ( ( t ` 
0 )  e.  D  /\  A. k  e.  ( 1..^ ( # `  t
) ) ( t `
 k )  e. 
ran  ( T `  ( t `  (
k  -  1 ) ) ) ) } 
|->  ( m `  (
( # `  m )  -  1 ) ) )
Assertion
Ref Expression
efgsdm  |-  ( F  e.  dom  S  <->  ( F  e.  (Word  W  \  { (/)
} )  /\  ( F `  0 )  e.  D  /\  A. i  e.  ( 1..^ ( # `  F ) ) ( F `  i )  e.  ran  ( T `
 ( F `  ( i  -  1 ) ) ) ) )
Distinct variable groups:    y, z    i, F    t, n, v, w, y, z    i, m, n, t, v, w, x, M    i, k, T, m, t, x    y,
i, z, W    k, n, v, w, y, z, W, m, t, x    .~ , i, m, t, x, y, z    S, i   
i, I, m, n, t, v, w, x, y, z    D, i, m, t
Allowed substitution hints:    D( x, y, z, w, v, k, n)    .~ ( w, v, k, n)    S( x, y, z, w, v, t, k, m, n)    T( y,
z, w, v, n)    F( x, y, z, w, v, t, k, m, n)    I( k)    M( y, z, k)

Proof of Theorem efgsdm
Dummy variable  f is distinct from all other variables.
StepHypRef Expression
1 fveq1 5668 . . . . 5  |-  ( f  =  F  ->  (
f `  0 )  =  ( F ` 
0 ) )
21eleq1d 2454 . . . 4  |-  ( f  =  F  ->  (
( f `  0
)  e.  D  <->  ( F `  0 )  e.  D ) )
3 fveq2 5669 . . . . . 6  |-  ( f  =  F  ->  ( # `
 f )  =  ( # `  F
) )
43oveq2d 6037 . . . . 5  |-  ( f  =  F  ->  (
1..^ ( # `  f
) )  =  ( 1..^ ( # `  F
) ) )
5 fveq1 5668 . . . . . 6  |-  ( f  =  F  ->  (
f `  i )  =  ( F `  i ) )
6 fveq1 5668 . . . . . . . 8  |-  ( f  =  F  ->  (
f `  ( i  -  1 ) )  =  ( F `  ( i  -  1 ) ) )
76fveq2d 5673 . . . . . . 7  |-  ( f  =  F  ->  ( T `  ( f `  ( i  -  1 ) ) )  =  ( T `  ( F `  ( i  -  1 ) ) ) )
87rneqd 5038 . . . . . 6  |-  ( f  =  F  ->  ran  ( T `  ( f `
 ( i  - 
1 ) ) )  =  ran  ( T `
 ( F `  ( i  -  1 ) ) ) )
95, 8eleq12d 2456 . . . . 5  |-  ( f  =  F  ->  (
( f `  i
)  e.  ran  ( T `  ( f `  ( i  -  1 ) ) )  <->  ( F `  i )  e.  ran  ( T `  ( F `
 ( i  - 
1 ) ) ) ) )
104, 9raleqbidv 2860 . . . 4  |-  ( f  =  F  ->  ( A. i  e.  (
1..^ ( # `  f
) ) ( f `
 i )  e. 
ran  ( T `  ( f `  (
i  -  1 ) ) )  <->  A. i  e.  ( 1..^ ( # `  F ) ) ( F `  i )  e.  ran  ( T `
 ( F `  ( i  -  1 ) ) ) ) )
112, 10anbi12d 692 . . 3  |-  ( f  =  F  ->  (
( ( f ` 
0 )  e.  D  /\  A. i  e.  ( 1..^ ( # `  f
) ) ( f `
 i )  e. 
ran  ( T `  ( f `  (
i  -  1 ) ) ) )  <->  ( ( F `  0 )  e.  D  /\  A. i  e.  ( 1..^ ( # `  F ) ) ( F `  i )  e.  ran  ( T `
 ( F `  ( i  -  1 ) ) ) ) ) )
12 efgval.w . . . . . 6  |-  W  =  (  _I  ` Word  ( I  X.  2o ) )
13 efgval.r . . . . . 6  |-  .~  =  ( ~FG  `  I )
14 efgval2.m . . . . . 6  |-  M  =  ( y  e.  I ,  z  e.  2o  |->  <. y ,  ( 1o 
\  z ) >.
)
15 efgval2.t . . . . . 6  |-  T  =  ( v  e.  W  |->  ( n  e.  ( 0 ... ( # `  v ) ) ,  w  e.  ( I  X.  2o )  |->  ( v splice  <. n ,  n ,  <" w ( M `  w ) "> >. )
) )
16 efgred.d . . . . . 6  |-  D  =  ( W  \  U_ x  e.  W  ran  ( T `  x ) )
17 efgred.s . . . . . 6  |-  S  =  ( m  e.  {
t  e.  (Word  W  \  { (/) } )  |  ( ( t ` 
0 )  e.  D  /\  A. k  e.  ( 1..^ ( # `  t
) ) ( t `
 k )  e. 
ran  ( T `  ( t `  (
k  -  1 ) ) ) ) } 
|->  ( m `  (
( # `  m )  -  1 ) ) )
1812, 13, 14, 15, 16, 17efgsf 15289 . . . . 5  |-  S : { t  e.  (Word 
W  \  { (/) } )  |  ( ( t `
 0 )  e.  D  /\  A. k  e.  ( 1..^ ( # `  t ) ) ( t `  k )  e.  ran  ( T `
 ( t `  ( k  -  1 ) ) ) ) } --> W
1918fdmi 5537 . . . 4  |-  dom  S  =  { t  e.  (Word 
W  \  { (/) } )  |  ( ( t `
 0 )  e.  D  /\  A. k  e.  ( 1..^ ( # `  t ) ) ( t `  k )  e.  ran  ( T `
 ( t `  ( k  -  1 ) ) ) ) }
20 fveq1 5668 . . . . . . 7  |-  ( t  =  f  ->  (
t `  0 )  =  ( f ` 
0 ) )
2120eleq1d 2454 . . . . . 6  |-  ( t  =  f  ->  (
( t `  0
)  e.  D  <->  ( f `  0 )  e.  D ) )
22 fveq2 5669 . . . . . . . . 9  |-  ( k  =  i  ->  (
t `  k )  =  ( t `  i ) )
23 oveq1 6028 . . . . . . . . . . . 12  |-  ( k  =  i  ->  (
k  -  1 )  =  ( i  - 
1 ) )
2423fveq2d 5673 . . . . . . . . . . 11  |-  ( k  =  i  ->  (
t `  ( k  -  1 ) )  =  ( t `  ( i  -  1 ) ) )
2524fveq2d 5673 . . . . . . . . . 10  |-  ( k  =  i  ->  ( T `  ( t `  ( k  -  1 ) ) )  =  ( T `  (
t `  ( i  -  1 ) ) ) )
2625rneqd 5038 . . . . . . . . 9  |-  ( k  =  i  ->  ran  ( T `  ( t `
 ( k  - 
1 ) ) )  =  ran  ( T `
 ( t `  ( i  -  1 ) ) ) )
2722, 26eleq12d 2456 . . . . . . . 8  |-  ( k  =  i  ->  (
( t `  k
)  e.  ran  ( T `  ( t `  ( k  -  1 ) ) )  <->  ( t `  i )  e.  ran  ( T `  ( t `
 ( i  - 
1 ) ) ) ) )
2827cbvralv 2876 . . . . . . 7  |-  ( A. k  e.  ( 1..^ ( # `  t
) ) ( t `
 k )  e. 
ran  ( T `  ( t `  (
k  -  1 ) ) )  <->  A. i  e.  ( 1..^ ( # `  t ) ) ( t `  i )  e.  ran  ( T `
 ( t `  ( i  -  1 ) ) ) )
29 fveq2 5669 . . . . . . . . 9  |-  ( t  =  f  ->  ( # `
 t )  =  ( # `  f
) )
3029oveq2d 6037 . . . . . . . 8  |-  ( t  =  f  ->  (
1..^ ( # `  t
) )  =  ( 1..^ ( # `  f
) ) )
31 fveq1 5668 . . . . . . . . 9  |-  ( t  =  f  ->  (
t `  i )  =  ( f `  i ) )
32 fveq1 5668 . . . . . . . . . . 11  |-  ( t  =  f  ->  (
t `  ( i  -  1 ) )  =  ( f `  ( i  -  1 ) ) )
3332fveq2d 5673 . . . . . . . . . 10  |-  ( t  =  f  ->  ( T `  ( t `  ( i  -  1 ) ) )  =  ( T `  (
f `  ( i  -  1 ) ) ) )
3433rneqd 5038 . . . . . . . . 9  |-  ( t  =  f  ->  ran  ( T `  ( t `
 ( i  - 
1 ) ) )  =  ran  ( T `
 ( f `  ( i  -  1 ) ) ) )
3531, 34eleq12d 2456 . . . . . . . 8  |-  ( t  =  f  ->  (
( t `  i
)  e.  ran  ( T `  ( t `  ( i  -  1 ) ) )  <->  ( f `  i )  e.  ran  ( T `  ( f `
 ( i  - 
1 ) ) ) ) )
3630, 35raleqbidv 2860 . . . . . . 7  |-  ( t  =  f  ->  ( A. i  e.  (
1..^ ( # `  t
) ) ( t `
 i )  e. 
ran  ( T `  ( t `  (
i  -  1 ) ) )  <->  A. i  e.  ( 1..^ ( # `  f ) ) ( f `  i )  e.  ran  ( T `
 ( f `  ( i  -  1 ) ) ) ) )
3728, 36syl5bb 249 . . . . . 6  |-  ( t  =  f  ->  ( A. k  e.  (
1..^ ( # `  t
) ) ( t `
 k )  e. 
ran  ( T `  ( t `  (
k  -  1 ) ) )  <->  A. i  e.  ( 1..^ ( # `  f ) ) ( f `  i )  e.  ran  ( T `
 ( f `  ( i  -  1 ) ) ) ) )
3821, 37anbi12d 692 . . . . 5  |-  ( t  =  f  ->  (
( ( t ` 
0 )  e.  D  /\  A. k  e.  ( 1..^ ( # `  t
) ) ( t `
 k )  e. 
ran  ( T `  ( t `  (
k  -  1 ) ) ) )  <->  ( (
f `  0 )  e.  D  /\  A. i  e.  ( 1..^ ( # `  f ) ) ( f `  i )  e.  ran  ( T `
 ( f `  ( i  -  1 ) ) ) ) ) )
3938cbvrabv 2899 . . . 4  |-  { t  e.  (Word  W  \  { (/) } )  |  ( ( t ` 
0 )  e.  D  /\  A. k  e.  ( 1..^ ( # `  t
) ) ( t `
 k )  e. 
ran  ( T `  ( t `  (
k  -  1 ) ) ) ) }  =  { f  e.  (Word  W  \  { (/)
} )  |  ( ( f `  0
)  e.  D  /\  A. i  e.  ( 1..^ ( # `  f
) ) ( f `
 i )  e. 
ran  ( T `  ( f `  (
i  -  1 ) ) ) ) }
4019, 39eqtri 2408 . . 3  |-  dom  S  =  { f  e.  (Word 
W  \  { (/) } )  |  ( ( f `
 0 )  e.  D  /\  A. i  e.  ( 1..^ ( # `  f ) ) ( f `  i )  e.  ran  ( T `
 ( f `  ( i  -  1 ) ) ) ) }
4111, 40elrab2 3038 . 2  |-  ( F  e.  dom  S  <->  ( F  e.  (Word  W  \  { (/)
} )  /\  (
( F `  0
)  e.  D  /\  A. i  e.  ( 1..^ ( # `  F
) ) ( F `
 i )  e. 
ran  ( T `  ( F `  ( i  -  1 ) ) ) ) ) )
42 3anass 940 . 2  |-  ( ( F  e.  (Word  W  \  { (/) } )  /\  ( F `  0 )  e.  D  /\  A. i  e.  ( 1..^ ( # `  F
) ) ( F `
 i )  e. 
ran  ( T `  ( F `  ( i  -  1 ) ) ) )  <->  ( F  e.  (Word  W  \  { (/)
} )  /\  (
( F `  0
)  e.  D  /\  A. i  e.  ( 1..^ ( # `  F
) ) ( F `
 i )  e. 
ran  ( T `  ( F `  ( i  -  1 ) ) ) ) ) )
4341, 42bitr4i 244 1  |-  ( F  e.  dom  S  <->  ( F  e.  (Word  W  \  { (/)
} )  /\  ( F `  0 )  e.  D  /\  A. i  e.  ( 1..^ ( # `  F ) ) ( F `  i )  e.  ran  ( T `
 ( F `  ( i  -  1 ) ) ) ) )
Colors of variables: wff set class
Syntax hints:    <-> wb 177    /\ wa 359    /\ w3a 936    = wceq 1649    e. wcel 1717   A.wral 2650   {crab 2654    \ cdif 3261   (/)c0 3572   {csn 3758   <.cop 3761   <.cotp 3762   U_ciun 4036    e. cmpt 4208    _I cid 4435    X. cxp 4817   dom cdm 4819   ran crn 4820   ` cfv 5395  (class class class)co 6021    e. cmpt2 6023   1oc1o 6654   2oc2o 6655   0cc0 8924   1c1 8925    - cmin 9224   ...cfz 10976  ..^cfzo 11066   #chash 11546  Word cword 11645   splice csplice 11649   <"cs2 11733   ~FG cefg 15266
This theorem is referenced by:  efgsdmi  15292  efgsrel  15294  efgs1  15295  efgs1b  15296  efgsp1  15297  efgsres  15298  efgsfo  15299  efgredlema  15300  efgredlemf  15301  efgredlemd  15304  efgredlemc  15305  efgredlem  15307  efgrelexlemb  15310  efgredeu  15312  efgred2  15313
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-13 1719  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2369  ax-rep 4262  ax-sep 4272  ax-nul 4280  ax-pow 4319  ax-pr 4345  ax-un 4642  ax-cnex 8980  ax-resscn 8981  ax-1cn 8982  ax-icn 8983  ax-addcl 8984  ax-addrcl 8985  ax-mulcl 8986  ax-mulrcl 8987  ax-mulcom 8988  ax-addass 8989  ax-mulass 8990  ax-distr 8991  ax-i2m1 8992  ax-1ne0 8993  ax-1rid 8994  ax-rnegex 8995  ax-rrecex 8996  ax-cnre 8997  ax-pre-lttri 8998  ax-pre-lttrn 8999  ax-pre-ltadd 9000  ax-pre-mulgt0 9001
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2243  df-mo 2244  df-clab 2375  df-cleq 2381  df-clel 2384  df-nfc 2513  df-ne 2553  df-nel 2554  df-ral 2655  df-rex 2656  df-reu 2657  df-rab 2659  df-v 2902  df-sbc 3106  df-csb 3196  df-dif 3267  df-un 3269  df-in 3271  df-ss 3278  df-pss 3280  df-nul 3573  df-if 3684  df-pw 3745  df-sn 3764  df-pr 3765  df-tp 3766  df-op 3767  df-uni 3959  df-int 3994  df-iun 4038  df-br 4155  df-opab 4209  df-mpt 4210  df-tr 4245  df-eprel 4436  df-id 4440  df-po 4445  df-so 4446  df-fr 4483  df-we 4485  df-ord 4526  df-on 4527  df-lim 4528  df-suc 4529  df-om 4787  df-xp 4825  df-rel 4826  df-cnv 4827  df-co 4828  df-dm 4829  df-rn 4830  df-res 4831  df-ima 4832  df-iota 5359  df-fun 5397  df-fn 5398  df-f 5399  df-f1 5400  df-fo 5401  df-f1o 5402  df-fv 5403  df-ov 6024  df-oprab 6025  df-mpt2 6026  df-1st 6289  df-2nd 6290  df-riota 6486  df-recs 6570  df-rdg 6605  df-1o 6661  df-oadd 6665  df-er 6842  df-en 7047  df-dom 7048  df-sdom 7049  df-fin 7050  df-card 7760  df-pnf 9056  df-mnf 9057  df-xr 9058  df-ltxr 9059  df-le 9060  df-sub 9226  df-neg 9227  df-nn 9934  df-n0 10155  df-z 10216  df-uz 10422  df-fz 10977  df-fzo 11067  df-hash 11547  df-word 11651
  Copyright terms: Public domain W3C validator