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

Theorem clwwlkvbij 24922
Description: There is a bijection between the set of closed walks of a fixed length starting at a fixed vertex represented by walks (as word) and the set of closed walks (as words) of a fixed length starting at a fixed vertex. The difference between these two representations is that in the first case the starting vertex is repeated at the end of the word, and in the second case it is not. (Contributed by Alexander van der Vekens, 29-Sep-2018.)
Assertion
Ref Expression
clwwlkvbij  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  E. f  f : { w  e.  ( ( V WWalksN  E ) `  N )  |  ( ( lastS  `  w )  =  ( w ` 
0 )  /\  (
w `  0 )  =  S ) } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S } )
Distinct variable groups:    f, E, w    f, N, w    S, f, w    f, V, w   
f, X, w    f, Y, w

Proof of Theorem clwwlkvbij
Dummy variables  i  x  y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fvex 5784 . . . . . 6  |-  ( ( V WWalksN  E ) `  N
)  e.  _V
21mptrabex 6045 . . . . 5  |-  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  e.  _V
32resex 5229 . . . 4  |-  ( ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  |`  { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } )  e. 
_V
4 eqid 2382 . . . . 5  |-  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  =  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  |->  ( w substr  <. 0 ,  N >. ) )
5 eqid 2382 . . . . . 6  |-  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  =  { x  e.  (
( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }
65, 4clwwlkf1o 24919 . . . . 5  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  ( w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) } 
|->  ( w substr  <. 0 ,  N >. ) ) : { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) } -1-1-onto-> ( ( V ClWWalksN  E ) `
 N ) )
7 fveq1 5773 . . . . . . . 8  |-  ( y  =  ( w substr  <. 0 ,  N >. )  ->  (
y `  0 )  =  ( ( w substr  <. 0 ,  N >. ) `
 0 ) )
87eqeq1d 2384 . . . . . . 7  |-  ( y  =  ( w substr  <. 0 ,  N >. )  ->  (
( y `  0
)  =  S  <->  ( (
w substr  <. 0 ,  N >. ) `  0 )  =  S ) )
983ad2ant3 1017 . . . . . 6  |-  ( ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  /\  w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) }  /\  y  =  ( w substr  <. 0 ,  N >. ) )  ->  (
( y `  0
)  =  S  <->  ( (
w substr  <. 0 ,  N >. ) `  0 )  =  S ) )
10 fveq2 5774 . . . . . . . . . . . . . . 15  |-  ( x  =  w  ->  ( lastS  `  x )  =  ( lastS  `  w ) )
11 fveq1 5773 . . . . . . . . . . . . . . 15  |-  ( x  =  w  ->  (
x `  0 )  =  ( w ` 
0 ) )
1210, 11eqeq12d 2404 . . . . . . . . . . . . . 14  |-  ( x  =  w  ->  (
( lastS  `  x )  =  ( x `  0
)  <->  ( lastS  `  w )  =  ( w ` 
0 ) ) )
1312elrab 3182 . . . . . . . . . . . . 13  |-  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  <->  ( w  e.  ( ( V WWalksN  E
) `  N )  /\  ( lastS  `  w )  =  ( w ` 
0 ) ) )
14 wwlknimp 24808 . . . . . . . . . . . . . . 15  |-  ( w  e.  ( ( V WWalksN  E ) `  N
)  ->  ( w  e. Word  V  /\  ( # `  w )  =  ( N  +  1 )  /\  A. i  e.  ( 0..^ N ) { ( w `  i ) ,  ( w `  ( i  +  1 ) ) }  e.  ran  E
) )
15 simpll 751 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  w  e. Word  V
)
16 nnz 10803 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( N  e.  NN  ->  N  e.  ZZ )
17 uzid 11015 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( N  e.  ZZ  ->  N  e.  ( ZZ>= `  N )
)
1816, 17syl 16 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( N  e.  NN  ->  N  e.  ( ZZ>= `  N )
)
19 peano2uz 11054 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( N  e.  ( ZZ>= `  N
)  ->  ( N  +  1 )  e.  ( ZZ>= `  N )
)
2018, 19syl 16 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( N  e.  NN  ->  ( N  +  1 )  e.  ( ZZ>= `  N
) )
21 elfz1end 11636 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( N  e.  NN  <->  N  e.  ( 1 ... N
) )
2221biimpi 194 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( N  e.  NN  ->  N  e.  ( 1 ... N
) )
2320, 22jca 530 . . . . . . . . . . . . . . . . . . . . 21  |-  ( N  e.  NN  ->  (
( N  +  1 )  e.  ( ZZ>= `  N )  /\  N  e.  ( 1 ... N
) ) )
24 fzss2 11645 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( N  +  1 )  e.  ( ZZ>= `  N
)  ->  ( 1 ... N )  C_  ( 1 ... ( N  +  1 ) ) )
2524sselda 3417 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( N  +  1 )  e.  ( ZZ>= `  N )  /\  N  e.  ( 1 ... N
) )  ->  N  e.  ( 1 ... ( N  +  1 ) ) )
2623, 25syl 16 . . . . . . . . . . . . . . . . . . . 20  |-  ( N  e.  NN  ->  N  e.  ( 1 ... ( N  +  1 ) ) )
2726adantl 464 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  N  e.  ( 1 ... ( N  +  1 ) ) )
28 oveq2 6204 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( (
# `  w )  =  ( N  + 
1 )  ->  (
1 ... ( # `  w
) )  =  ( 1 ... ( N  +  1 ) ) )
2928eleq2d 2452 . . . . . . . . . . . . . . . . . . . . 21  |-  ( (
# `  w )  =  ( N  + 
1 )  ->  ( N  e.  ( 1 ... ( # `  w
) )  <->  N  e.  ( 1 ... ( N  +  1 ) ) ) )
3029adantl 464 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( w  e. Word  V  /\  ( # `  w )  =  ( N  + 
1 ) )  -> 
( N  e.  ( 1 ... ( # `  w ) )  <->  N  e.  ( 1 ... ( N  +  1 ) ) ) )
3130adantr 463 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  ( N  e.  ( 1 ... ( # `
 w ) )  <-> 
N  e.  ( 1 ... ( N  + 
1 ) ) ) )
3227, 31mpbird 232 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  N  e.  ( 1 ... ( # `  w ) ) )
3315, 32jca 530 . . . . . . . . . . . . . . . . 17  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w ) ) ) )
3433ex 432 . . . . . . . . . . . . . . . 16  |-  ( ( w  e. Word  V  /\  ( # `  w )  =  ( N  + 
1 ) )  -> 
( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  (
1 ... ( # `  w
) ) ) ) )
35343adant3 1014 . . . . . . . . . . . . . . 15  |-  ( ( w  e. Word  V  /\  ( # `  w )  =  ( N  + 
1 )  /\  A. i  e.  ( 0..^ N ) { ( w `  i ) ,  ( w `  ( i  +  1 ) ) }  e.  ran  E )  ->  ( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w
) ) ) ) )
3614, 35syl 16 . . . . . . . . . . . . . 14  |-  ( w  e.  ( ( V WWalksN  E ) `  N
)  ->  ( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `
 w ) ) ) ) )
3736adantr 463 . . . . . . . . . . . . 13  |-  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  ->  ( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `
 w ) ) ) ) )
3813, 37sylbi 195 . . . . . . . . . . . 12  |-  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  ->  ( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w
) ) ) ) )
3938com12 31 . . . . . . . . . . 11  |-  ( N  e.  NN  ->  (
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w
) ) ) ) )
40393ad2ant3 1017 . . . . . . . . . 10  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  ( w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) }  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w ) ) ) ) )
4140imp 427 . . . . . . . . 9  |-  ( ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  /\  w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) } )  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `
 w ) ) ) )
42 swrd0fv0 12576 . . . . . . . . 9  |-  ( ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w
) ) )  -> 
( ( w substr  <. 0 ,  N >. ) `  0
)  =  ( w `
 0 ) )
4341, 42syl 16 . . . . . . . 8  |-  ( ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  /\  w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) } )  ->  ( (
w substr  <. 0 ,  N >. ) `  0 )  =  ( w ` 
0 ) )
4443eqeq1d 2384 . . . . . . 7  |-  ( ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  /\  w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) } )  ->  ( (
( w substr  <. 0 ,  N >. ) `  0
)  =  S  <->  ( w `  0 )  =  S ) )
45443adant3 1014 . . . . . 6  |-  ( ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  /\  w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) }  /\  y  =  ( w substr  <. 0 ,  N >. ) )  ->  (
( ( w substr  <. 0 ,  N >. ) `  0
)  =  S  <->  ( w `  0 )  =  S ) )
469, 45bitrd 253 . . . . 5  |-  ( ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  /\  w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) }  /\  y  =  ( w substr  <. 0 ,  N >. ) )  ->  (
( y `  0
)  =  S  <->  ( w `  0 )  =  S ) )
474, 6, 46f1oresrab 5965 . . . 4  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  ( ( w  e. 
{ x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  |`  { w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S }
) : { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } -1-1-onto-> { y  e.  ( ( V ClWWalksN  E ) `  N )  |  ( y `  0 )  =  S } )
48 f1oeq1 5715 . . . . 5  |-  ( f  =  ( ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  |`  { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } )  -> 
( f : {
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S } -1-1-onto-> {
y  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( y `
 0 )  =  S }  <->  ( (
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  |`  { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } ) : { w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) }  |  ( w ` 
0 )  =  S } -1-1-onto-> { y  e.  ( ( V ClWWalksN  E ) `  N )  |  ( y `  0 )  =  S } ) )
4948spcegv 3120 . . . 4  |-  ( ( ( w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) } 
|->  ( w substr  <. 0 ,  N >. ) )  |`  { w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S }
)  e.  _V  ->  ( ( ( w  e. 
{ x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  |`  { w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S }
) : { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } -1-1-onto-> { y  e.  ( ( V ClWWalksN  E ) `  N )  |  ( y `  0 )  =  S }  ->  E. f  f : {
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S } -1-1-onto-> {
y  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( y `
 0 )  =  S } ) )
503, 47, 49mpsyl 63 . . 3  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  E. f  f : { w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) }  |  ( w ` 
0 )  =  S } -1-1-onto-> { y  e.  ( ( V ClWWalksN  E ) `  N )  |  ( y `  0 )  =  S } )
51 fveq1 5773 . . . . . . 7  |-  ( w  =  y  ->  (
w `  0 )  =  ( y ` 
0 ) )
5251eqeq1d 2384 . . . . . 6  |-  ( w  =  y  ->  (
( w `  0
)  =  S  <->  ( y `  0 )  =  S ) )
5352cbvrabv 3033 . . . . 5  |-  { w  e.  ( ( V ClWWalksN  E ) `
 N )  |  ( w `  0
)  =  S }  =  { y  e.  ( ( V ClWWalksN  E ) `  N )  |  ( y `  0 )  =  S }
54 f1oeq3 5717 . . . . 5  |-  ( { w  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( w `
 0 )  =  S }  =  {
y  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( y `
 0 )  =  S }  ->  (
f : { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S }  <->  f : { w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S } -1-1-onto-> {
y  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( y `
 0 )  =  S } ) )
5553, 54mp1i 12 . . . 4  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  ( f : {
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S } -1-1-onto-> {
w  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( w `
 0 )  =  S }  <->  f : { w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S } -1-1-onto-> {
y  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( y `
 0 )  =  S } ) )
5655exbidv 1722 . . 3  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  ( E. f  f : { w  e. 
{ x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S }  <->  E. f 
f : { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } -1-1-onto-> { y  e.  ( ( V ClWWalksN  E ) `  N )  |  ( y `  0 )  =  S } ) )
5750, 56mpbird 232 . 2  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  E. f  f : { w  e.  {
x  e.  ( ( V WWalksN  E ) `  N
)  |  ( lastS  `  x
)  =  ( x `
 0 ) }  |  ( w ` 
0 )  =  S } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S } )
58 df-rab 2741 . . . . 5  |-  { w  e.  ( ( V WWalksN  E
) `  N )  |  ( ( lastS  `  w
)  =  ( w `
 0 )  /\  ( w `  0
)  =  S ) }  =  { w  |  ( w  e.  ( ( V WWalksN  E
) `  N )  /\  ( ( lastS  `  w
)  =  ( w `
 0 )  /\  ( w `  0
)  =  S ) ) }
59 anass 647 . . . . . . 7  |-  ( ( ( w  e.  ( ( V WWalksN  E ) `  N )  /\  ( lastS  `  w )  =  ( w `  0 ) )  /\  ( w `
 0 )  =  S )  <->  ( w  e.  ( ( V WWalksN  E
) `  N )  /\  ( ( lastS  `  w
)  =  ( w `
 0 )  /\  ( w `  0
)  =  S ) ) )
6059bicomi 202 . . . . . 6  |-  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( ( lastS  `  w )  =  ( w `  0 )  /\  ( w ` 
0 )  =  S ) )  <->  ( (
w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  /\  ( w ` 
0 )  =  S ) )
6160abbii 2516 . . . . 5  |-  { w  |  ( w  e.  ( ( V WWalksN  E
) `  N )  /\  ( ( lastS  `  w
)  =  ( w `
 0 )  /\  ( w `  0
)  =  S ) ) }  =  {
w  |  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  /\  ( w ` 
0 )  =  S ) }
6213bicomi 202 . . . . . . . 8  |-  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  <-> 
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) } )
6362anbi1i 693 . . . . . . 7  |-  ( ( ( w  e.  ( ( V WWalksN  E ) `  N )  /\  ( lastS  `  w )  =  ( w `  0 ) )  /\  ( w `
 0 )  =  S )  <->  ( w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  /\  ( w `
 0 )  =  S ) )
6463abbii 2516 . . . . . 6  |-  { w  |  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  /\  ( w ` 
0 )  =  S ) }  =  {
w  |  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  /\  ( w `  0
)  =  S ) }
65 df-rab 2741 . . . . . 6  |-  { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S }  =  {
w  |  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  /\  ( w `  0
)  =  S ) }
6664, 65eqtr4i 2414 . . . . 5  |-  { w  |  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  /\  ( w ` 
0 )  =  S ) }  =  {
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S }
6758, 61, 663eqtri 2415 . . . 4  |-  { w  e.  ( ( V WWalksN  E
) `  N )  |  ( ( lastS  `  w
)  =  ( w `
 0 )  /\  ( w `  0
)  =  S ) }  =  { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S }
68 f1oeq2 5716 . . . 4  |-  ( { w  e.  ( ( V WWalksN  E ) `  N
)  |  ( ( lastS  `  w )  =  ( w `  0 )  /\  ( w ` 
0 )  =  S ) }  =  {
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S }  ->  ( f : {
w  e.  ( ( V WWalksN  E ) `  N
)  |  ( ( lastS  `  w )  =  ( w `  0 )  /\  ( w ` 
0 )  =  S ) } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S }  <->  f : { w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S } -1-1-onto-> {
w  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( w `
 0 )  =  S } ) )
6967, 68mp1i 12 . . 3  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  ( f : {
w  e.  ( ( V WWalksN  E ) `  N
)  |  ( ( lastS  `  w )  =  ( w `  0 )  /\  ( w ` 
0 )  =  S ) } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S }  <->  f : { w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  | 
( w `  0
)  =  S } -1-1-onto-> {
w  e.  ( ( V ClWWalksN  E ) `  N
)  |  ( w `
 0 )  =  S } ) )
7069exbidv 1722 . 2  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  ( E. f  f : { w  e.  ( ( V WWalksN  E
) `  N )  |  ( ( lastS  `  w
)  =  ( w `
 0 )  /\  ( w `  0
)  =  S ) } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S }  <->  E. f 
f : { w  e.  { x  e.  ( ( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }  |  ( w `
 0 )  =  S } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S } ) )
7157, 70mpbird 232 1  |-  ( ( V  e.  X  /\  E  e.  Y  /\  N  e.  NN )  ->  E. f  f : { w  e.  ( ( V WWalksN  E ) `  N )  |  ( ( lastS  `  w )  =  ( w ` 
0 )  /\  (
w `  0 )  =  S ) } -1-1-onto-> { w  e.  ( ( V ClWWalksN  E ) `  N )  |  ( w `  0 )  =  S } )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 184    /\ wa 367    /\ w3a 971    = wceq 1399   E.wex 1620    e. wcel 1826   {cab 2367   A.wral 2732   {crab 2736   _Vcvv 3034   {cpr 3946   <.cop 3950    |-> cmpt 4425   ran crn 4914    |` cres 4915   -1-1-onto->wf1o 5495   ` cfv 5496  (class class class)co 6196   0cc0 9403   1c1 9404    + caddc 9406   NNcn 10452   ZZcz 10781   ZZ>=cuz 11001   ...cfz 11593  ..^cfzo 11717   #chash 12307  Word cword 12438   lastS clsw 12439   substr csubstr 12442   WWalksN cwwlkn 24799   ClWWalksN cclwwlkn 24870
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1626  ax-4 1639  ax-5 1712  ax-6 1755  ax-7 1798  ax-8 1828  ax-9 1830  ax-10 1845  ax-11 1850  ax-12 1862  ax-13 2006  ax-ext 2360  ax-rep 4478  ax-sep 4488  ax-nul 4496  ax-pow 4543  ax-pr 4601  ax-un 6491  ax-cnex 9459  ax-resscn 9460  ax-1cn 9461  ax-icn 9462  ax-addcl 9463  ax-addrcl 9464  ax-mulcl 9465  ax-mulrcl 9466  ax-mulcom 9467  ax-addass 9468  ax-mulass 9469  ax-distr 9470  ax-i2m1 9471  ax-1ne0 9472  ax-1rid 9473  ax-rnegex 9474  ax-rrecex 9475  ax-cnre 9476  ax-pre-lttri 9477  ax-pre-lttrn 9478  ax-pre-ltadd 9479  ax-pre-mulgt0 9480
This theorem depends on definitions:  df-bi 185  df-or 368  df-an 369  df-3or 972  df-3an 973  df-tru 1402  df-fal 1405  df-ex 1621  df-nf 1625  df-sb 1748  df-eu 2222  df-mo 2223  df-clab 2368  df-cleq 2374  df-clel 2377  df-nfc 2532  df-ne 2579  df-nel 2580  df-ral 2737  df-rex 2738  df-reu 2739  df-rmo 2740  df-rab 2741  df-v 3036  df-sbc 3253  df-csb 3349  df-dif 3392  df-un 3394  df-in 3396  df-ss 3403  df-pss 3405  df-nul 3712  df-if 3858  df-pw 3929  df-sn 3945  df-pr 3947  df-tp 3949  df-op 3951  df-uni 4164  df-int 4200  df-iun 4245  df-br 4368  df-opab 4426  df-mpt 4427  df-tr 4461  df-eprel 4705  df-id 4709  df-po 4714  df-so 4715  df-fr 4752  df-we 4754  df-ord 4795  df-on 4796  df-lim 4797  df-suc 4798  df-xp 4919  df-rel 4920  df-cnv 4921  df-co 4922  df-dm 4923  df-rn 4924  df-res 4925  df-ima 4926  df-iota 5460  df-fun 5498  df-fn 5499  df-f 5500  df-f1 5501  df-fo 5502  df-f1o 5503  df-fv 5504  df-riota 6158  df-ov 6199  df-oprab 6200  df-mpt2 6201  df-om 6600  df-1st 6699  df-2nd 6700  df-recs 6960  df-rdg 6994  df-1o 7048  df-oadd 7052  df-er 7229  df-map 7340  df-pm 7341  df-en 7436  df-dom 7437  df-sdom 7438  df-fin 7439  df-card 8233  df-cda 8461  df-pnf 9541  df-mnf 9542  df-xr 9543  df-ltxr 9544  df-le 9545  df-sub 9720  df-neg 9721  df-nn 10453  df-2 10511  df-n0 10713  df-z 10782  df-uz 11002  df-rp 11140  df-fz 11594  df-fzo 11718  df-hash 12308  df-word 12446  df-lsw 12447  df-concat 12448  df-s1 12449  df-substr 12450  df-wwlk 24800  df-wwlkn 24801  df-clwwlk 24872  df-clwwlkn 24873
This theorem is referenced by:  numclwwlkqhash  25221
  Copyright terms: Public domain W3C validator