Step | Hyp | Ref
| Expression |
1 | | uspgrupgr 40406 |
. . 3
⊢ (𝐺 ∈ USPGraph → 𝐺 ∈ UPGraph
) |
2 | | wlkwwlkbij.t |
. . . 4
⊢ 𝑇 = {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} |
3 | | wlkwwlkbij.w |
. . . 4
⊢ 𝑊 = {𝑤 ∈ (𝑁 WWalkSN 𝐺) ∣ (𝑤‘0) = 𝑃} |
4 | | wlkwwlkbij.f |
. . . 4
⊢ 𝐹 = (𝑡 ∈ 𝑇 ↦ (2nd ‘𝑡)) |
5 | 2, 3, 4 | wlkwwlkfun 41092 |
. . 3
⊢ ((𝐺 ∈ UPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐹:𝑇⟶𝑊) |
6 | 1, 5 | syl3an1 1351 |
. 2
⊢ ((𝐺 ∈ USPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐹:𝑇⟶𝑊) |
7 | | fveq1 6102 |
. . . . . . 7
⊢ (𝑤 = 𝑝 → (𝑤‘0) = (𝑝‘0)) |
8 | 7 | eqeq1d 2612 |
. . . . . 6
⊢ (𝑤 = 𝑝 → ((𝑤‘0) = 𝑃 ↔ (𝑝‘0) = 𝑃)) |
9 | 8, 3 | elrab2 3333 |
. . . . 5
⊢ (𝑝 ∈ 𝑊 ↔ (𝑝 ∈ (𝑁 WWalkSN 𝐺) ∧ (𝑝‘0) = 𝑃)) |
10 | | 1wlklnwwlkn 41081 |
. . . . . . . . . . 11
⊢ (𝐺 ∈ USPGraph →
(∃𝑓(𝑓(1Walks‘𝐺)𝑝 ∧ (#‘𝑓) = 𝑁) ↔ 𝑝 ∈ (𝑁 WWalkSN 𝐺))) |
11 | | df-br 4584 |
. . . . . . . . . . . . 13
⊢ (𝑓(1Walks‘𝐺)𝑝 ↔ 〈𝑓, 𝑝〉 ∈ (1Walks‘𝐺)) |
12 | | vex 3176 |
. . . . . . . . . . . . . . . . 17
⊢ 𝑓 ∈ V |
13 | | vex 3176 |
. . . . . . . . . . . . . . . . 17
⊢ 𝑝 ∈ V |
14 | 12, 13 | op1st 7067 |
. . . . . . . . . . . . . . . 16
⊢
(1st ‘〈𝑓, 𝑝〉) = 𝑓 |
15 | 14 | eqcomi 2619 |
. . . . . . . . . . . . . . 15
⊢ 𝑓 = (1st
‘〈𝑓, 𝑝〉) |
16 | 15 | fveq2i 6106 |
. . . . . . . . . . . . . 14
⊢
(#‘𝑓) =
(#‘(1st ‘〈𝑓, 𝑝〉)) |
17 | 16 | eqeq1i 2615 |
. . . . . . . . . . . . 13
⊢
((#‘𝑓) = 𝑁 ↔ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) |
18 | 12, 13 | op2nd 7068 |
. . . . . . . . . . . . . . . . 17
⊢
(2nd ‘〈𝑓, 𝑝〉) = 𝑝 |
19 | 18 | eqcomi 2619 |
. . . . . . . . . . . . . . . 16
⊢ 𝑝 = (2nd
‘〈𝑓, 𝑝〉) |
20 | 19 | fveq1i 6104 |
. . . . . . . . . . . . . . 15
⊢ (𝑝‘0) = ((2nd
‘〈𝑓, 𝑝〉)‘0) |
21 | 20 | eqeq1i 2615 |
. . . . . . . . . . . . . 14
⊢ ((𝑝‘0) = 𝑃 ↔ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) |
22 | | opex 4859 |
. . . . . . . . . . . . . . . 16
⊢
〈𝑓, 𝑝〉 ∈ V |
23 | 22 | a1i 11 |
. . . . . . . . . . . . . . 15
⊢
((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) → 〈𝑓, 𝑝〉 ∈ V) |
24 | | simpll 786 |
. . . . . . . . . . . . . . . . . 18
⊢
(((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → 〈𝑓, 𝑝〉 ∈ (1Walks‘𝐺)) |
25 | | simpr 476 |
. . . . . . . . . . . . . . . . . . 19
⊢
((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) → (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁) |
26 | 25 | anim1i 590 |
. . . . . . . . . . . . . . . . . 18
⊢
(((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) |
27 | 19 | a1i 11 |
. . . . . . . . . . . . . . . . . 18
⊢
(((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → 𝑝 = (2nd ‘〈𝑓, 𝑝〉)) |
28 | 24, 26, 27 | jca31 555 |
. . . . . . . . . . . . . . . . 17
⊢
(((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → ((〈𝑓, 𝑝〉 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘〈𝑓, 𝑝〉))) |
29 | | eleq1 2676 |
. . . . . . . . . . . . . . . . . . 19
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (𝑢 ∈ (1Walks‘𝐺) ↔ 〈𝑓, 𝑝〉 ∈ (1Walks‘𝐺))) |
30 | | fveq2 6103 |
. . . . . . . . . . . . . . . . . . . . . 22
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (1st ‘𝑢) = (1st
‘〈𝑓, 𝑝〉)) |
31 | 30 | fveq2d 6107 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (#‘(1st
‘𝑢)) =
(#‘(1st ‘〈𝑓, 𝑝〉))) |
32 | 31 | eqeq1d 2612 |
. . . . . . . . . . . . . . . . . . . 20
⊢ (𝑢 = 〈𝑓, 𝑝〉 → ((#‘(1st
‘𝑢)) = 𝑁 ↔ (#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁)) |
33 | | fveq2 6103 |
. . . . . . . . . . . . . . . . . . . . . 22
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (2nd ‘𝑢) = (2nd
‘〈𝑓, 𝑝〉)) |
34 | 33 | fveq1d 6105 |
. . . . . . . . . . . . . . . . . . . . 21
⊢ (𝑢 = 〈𝑓, 𝑝〉 → ((2nd ‘𝑢)‘0) = ((2nd
‘〈𝑓, 𝑝〉)‘0)) |
35 | 34 | eqeq1d 2612 |
. . . . . . . . . . . . . . . . . . . 20
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (((2nd ‘𝑢)‘0) = 𝑃 ↔ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) |
36 | 32, 35 | anbi12d 743 |
. . . . . . . . . . . . . . . . . . 19
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃) ↔
((#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃))) |
37 | 29, 36 | anbi12d 743 |
. . . . . . . . . . . . . . . . . 18
⊢ (𝑢 = 〈𝑓, 𝑝〉 → ((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ↔ (〈𝑓, 𝑝〉 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)))) |
38 | 33 | eqeq2d 2620 |
. . . . . . . . . . . . . . . . . 18
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (𝑝 = (2nd ‘𝑢) ↔ 𝑝 = (2nd ‘〈𝑓, 𝑝〉))) |
39 | 37, 38 | anbi12d 743 |
. . . . . . . . . . . . . . . . 17
⊢ (𝑢 = 〈𝑓, 𝑝〉 → (((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)) ↔ ((〈𝑓, 𝑝〉 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘〈𝑓, 𝑝〉)) = 𝑁 ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘〈𝑓, 𝑝〉)))) |
40 | 28, 39 | syl5ibrcom 236 |
. . . . . . . . . . . . . . . 16
⊢
(((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) ∧ ((2nd ‘〈𝑓, 𝑝〉)‘0) = 𝑃) → (𝑢 = 〈𝑓, 𝑝〉 → ((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
41 | 40 | impancom 455 |
. . . . . . . . . . . . . . 15
⊢
(((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) ∧ 𝑢 = 〈𝑓, 𝑝〉) → (((2nd
‘〈𝑓, 𝑝〉)‘0) = 𝑃 → ((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
42 | 23, 41 | spcimedv 3265 |
. . . . . . . . . . . . . 14
⊢
((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) → (((2nd
‘〈𝑓, 𝑝〉)‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
43 | 21, 42 | syl5bi 231 |
. . . . . . . . . . . . 13
⊢
((〈𝑓, 𝑝〉 ∈
(1Walks‘𝐺) ∧
(#‘(1st ‘〈𝑓, 𝑝〉)) = 𝑁) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
44 | 11, 17, 43 | syl2anb 495 |
. . . . . . . . . . . 12
⊢ ((𝑓(1Walks‘𝐺)𝑝 ∧ (#‘𝑓) = 𝑁) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
45 | 44 | exlimiv 1845 |
. . . . . . . . . . 11
⊢
(∃𝑓(𝑓(1Walks‘𝐺)𝑝 ∧ (#‘𝑓) = 𝑁) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢)))) |
46 | 10, 45 | syl6bir 243 |
. . . . . . . . . 10
⊢ (𝐺 ∈ USPGraph → (𝑝 ∈ (𝑁 WWalkSN 𝐺) → ((𝑝‘0) = 𝑃 → ∃𝑢((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))))) |
47 | 46 | imp32 448 |
. . . . . . . . 9
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalkSN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))) |
48 | | fveq2 6103 |
. . . . . . . . . . . . . . 15
⊢ (𝑝 = 𝑢 → (1st ‘𝑝) = (1st ‘𝑢)) |
49 | 48 | fveq2d 6107 |
. . . . . . . . . . . . . 14
⊢ (𝑝 = 𝑢 → (#‘(1st ‘𝑝)) = (#‘(1st
‘𝑢))) |
50 | 49 | eqeq1d 2612 |
. . . . . . . . . . . . 13
⊢ (𝑝 = 𝑢 → ((#‘(1st
‘𝑝)) = 𝑁 ↔ (#‘(1st
‘𝑢)) = 𝑁)) |
51 | | fveq2 6103 |
. . . . . . . . . . . . . . 15
⊢ (𝑝 = 𝑢 → (2nd ‘𝑝) = (2nd ‘𝑢)) |
52 | 51 | fveq1d 6105 |
. . . . . . . . . . . . . 14
⊢ (𝑝 = 𝑢 → ((2nd ‘𝑝)‘0) = ((2nd
‘𝑢)‘0)) |
53 | 52 | eqeq1d 2612 |
. . . . . . . . . . . . 13
⊢ (𝑝 = 𝑢 → (((2nd ‘𝑝)‘0) = 𝑃 ↔ ((2nd ‘𝑢)‘0) = 𝑃)) |
54 | 50, 53 | anbi12d 743 |
. . . . . . . . . . . 12
⊢ (𝑝 = 𝑢 → (((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃) ↔
((#‘(1st ‘𝑢)) = 𝑁 ∧ ((2nd ‘𝑢)‘0) = 𝑃))) |
55 | 54 | elrab 3331 |
. . . . . . . . . . 11
⊢ (𝑢 ∈ {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ↔ (𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃))) |
56 | 55 | anbi1i 727 |
. . . . . . . . . 10
⊢ ((𝑢 ∈ {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢)) ↔ ((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))) |
57 | 56 | exbii 1764 |
. . . . . . . . 9
⊢
(∃𝑢(𝑢 ∈ {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢)) ↔ ∃𝑢((𝑢 ∈ (1Walks‘𝐺) ∧ ((#‘(1st
‘𝑢)) = 𝑁 ∧ ((2nd
‘𝑢)‘0) = 𝑃)) ∧ 𝑝 = (2nd ‘𝑢))) |
58 | 47, 57 | sylibr 223 |
. . . . . . . 8
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalkSN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢(𝑢 ∈ {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢))) |
59 | | df-rex 2902 |
. . . . . . . 8
⊢
(∃𝑢 ∈
{𝑝 ∈
(1Walks‘𝐺) ∣
((#‘(1st ‘𝑝)) = 𝑁 ∧ ((2nd ‘𝑝)‘0) = 𝑃)}𝑝 = (2nd ‘𝑢) ↔ ∃𝑢(𝑢 ∈ {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)} ∧ 𝑝 = (2nd ‘𝑢))) |
60 | 58, 59 | sylibr 223 |
. . . . . . 7
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalkSN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢 ∈ {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)}𝑝 = (2nd ‘𝑢)) |
61 | 2 | rexeqi 3120 |
. . . . . . 7
⊢
(∃𝑢 ∈
𝑇 𝑝 = (2nd ‘𝑢) ↔ ∃𝑢 ∈ {𝑝 ∈ (1Walks‘𝐺) ∣ ((#‘(1st
‘𝑝)) = 𝑁 ∧ ((2nd
‘𝑝)‘0) = 𝑃)}𝑝 = (2nd ‘𝑢)) |
62 | 60, 61 | sylibr 223 |
. . . . . 6
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalkSN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢 ∈ 𝑇 𝑝 = (2nd ‘𝑢)) |
63 | | fveq2 6103 |
. . . . . . . . 9
⊢ (𝑡 = 𝑢 → (2nd ‘𝑡) = (2nd ‘𝑢)) |
64 | | fvex 6113 |
. . . . . . . . 9
⊢
(2nd ‘𝑢) ∈ V |
65 | 63, 4, 64 | fvmpt 6191 |
. . . . . . . 8
⊢ (𝑢 ∈ 𝑇 → (𝐹‘𝑢) = (2nd ‘𝑢)) |
66 | 65 | eqeq2d 2620 |
. . . . . . 7
⊢ (𝑢 ∈ 𝑇 → (𝑝 = (𝐹‘𝑢) ↔ 𝑝 = (2nd ‘𝑢))) |
67 | 66 | rexbiia 3022 |
. . . . . 6
⊢
(∃𝑢 ∈
𝑇 𝑝 = (𝐹‘𝑢) ↔ ∃𝑢 ∈ 𝑇 𝑝 = (2nd ‘𝑢)) |
68 | 62, 67 | sylibr 223 |
. . . . 5
⊢ ((𝐺 ∈ USPGraph ∧ (𝑝 ∈ (𝑁 WWalkSN 𝐺) ∧ (𝑝‘0) = 𝑃)) → ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
69 | 9, 68 | sylan2b 491 |
. . . 4
⊢ ((𝐺 ∈ USPGraph ∧ 𝑝 ∈ 𝑊) → ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
70 | 69 | ralrimiva 2949 |
. . 3
⊢ (𝐺 ∈ USPGraph →
∀𝑝 ∈ 𝑊 ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
71 | 70 | 3ad2ant1 1075 |
. 2
⊢ ((𝐺 ∈ USPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) →
∀𝑝 ∈ 𝑊 ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢)) |
72 | | dffo3 6282 |
. 2
⊢ (𝐹:𝑇–onto→𝑊 ↔ (𝐹:𝑇⟶𝑊 ∧ ∀𝑝 ∈ 𝑊 ∃𝑢 ∈ 𝑇 𝑝 = (𝐹‘𝑢))) |
73 | 6, 71, 72 | sylanbrc 695 |
1
⊢ ((𝐺 ∈ USPGraph ∧ 𝑃 ∈ 𝑉 ∧ 𝑁 ∈ ℕ0) → 𝐹:𝑇–onto→𝑊) |