Metamath Proof Explorer

Theorem ispth

Description: Conditions for a pair of classes/functions to be a path (in an undirected graph). (Contributed by Alexander van der Vekens, 21-Oct-2017) (Revised by AV, 9-Jan-2021) (Revised by AV, 29-Oct-2021)

Ref Expression
Assertion ispth 
|- ( F ( Paths ` G ) P <-> ( F ( Trails ` G ) P /\ Fun `' ( P |` ( 1 ..^ ( # ` F ) ) ) /\ ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) = (/) ) )

Proof

Step Hyp Ref Expression
1 pthsfval 
 |-  ( Paths ` G ) = { <. f , p >. | ( f ( Trails ` G ) p /\ Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) /\ ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) ) }
2 3anass 
 |-  ( ( f ( Trails ` G ) p /\ Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) /\ ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) ) <-> ( f ( Trails ` G ) p /\ ( Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) /\ ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) ) ) )
3 2 opabbii 
 |-  { <. f , p >. | ( f ( Trails ` G ) p /\ Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) /\ ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) ) } = { <. f , p >. | ( f ( Trails ` G ) p /\ ( Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) /\ ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) ) ) }
4 1 3 eqtri 
 |-  ( Paths ` G ) = { <. f , p >. | ( f ( Trails ` G ) p /\ ( Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) /\ ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) ) ) }
5 simpr 
 |-  ( ( f = F /\ p = P ) -> p = P )
6 fveq2 
 |-  ( f = F -> ( # ` f ) = ( # ` F ) )
7 6 oveq2d 
 |-  ( f = F -> ( 1 ..^ ( # ` f ) ) = ( 1 ..^ ( # ` F ) ) )
8 7 adantr 
 |-  ( ( f = F /\ p = P ) -> ( 1 ..^ ( # ` f ) ) = ( 1 ..^ ( # ` F ) ) )
9 5 8 reseq12d 
 |-  ( ( f = F /\ p = P ) -> ( p |` ( 1 ..^ ( # ` f ) ) ) = ( P |` ( 1 ..^ ( # ` F ) ) ) )
10 9 cnveqd 
 |-  ( ( f = F /\ p = P ) -> `' ( p |` ( 1 ..^ ( # ` f ) ) ) = `' ( P |` ( 1 ..^ ( # ` F ) ) ) )
11 10 funeqd 
 |-  ( ( f = F /\ p = P ) -> ( Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) <-> Fun `' ( P |` ( 1 ..^ ( # ` F ) ) ) ) )
12 6 preq2d 
 |-  ( f = F -> { 0 , ( # ` f ) } = { 0 , ( # ` F ) } )
13 12 adantr 
 |-  ( ( f = F /\ p = P ) -> { 0 , ( # ` f ) } = { 0 , ( # ` F ) } )
14 5 13 imaeq12d 
 |-  ( ( f = F /\ p = P ) -> ( p " { 0 , ( # ` f ) } ) = ( P " { 0 , ( # ` F ) } ) )
15 5 8 imaeq12d 
 |-  ( ( f = F /\ p = P ) -> ( p " ( 1 ..^ ( # ` f ) ) ) = ( P " ( 1 ..^ ( # ` F ) ) ) )
16 14 15 ineq12d 
 |-  ( ( f = F /\ p = P ) -> ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) )
17 16 eqeq1d 
 |-  ( ( f = F /\ p = P ) -> ( ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) <-> ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) = (/) ) )
18 11 17 anbi12d 
 |-  ( ( f = F /\ p = P ) -> ( ( Fun `' ( p |` ( 1 ..^ ( # ` f ) ) ) /\ ( ( p " { 0 , ( # ` f ) } ) i^i ( p " ( 1 ..^ ( # ` f ) ) ) ) = (/) ) <-> ( Fun `' ( P |` ( 1 ..^ ( # ` F ) ) ) /\ ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) = (/) ) ) )
19 reltrls 
 |-  Rel ( Trails ` G )
20 4 18 19 brfvopabrbr 
 |-  ( F ( Paths ` G ) P <-> ( F ( Trails ` G ) P /\ ( Fun `' ( P |` ( 1 ..^ ( # ` F ) ) ) /\ ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) = (/) ) ) )
21 3anass 
 |-  ( ( F ( Trails ` G ) P /\ Fun `' ( P |` ( 1 ..^ ( # ` F ) ) ) /\ ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) = (/) ) <-> ( F ( Trails ` G ) P /\ ( Fun `' ( P |` ( 1 ..^ ( # ` F ) ) ) /\ ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) = (/) ) ) )
22 20 21 bitr4i 
 |-  ( F ( Paths ` G ) P <-> ( F ( Trails ` G ) P /\ Fun `' ( P |` ( 1 ..^ ( # ` F ) ) ) /\ ( ( P " { 0 , ( # ` F ) } ) i^i ( P " ( 1 ..^ ( # ` F ) ) ) ) = (/) ) )