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

Theorem clwwlkvbij 24465
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 5869 . . . . . . 7  |-  ( ( V WWalksN  E ) `  N
)  e.  _V
21rabex 4593 . . . . . 6  |-  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  e.  _V
32mptex 6124 . . . . 5  |-  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  |->  ( w substr  <. 0 ,  N >. ) )  e.  _V
43resex 5310 . . . 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
5 eqid 2462 . . . . 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 >. ) )
6 eqid 2462 . . . . . 6  |-  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  =  { x  e.  (
( V WWalksN  E ) `  N )  |  ( lastS  `  x )  =  ( x `  0 ) }
76, 5clwwlkf1o 24462 . . . . 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 ) )
8 fveq1 5858 . . . . . . . 8  |-  ( y  =  ( w substr  <. 0 ,  N >. )  ->  (
y `  0 )  =  ( ( w substr  <. 0 ,  N >. ) `
 0 ) )
98eqeq1d 2464 . . . . . . 7  |-  ( y  =  ( w substr  <. 0 ,  N >. )  ->  (
( y `  0
)  =  S  <->  ( (
w substr  <. 0 ,  N >. ) `  0 )  =  S ) )
1093ad2ant3 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 >. ) )  ->  (
( y `  0
)  =  S  <->  ( (
w substr  <. 0 ,  N >. ) `  0 )  =  S ) )
11 fveq2 5859 . . . . . . . . . . . . . . 15  |-  ( x  =  w  ->  ( lastS  `  x )  =  ( lastS  `  w ) )
12 fveq1 5858 . . . . . . . . . . . . . . 15  |-  ( x  =  w  ->  (
x `  0 )  =  ( w ` 
0 ) )
1311, 12eqeq12d 2484 . . . . . . . . . . . . . 14  |-  ( x  =  w  ->  (
( lastS  `  x )  =  ( x `  0
)  <->  ( lastS  `  w )  =  ( w ` 
0 ) ) )
1413elrab 3256 . . . . . . . . . . . . 13  |-  ( w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) }  <->  ( w  e.  ( ( V WWalksN  E
) `  N )  /\  ( lastS  `  w )  =  ( w ` 
0 ) ) )
15 wwlknimp 24351 . . . . . . . . . . . . . . 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
) )
16 simpll 753 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  w  e. Word  V
)
17 nnz 10877 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( N  e.  NN  ->  N  e.  ZZ )
18 uzid 11087 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( N  e.  ZZ  ->  N  e.  ( ZZ>= `  N )
)
1917, 18syl 16 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( N  e.  NN  ->  N  e.  ( ZZ>= `  N )
)
20 peano2uz 11125 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( N  e.  ( ZZ>= `  N
)  ->  ( N  +  1 )  e.  ( ZZ>= `  N )
)
2119, 20syl 16 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( N  e.  NN  ->  ( N  +  1 )  e.  ( ZZ>= `  N
) )
22 elfz1end 11706 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( N  e.  NN  <->  N  e.  ( 1 ... N
) )
2322biimpi 194 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( N  e.  NN  ->  N  e.  ( 1 ... N
) )
2421, 23jca 532 . . . . . . . . . . . . . . . . . . . . 21  |-  ( N  e.  NN  ->  (
( N  +  1 )  e.  ( ZZ>= `  N )  /\  N  e.  ( 1 ... N
) ) )
25 fzss2 11714 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( N  +  1 )  e.  ( ZZ>= `  N
)  ->  ( 1 ... N )  C_  ( 1 ... ( N  +  1 ) ) )
2625sselda 3499 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( N  +  1 )  e.  ( ZZ>= `  N )  /\  N  e.  ( 1 ... N
) )  ->  N  e.  ( 1 ... ( N  +  1 ) ) )
2724, 26syl 16 . . . . . . . . . . . . . . . . . . . 20  |-  ( N  e.  NN  ->  N  e.  ( 1 ... ( N  +  1 ) ) )
2827adantl 466 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  N  e.  ( 1 ... ( N  +  1 ) ) )
29 oveq2 6285 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( (
# `  w )  =  ( N  + 
1 )  ->  (
1 ... ( # `  w
) )  =  ( 1 ... ( N  +  1 ) ) )
3029eleq2d 2532 . . . . . . . . . . . . . . . . . . . . 21  |-  ( (
# `  w )  =  ( N  + 
1 )  ->  ( N  e.  ( 1 ... ( # `  w
) )  <->  N  e.  ( 1 ... ( N  +  1 ) ) ) )
3130adantl 466 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( w  e. Word  V  /\  ( # `  w )  =  ( N  + 
1 ) )  -> 
( N  e.  ( 1 ... ( # `  w ) )  <->  N  e.  ( 1 ... ( N  +  1 ) ) ) )
3231adantr 465 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  ( N  e.  ( 1 ... ( # `
 w ) )  <-> 
N  e.  ( 1 ... ( N  + 
1 ) ) ) )
3328, 32mpbird 232 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  N  e.  ( 1 ... ( # `  w ) ) )
3416, 33jca 532 . . . . . . . . . . . . . . . . 17  |-  ( ( ( w  e. Word  V  /\  ( # `  w
)  =  ( N  +  1 ) )  /\  N  e.  NN )  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w ) ) ) )
3534ex 434 . . . . . . . . . . . . . . . 16  |-  ( ( w  e. Word  V  /\  ( # `  w )  =  ( N  + 
1 ) )  -> 
( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  (
1 ... ( # `  w
) ) ) ) )
36353adant3 1011 . . . . . . . . . . . . . . 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
) ) ) ) )
3715, 36syl 16 . . . . . . . . . . . . . 14  |-  ( w  e.  ( ( V WWalksN  E ) `  N
)  ->  ( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `
 w ) ) ) ) )
3837adantr 465 . . . . . . . . . . . . 13  |-  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  ->  ( N  e.  NN  ->  ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `
 w ) ) ) ) )
3914, 38sylbi 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
) ) ) ) )
4039com12 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
) ) ) ) )
41403ad2ant3 1014 . . . . . . . . . 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 ) ) ) ) )
4241imp 429 . . . . . . . . 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 ) ) ) )
43 swrd0fv0 12619 . . . . . . . . 9  |-  ( ( w  e. Word  V  /\  N  e.  ( 1 ... ( # `  w
) ) )  -> 
( ( w substr  <. 0 ,  N >. ) `  0
)  =  ( w `
 0 ) )
4442, 43syl 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 ) )
4544eqeq1d 2464 . . . . . . 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 ) )
46453adant3 1011 . . . . . 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 ) )
4710, 46bitrd 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 ) )
485, 7, 47f1oresrab 6046 . . . 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 } )
49 f1oeq1 5800 . . . . 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 } ) )
5049spcegv 3194 . . . 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 } ) )
514, 48, 50mpsyl 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 } )
52 fveq1 5858 . . . . . . 7  |-  ( w  =  y  ->  (
w `  0 )  =  ( y ` 
0 ) )
5352eqeq1d 2464 . . . . . 6  |-  ( w  =  y  ->  (
( w `  0
)  =  S  <->  ( y `  0 )  =  S ) )
5453cbvrabv 3107 . . . . 5  |-  { w  e.  ( ( V ClWWalksN  E ) `
 N )  |  ( w `  0
)  =  S }  =  { y  e.  ( ( V ClWWalksN  E ) `  N )  |  ( y `  0 )  =  S }
55 f1oeq3 5802 . . . . 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 } ) )
5654, 55mp1i 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 } ) )
5756exbidv 1685 . . 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 } ) )
5851, 57mpbird 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 } )
59 df-rab 2818 . . . . 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 ) ) }
60 anass 649 . . . . . . 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 ) ) )
6160bicomi 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 ) )
6261abbii 2596 . . . . 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 ) }
6314bicomi 202 . . . . . . . 8  |-  ( ( w  e.  ( ( V WWalksN  E ) `  N
)  /\  ( lastS  `  w
)  =  ( w `
 0 ) )  <-> 
w  e.  { x  e.  ( ( V WWalksN  E
) `  N )  |  ( lastS  `  x )  =  ( x ` 
0 ) } )
6463anbi1i 695 . . . . . . 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 ) )
6564abbii 2596 . . . . . 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 ) }
66 df-rab 2818 . . . . . 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 ) }
6765, 66eqtr4i 2494 . . . . 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 }
6859, 62, 673eqtri 2495 . . . 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 }
69 f1oeq2 5801 . . . 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 } ) )
7068, 69mp1i 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 } ) )
7170exbidv 1685 . 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 } ) )
7258, 71mpbird 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 369    /\ w3a 968    = wceq 1374   E.wex 1591    e. wcel 1762   {cab 2447   A.wral 2809   {crab 2813   _Vcvv 3108   {cpr 4024   <.cop 4028    |-> cmpt 4500   ran crn 4995    |` cres 4996   -1-1-onto->wf1o 5580   ` cfv 5581  (class class class)co 6277   0cc0 9483   1c1 9484    + caddc 9486   NNcn 10527   ZZcz 10855   ZZ>=cuz 11073   ...cfz 11663  ..^cfzo 11783   #chash 12362  Word cword 12489   lastS clsw 12490   substr csubstr 12493   WWalksN cwwlkn 24342   ClWWalksN cclwwlkn 24413
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1596  ax-4 1607  ax-5 1675  ax-6 1714  ax-7 1734  ax-8 1764  ax-9 1766  ax-10 1781  ax-11 1786  ax-12 1798  ax-13 1963  ax-ext 2440  ax-rep 4553  ax-sep 4563  ax-nul 4571  ax-pow 4620  ax-pr 4681  ax-un 6569  ax-cnex 9539  ax-resscn 9540  ax-1cn 9541  ax-icn 9542  ax-addcl 9543  ax-addrcl 9544  ax-mulcl 9545  ax-mulrcl 9546  ax-mulcom 9547  ax-addass 9548  ax-mulass 9549  ax-distr 9550  ax-i2m1 9551  ax-1ne0 9552  ax-1rid 9553  ax-rnegex 9554  ax-rrecex 9555  ax-cnre 9556  ax-pre-lttri 9557  ax-pre-lttrn 9558  ax-pre-ltadd 9559  ax-pre-mulgt0 9560
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 969  df-3an 970  df-tru 1377  df-fal 1380  df-ex 1592  df-nf 1595  df-sb 1707  df-eu 2274  df-mo 2275  df-clab 2448  df-cleq 2454  df-clel 2457  df-nfc 2612  df-ne 2659  df-nel 2660  df-ral 2814  df-rex 2815  df-reu 2816  df-rab 2818  df-v 3110  df-sbc 3327  df-csb 3431  df-dif 3474  df-un 3476  df-in 3478  df-ss 3485  df-pss 3487  df-nul 3781  df-if 3935  df-pw 4007  df-sn 4023  df-pr 4025  df-tp 4027  df-op 4029  df-uni 4241  df-int 4278  df-iun 4322  df-br 4443  df-opab 4501  df-mpt 4502  df-tr 4536  df-eprel 4786  df-id 4790  df-po 4795  df-so 4796  df-fr 4833  df-we 4835  df-ord 4876  df-on 4877  df-lim 4878  df-suc 4879  df-xp 5000  df-rel 5001  df-cnv 5002  df-co 5003  df-dm 5004  df-rn 5005  df-res 5006  df-ima 5007  df-iota 5544  df-fun 5583  df-fn 5584  df-f 5585  df-f1 5586  df-fo 5587  df-f1o 5588  df-fv 5589  df-riota 6238  df-ov 6280  df-oprab 6281  df-mpt2 6282  df-om 6674  df-1st 6776  df-2nd 6777  df-recs 7034  df-rdg 7068  df-1o 7122  df-oadd 7126  df-er 7303  df-map 7414  df-pm 7415  df-en 7509  df-dom 7510  df-sdom 7511  df-fin 7512  df-card 8311  df-pnf 9621  df-mnf 9622  df-xr 9623  df-ltxr 9624  df-le 9625  df-sub 9798  df-neg 9799  df-nn 10528  df-n0 10787  df-z 10856  df-uz 11074  df-fz 11664  df-fzo 11784  df-hash 12363  df-word 12497  df-lsw 12498  df-concat 12499  df-s1 12500  df-substr 12501  df-wwlk 24343  df-wwlkn 24344  df-clwwlk 24415  df-clwwlkn 24416
This theorem is referenced by:  numclwwlkqhash  24765
  Copyright terms: Public domain W3C validator