Theorem incistruhgr 15855

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 2771	. . . . . . . . 9 |- ( V = P -> { v e. V | v I e } = { v e. P | v I e } )
2	1	mpteq2dv 4154	. . . . . . . 8 |- ( V = P -> ( e e. L |-> { v e. V | v I e } ) = ( e e. L |-> { v e. P | v I e } ) )
3	2	eqeq2d 2221	. . . . . . 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 4710	. . . . . . . . 9 |- ( V = P -> ( V X. L ) = ( P X. L ) )
5	4	sseq2d 3234	. . . . . . . 8 |- ( V = P -> ( I C_ ( V X. L ) <-> I C_ ( P X. L ) ) )
6	5	3anbi2d 1332	. . . . . . 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 4900	. . . . . . . . 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 2209	. . . . . . . . . 10 |- ( e e. L |-> { v e. V | v I e } ) = ( e e. L |-> { v e. V | v I e } )
11		eqid 2209	. . . . . . . . . . 11 |- { v e. V | v I e } = { v e. V | v I e }
12		incistruhgr.v	. . . . . . . . . . . 12 |- V = (Vtx ` G )
13		simpl1 1005	. . . . . . . . . . . . 13 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> G e. W )
14		vtxex 15784	. . . . . . . . . . . . 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 2296	. . . . . . . . . . 11 |- ( ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) /\ e e. L ) -> V e. _V )
17	11, 16	rabexd 4208	. . . . . . . . . 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 5430	. . . . . . . . 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 2262	. . . . . . . 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 2273	. . . . . . . . . . 11 |- ( s = { v e. V | v I e } -> ( j e. s <-> j e. { v e. V | v I e } ) )
23	22	exbidv 1851	. . . . . . . . . 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 3289	. . . . . . . . . . 11 |- { v e. V | v I e } C_ V
25		elpwg 3637	. . . . . . . . . . . 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 2273	. . . . . . . . . . . . . 14 |- ( ran I = L -> ( e e. ran I <-> e e. L ) )
29	28	3ad2ant3 1025	. . . . . . . . . . . . 13 |- ( ( G e. W /\ I C_ ( V X. L ) /\ ran I = L ) -> ( e e. ran I <-> e e. L ) )
30		ssrelrn 4891	. . . . . . . . . . . . . . 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 1024	. . . . . . . . . . . . 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 3499	. . . . . . . . . . 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 2941	. . . . . . . . 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 5763	. . . . . . . 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 5439	. . . . . . . 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 15836	. . . . 5 |- ( G e. W -> ( G e. UHGraph <-> E : dom E --> { s e. ~P V | E. j j e. s } ) )
49	48	3ad2ant1 1023	. . . 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 983   = wceq 1375   E.wex 1518   e. wcel 2180   E.wrex 2489   {crab 2492   _Vcvv 2779   C_ wss 3177   ~Pcpw 3629   class class class wbr 4062   |-> cmpt 4124   X. cxp 4694   dom cdm 4696   ran crn 4697   -->wf 5290   ` cfv 5294  Vtxcvtx 15778  iEdgciedg 15779  UHGraphcuhgr 15832

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 617  ax-in2 618  ax-io 713  ax-5 1473  ax-7 1474  ax-gen 1475  ax-ie1 1519  ax-ie2 1520  ax-8 1530  ax-10 1531  ax-11 1532  ax-i12 1533  ax-bndl 1535  ax-4 1536  ax-17 1552  ax-i9 1556  ax-ial 1560  ax-i5r 1561  ax-13 2182  ax-14 2183  ax-ext 2191  ax-sep 4181  ax-pow 4237  ax-pr 4272  ax-un 4501  ax-setind 4606  ax-cnex 8058  ax-resscn 8059  ax-1cn 8060  ax-1re 8061  ax-icn 8062  ax-addcl 8063  ax-addrcl 8064  ax-mulcl 8065  ax-addcom 8067  ax-mulcom 8068  ax-addass 8069  ax-mulass 8070  ax-distr 8071  ax-i2m1 8072  ax-1rid 8074  ax-0id 8075  ax-rnegex 8076  ax-cnre 8078

This theorem depends on definitions:  df-bi 117  df-3an 985  df-tru 1378  df-fal 1381  df-nf 1487  df-sb 1789  df-eu 2060  df-mo 2061  df-clab 2196  df-cleq 2202  df-clel 2205  df-nfc 2341  df-ne 2381  df-ral 2493  df-rex 2494  df-reu 2495  df-rab 2497  df-v 2781  df-sbc 3009  df-csb 3105  df-dif 3179  df-un 3181  df-in 3183  df-ss 3190  df-if 3583  df-pw 3631  df-sn 3652  df-pr 3653  df-op 3655  df-uni 3868  df-int 3903  df-br 4063  df-opab 4125  df-mpt 4126  df-id 4361  df-xp 4702  df-rel 4703  df-cnv 4704  df-co 4705  df-dm 4706  df-rn 4707  df-res 4708  df-ima 4709  df-iota 5254  df-fun 5296  df-fn 5297  df-f 5298  df-fo 5300  df-fv 5302  df-riota 5927  df-ov 5977  df-oprab 5978  df-mpo 5979  df-1st 6256  df-2nd 6257  df-sub 8287  df-inn 9079  df-2 9137  df-3 9138  df-4 9139  df-5 9140  df-6 9141  df-7 9142  df-8 9143  df-9 9144  df-n0 9338  df-dec 9547  df-ndx 13001  df-slot 13002  df-base 13004  df-edgf 15771  df-vtx 15780  df-iedg 15781  df-uhgrm 15834

This theorem is referenced by: (None)