MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  incistruhgr Structured version   Visualization version   GIF version

Theorem incistruhgr 26778
Description: An incidence structure 𝑃, 𝐿, 𝐼 "where 𝑃 is a set whose elements are called points, 𝐿 is a distinct set whose elements are called lines and 𝐼 ⊆ (𝑃 × 𝐿) 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 𝑃 = (Base‘𝑆) 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 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 𝑉 = (Vtx‘𝐺)
incistruhgr.e 𝐸 = (iEdg‘𝐺)
Assertion
Ref Expression
incistruhgr ((𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿) → ((𝑉 = 𝑃𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒})) → 𝐺 ∈ UHGraph))
Distinct variable groups:   𝑒,𝐸   𝑒,𝐺   𝑒,𝐼,𝑣   𝑒,𝐿,𝑣   𝑃,𝑒,𝑣   𝑒,𝑉,𝑣   𝑒,𝑊
Allowed substitution hints:   𝐸(𝑣)   𝐺(𝑣)   𝑊(𝑣)

Proof of Theorem incistruhgr
StepHypRef Expression
1 rabeq 3488 . . . . . . . . 9 (𝑉 = 𝑃 → {𝑣𝑉𝑣𝐼𝑒} = {𝑣𝑃𝑣𝐼𝑒})
21mpteq2dv 5158 . . . . . . . 8 (𝑉 = 𝑃 → (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒}))
32eqeq2d 2836 . . . . . . 7 (𝑉 = 𝑃 → (𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) ↔ 𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒})))
4 xpeq1 5567 . . . . . . . . 9 (𝑉 = 𝑃 → (𝑉 × 𝐿) = (𝑃 × 𝐿))
54sseq2d 4002 . . . . . . . 8 (𝑉 = 𝑃 → (𝐼 ⊆ (𝑉 × 𝐿) ↔ 𝐼 ⊆ (𝑃 × 𝐿)))
653anbi2d 1434 . . . . . . 7 (𝑉 = 𝑃 → ((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) ↔ (𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿)))
73, 6anbi12d 630 . . . . . 6 (𝑉 = 𝑃 → ((𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) ∧ (𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿)) ↔ (𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒}) ∧ (𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿))))
8 dmeq 5770 . . . . . . . . 9 (𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) → dom 𝐸 = dom (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}))
9 incistruhgr.v . . . . . . . . . . . 12 𝑉 = (Vtx‘𝐺)
109fvexi 6680 . . . . . . . . . . 11 𝑉 ∈ V
1110rabex 5231 . . . . . . . . . 10 {𝑣𝑉𝑣𝐼𝑒} ∈ V
12 eqid 2825 . . . . . . . . . 10 (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒})
1311, 12dmmpti 6488 . . . . . . . . 9 dom (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) = 𝐿
148, 13syl6eq 2876 . . . . . . . 8 (𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) → dom 𝐸 = 𝐿)
15 ssrab2 4059 . . . . . . . . . . . . 13 {𝑣𝑉𝑣𝐼𝑒} ⊆ 𝑉
1615a1i 11 . . . . . . . . . . . 12 (((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ 𝑒𝐿) → {𝑣𝑉𝑣𝐼𝑒} ⊆ 𝑉)
1711elpw 4548 . . . . . . . . . . . 12 ({𝑣𝑉𝑣𝐼𝑒} ∈ 𝒫 𝑉 ↔ {𝑣𝑉𝑣𝐼𝑒} ⊆ 𝑉)
1816, 17sylibr 235 . . . . . . . . . . 11 (((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ 𝑒𝐿) → {𝑣𝑉𝑣𝐼𝑒} ∈ 𝒫 𝑉)
19 eleq2 2905 . . . . . . . . . . . . . . . 16 (ran 𝐼 = 𝐿 → (𝑒 ∈ ran 𝐼𝑒𝐿))
20193ad2ant3 1129 . . . . . . . . . . . . . . 15 ((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) → (𝑒 ∈ ran 𝐼𝑒𝐿))
21 ssrelrn 5761 . . . . . . . . . . . . . . . . 17 ((𝐼 ⊆ (𝑉 × 𝐿) ∧ 𝑒 ∈ ran 𝐼) → ∃𝑣𝑉 𝑣𝐼𝑒)
2221ex 413 . . . . . . . . . . . . . . . 16 (𝐼 ⊆ (𝑉 × 𝐿) → (𝑒 ∈ ran 𝐼 → ∃𝑣𝑉 𝑣𝐼𝑒))
23223ad2ant2 1128 . . . . . . . . . . . . . . 15 ((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) → (𝑒 ∈ ran 𝐼 → ∃𝑣𝑉 𝑣𝐼𝑒))
2420, 23sylbird 261 . . . . . . . . . . . . . 14 ((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) → (𝑒𝐿 → ∃𝑣𝑉 𝑣𝐼𝑒))
2524imp 407 . . . . . . . . . . . . 13 (((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ 𝑒𝐿) → ∃𝑣𝑉 𝑣𝐼𝑒)
26 df-ne 3021 . . . . . . . . . . . . . 14 ({𝑣𝑉𝑣𝐼𝑒} ≠ ∅ ↔ ¬ {𝑣𝑉𝑣𝐼𝑒} = ∅)
27 rabn0 4342 . . . . . . . . . . . . . 14 ({𝑣𝑉𝑣𝐼𝑒} ≠ ∅ ↔ ∃𝑣𝑉 𝑣𝐼𝑒)
2826, 27bitr3i 278 . . . . . . . . . . . . 13 (¬ {𝑣𝑉𝑣𝐼𝑒} = ∅ ↔ ∃𝑣𝑉 𝑣𝐼𝑒)
2925, 28sylibr 235 . . . . . . . . . . . 12 (((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ 𝑒𝐿) → ¬ {𝑣𝑉𝑣𝐼𝑒} = ∅)
3011elsn 4578 . . . . . . . . . . . 12 ({𝑣𝑉𝑣𝐼𝑒} ∈ {∅} ↔ {𝑣𝑉𝑣𝐼𝑒} = ∅)
3129, 30sylnibr 330 . . . . . . . . . . 11 (((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ 𝑒𝐿) → ¬ {𝑣𝑉𝑣𝐼𝑒} ∈ {∅})
3218, 31eldifd 3950 . . . . . . . . . 10 (((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ 𝑒𝐿) → {𝑣𝑉𝑣𝐼𝑒} ∈ (𝒫 𝑉 ∖ {∅}))
3332fmpttd 6874 . . . . . . . . 9 ((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) → (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}):𝐿⟶(𝒫 𝑉 ∖ {∅}))
34 simpl 483 . . . . . . . . . 10 ((𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) ∧ dom 𝐸 = 𝐿) → 𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}))
35 simpr 485 . . . . . . . . . 10 ((𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) ∧ dom 𝐸 = 𝐿) → dom 𝐸 = 𝐿)
3634, 35feq12d 6498 . . . . . . . . 9 ((𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) ∧ dom 𝐸 = 𝐿) → (𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅}) ↔ (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}):𝐿⟶(𝒫 𝑉 ∖ {∅})))
3733, 36syl5ibr 247 . . . . . . . 8 ((𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) ∧ dom 𝐸 = 𝐿) → ((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) → 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅})))
3814, 37mpdan 683 . . . . . . 7 (𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) → ((𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿) → 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅})))
3938imp 407 . . . . . 6 ((𝐸 = (𝑒𝐿 ↦ {𝑣𝑉𝑣𝐼𝑒}) ∧ (𝐺𝑊𝐼 ⊆ (𝑉 × 𝐿) ∧ ran 𝐼 = 𝐿)) → 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅}))
407, 39syl6bir 255 . . . . 5 (𝑉 = 𝑃 → ((𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒}) ∧ (𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿)) → 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅})))
4140expdimp 453 . . . 4 ((𝑉 = 𝑃𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒})) → ((𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿) → 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅})))
4241impcom 408 . . 3 (((𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ (𝑉 = 𝑃𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒}))) → 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅}))
43 incistruhgr.e . . . . . 6 𝐸 = (iEdg‘𝐺)
449, 43isuhgr 26759 . . . . 5 (𝐺𝑊 → (𝐺 ∈ UHGraph ↔ 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅})))
45443ad2ant1 1127 . . . 4 ((𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿) → (𝐺 ∈ UHGraph ↔ 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅})))
4645adantr 481 . . 3 (((𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ (𝑉 = 𝑃𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒}))) → (𝐺 ∈ UHGraph ↔ 𝐸:dom 𝐸⟶(𝒫 𝑉 ∖ {∅})))
4742, 46mpbird 258 . 2 (((𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿) ∧ (𝑉 = 𝑃𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒}))) → 𝐺 ∈ UHGraph)
4847ex 413 1 ((𝐺𝑊𝐼 ⊆ (𝑃 × 𝐿) ∧ ran 𝐼 = 𝐿) → ((𝑉 = 𝑃𝐸 = (𝑒𝐿 ↦ {𝑣𝑃𝑣𝐼𝑒})) → 𝐺 ∈ UHGraph))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 207  wa 396  w3a 1081   = wceq 1530  wcel 2107  wne 3020  wrex 3143  {crab 3146  cdif 3936  wss 3939  c0 4294  𝒫 cpw 4541  {csn 4563   class class class wbr 5062  cmpt 5142   × cxp 5551  dom cdm 5553  ran crn 5554  wf 6347  cfv 6351  Vtxcvtx 26695  iEdgciedg 26696  UHGraphcuhgr 26755
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1789  ax-4 1803  ax-5 1904  ax-6 1963  ax-7 2008  ax-8 2109  ax-9 2117  ax-10 2138  ax-11 2153  ax-12 2169  ax-ext 2797  ax-sep 5199  ax-nul 5206  ax-pr 5325
This theorem depends on definitions:  df-bi 208  df-an 397  df-or 844  df-3an 1083  df-tru 1533  df-ex 1774  df-nf 1778  df-sb 2063  df-mo 2619  df-eu 2651  df-clab 2804  df-cleq 2818  df-clel 2897  df-nfc 2967  df-ne 3021  df-ral 3147  df-rex 3148  df-rab 3151  df-v 3501  df-sbc 3776  df-dif 3942  df-un 3944  df-in 3946  df-ss 3955  df-nul 4295  df-if 4470  df-pw 4543  df-sn 4564  df-pr 4566  df-op 4570  df-uni 4837  df-br 5063  df-opab 5125  df-mpt 5143  df-id 5458  df-xp 5559  df-rel 5560  df-cnv 5561  df-co 5562  df-dm 5563  df-rn 5564  df-res 5565  df-ima 5566  df-iota 6311  df-fun 6353  df-fn 6354  df-f 6355  df-fv 6359  df-uhgr 26757
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator