Proof of Theorem eulerpartlemmf
Step | Hyp | Ref
| Expression |
1 | | bitsf1o 15901 |
. . . . 5
⊢ (bits
↾ ℕ0):ℕ0–1-1-onto→(𝒫 ℕ0 ∩
Fin) |
2 | | f1of 6631 |
. . . . 5
⊢ ((bits
↾ ℕ0):ℕ0–1-1-onto→(𝒫 ℕ0 ∩ Fin)
→ (bits ↾ ℕ0):ℕ0⟶(𝒫
ℕ0 ∩ Fin)) |
3 | 1, 2 | ax-mp 5 |
. . . 4
⊢ (bits
↾ ℕ0):ℕ0⟶(𝒫
ℕ0 ∩ Fin) |
4 | | eulerpart.p |
. . . . . . . . 9
⊢ 𝑃 = {𝑓 ∈ (ℕ0
↑m ℕ) ∣ ((◡𝑓 “ ℕ) ∈ Fin ∧
Σ𝑘 ∈ ℕ
((𝑓‘𝑘) · 𝑘) = 𝑁)} |
5 | | eulerpart.o |
. . . . . . . . 9
⊢ 𝑂 = {𝑔 ∈ 𝑃 ∣ ∀𝑛 ∈ (◡𝑔 “ ℕ) ¬ 2 ∥ 𝑛} |
6 | | eulerpart.d |
. . . . . . . . 9
⊢ 𝐷 = {𝑔 ∈ 𝑃 ∣ ∀𝑛 ∈ ℕ (𝑔‘𝑛) ≤ 1} |
7 | | eulerpart.j |
. . . . . . . . 9
⊢ 𝐽 = {𝑧 ∈ ℕ ∣ ¬ 2 ∥ 𝑧} |
8 | | eulerpart.f |
. . . . . . . . 9
⊢ 𝐹 = (𝑥 ∈ 𝐽, 𝑦 ∈ ℕ0 ↦
((2↑𝑦) · 𝑥)) |
9 | | eulerpart.h |
. . . . . . . . 9
⊢ 𝐻 = {𝑟 ∈ ((𝒫 ℕ0 ∩
Fin) ↑m 𝐽)
∣ (𝑟 supp ∅)
∈ Fin} |
10 | | eulerpart.m |
. . . . . . . . 9
⊢ 𝑀 = (𝑟 ∈ 𝐻 ↦ {〈𝑥, 𝑦〉 ∣ (𝑥 ∈ 𝐽 ∧ 𝑦 ∈ (𝑟‘𝑥))}) |
11 | | eulerpart.r |
. . . . . . . . 9
⊢ 𝑅 = {𝑓 ∣ (◡𝑓 “ ℕ) ∈
Fin} |
12 | | eulerpart.t |
. . . . . . . . 9
⊢ 𝑇 = {𝑓 ∈ (ℕ0
↑m ℕ) ∣ (◡𝑓 “ ℕ) ⊆ 𝐽} |
13 | 4, 5, 6, 7, 8, 9, 10, 11, 12 | eulerpartlemt0 31919 |
. . . . . . . 8
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) ↔ (𝐴 ∈ (ℕ0
↑m ℕ) ∧ (◡𝐴 “ ℕ) ∈ Fin ∧ (◡𝐴 “ ℕ) ⊆ 𝐽)) |
14 | 13 | biimpi 219 |
. . . . . . 7
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 ∈ (ℕ0
↑m ℕ) ∧ (◡𝐴 “ ℕ) ∈ Fin ∧ (◡𝐴 “ ℕ) ⊆ 𝐽)) |
15 | 14 | simp1d 1143 |
. . . . . 6
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → 𝐴 ∈ (ℕ0
↑m ℕ)) |
16 | | nn0ex 11995 |
. . . . . . 7
⊢
ℕ0 ∈ V |
17 | | nnex 11735 |
. . . . . . 7
⊢ ℕ
∈ V |
18 | 16, 17 | elmap 8494 |
. . . . . 6
⊢ (𝐴 ∈ (ℕ0
↑m ℕ) ↔ 𝐴:ℕ⟶ℕ0) |
19 | 15, 18 | sylib 221 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → 𝐴:ℕ⟶ℕ0) |
20 | | ssrab2 3979 |
. . . . . 6
⊢ {𝑧 ∈ ℕ ∣ ¬ 2
∥ 𝑧} ⊆
ℕ |
21 | 7, 20 | eqsstri 3921 |
. . . . 5
⊢ 𝐽 ⊆
ℕ |
22 | | fssres 6555 |
. . . . 5
⊢ ((𝐴:ℕ⟶ℕ0 ∧
𝐽 ⊆ ℕ) →
(𝐴 ↾ 𝐽):𝐽⟶ℕ0) |
23 | 19, 21, 22 | sylancl 589 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 ↾ 𝐽):𝐽⟶ℕ0) |
24 | | fco2 6542 |
. . . 4
⊢ (((bits
↾ ℕ0):ℕ0⟶(𝒫
ℕ0 ∩ Fin) ∧ (𝐴 ↾ 𝐽):𝐽⟶ℕ0) → (bits
∘ (𝐴 ↾ 𝐽)):𝐽⟶(𝒫 ℕ0 ∩
Fin)) |
25 | 3, 23, 24 | sylancr 590 |
. . 3
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)):𝐽⟶(𝒫 ℕ0 ∩
Fin)) |
26 | 16 | pwex 5257 |
. . . . 5
⊢ 𝒫
ℕ0 ∈ V |
27 | 26 | inex1 5195 |
. . . 4
⊢
(𝒫 ℕ0 ∩ Fin) ∈ V |
28 | 17, 21 | ssexi 5200 |
. . . 4
⊢ 𝐽 ∈ V |
29 | 27, 28 | elmap 8494 |
. . 3
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫
ℕ0 ∩ Fin) ↑m 𝐽) ↔ (bits ∘ (𝐴 ↾ 𝐽)):𝐽⟶(𝒫 ℕ0 ∩
Fin)) |
30 | 25, 29 | sylibr 237 |
. 2
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫 ℕ0
∩ Fin) ↑m 𝐽)) |
31 | 14 | simp2d 1144 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡𝐴 “ ℕ) ∈
Fin) |
32 | | 0nn0 12004 |
. . . . . . . . 9
⊢ 0 ∈
ℕ0 |
33 | | suppimacnv 7882 |
. . . . . . . . 9
⊢ ((𝐴 ∈ (𝑇 ∩ 𝑅) ∧ 0 ∈ ℕ0) →
(𝐴 supp 0) = (◡𝐴 “ (V ∖ {0}))) |
34 | 32, 33 | mpan2 691 |
. . . . . . . 8
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 supp 0) = (◡𝐴 “ (V ∖ {0}))) |
35 | | frnsuppeq 7883 |
. . . . . . . . . 10
⊢ ((ℕ
∈ V ∧ 0 ∈ ℕ0) → (𝐴:ℕ⟶ℕ0 →
(𝐴 supp 0) = (◡𝐴 “ (ℕ0 ∖
{0})))) |
36 | 17, 32, 35 | mp2an 692 |
. . . . . . . . 9
⊢ (𝐴:ℕ⟶ℕ0 →
(𝐴 supp 0) = (◡𝐴 “ (ℕ0 ∖
{0}))) |
37 | 19, 36 | syl 17 |
. . . . . . . 8
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 supp 0) = (◡𝐴 “ (ℕ0 ∖
{0}))) |
38 | 34, 37 | eqtr3d 2776 |
. . . . . . 7
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡𝐴 “ (V ∖ {0})) = (◡𝐴 “ (ℕ0 ∖
{0}))) |
39 | 38 | eleq1d 2818 |
. . . . . 6
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → ((◡𝐴 “ (V ∖ {0})) ∈ Fin ↔
(◡𝐴 “ (ℕ0 ∖ {0}))
∈ Fin)) |
40 | | dfn2 12002 |
. . . . . . . 8
⊢ ℕ =
(ℕ0 ∖ {0}) |
41 | 40 | imaeq2i 5911 |
. . . . . . 7
⊢ (◡𝐴 “ ℕ) = (◡𝐴 “ (ℕ0 ∖
{0})) |
42 | 41 | eleq1i 2824 |
. . . . . 6
⊢ ((◡𝐴 “ ℕ) ∈ Fin ↔ (◡𝐴 “ (ℕ0 ∖ {0}))
∈ Fin) |
43 | 39, 42 | bitr4di 292 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → ((◡𝐴 “ (V ∖ {0})) ∈ Fin ↔
(◡𝐴 “ ℕ) ∈
Fin)) |
44 | 31, 43 | mpbird 260 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡𝐴 “ (V ∖ {0})) ∈
Fin) |
45 | | resss 5860 |
. . . . 5
⊢ (𝐴 ↾ 𝐽) ⊆ 𝐴 |
46 | | cnvss 5725 |
. . . . 5
⊢ ((𝐴 ↾ 𝐽) ⊆ 𝐴 → ◡(𝐴 ↾ 𝐽) ⊆ ◡𝐴) |
47 | | imass1 5948 |
. . . . 5
⊢ (◡(𝐴 ↾ 𝐽) ⊆ ◡𝐴 → (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ⊆ (◡𝐴 “ (V ∖ {0}))) |
48 | 45, 46, 47 | mp2b 10 |
. . . 4
⊢ (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ⊆ (◡𝐴 “ (V ∖ {0})) |
49 | | ssfi 8785 |
. . . 4
⊢ (((◡𝐴 “ (V ∖ {0})) ∈ Fin ∧
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ⊆ (◡𝐴 “ (V ∖ {0}))) → (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ∈
Fin) |
50 | 44, 48, 49 | sylancl 589 |
. . 3
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ∈
Fin) |
51 | | cnvco 5738 |
. . . . . 6
⊢ ◡(bits ∘ (𝐴 ↾ 𝐽)) = (◡(𝐴 ↾ 𝐽) ∘ ◡bits) |
52 | 51 | imaeq1i 5910 |
. . . . 5
⊢ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) = ((◡(𝐴 ↾ 𝐽) ∘ ◡bits) “ (V ∖
{∅})) |
53 | | imaco 6094 |
. . . . 5
⊢ ((◡(𝐴 ↾ 𝐽) ∘ ◡bits) “ (V ∖ {∅})) =
(◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖
{∅}))) |
54 | 52, 53 | eqtri 2762 |
. . . 4
⊢ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) = (◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖
{∅}))) |
55 | | ffun 6518 |
. . . . . 6
⊢ (𝐴:ℕ⟶ℕ0 →
Fun 𝐴) |
56 | | funres 6392 |
. . . . . 6
⊢ (Fun
𝐴 → Fun (𝐴 ↾ 𝐽)) |
57 | 19, 55, 56 | 3syl 18 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → Fun (𝐴 ↾ 𝐽)) |
58 | | ssv 3911 |
. . . . . . 7
⊢ (◡bits “ V) ⊆ V |
59 | | ssdif 4040 |
. . . . . . 7
⊢ ((◡bits “ V) ⊆ V → ((◡bits “ V) ∖ (◡bits “ {∅})) ⊆ (V ∖
(◡bits “
{∅}))) |
60 | 58, 59 | ax-mp 5 |
. . . . . 6
⊢ ((◡bits “ V) ∖ (◡bits “ {∅})) ⊆ (V ∖
(◡bits “
{∅})) |
61 | | bitsf 15883 |
. . . . . . 7
⊢
bits:ℤ⟶𝒫 ℕ0 |
62 | | ffun 6518 |
. . . . . . 7
⊢
(bits:ℤ⟶𝒫 ℕ0 → Fun
bits) |
63 | | difpreima 6855 |
. . . . . . 7
⊢ (Fun bits
→ (◡bits “ (V ∖
{∅})) = ((◡bits “ V)
∖ (◡bits “
{∅}))) |
64 | 61, 62, 63 | mp2b 10 |
. . . . . 6
⊢ (◡bits “ (V ∖ {∅})) =
((◡bits “ V) ∖ (◡bits “ {∅})) |
65 | | bitsf1 15902 |
. . . . . . . . 9
⊢
bits:ℤ–1-1→𝒫 ℕ0 |
66 | | 0z 12086 |
. . . . . . . . . 10
⊢ 0 ∈
ℤ |
67 | | snssi 4706 |
. . . . . . . . . 10
⊢ (0 ∈
ℤ → {0} ⊆ ℤ) |
68 | 66, 67 | ax-mp 5 |
. . . . . . . . 9
⊢ {0}
⊆ ℤ |
69 | | f1imacnv 6647 |
. . . . . . . . 9
⊢
((bits:ℤ–1-1→𝒫 ℕ0 ∧ {0} ⊆
ℤ) → (◡bits “ (bits
“ {0})) = {0}) |
70 | 65, 68, 69 | mp2an 692 |
. . . . . . . 8
⊢ (◡bits “ (bits “ {0})) =
{0} |
71 | | ffn 6515 |
. . . . . . . . . . . 12
⊢
(bits:ℤ⟶𝒫 ℕ0 → bits Fn
ℤ) |
72 | 61, 71 | ax-mp 5 |
. . . . . . . . . . 11
⊢ bits Fn
ℤ |
73 | | fnsnfv 6760 |
. . . . . . . . . . 11
⊢ ((bits Fn
ℤ ∧ 0 ∈ ℤ) → {(bits‘0)} = (bits “
{0})) |
74 | 72, 66, 73 | mp2an 692 |
. . . . . . . . . 10
⊢
{(bits‘0)} = (bits “ {0}) |
75 | | 0bits 15895 |
. . . . . . . . . . 11
⊢
(bits‘0) = ∅ |
76 | 75 | sneqi 4537 |
. . . . . . . . . 10
⊢
{(bits‘0)} = {∅} |
77 | 74, 76 | eqtr3i 2764 |
. . . . . . . . 9
⊢ (bits
“ {0}) = {∅} |
78 | 77 | imaeq2i 5911 |
. . . . . . . 8
⊢ (◡bits “ (bits “ {0})) = (◡bits “ {∅}) |
79 | 70, 78 | eqtr3i 2764 |
. . . . . . 7
⊢ {0} =
(◡bits “
{∅}) |
80 | 79 | difeq2i 4020 |
. . . . . 6
⊢ (V
∖ {0}) = (V ∖ (◡bits
“ {∅})) |
81 | 60, 64, 80 | 3sstr4i 3930 |
. . . . 5
⊢ (◡bits “ (V ∖ {∅})) ⊆
(V ∖ {0}) |
82 | | sspreima 6858 |
. . . . 5
⊢ ((Fun
(𝐴 ↾ 𝐽) ∧ (◡bits “ (V ∖ {∅})) ⊆
(V ∖ {0})) → (◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖ {∅}))) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) |
83 | 57, 81, 82 | sylancl 589 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖ {∅}))) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) |
84 | 54, 83 | eqsstrid 3935 |
. . 3
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) |
85 | | ssfi 8785 |
. . 3
⊢ (((◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ∈ Fin ∧
(◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) → (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin) |
86 | 50, 84, 85 | syl2anc 587 |
. 2
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin) |
87 | | oveq1 7190 |
. . . . 5
⊢ (𝑟 = (bits ∘ (𝐴 ↾ 𝐽)) → (𝑟 supp ∅) = ((bits ∘ (𝐴 ↾ 𝐽)) supp ∅)) |
88 | 87 | eleq1d 2818 |
. . . 4
⊢ (𝑟 = (bits ∘ (𝐴 ↾ 𝐽)) → ((𝑟 supp ∅) ∈ Fin ↔ ((bits
∘ (𝐴 ↾ 𝐽)) supp ∅) ∈
Fin)) |
89 | 88, 9 | elrab2 3596 |
. . 3
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ 𝐻 ↔ ((bits ∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫 ℕ0
∩ Fin) ↑m 𝐽) ∧ ((bits ∘ (𝐴 ↾ 𝐽)) supp ∅) ∈
Fin)) |
90 | | zex 12084 |
. . . . . 6
⊢ ℤ
∈ V |
91 | | fex 7012 |
. . . . . 6
⊢
((bits:ℤ⟶𝒫 ℕ0 ∧ ℤ ∈
V) → bits ∈ V) |
92 | 61, 90, 91 | mp2an 692 |
. . . . 5
⊢ bits
∈ V |
93 | | resexg 5881 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 ↾ 𝐽) ∈ V) |
94 | | coexg 7673 |
. . . . 5
⊢ ((bits
∈ V ∧ (𝐴 ↾
𝐽) ∈ V) → (bits
∘ (𝐴 ↾ 𝐽)) ∈ V) |
95 | 92, 93, 94 | sylancr 590 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)) ∈ V) |
96 | | 0ex 5185 |
. . . . . . 7
⊢ ∅
∈ V |
97 | | suppimacnv 7882 |
. . . . . . 7
⊢ (((bits
∘ (𝐴 ↾ 𝐽)) ∈ V ∧ ∅ ∈
V) → ((bits ∘ (𝐴
↾ 𝐽)) supp ∅) =
(◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖
{∅}))) |
98 | 96, 97 | mpan2 691 |
. . . . . 6
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ V → ((bits
∘ (𝐴 ↾ 𝐽)) supp ∅) = (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖
{∅}))) |
99 | 98 | eleq1d 2818 |
. . . . 5
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ V → (((bits
∘ (𝐴 ↾ 𝐽)) supp ∅) ∈ Fin
↔ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin)) |
100 | 99 | anbi2d 632 |
. . . 4
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ V → (((bits
∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫
ℕ0 ∩ Fin) ↑m 𝐽) ∧ ((bits ∘ (𝐴 ↾ 𝐽)) supp ∅) ∈ Fin) ↔ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫
ℕ0 ∩ Fin) ↑m 𝐽) ∧ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin))) |
101 | 95, 100 | syl 17 |
. . 3
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (((bits ∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫 ℕ0
∩ Fin) ↑m 𝐽) ∧ ((bits ∘ (𝐴 ↾ 𝐽)) supp ∅) ∈ Fin) ↔ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫
ℕ0 ∩ Fin) ↑m 𝐽) ∧ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin))) |
102 | 89, 101 | syl5bb 286 |
. 2
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → ((bits ∘ (𝐴 ↾ 𝐽)) ∈ 𝐻 ↔ ((bits ∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫 ℕ0
∩ Fin) ↑m 𝐽) ∧ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin))) |
103 | 30, 86, 102 | mpbir2and 713 |
1
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)) ∈ 𝐻) |