Users' Mathboxes Mathbox for Alexander van der Vekens < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  incistruhgr Structured version   Visualization version   Unicode version

Theorem incistruhgr 39325
Description: An incident structure  <. P ,  L ,  I >. "where  P is a set whose elements are called points,  L is a distinct set whose elements are called lines and  I  C_  ( P  X.  L ) is the incidence relation" ( see Wikipedia "Incidence structure" (24-Oct-2020), https://en.wikipedia.org/wiki/Incidence_structure) implies an undirected hypergraph, if the incidence relation is right-total (to exclude empty edges). The points become the vertices, and the edge function is derived from the incidence relation by mapping each line ("edge") to the set of vertices incident to the line/edge. With  P  =  (
Base `  S ) and by defining two new slots for lines and incidence relations (analogous to LineG and Itv) and enhancing the definition of iEdg accordingly, it would even be possible to express that a corresponding incident structure is an undirected hypergraph. By choosing the incident relation appropriately, other kinds of undirected graphs (pseudographs, multigraphs, simple graphs, etc.) could be defined. (Contributed by AV, 24-Oct-2020.)
Hypotheses
Ref Expression
incistruhgr.v  |-  V  =  (Vtx `  G )
incistruhgr.e  |-  E  =  (iEdg `  G )
Assertion
Ref Expression
incistruhgr  |-  ( ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L )  ->  ( ( V  =  P  /\  E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) )  ->  G  e. UHGraph  ) )
Distinct variable groups:    e, E    e, G    e, I, v   
e, L, v    P, e, v    e, V, v   
e, W
Allowed substitution hints:    E( v)    G( v)    W( v)

Proof of Theorem incistruhgr
StepHypRef Expression
1 id 22 . . . . . . . . . 10  |-  ( V  =  P  ->  V  =  P )
21rabeqdv 3025 . . . . . . . . 9  |-  ( V  =  P  ->  { v  e.  V  |  v I e }  =  { v  e.  P  |  v I e } )
32mpteq2dv 4483 . . . . . . . 8  |-  ( V  =  P  ->  (
e  e.  L  |->  { v  e.  V  | 
v I e } )  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) )
43eqeq2d 2481 . . . . . . 7  |-  ( V  =  P  ->  ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  <-> 
E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) ) )
5 xpeq1 4853 . . . . . . . . 9  |-  ( V  =  P  ->  ( V  X.  L )  =  ( P  X.  L
) )
65sseq2d 3446 . . . . . . . 8  |-  ( V  =  P  ->  (
I  C_  ( V  X.  L )  <->  I  C_  ( P  X.  L ) ) )
763anbi2d 1370 . . . . . . 7  |-  ( V  =  P  ->  (
( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  <-> 
( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L ) ) )
84, 7anbi12d 725 . . . . . 6  |-  ( V  =  P  ->  (
( E  =  ( e  e.  L  |->  { v  e.  V  | 
v I e } )  /\  ( G  e.  W  /\  I  C_  ( V  X.  L
)  /\  ran  I  =  L ) )  <->  ( E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } )  /\  ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L ) ) ) )
9 dmeq 5040 . . . . . . . . 9  |-  ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  ->  dom  E  =  dom  (
e  e.  L  |->  { v  e.  V  | 
v I e } ) )
10 incistruhgr.v . . . . . . . . . . . . 13  |-  V  =  (Vtx `  G )
11 fvex 5889 . . . . . . . . . . . . 13  |-  (Vtx `  G )  e.  _V
1210, 11eqeltri 2545 . . . . . . . . . . . 12  |-  V  e. 
_V
1312rabex 4550 . . . . . . . . . . 11  |-  { v  e.  V  |  v I e }  e.  _V
14 eqid 2471 . . . . . . . . . . 11  |-  ( e  e.  L  |->  { v  e.  V  |  v I e } )  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )
1513, 14dmmpti 5717 . . . . . . . . . 10  |-  dom  (
e  e.  L  |->  { v  e.  V  | 
v I e } )  =  L
1615a1i 11 . . . . . . . . 9  |-  ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  ->  dom  ( e  e.  L  |->  { v  e.  V  |  v I e } )  =  L )
179, 16eqtrd 2505 . . . . . . . 8  |-  ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  ->  dom  E  =  L )
18 ssrab2 3500 . . . . . . . . . . . . 13  |-  { v  e.  V  |  v I e }  C_  V
1918a1i 11 . . . . . . . . . . . 12  |-  ( ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  /\  e  e.  L
)  ->  { v  e.  V  |  v
I e }  C_  V )
2013elpw 3948 . . . . . . . . . . . 12  |-  ( { v  e.  V  | 
v I e }  e.  ~P V  <->  { v  e.  V  |  v
I e }  C_  V )
2119, 20sylibr 217 . . . . . . . . . . 11  |-  ( ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  /\  e  e.  L
)  ->  { v  e.  V  |  v
I e }  e.  ~P V )
22 eleq2 2538 . . . . . . . . . . . . . . . 16  |-  ( ran  I  =  L  -> 
( e  e.  ran  I 
<->  e  e.  L ) )
23223ad2ant3 1053 . . . . . . . . . . . . . . 15  |-  ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  ->  ( e  e.  ran  I 
<->  e  e.  L ) )
24 ssrelrn 39156 . . . . . . . . . . . . . . . . 17  |-  ( ( I  C_  ( V  X.  L )  /\  e  e.  ran  I )  ->  E. v  e.  V  v I e )
2524ex 441 . . . . . . . . . . . . . . . 16  |-  ( I 
C_  ( V  X.  L )  ->  (
e  e.  ran  I  ->  E. v  e.  V  v I e ) )
26253ad2ant2 1052 . . . . . . . . . . . . . . 15  |-  ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  ->  ( e  e.  ran  I  ->  E. v  e.  V  v I e ) )
2723, 26sylbird 243 . . . . . . . . . . . . . 14  |-  ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  ->  ( e  e.  L  ->  E. v  e.  V  v I e ) )
2827imp 436 . . . . . . . . . . . . 13  |-  ( ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  /\  e  e.  L
)  ->  E. v  e.  V  v I
e )
29 df-ne 2643 . . . . . . . . . . . . . 14  |-  ( { v  e.  V  | 
v I e }  =/=  (/)  <->  -.  { v  e.  V  |  v
I e }  =  (/) )
30 rabn0 3755 . . . . . . . . . . . . . 14  |-  ( { v  e.  V  | 
v I e }  =/=  (/)  <->  E. v  e.  V  v I e )
3129, 30bitr3i 259 . . . . . . . . . . . . 13  |-  ( -. 
{ v  e.  V  |  v I e }  =  (/)  <->  E. v  e.  V  v I
e )
3228, 31sylibr 217 . . . . . . . . . . . 12  |-  ( ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  /\  e  e.  L
)  ->  -.  { v  e.  V  |  v I e }  =  (/) )
3313elsnc 3984 . . . . . . . . . . . 12  |-  ( { v  e.  V  | 
v I e }  e.  { (/) }  <->  { v  e.  V  |  v
I e }  =  (/) )
3432, 33sylnibr 312 . . . . . . . . . . 11  |-  ( ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  /\  e  e.  L
)  ->  -.  { v  e.  V  |  v I e }  e.  {
(/) } )
3521, 34eldifd 3401 . . . . . . . . . 10  |-  ( ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  /\  e  e.  L
)  ->  { v  e.  V  |  v
I e }  e.  ( ~P V  \  { (/)
} ) )
3635, 14fmptd 6061 . . . . . . . . 9  |-  ( ( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  ->  ( e  e.  L  |->  { v  e.  V  |  v I e } ) : L --> ( ~P V  \  { (/)
} ) )
37 simpl 464 . . . . . . . . . 10  |-  ( ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  /\  dom  E  =  L )  ->  E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } ) )
38 simpr 468 . . . . . . . . . 10  |-  ( ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  /\  dom  E  =  L )  ->  dom  E  =  L )
3937, 38feq12d 5727 . . . . . . . . 9  |-  ( ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  /\  dom  E  =  L )  ->  ( E : dom  E --> ( ~P V  \  { (/) } )  <->  ( e  e.  L  |->  { v  e.  V  |  v I e } ) : L --> ( ~P V  \  { (/) } ) ) )
4036, 39syl5ibr 229 . . . . . . . 8  |-  ( ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  /\  dom  E  =  L )  ->  (
( G  e.  W  /\  I  C_  ( V  X.  L )  /\  ran  I  =  L )  ->  E : dom  E --> ( ~P V  \  { (/) } ) ) )
4117, 40mpdan 681 . . . . . . 7  |-  ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  -> 
( ( G  e.  W  /\  I  C_  ( V  X.  L
)  /\  ran  I  =  L )  ->  E : dom  E --> ( ~P V  \  { (/) } ) ) )
4241imp 436 . . . . . 6  |-  ( ( E  =  ( e  e.  L  |->  { v  e.  V  |  v I e } )  /\  ( G  e.  W  /\  I  C_  ( V  X.  L
)  /\  ran  I  =  L ) )  ->  E : dom  E --> ( ~P V  \  { (/) } ) )
438, 42syl6bir 237 . . . . 5  |-  ( V  =  P  ->  (
( E  =  ( e  e.  L  |->  { v  e.  P  | 
v I e } )  /\  ( G  e.  W  /\  I  C_  ( P  X.  L
)  /\  ran  I  =  L ) )  ->  E : dom  E --> ( ~P V  \  { (/) } ) ) )
4443expdimp 444 . . . 4  |-  ( ( V  =  P  /\  E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) )  ->  ( ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L )  ->  E : dom  E --> ( ~P V  \  { (/)
} ) ) )
4544impcom 437 . . 3  |-  ( ( ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L )  /\  ( V  =  P  /\  E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) ) )  ->  E : dom  E --> ( ~P V  \  { (/) } ) )
46 incistruhgr.e . . . . . 6  |-  E  =  (iEdg `  G )
4710, 46isuhgr 39304 . . . . 5  |-  ( G  e.  W  ->  ( G  e. UHGraph  <->  E : dom  E --> ( ~P V  \  { (/)
} ) ) )
48473ad2ant1 1051 . . . 4  |-  ( ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L )  ->  ( G  e. UHGraph  <->  E : dom  E --> ( ~P V  \  { (/) } ) ) )
4948adantr 472 . . 3  |-  ( ( ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L )  /\  ( V  =  P  /\  E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) ) )  ->  ( G  e. UHGraph  <->  E : dom  E --> ( ~P V  \  { (/) } ) ) )
5045, 49mpbird 240 . 2  |-  ( ( ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L )  /\  ( V  =  P  /\  E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) ) )  ->  G  e. UHGraph  )
5150ex 441 1  |-  ( ( G  e.  W  /\  I  C_  ( P  X.  L )  /\  ran  I  =  L )  ->  ( ( V  =  P  /\  E  =  ( e  e.  L  |->  { v  e.  P  |  v I e } ) )  ->  G  e. UHGraph  ) )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 189    /\ wa 376    /\ w3a 1007    = wceq 1452    e. wcel 1904    =/= wne 2641   E.wrex 2757   {crab 2760   _Vcvv 3031    \ cdif 3387    C_ wss 3390   (/)c0 3722   ~Pcpw 3942   {csn 3959   class class class wbr 4395    |-> cmpt 4454    X. cxp 4837   dom cdm 4839   ran crn 4840   -->wf 5585   ` cfv 5589  Vtxcvtx 39251  iEdgciedg 39252   UHGraph cuhgr 39300
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1677  ax-4 1690  ax-5 1766  ax-6 1813  ax-7 1859  ax-9 1913  ax-10 1932  ax-11 1937  ax-12 1950  ax-13 2104  ax-ext 2451  ax-sep 4518  ax-nul 4527  ax-pr 4639
This theorem depends on definitions:  df-bi 190  df-or 377  df-an 378  df-3an 1009  df-tru 1455  df-ex 1672  df-nf 1676  df-sb 1806  df-eu 2323  df-mo 2324  df-clab 2458  df-cleq 2464  df-clel 2467  df-nfc 2601  df-ne 2643  df-ral 2761  df-rex 2762  df-rab 2765  df-v 3033  df-sbc 3256  df-dif 3393  df-un 3395  df-in 3397  df-ss 3404  df-nul 3723  df-if 3873  df-pw 3944  df-sn 3960  df-pr 3962  df-op 3966  df-uni 4191  df-br 4396  df-opab 4455  df-mpt 4456  df-id 4754  df-xp 4845  df-rel 4846  df-cnv 4847  df-co 4848  df-dm 4849  df-rn 4850  df-res 4851  df-ima 4852  df-iota 5553  df-fun 5591  df-fn 5592  df-f 5593  df-fv 5597  df-uhgr 39302
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator