Step | Hyp | Ref
| Expression |
1 | | uspgrupgr 26071 |
. . 3
⊢ (𝐺 ∈ USPGraph → 𝐺 ∈ UPGraph
) |
2 | | wlkwwlkbij.t |
. . . 4
⊢ 𝑇 = {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} |
3 | | wlkwwlkbij.w |
. . . 4
⊢ 𝑊 = {𝑤 ∈ (𝑁 WWalksN 𝐺) ∣ (𝑤‘0) = 𝑃} |
4 | | wlkwwlkbij.f |
. . . 4
⊢ 𝐹 = (𝑡 ∈ 𝑇 ↦ (2nd ‘𝑡)) |
5 | 2, 3, 4 | wlkwwlkfun 26781 |
. . 3
⊢ ((𝐺 ∈ UPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐹:𝑇⟶𝑊) |
6 | 1, 5 | syl3an1 1359 |
. 2
⊢ ((𝐺 ∈ USPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐹:𝑇⟶𝑊) |
7 | | fveq1 6190 |
. . . . . . 7
⊢ (𝑤 = 𝑝 → (𝑤‘0) = (𝑝‘0)) |
8 | 7 | eqeq1d 2624 |
. . . . . 6
⊢ (𝑤 = 𝑝 → ((𝑤‘0) = 𝑃 ↔ (𝑝‘0) = 𝑃)) |
9 | 8, 3 | elrab2 3366 |
. . . . 5
⊢ (𝑝 ∈ 𝑊 ↔ (𝑝 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑝‘0) = 𝑃)) |
10 | | wlklnwwlkn 26770 |
. . . . . . . . . . 11
⊢ (𝐺 ∈ USPGraph →
(∃𝑓(𝑓(Walks‘𝐺)𝑝 ∧ (#‘𝑓) = 𝑁) ↔ 𝑝 ∈ (𝑁 WWalksN 𝐺))) |
11 | | df-br 4654 |
. . . . . . . . . . . . 13
⊢ (𝑓(Walks‘𝐺)𝑝 ↔ 〈𝑓, 𝑝〉 ∈ (Walks‘𝐺)) |
12 | | vex 3203 |
. . . . . . . . . . . . . . . . 17
⊢ 𝑓 ∈ V |
13 | | vex 3203 |
. . . . . . . . . . . . . . . . 17
⊢ 𝑝 ∈ V |
14 | 12, 13 | op1st 7176 |
. . . . . . . . . . . . . . . 16
⊢
(1st ‘〈𝑓, 𝑝〉) = 𝑓 |
15 | 14 | eqcomi 2631 |
. . . . . . . . . . . . . . 15
⊢ 𝑓 = (1st
‘〈𝑓, 𝑝〉) |
16 | 15 | fveq2i 6194 |
. . . . . . . . . . . . . 14
⊢
(#‘𝑓) =
(#‘(1st ‘〈𝑓, 𝑝〉)) |
17 | 16 | eqeq1i 2627 |
. . . . . . . . . . . . 13
⊢
((#‘𝑓) = 𝑁 ↔ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) |
18 | 12, 13 | op2nd 7177 |
. . . . . . . . . . . . . . . . 17
⊢
(2nd ‘〈𝑓, 𝑝〉) = 𝑝 |
19 | 18 | eqcomi 2631 |
. . . . . . . . . . . . . . . 16
⊢ 𝑝 = (2nd
‘〈𝑓, 𝑝〉) |
20 | 19 | fveq1i 6192 |
. . . . . . . . . . . . . . 15
⊢ (𝑝‘0) = ((2nd
‘〈𝑓, 𝑝〉)‘0) |
21 | 20 | eqeq1i 2627 |
. . . . . . . . . . . . . 14
⊢ ((𝑝‘0) = 𝑃 ↔ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) |
22 | | opex 4932 |
. . . . . . . . . . . . . . . 16
⊢
〈𝑓, 𝑝〉 ∈ V |
23 | 22 | a1i 11 |
. . . . . . . . . . . . . . 15
⊢
((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) → 〈𝑓, 𝑝〉 ∈ V) |
24 | | simpll 790 |
. . . . . . . . . . . . . . . . . 18
⊢
(((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → 〈𝑓, 𝑝〉 ∈ (Walks‘𝐺)) |
25 | | simpr 477 |
. . . . . . . . . . . . . . . . . . 19
⊢
((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) → (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) |
26 | 25 | anim1i 592 |
. . . . . . . . . . . . . . . . . 18
⊢
(((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) |
27 | 19 | a1i 11 |
. . . . . . . . . . . . . . . . . 18
⊢
(((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → 𝑝 = (2nd ‘〈𝑓, 𝑝〉)) |
28 | 24, 26, 27 | jca31 557 |
. . . . . . . . . . . . . . . . 17
⊢
(((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → ((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘〈𝑓, 𝑝〉))) |
29 | | eleq1 2689 |
. . . . . . . . . . . . . . . . . . 19
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (𝑢 ∈ (Walks‘𝐺) ↔ 〈𝑓, 𝑝〉 ∈ (Walks‘𝐺))) |
30 | | fveq2 6191 |
. . . . . . . . . . . . . . . . . . . . . 22
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (1st ‘𝑢) = (1st
‘〈𝑓, 𝑝〉)) |
31 | 30 | fveq2d 6195 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (#‘(1st
‘𝑢)) =
(#‘(1st ‘〈𝑓, 𝑝〉))) |
32 | 31 | eqeq1d 2624 |
. . . . . . . . . . . . . . . . . . . 20
⊢ (𝑢 = 〈𝑓, 𝑝〉 → ((#‘(1st
‘𝑢)) = 𝑁 ↔ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁)) |
33 | | fveq2 6191 |
. . . . . . . . . . . . . . . . . . . . . 22
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (2nd ‘𝑢) = (2nd
‘〈𝑓, 𝑝〉)) |
34 | 33 | fveq1d 6193 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ (𝑢 = 〈𝑓, 𝑝〉 → ((2nd ‘𝑢)‘0) = ((2nd
‘〈𝑓, 𝑝〉)‘0)) |
35 | 34 | eqeq1d 2624 |
. . . . . . . . . . . . . . . . . . . 20
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (((2nd ‘𝑢)‘0) = 𝑃 ↔ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) |
36 | 32, 35 | anbi12d 747 |
. . . . . . . . . . . . . . . . . . 19
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃) ↔
((#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃))) |
37 | 29, 36 | anbi12d 747 |
. . . . . . . . . . . . . . . . . 18
⊢ (𝑢 = 〈𝑓, 𝑝〉 → ((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ↔ (〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)))) |
38 | 33 | eqeq2d 2632 |
. . . . . . . . . . . . . . . . . 18
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (𝑝 = (2nd ‘𝑢) ↔ 𝑝 = (2nd ‘〈𝑓, 𝑝〉))) |
39 | 37, 38 | anbi12d 747 |
. . . . . . . . . . . . . . . . 17
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)) ↔ ((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘〈𝑓, 𝑝〉)))) |
40 | 28, 39 | syl5ibrcom 237 |
. . . . . . . . . . . . . . . 16
⊢
(((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → (𝑢 = 〈𝑓, 𝑝〉 → ((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
41 | 40 | impancom 456 |
. . . . . . . . . . . . . . 15
⊢
(((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) ∧ 𝑢 = 〈𝑓, 𝑝〉) → (((2nd
‘〈𝑓, 𝑝〉)‘0) = 𝑃 → ((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
42 | 23, 41 | spcimedv 3292 |
. . . . . . . . . . . . . 14
⊢
((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) → (((2nd
‘〈𝑓, 𝑝〉)‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
43 | 21, 42 | syl5bi 232 |
. . . . . . . . . . . . 13
⊢
((〈𝑓, 𝑝〉 ∈ (Walks‘𝐺) ∧ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
44 | 11, 17, 43 | syl2anb 496 |
. . . . . . . . . . . 12
⊢ ((𝑓(Walks‘𝐺)𝑝 ∧ (#‘𝑓) = 𝑁) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
45 | 44 | exlimiv 1858 |
. . . . . . . . . . 11
⊢
(∃𝑓(𝑓(Walks‘𝐺)𝑝 ∧ (#‘𝑓) = 𝑁) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
46 | 10, 45 | syl6bir 244 |
. . . . . . . . . 10
⊢ (𝐺 ∈ USPGraph → (𝑝 ∈ (𝑁 WWalksN 𝐺) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))))) |
47 | 46 | imp32 449 |
. . . . . . . . 9
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))) |
48 | | fveq2 6191 |
. . . . . . . . . . . . . . 15
⊢ (𝑝 = 𝑢 → (1st ‘𝑝) = (1st ‘𝑢)) |
49 | 48 | fveq2d 6195 |
. . . . . . . . . . . . . 14
⊢ (𝑝 = 𝑢 → (#‘(1st ‘𝑝)) = (#‘(1st
‘𝑢))) |
50 | 49 | eqeq1d 2624 |
. . . . . . . . . . . . 13
⊢ (𝑝 = 𝑢 → ((#‘(1st
‘𝑝)) = 𝑁 ↔ (#‘(1st
‘𝑢)) = 𝑁)) |
51 | | fveq2 6191 |
. . . . . . . . . . . . . . 15
⊢ (𝑝 = 𝑢 → (2nd ‘𝑝) = (2nd ‘𝑢)) |
52 | 51 | fveq1d 6193 |
. . . . . . . . . . . . . 14
⊢ (𝑝 = 𝑢 → ((2nd ‘𝑝)‘0) = ((2nd
‘𝑢)‘0)) |
53 | 52 | eqeq1d 2624 |
. . . . . . . . . . . . 13
⊢ (𝑝 = 𝑢 → (((2nd ‘𝑝)‘0) = 𝑃 ↔ ((2nd ‘𝑢)‘0) = 𝑃)) |
54 | 50, 53 | anbi12d 747 |
. . . . . . . . . . . 12
⊢ (𝑝 = 𝑢 → (((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃) ↔
((#‘(1st ‘𝑢)) = 𝑁 ∧ ((2nd ‘𝑢)‘0) = 𝑃))) |
55 | 54 | elrab 3363 |
. . . . . . . . . . 11
⊢ (𝑢 ∈ {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ↔ (𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃))) |
56 | 55 | anbi1i 731 |
. . . . . . . . . 10
⊢ ((𝑢 ∈ {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢)) ↔ ((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))) |
57 | 56 | exbii 1774 |
. . . . . . . . 9
⊢
(∃𝑢(𝑢 ∈ {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢)) ↔ ∃𝑢((𝑢 ∈ (Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))) |
58 | 47, 57 | sylibr 224 |
. . . . . . . 8
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢(𝑢 ∈ {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢))) |
59 | | df-rex 2918 |
. . . . . . . 8
⊢
(∃𝑢 ∈
{𝑝 ∈
(Walks‘𝐺) ∣
((#‘(1st ‘𝑝)) = 𝑁 ∧ ((2nd ‘𝑝)‘0) = 𝑃)}𝑝 = (2nd ‘𝑢) ↔ ∃𝑢(𝑢 ∈ {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢))) |
60 | 58, 59 | sylibr 224 |
. . . . . . 7
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢 ∈ {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)}𝑝 = (2nd ‘𝑢)) |
61 | 2 | rexeqi 3143 |
. . . . . . 7
⊢
(∃𝑢 ∈
𝑇 𝑝 = (2nd ‘𝑢) ↔ ∃𝑢 ∈ {𝑝 ∈ (Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)}𝑝 = (2nd ‘𝑢)) |
62 | 60, 61 | sylibr 224 |
. . . . . 6
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢 ∈ 𝑇 𝑝 = (2nd ‘𝑢)) |
63 | | fveq2 6191 |
. . . . . . . . 9
⊢ (𝑡 = 𝑢 → (2nd ‘𝑡) = (2nd ‘𝑢)) |
64 | | fvex 6201 |
. . . . . . . . 9
⊢
(2nd ‘𝑢) ∈ V |
65 | 63, 4, 64 | fvmpt 6282 |
. . . . . . . 8
⊢ (𝑢 ∈ 𝑇 → (𝐹‘𝑢) = (2nd ‘𝑢)) |
66 | 65 | eqeq2d 2632 |
. . . . . . 7
⊢ (𝑢 ∈ 𝑇 → (𝑝 = (𝐹‘𝑢) ↔ 𝑝 = (2nd ‘𝑢))) |
67 | 66 | rexbiia 3040 |
. . . . . 6
⊢
(∃𝑢 ∈
𝑇 𝑝 = (𝐹‘𝑢) ↔ ∃𝑢 ∈ 𝑇 𝑝 = (2nd ‘𝑢)) |
68 | 62, 67 | sylibr 224 |
. . . . 5
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalksN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
69 | 9, 68 | sylan2b 492 |
. . . 4
⊢ ((𝐺 ∈ USPGraph ∧ 𝑝 ∈ 𝑊) → ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
70 | 69 | ralrimiva 2966 |
. . 3
⊢ (𝐺 ∈ USPGraph →
∀𝑝 ∈ 𝑊 ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
71 | 70 | 3ad2ant1 1082 |
. 2
⊢ ((𝐺 ∈ USPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) →
∀𝑝 ∈ 𝑊 ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
72 | | dffo3 6374 |
. 2
⊢ (𝐹:𝑇–onto→𝑊 ↔ (𝐹:𝑇⟶𝑊 ∧ ∀𝑝 ∈ 𝑊 ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢))) |
73 | 6, 71, 72 | sylanbrc 698 |
1
⊢ ((𝐺 ∈ USPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐹:𝑇–onto→𝑊) |