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

Theorem disjxwwlksn 28796
Description: Sets of walks (as words) extended by an edge are disjunct if each set contains extensions of distinct walks. (Contributed by Alexander van der Vekens, 29-Jul-2018.) (Revised by AV, 19-Apr-2021.) (Revised by AV, 27-Oct-2022.)
Hypotheses
Ref Expression
wwlksnexthasheq.v 𝑉 = (Vtx‘𝐺)
wwlksnexthasheq.e 𝐸 = (Edg‘𝐺)
Assertion
Ref Expression
disjxwwlksn Disj 𝑦 ∈ (𝑁 WWalksN 𝐺){𝑥 ∈ Word 𝑉 ∣ ((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸)}
Distinct variable groups:   𝑦,𝑁   𝑥,𝑉   𝑥,𝑦
Allowed substitution hints:   𝑃(𝑥,𝑦)   𝐸(𝑥,𝑦)   𝐺(𝑥,𝑦)   𝑁(𝑥)   𝑉(𝑦)

Proof of Theorem disjxwwlksn
StepHypRef Expression
1 simp1 1136 . . . . 5 (((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸) → (𝑥 prefix 𝑁) = 𝑦)
21a1i 11 . . . 4 (𝑥 ∈ Word 𝑉 → (((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸) → (𝑥 prefix 𝑁) = 𝑦))
32ss2rabi 4034 . . 3 {𝑥 ∈ Word 𝑉 ∣ ((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸)} ⊆ {𝑥 ∈ Word 𝑉 ∣ (𝑥 prefix 𝑁) = 𝑦}
43rgenw 3068 . 2 𝑦 ∈ (𝑁 WWalksN 𝐺){𝑥 ∈ Word 𝑉 ∣ ((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸)} ⊆ {𝑥 ∈ Word 𝑉 ∣ (𝑥 prefix 𝑁) = 𝑦}
5 disjwrdpfx 14587 . 2 Disj 𝑦 ∈ (𝑁 WWalksN 𝐺){𝑥 ∈ Word 𝑉 ∣ (𝑥 prefix 𝑁) = 𝑦}
6 disjss2 5073 . 2 (∀𝑦 ∈ (𝑁 WWalksN 𝐺){𝑥 ∈ Word 𝑉 ∣ ((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸)} ⊆ {𝑥 ∈ Word 𝑉 ∣ (𝑥 prefix 𝑁) = 𝑦} → (Disj 𝑦 ∈ (𝑁 WWalksN 𝐺){𝑥 ∈ Word 𝑉 ∣ (𝑥 prefix 𝑁) = 𝑦} → Disj 𝑦 ∈ (𝑁 WWalksN 𝐺){𝑥 ∈ Word 𝑉 ∣ ((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸)}))
74, 5, 6mp2 9 1 Disj 𝑦 ∈ (𝑁 WWalksN 𝐺){𝑥 ∈ Word 𝑉 ∣ ((𝑥 prefix 𝑁) = 𝑦 ∧ (𝑦‘0) = 𝑃 ∧ {(lastS‘𝑦), (lastS‘𝑥)} ∈ 𝐸)}
Colors of variables: wff setvar class
Syntax hints:  wi 4  w3a 1087   = wceq 1541  wcel 2106  wral 3064  {crab 3407  wss 3910  {cpr 4588  Disj wdisj 5070  cfv 6496  (class class class)co 7356  0cc0 11050  Word cword 14401  lastSclsw 14449   prefix cpfx 14557  Vtxcvtx 27894  Edgcedg 27945   WWalksN cwwlksn 28718
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2707
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3an 1089  df-tru 1544  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2538  df-clab 2714  df-cleq 2728  df-clel 2814  df-nfc 2889  df-ral 3065  df-rmo 3353  df-rab 3408  df-v 3447  df-sbc 3740  df-csb 3856  df-in 3917  df-ss 3927  df-disj 5071
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator