Theorem incistruhgr 16134

Description: An incidence 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 and enhancing the definition of iEdg accordingly, it would even be possible to express that a corresponding incidence 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

Dummy variables j s are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		rabeq 2807	. . . . . . . . 9 |- ( V = P -> { v e. V | v I e } = { v e. P | v I e } )
2	1	mpteq2dv 4203	. . . . . . . 8 |- ( V = P -> ( e e. L |-> { v e. V | v I e } ) = ( e e. L |-> { v e. P | v I e } ) )
3	2	eqeq2d 2246	. . . . . . 7 |- ( V = P -> ( E = ( e e. L |-> { v e. V | v I e } ) <-> E = ( e e. L |-> { v e. P | v I e } ) ) )
4		xpeq1 4765	. . . . . . . . 9 |- ( V = P -> ( V X. L ) = ( P X. L ) )
5	4	sseq2d 3270	. . . . . . . 8 |- ( V = P -> ( I C_ ( V X. L ) <-> I C_ ( P X. L ) ) )
6	5	3anbi2d 1354	. . . . . . 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 ) ) )
7	3, 6	anbi12d 473	. . . . . 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 ) ) ) )
8		simpl 109	. . . . . . . 8 |- ( ( 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. V | v I e } ) )
9		dmeq 4958	. . . . . . . . 9 |- ( E = ( e e. L |-> { v e. V | v I e } ) -> dom E = dom ( e e. L |-> { v e. V | v I e } ) )
10		eqid 2234	. . . . . . . . . 10 |- ( e e. L |-> { v e. V | v I e } ) = ( e e. L |-> { v e. V | v I e } )
11		eqid 2234	. . . . . . . . . . 11 |- { v e. V | v I e } = { v e. V | v I e }
12		incistruhgr.v	. . . . . . . . . . . 12 |- V = (Vtx ` G )
13		simpl1 1027	. . . . . . . . . . . . 13 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> G e. W )
14		vtxex 16062	. . . . . . . . . . . . 13 |- ( G e. W -> (Vtx ` G ) e. _V )
15	13, 14	syl 14	. . . . . . . . . . . 12 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> (Vtx ` G ) e. _V )
16	12, 15	eqeltrid 2321	. . . . . . . . . . 11 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> V e. _V )
17	11, 16	rabexd 4259	. . . . . . . . . 10 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> { v e. V | v I e } e. _V )
18	10, 17	dmmptd 5491	. . . . . . . . 9 |- ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) -> dom ( e e. L |-> { v e. V | v I e } ) = L )
19	9, 18	sylan9eq 2287	. . . . . . . 8 |- ( ( E = ( e e. L |-> { v e. V | v I e } ) /\ ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) ) -> dom E = L )
20	8, 19	jca 306	. . . . . . 7 |- ( ( 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. V | v I e } ) /\ dom E = L ) )
21		simpr 110	. . . . . . 7 |- ( ( E = ( e e. L |-> { v e. V | v I e } ) /\ ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) ) -> ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) )
22		eleq2 2298	. . . . . . . . . . 11 |- ( s = { v e. V | v I e } -> ( j e. s <-> j e. { v e. V | v I e } ) )
23	22	exbidv 1874	. . . . . . . . . 10 |- ( s = { v e. V | v I e } -> ( E. j j e. s <-> E. j j e. { v e. V | v I e } ) )
24		ssrab2 3325	. . . . . . . . . . 11 |- { v e. V | v I e } C_ V
25		elpwg 3679	. . . . . . . . . . . 12 |- ( { v e. V | v I e } e. _V -> ( { v e. V | v I e } e. ~P V <-> { v e. V | v I e } C_ V ) )
26	17, 25	syl 14	. . . . . . . . . . 11 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> ( { v e. V | v I e } e. ~P V <-> { v e. V | v I e } C_ V ) )
27	24, 26	mpbiri 168	. . . . . . . . . 10 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> { v e. V | v I e } e. ~P V )
28		eleq2 2298	. . . . . . . . . . . . . 14 |- ( ran I = L -> ( e e. ran I <-> e e. L ) )
29	28	3ad2ant3 1047	. . . . . . . . . . . . 13 |- ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) -> ( e e. ran I <-> e e. L ) )
30		ssrelrn 4949	. . . . . . . . . . . . . . 15 |- ( ( I C_ ( V X. L ) /\ e e. ran I ) -> E. v e. V v I e )
31	30	ex 115	. . . . . . . . . . . . . 14 |- ( I C_ ( V X. L ) -> ( e e. ran I -> E. v e. V v I e ) )
32	31	3ad2ant2 1046	. . . . . . . . . . . . 13 |- ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) -> ( e e. ran I -> E. v e. V v I e ) )
33	29, 32	sylbird 170	. . . . . . . . . . . 12 |- ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) -> ( e e. L -> E. v e. V v I e ) )
34	33	imp 124	. . . . . . . . . . 11 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> E. v e. V v I e )
35		rabn0m 3538	. . . . . . . . . . 11 |- ( E. j j e. { v e. V | v I e } <-> E. v e. V v I e )
36	34, 35	sylibr 134	. . . . . . . . . 10 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> E. j j e. { v e. V | v I e } )
37	23, 27, 36	elrabd 2977	. . . . . . . . 9 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> { v e. V | v I e } e. { s e. ~P V | E. j j e. s } )
38	37	fmpttd 5834	. . . . . . . 8 |- ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) -> ( e e. L |-> { v e. V | v I e } ) : L --> { s e. ~P V | E. j j e. s } )
39		simpl 109	. . . . . . . . 9 |- ( ( E = ( e e. L |-> { v e. V | v I e } ) /\ dom E = L ) -> E = ( e e. L |-> { v e. V | v I e } ) )
40		simpr 110	. . . . . . . . 9 |- ( ( E = ( e e. L |-> { v e. V | v I e } ) /\ dom E = L ) -> dom E = L )
41	39, 40	feq12d 5500	. . . . . . . 8 |- ( ( E = ( e e. L |-> { v e. V | v I e } ) /\ dom E = L ) -> ( E : dom E --> { s e. ~P V | E. j j e. s } <-> ( e e. L |-> { v e. V | v I e } ) : L --> { s e. ~P V | E. j j e. s } ) )
42	38, 41	imbitrrid 156	. . . . . . 7 |- ( ( 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 --> { s e. ~P V | E. j j e. s } ) )
43	20, 21, 42	sylc 62	. . . . . 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 --> { s e. ~P V | E. j j e. s } )
44	7, 43	biimtrrdi 164	. . . . 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 --> { s e. ~P V | E. j j e. s } ) )
45	44	expdimp 259	. . . 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 --> { s e. ~P V | E. j j e. s } ) )
46	45	impcom 125	. . 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 --> { s e. ~P V | E. j j e. s } )
47		incistruhgr.e	. . . . . 6 |- E = (iEdg ` G )
48	12, 47	isuhgrm 16115	. . . . 5 |- ( G e. W -> ( G e. UHGraph <-> E : dom E --> { s e. ~P V | E. j j e. s } ) )
49	48	3ad2ant1 1045	. . . 4 |- ( ( G e. W /\ I C_ ( P X. L ) /\ ran I = L ) -> ( G e. UHGraph <-> E : dom E --> { s e. ~P V | E. j j e. s } ) )
50	49	adantr 276	. . 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 --> { s e. ~P V | E. j j e. s } ) )
51	46, 50	mpbird 167	. 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 )
52	51	ex 115	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 ) )

Syntax hints:   -> wi 4   /\ wa 104   <-> wb 105   /\ w3a 1005   = wceq 1398   E.wex 1541   e. wcel 2205   E.wrex 2523   {crab 2526   _Vcvv 2815   C_ wss 3213   ~Pcpw 3671   class class class wbr 4111   |-> cmpt 4173   X. cxp 4749   dom cdm 4751   ran crn 4752   -->wf 5350   ` cfv 5354  Vtxcvtx 16056  iEdgciedg 16057  UHGraphcuhgr 16111

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 619  ax-in2 620  ax-io 717  ax-5 1496  ax-7 1497  ax-gen 1498  ax-ie1 1542  ax-ie2 1543  ax-8 1553  ax-10 1554  ax-11 1555  ax-i12 1556  ax-bndl 1558  ax-4 1559  ax-17 1575  ax-i9 1579  ax-ial 1583  ax-i5r 1584  ax-13 2207  ax-14 2208  ax-ext 2216  ax-sep 4230  ax-pow 4289  ax-pr 4324  ax-un 4556  ax-setind 4661  ax-cnex 8223  ax-resscn 8224  ax-1cn 8225  ax-1re 8226  ax-icn 8227  ax-addcl 8228  ax-addrcl 8229  ax-mulcl 8230  ax-addcom 8232  ax-mulcom 8233  ax-addass 8234  ax-mulass 8235  ax-distr 8236  ax-i2m1 8237  ax-1rid 8239  ax-0id 8240  ax-rnegex 8241  ax-cnre 8243

This theorem depends on definitions:  df-bi 117  df-3an 1007  df-tru 1401  df-fal 1404  df-nf 1510  df-sb 1812  df-eu 2085  df-mo 2086  df-clab 2221  df-cleq 2227  df-clel 2230  df-nfc 2375  df-ne 2415  df-ral 2527  df-rex 2528  df-reu 2529  df-rab 2531  df-v 2817  df-sbc 3045  df-csb 3141  df-dif 3215  df-un 3217  df-in 3219  df-ss 3226  df-if 3623  df-pw 3673  df-sn 3697  df-pr 3698  df-op 3700  df-uni 3917  df-int 3952  df-br 4112  df-opab 4174  df-mpt 4175  df-id 4416  df-xp 4757  df-rel 4758  df-cnv 4759  df-co 4760  df-dm 4761  df-rn 4762  df-res 4763  df-ima 4764  df-iota 5314  df-fun 5356  df-fn 5357  df-f 5358  df-fo 5360  df-fv 5362  df-riota 6005  df-ov 6055  df-oprab 6056  df-mpo 6057  df-1st 6336  df-2nd 6337  df-sub 8451  df-inn 9243  df-2 9301  df-3 9302  df-4 9303  df-5 9304  df-6 9305  df-7 9306  df-8 9307  df-9 9308  df-n0 9502  df-dec 9716  df-ndx 13236  df-slot 13237  df-base 13239  df-edgf 16049  df-vtx 16058  df-iedg 16059  df-uhgrm 16113

This theorem is referenced by: (None)