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

Theorem frgrncvvdeqlem9 27481
Description: Lemma 9 for frgrncvvdeq 27483. This corresponds to statement 3 in [Huneke] p. 1: "By symmetry the map is onto". (Contributed by Alexander van der Vekens, 24-Dec-2017.) (Revised by AV, 10-May-2021.) (Proof shortened by AV, 12-Feb-2022.)
Hypotheses
Ref Expression
frgrncvvdeq.v1 𝑉 = (Vtx‘𝐺)
frgrncvvdeq.e 𝐸 = (Edg‘𝐺)
frgrncvvdeq.nx 𝐷 = (𝐺 NeighbVtx 𝑋)
frgrncvvdeq.ny 𝑁 = (𝐺 NeighbVtx 𝑌)
frgrncvvdeq.x (𝜑𝑋𝑉)
frgrncvvdeq.y (𝜑𝑌𝑉)
frgrncvvdeq.ne (𝜑𝑋𝑌)
frgrncvvdeq.xy (𝜑𝑌𝐷)
frgrncvvdeq.f (𝜑𝐺 ∈ FriendGraph )
frgrncvvdeq.a 𝐴 = (𝑥𝐷 ↦ (𝑦𝑁 {𝑥, 𝑦} ∈ 𝐸))
Assertion
Ref Expression
frgrncvvdeqlem9 (𝜑𝐴:𝐷onto𝑁)
Distinct variable groups:   𝑦,𝐺   𝑦,𝑉   𝑦,𝑌   𝑥,𝑦,𝐸   𝑦,𝑁   𝑥,𝐷   𝑥,𝑁   𝜑,𝑥   𝑦,𝐷   𝑥,𝐸
Allowed substitution hints:   𝜑(𝑦)   𝐴(𝑥,𝑦)   𝐺(𝑥)   𝑉(𝑥)   𝑋(𝑥,𝑦)   𝑌(𝑥)

Proof of Theorem frgrncvvdeqlem9
Dummy variables 𝑛 𝑚 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 frgrncvvdeq.v1 . . 3 𝑉 = (Vtx‘𝐺)
2 frgrncvvdeq.e . . 3 𝐸 = (Edg‘𝐺)
3 frgrncvvdeq.nx . . 3 𝐷 = (𝐺 NeighbVtx 𝑋)
4 frgrncvvdeq.ny . . 3 𝑁 = (𝐺 NeighbVtx 𝑌)
5 frgrncvvdeq.x . . 3 (𝜑𝑋𝑉)
6 frgrncvvdeq.y . . 3 (𝜑𝑌𝑉)
7 frgrncvvdeq.ne . . 3 (𝜑𝑋𝑌)
8 frgrncvvdeq.xy . . 3 (𝜑𝑌𝐷)
9 frgrncvvdeq.f . . 3 (𝜑𝐺 ∈ FriendGraph )
10 frgrncvvdeq.a . . 3 𝐴 = (𝑥𝐷 ↦ (𝑦𝑁 {𝑥, 𝑦} ∈ 𝐸))
111, 2, 3, 4, 5, 6, 7, 8, 9, 10frgrncvvdeqlem4 27476 . 2 (𝜑𝐴:𝐷𝑁)
129adantr 468 . . . . . . 7 ((𝜑𝑛𝑁) → 𝐺 ∈ FriendGraph )
134eleq2i 2877 . . . . . . . . . 10 (𝑛𝑁𝑛 ∈ (𝐺 NeighbVtx 𝑌))
141nbgrisvtx 26450 . . . . . . . . . . 11 (𝑛 ∈ (𝐺 NeighbVtx 𝑌) → 𝑛𝑉)
1514a1i 11 . . . . . . . . . 10 (𝜑 → (𝑛 ∈ (𝐺 NeighbVtx 𝑌) → 𝑛𝑉))
1613, 15syl5bi 233 . . . . . . . . 9 (𝜑 → (𝑛𝑁𝑛𝑉))
1716imp 395 . . . . . . . 8 ((𝜑𝑛𝑁) → 𝑛𝑉)
185adantr 468 . . . . . . . 8 ((𝜑𝑛𝑁) → 𝑋𝑉)
191, 2, 3, 4, 5, 6, 7, 8, 9, 10frgrncvvdeqlem1 27473 . . . . . . . . . 10 (𝜑𝑋𝑁)
20 df-nel 3082 . . . . . . . . . . 11 (𝑋𝑁 ↔ ¬ 𝑋𝑁)
21 nelelne 3076 . . . . . . . . . . 11 𝑋𝑁 → (𝑛𝑁𝑛𝑋))
2220, 21sylbi 208 . . . . . . . . . 10 (𝑋𝑁 → (𝑛𝑁𝑛𝑋))
2319, 22syl 17 . . . . . . . . 9 (𝜑 → (𝑛𝑁𝑛𝑋))
2423imp 395 . . . . . . . 8 ((𝜑𝑛𝑁) → 𝑛𝑋)
2517, 18, 243jca 1151 . . . . . . 7 ((𝜑𝑛𝑁) → (𝑛𝑉𝑋𝑉𝑛𝑋))
2612, 25jca 503 . . . . . 6 ((𝜑𝑛𝑁) → (𝐺 ∈ FriendGraph ∧ (𝑛𝑉𝑋𝑉𝑛𝑋)))
271, 2frcond2 27441 . . . . . . 7 (𝐺 ∈ FriendGraph → ((𝑛𝑉𝑋𝑉𝑛𝑋) → ∃!𝑚𝑉 ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)))
2827imp 395 . . . . . 6 ((𝐺 ∈ FriendGraph ∧ (𝑛𝑉𝑋𝑉𝑛𝑋)) → ∃!𝑚𝑉 ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸))
29 reurex 3349 . . . . . . 7 (∃!𝑚𝑉 ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) → ∃𝑚𝑉 ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸))
30 df-rex 3102 . . . . . . 7 (∃𝑚𝑉 ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) ↔ ∃𝑚(𝑚𝑉 ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)))
3129, 30sylib 209 . . . . . 6 (∃!𝑚𝑉 ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) → ∃𝑚(𝑚𝑉 ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)))
3226, 28, 313syl 18 . . . . 5 ((𝜑𝑛𝑁) → ∃𝑚(𝑚𝑉 ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)))
33 frgrusgr 27434 . . . . . . . . . . . . 13 (𝐺 ∈ FriendGraph → 𝐺 ∈ USGraph)
342nbusgreledg 26464 . . . . . . . . . . . . . 14 (𝐺 ∈ USGraph → (𝑚 ∈ (𝐺 NeighbVtx 𝑋) ↔ {𝑚, 𝑋} ∈ 𝐸))
3534bicomd 214 . . . . . . . . . . . . 13 (𝐺 ∈ USGraph → ({𝑚, 𝑋} ∈ 𝐸𝑚 ∈ (𝐺 NeighbVtx 𝑋)))
369, 33, 353syl 18 . . . . . . . . . . . 12 (𝜑 → ({𝑚, 𝑋} ∈ 𝐸𝑚 ∈ (𝐺 NeighbVtx 𝑋)))
3736biimpa 464 . . . . . . . . . . 11 ((𝜑 ∧ {𝑚, 𝑋} ∈ 𝐸) → 𝑚 ∈ (𝐺 NeighbVtx 𝑋))
383eleq2i 2877 . . . . . . . . . . 11 (𝑚𝐷𝑚 ∈ (𝐺 NeighbVtx 𝑋))
3937, 38sylibr 225 . . . . . . . . . 10 ((𝜑 ∧ {𝑚, 𝑋} ∈ 𝐸) → 𝑚𝐷)
4039ad2ant2rl 746 . . . . . . . . 9 (((𝜑𝑛𝑁) ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)) → 𝑚𝐷)
412nbusgreledg 26464 . . . . . . . . . . . . . . . 16 (𝐺 ∈ USGraph → (𝑛 ∈ (𝐺 NeighbVtx 𝑚) ↔ {𝑛, 𝑚} ∈ 𝐸))
4241biimpar 465 . . . . . . . . . . . . . . 15 ((𝐺 ∈ USGraph ∧ {𝑛, 𝑚} ∈ 𝐸) → 𝑛 ∈ (𝐺 NeighbVtx 𝑚))
4342a1d 25 . . . . . . . . . . . . . 14 ((𝐺 ∈ USGraph ∧ {𝑛, 𝑚} ∈ 𝐸) → ({𝑚, 𝑋} ∈ 𝐸𝑛 ∈ (𝐺 NeighbVtx 𝑚)))
4443expimpd 443 . . . . . . . . . . . . 13 (𝐺 ∈ USGraph → (({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) → 𝑛 ∈ (𝐺 NeighbVtx 𝑚)))
459, 33, 443syl 18 . . . . . . . . . . . 12 (𝜑 → (({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) → 𝑛 ∈ (𝐺 NeighbVtx 𝑚)))
4645adantr 468 . . . . . . . . . . 11 ((𝜑𝑛𝑁) → (({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) → 𝑛 ∈ (𝐺 NeighbVtx 𝑚)))
4746imp 395 . . . . . . . . . 10 (((𝜑𝑛𝑁) ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)) → 𝑛 ∈ (𝐺 NeighbVtx 𝑚))
48 elin 3995 . . . . . . . . . . . . . . . 16 (𝑛 ∈ ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) ↔ (𝑛 ∈ (𝐺 NeighbVtx 𝑚) ∧ 𝑛𝑁))
49 simpl 470 . . . . . . . . . . . . . . . . . . . 20 ((𝜑 ∧ {𝑚, 𝑋} ∈ 𝐸) → 𝜑)
5049, 39jca 503 . . . . . . . . . . . . . . . . . . 19 ((𝜑 ∧ {𝑚, 𝑋} ∈ 𝐸) → (𝜑𝑚𝐷))
51 preq1 4459 . . . . . . . . . . . . . . . . . . . . . . . 24 (𝑥 = 𝑚 → {𝑥, 𝑦} = {𝑚, 𝑦})
5251eleq1d 2870 . . . . . . . . . . . . . . . . . . . . . . 23 (𝑥 = 𝑚 → ({𝑥, 𝑦} ∈ 𝐸 ↔ {𝑚, 𝑦} ∈ 𝐸))
5352riotabidv 6833 . . . . . . . . . . . . . . . . . . . . . 22 (𝑥 = 𝑚 → (𝑦𝑁 {𝑥, 𝑦} ∈ 𝐸) = (𝑦𝑁 {𝑚, 𝑦} ∈ 𝐸))
5453cbvmptv 4944 . . . . . . . . . . . . . . . . . . . . 21 (𝑥𝐷 ↦ (𝑦𝑁 {𝑥, 𝑦} ∈ 𝐸)) = (𝑚𝐷 ↦ (𝑦𝑁 {𝑚, 𝑦} ∈ 𝐸))
5510, 54eqtri 2828 . . . . . . . . . . . . . . . . . . . 20 𝐴 = (𝑚𝐷 ↦ (𝑦𝑁 {𝑚, 𝑦} ∈ 𝐸))
561, 2, 3, 4, 5, 6, 7, 8, 9, 55frgrncvvdeqlem5 27477 . . . . . . . . . . . . . . . . . . 19 ((𝜑𝑚𝐷) → {(𝐴𝑚)} = ((𝐺 NeighbVtx 𝑚) ∩ 𝑁))
57 eleq2 2874 . . . . . . . . . . . . . . . . . . . . 21 (((𝐺 NeighbVtx 𝑚) ∩ 𝑁) = {(𝐴𝑚)} → (𝑛 ∈ ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) ↔ 𝑛 ∈ {(𝐴𝑚)}))
5857eqcoms 2814 . . . . . . . . . . . . . . . . . . . 20 ({(𝐴𝑚)} = ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) → (𝑛 ∈ ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) ↔ 𝑛 ∈ {(𝐴𝑚)}))
59 elsni 4387 . . . . . . . . . . . . . . . . . . . 20 (𝑛 ∈ {(𝐴𝑚)} → 𝑛 = (𝐴𝑚))
6058, 59syl6bi 244 . . . . . . . . . . . . . . . . . . 19 ({(𝐴𝑚)} = ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) → (𝑛 ∈ ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) → 𝑛 = (𝐴𝑚)))
6150, 56, 603syl 18 . . . . . . . . . . . . . . . . . 18 ((𝜑 ∧ {𝑚, 𝑋} ∈ 𝐸) → (𝑛 ∈ ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) → 𝑛 = (𝐴𝑚)))
6261expcom 400 . . . . . . . . . . . . . . . . 17 ({𝑚, 𝑋} ∈ 𝐸 → (𝜑 → (𝑛 ∈ ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) → 𝑛 = (𝐴𝑚))))
6362com3r 87 . . . . . . . . . . . . . . . 16 (𝑛 ∈ ((𝐺 NeighbVtx 𝑚) ∩ 𝑁) → ({𝑚, 𝑋} ∈ 𝐸 → (𝜑𝑛 = (𝐴𝑚))))
6448, 63sylbir 226 . . . . . . . . . . . . . . 15 ((𝑛 ∈ (𝐺 NeighbVtx 𝑚) ∧ 𝑛𝑁) → ({𝑚, 𝑋} ∈ 𝐸 → (𝜑𝑛 = (𝐴𝑚))))
6564ex 399 . . . . . . . . . . . . . 14 (𝑛 ∈ (𝐺 NeighbVtx 𝑚) → (𝑛𝑁 → ({𝑚, 𝑋} ∈ 𝐸 → (𝜑𝑛 = (𝐴𝑚)))))
6665com14 96 . . . . . . . . . . . . 13 (𝜑 → (𝑛𝑁 → ({𝑚, 𝑋} ∈ 𝐸 → (𝑛 ∈ (𝐺 NeighbVtx 𝑚) → 𝑛 = (𝐴𝑚)))))
6766imp 395 . . . . . . . . . . . 12 ((𝜑𝑛𝑁) → ({𝑚, 𝑋} ∈ 𝐸 → (𝑛 ∈ (𝐺 NeighbVtx 𝑚) → 𝑛 = (𝐴𝑚))))
6867adantld 480 . . . . . . . . . . 11 ((𝜑𝑛𝑁) → (({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) → (𝑛 ∈ (𝐺 NeighbVtx 𝑚) → 𝑛 = (𝐴𝑚))))
6968imp 395 . . . . . . . . . 10 (((𝜑𝑛𝑁) ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)) → (𝑛 ∈ (𝐺 NeighbVtx 𝑚) → 𝑛 = (𝐴𝑚)))
7047, 69mpd 15 . . . . . . . . 9 (((𝜑𝑛𝑁) ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)) → 𝑛 = (𝐴𝑚))
7140, 70jca 503 . . . . . . . 8 (((𝜑𝑛𝑁) ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)) → (𝑚𝐷𝑛 = (𝐴𝑚)))
7271ex 399 . . . . . . 7 ((𝜑𝑛𝑁) → (({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸) → (𝑚𝐷𝑛 = (𝐴𝑚))))
7372adantld 480 . . . . . 6 ((𝜑𝑛𝑁) → ((𝑚𝑉 ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)) → (𝑚𝐷𝑛 = (𝐴𝑚))))
7473eximdv 2008 . . . . 5 ((𝜑𝑛𝑁) → (∃𝑚(𝑚𝑉 ∧ ({𝑛, 𝑚} ∈ 𝐸 ∧ {𝑚, 𝑋} ∈ 𝐸)) → ∃𝑚(𝑚𝐷𝑛 = (𝐴𝑚))))
7532, 74mpd 15 . . . 4 ((𝜑𝑛𝑁) → ∃𝑚(𝑚𝐷𝑛 = (𝐴𝑚)))
76 df-rex 3102 . . . 4 (∃𝑚𝐷 𝑛 = (𝐴𝑚) ↔ ∃𝑚(𝑚𝐷𝑛 = (𝐴𝑚)))
7775, 76sylibr 225 . . 3 ((𝜑𝑛𝑁) → ∃𝑚𝐷 𝑛 = (𝐴𝑚))
7877ralrimiva 3154 . 2 (𝜑 → ∀𝑛𝑁𝑚𝐷 𝑛 = (𝐴𝑚))
79 dffo3 6592 . 2 (𝐴:𝐷onto𝑁 ↔ (𝐴:𝐷𝑁 ∧ ∀𝑛𝑁𝑚𝐷 𝑛 = (𝐴𝑚)))
8011, 78, 79sylanbrc 574 1 (𝜑𝐴:𝐷onto𝑁)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 197  wa 384  w3a 1100   = wceq 1637  wex 1859  wcel 2156  wne 2978  wnel 3081  wral 3096  wrex 3097  ∃!wreu 3098  cin 3768  {csn 4370  {cpr 4372  cmpt 4923  wf 6093  ontowfo 6095  cfv 6097  crio 6830  (class class class)co 6870  Vtxcvtx 26087  Edgcedg 26152  USGraphcusgr 26258   NeighbVtx cnbgr 26439   FriendGraph cfrgr 27430
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2068  ax-7 2104  ax-8 2158  ax-9 2165  ax-10 2185  ax-11 2201  ax-12 2214  ax-13 2420  ax-ext 2784  ax-rep 4964  ax-sep 4975  ax-nul 4983  ax-pow 5035  ax-pr 5096  ax-un 7175  ax-cnex 10273  ax-resscn 10274  ax-1cn 10275  ax-icn 10276  ax-addcl 10277  ax-addrcl 10278  ax-mulcl 10279  ax-mulrcl 10280  ax-mulcom 10281  ax-addass 10282  ax-mulass 10283  ax-distr 10284  ax-i2m1 10285  ax-1ne0 10286  ax-1rid 10287  ax-rnegex 10288  ax-rrecex 10289  ax-cnre 10290  ax-pre-lttri 10291  ax-pre-lttrn 10292  ax-pre-ltadd 10293  ax-pre-mulgt0 10294
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-fal 1651  df-ex 1860  df-nf 1864  df-sb 2061  df-eu 2634  df-mo 2635  df-clab 2793  df-cleq 2799  df-clel 2802  df-nfc 2937  df-ne 2979  df-nel 3082  df-ral 3101  df-rex 3102  df-reu 3103  df-rmo 3104  df-rab 3105  df-v 3393  df-sbc 3634  df-csb 3729  df-dif 3772  df-un 3774  df-in 3776  df-ss 3783  df-pss 3785  df-nul 4117  df-if 4280  df-pw 4353  df-sn 4371  df-pr 4373  df-tp 4375  df-op 4377  df-uni 4631  df-int 4670  df-iun 4714  df-br 4845  df-opab 4907  df-mpt 4924  df-tr 4947  df-id 5219  df-eprel 5224  df-po 5232  df-so 5233  df-fr 5270  df-we 5272  df-xp 5317  df-rel 5318  df-cnv 5319  df-co 5320  df-dm 5321  df-rn 5322  df-res 5323  df-ima 5324  df-pred 5893  df-ord 5939  df-on 5940  df-lim 5941  df-suc 5942  df-iota 6060  df-fun 6099  df-fn 6100  df-f 6101  df-f1 6102  df-fo 6103  df-f1o 6104  df-fv 6105  df-riota 6831  df-ov 6873  df-oprab 6874  df-mpt2 6875  df-om 7292  df-1st 7394  df-2nd 7395  df-wrecs 7638  df-recs 7700  df-rdg 7738  df-1o 7792  df-2o 7793  df-oadd 7796  df-er 7975  df-en 8189  df-dom 8190  df-sdom 8191  df-fin 8192  df-card 9044  df-cda 9271  df-pnf 10357  df-mnf 10358  df-xr 10359  df-ltxr 10360  df-le 10361  df-sub 10549  df-neg 10550  df-nn 11302  df-2 11360  df-n0 11556  df-xnn0 11626  df-z 11640  df-uz 11901  df-fz 12546  df-hash 13334  df-edg 26153  df-upgr 26190  df-umgr 26191  df-usgr 26260  df-nbgr 26440  df-frgr 27431
This theorem is referenced by:  frgrncvvdeqlem10  27482
  Copyright terms: Public domain W3C validator