Proof of Theorem eulerpartlemmf
| Step | Hyp | Ref
| Expression |
| 1 | | bitsf1o 16482 |
. . . . 5
⊢ (bits
↾ ℕ0):ℕ0–1-1-onto→(𝒫 ℕ0 ∩
Fin) |
| 2 | | f1of 6848 |
. . . . 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 34371 |
. . . . . . . 8
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) ↔ (𝐴 ∈ (ℕ0
↑m ℕ) ∧ (◡𝐴 “ ℕ) ∈ Fin ∧ (◡𝐴 “ ℕ) ⊆ 𝐽)) |
| 14 | 13 | biimpi 216 |
. . . . . . 7
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 ∈ (ℕ0
↑m ℕ) ∧ (◡𝐴 “ ℕ) ∈ Fin ∧ (◡𝐴 “ ℕ) ⊆ 𝐽)) |
| 15 | 14 | simp1d 1143 |
. . . . . 6
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → 𝐴 ∈ (ℕ0
↑m ℕ)) |
| 16 | | nn0ex 12532 |
. . . . . . 7
⊢
ℕ0 ∈ V |
| 17 | | nnex 12272 |
. . . . . . 7
⊢ ℕ
∈ V |
| 18 | 16, 17 | elmap 8911 |
. . . . . 6
⊢ (𝐴 ∈ (ℕ0
↑m ℕ) ↔ 𝐴:ℕ⟶ℕ0) |
| 19 | 15, 18 | sylib 218 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → 𝐴:ℕ⟶ℕ0) |
| 20 | | ssrab2 4080 |
. . . . . 6
⊢ {𝑧 ∈ ℕ ∣ ¬ 2
∥ 𝑧} ⊆
ℕ |
| 21 | 7, 20 | eqsstri 4030 |
. . . . 5
⊢ 𝐽 ⊆
ℕ |
| 22 | | fssres 6774 |
. . . . 5
⊢ ((𝐴:ℕ⟶ℕ0 ∧
𝐽 ⊆ ℕ) →
(𝐴 ↾ 𝐽):𝐽⟶ℕ0) |
| 23 | 19, 21, 22 | sylancl 586 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 ↾ 𝐽):𝐽⟶ℕ0) |
| 24 | | fco2 6762 |
. . . 4
⊢ (((bits
↾ ℕ0):ℕ0⟶(𝒫
ℕ0 ∩ Fin) ∧ (𝐴 ↾ 𝐽):𝐽⟶ℕ0) → (bits
∘ (𝐴 ↾ 𝐽)):𝐽⟶(𝒫 ℕ0 ∩
Fin)) |
| 25 | 3, 23, 24 | sylancr 587 |
. . 3
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)):𝐽⟶(𝒫 ℕ0 ∩
Fin)) |
| 26 | 16 | pwex 5380 |
. . . . 5
⊢ 𝒫
ℕ0 ∈ V |
| 27 | 26 | inex1 5317 |
. . . 4
⊢
(𝒫 ℕ0 ∩ Fin) ∈ V |
| 28 | 17, 21 | ssexi 5322 |
. . . 4
⊢ 𝐽 ∈ V |
| 29 | 27, 28 | elmap 8911 |
. . 3
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫
ℕ0 ∩ Fin) ↑m 𝐽) ↔ (bits ∘ (𝐴 ↾ 𝐽)):𝐽⟶(𝒫 ℕ0 ∩
Fin)) |
| 30 | 25, 29 | sylibr 234 |
. 2
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫 ℕ0
∩ Fin) ↑m 𝐽)) |
| 31 | 14 | simp2d 1144 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡𝐴 “ ℕ) ∈
Fin) |
| 32 | | 0nn0 12541 |
. . . . . . . . 9
⊢ 0 ∈
ℕ0 |
| 33 | | suppimacnv 8199 |
. . . . . . . . 9
⊢ ((𝐴 ∈ (𝑇 ∩ 𝑅) ∧ 0 ∈ ℕ0) →
(𝐴 supp 0) = (◡𝐴 “ (V ∖ {0}))) |
| 34 | 32, 33 | mpan2 691 |
. . . . . . . 8
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 supp 0) = (◡𝐴 “ (V ∖ {0}))) |
| 35 | | fsuppeq 8200 |
. . . . . . . . . 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 2779 |
. . . . . . 7
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡𝐴 “ (V ∖ {0})) = (◡𝐴 “ (ℕ0 ∖
{0}))) |
| 39 | 38 | eleq1d 2826 |
. . . . . 6
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → ((◡𝐴 “ (V ∖ {0})) ∈ Fin ↔
(◡𝐴 “ (ℕ0 ∖ {0}))
∈ Fin)) |
| 40 | | dfn2 12539 |
. . . . . . . 8
⊢ ℕ =
(ℕ0 ∖ {0}) |
| 41 | 40 | imaeq2i 6076 |
. . . . . . 7
⊢ (◡𝐴 “ ℕ) = (◡𝐴 “ (ℕ0 ∖
{0})) |
| 42 | 41 | eleq1i 2832 |
. . . . . 6
⊢ ((◡𝐴 “ ℕ) ∈ Fin ↔ (◡𝐴 “ (ℕ0 ∖ {0}))
∈ Fin) |
| 43 | 39, 42 | bitr4di 289 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → ((◡𝐴 “ (V ∖ {0})) ∈ Fin ↔
(◡𝐴 “ ℕ) ∈
Fin)) |
| 44 | 31, 43 | mpbird 257 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡𝐴 “ (V ∖ {0})) ∈
Fin) |
| 45 | | resss 6019 |
. . . . 5
⊢ (𝐴 ↾ 𝐽) ⊆ 𝐴 |
| 46 | | cnvss 5883 |
. . . . 5
⊢ ((𝐴 ↾ 𝐽) ⊆ 𝐴 → ◡(𝐴 ↾ 𝐽) ⊆ ◡𝐴) |
| 47 | | imass1 6119 |
. . . . 5
⊢ (◡(𝐴 ↾ 𝐽) ⊆ ◡𝐴 → (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ⊆ (◡𝐴 “ (V ∖ {0}))) |
| 48 | 45, 46, 47 | mp2b 10 |
. . . 4
⊢ (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ⊆ (◡𝐴 “ (V ∖ {0})) |
| 49 | | ssfi 9213 |
. . . 4
⊢ (((◡𝐴 “ (V ∖ {0})) ∈ Fin ∧
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ⊆ (◡𝐴 “ (V ∖ {0}))) → (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ∈
Fin) |
| 50 | 44, 48, 49 | sylancl 586 |
. . 3
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ∈
Fin) |
| 51 | | cnvco 5896 |
. . . . . 6
⊢ ◡(bits ∘ (𝐴 ↾ 𝐽)) = (◡(𝐴 ↾ 𝐽) ∘ ◡bits) |
| 52 | 51 | imaeq1i 6075 |
. . . . 5
⊢ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) = ((◡(𝐴 ↾ 𝐽) ∘ ◡bits) “ (V ∖
{∅})) |
| 53 | | imaco 6271 |
. . . . 5
⊢ ((◡(𝐴 ↾ 𝐽) ∘ ◡bits) “ (V ∖ {∅})) =
(◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖
{∅}))) |
| 54 | 52, 53 | eqtri 2765 |
. . . 4
⊢ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) = (◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖
{∅}))) |
| 55 | | ffun 6739 |
. . . . . 6
⊢ (𝐴:ℕ⟶ℕ0 →
Fun 𝐴) |
| 56 | | funres 6608 |
. . . . . 6
⊢ (Fun
𝐴 → Fun (𝐴 ↾ 𝐽)) |
| 57 | 19, 55, 56 | 3syl 18 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → Fun (𝐴 ↾ 𝐽)) |
| 58 | | ssv 4008 |
. . . . . . 7
⊢ (◡bits “ V) ⊆ V |
| 59 | | ssdif 4144 |
. . . . . . 7
⊢ ((◡bits “ V) ⊆ V → ((◡bits “ V) ∖ (◡bits “ {∅})) ⊆ (V ∖
(◡bits “
{∅}))) |
| 60 | 58, 59 | ax-mp 5 |
. . . . . 6
⊢ ((◡bits “ V) ∖ (◡bits “ {∅})) ⊆ (V ∖
(◡bits “
{∅})) |
| 61 | | bitsf 16464 |
. . . . . . 7
⊢
bits:ℤ⟶𝒫 ℕ0 |
| 62 | | ffun 6739 |
. . . . . . 7
⊢
(bits:ℤ⟶𝒫 ℕ0 → Fun
bits) |
| 63 | | difpreima 7085 |
. . . . . . 7
⊢ (Fun bits
→ (◡bits “ (V ∖
{∅})) = ((◡bits “ V)
∖ (◡bits “
{∅}))) |
| 64 | 61, 62, 63 | mp2b 10 |
. . . . . 6
⊢ (◡bits “ (V ∖ {∅})) =
((◡bits “ V) ∖ (◡bits “ {∅})) |
| 65 | | bitsf1 16483 |
. . . . . . . . 9
⊢
bits:ℤ–1-1→𝒫 ℕ0 |
| 66 | | 0z 12624 |
. . . . . . . . . 10
⊢ 0 ∈
ℤ |
| 67 | | snssi 4808 |
. . . . . . . . . 10
⊢ (0 ∈
ℤ → {0} ⊆ ℤ) |
| 68 | 66, 67 | ax-mp 5 |
. . . . . . . . 9
⊢ {0}
⊆ ℤ |
| 69 | | f1imacnv 6864 |
. . . . . . . . 9
⊢
((bits:ℤ–1-1→𝒫 ℕ0 ∧ {0} ⊆
ℤ) → (◡bits “ (bits
“ {0})) = {0}) |
| 70 | 65, 68, 69 | mp2an 692 |
. . . . . . . 8
⊢ (◡bits “ (bits “ {0})) =
{0} |
| 71 | | ffn 6736 |
. . . . . . . . . . . 12
⊢
(bits:ℤ⟶𝒫 ℕ0 → bits Fn
ℤ) |
| 72 | 61, 71 | ax-mp 5 |
. . . . . . . . . . 11
⊢ bits Fn
ℤ |
| 73 | | fnsnfv 6988 |
. . . . . . . . . . 11
⊢ ((bits Fn
ℤ ∧ 0 ∈ ℤ) → {(bits‘0)} = (bits “
{0})) |
| 74 | 72, 66, 73 | mp2an 692 |
. . . . . . . . . 10
⊢
{(bits‘0)} = (bits “ {0}) |
| 75 | | 0bits 16476 |
. . . . . . . . . . 11
⊢
(bits‘0) = ∅ |
| 76 | 75 | sneqi 4637 |
. . . . . . . . . 10
⊢
{(bits‘0)} = {∅} |
| 77 | 74, 76 | eqtr3i 2767 |
. . . . . . . . 9
⊢ (bits
“ {0}) = {∅} |
| 78 | 77 | imaeq2i 6076 |
. . . . . . . 8
⊢ (◡bits “ (bits “ {0})) = (◡bits “ {∅}) |
| 79 | 70, 78 | eqtr3i 2767 |
. . . . . . 7
⊢ {0} =
(◡bits “
{∅}) |
| 80 | 79 | difeq2i 4123 |
. . . . . 6
⊢ (V
∖ {0}) = (V ∖ (◡bits
“ {∅})) |
| 81 | 60, 64, 80 | 3sstr4i 4035 |
. . . . 5
⊢ (◡bits “ (V ∖ {∅})) ⊆
(V ∖ {0}) |
| 82 | | sspreima 7088 |
. . . . 5
⊢ ((Fun
(𝐴 ↾ 𝐽) ∧ (◡bits “ (V ∖ {∅})) ⊆
(V ∖ {0})) → (◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖ {∅}))) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) |
| 83 | 57, 81, 82 | sylancl 586 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(𝐴 ↾ 𝐽) “ (◡bits “ (V ∖ {∅}))) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) |
| 84 | 54, 83 | eqsstrid 4022 |
. . 3
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) |
| 85 | | ssfi 9213 |
. . 3
⊢ (((◡(𝐴 ↾ 𝐽) “ (V ∖ {0})) ∈ Fin ∧
(◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ⊆
(◡(𝐴 ↾ 𝐽) “ (V ∖ {0}))) → (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin) |
| 86 | 50, 84, 85 | syl2anc 584 |
. 2
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin) |
| 87 | | oveq1 7438 |
. . . . 5
⊢ (𝑟 = (bits ∘ (𝐴 ↾ 𝐽)) → (𝑟 supp ∅) = ((bits ∘ (𝐴 ↾ 𝐽)) supp ∅)) |
| 88 | 87 | eleq1d 2826 |
. . . 4
⊢ (𝑟 = (bits ∘ (𝐴 ↾ 𝐽)) → ((𝑟 supp ∅) ∈ Fin ↔ ((bits
∘ (𝐴 ↾ 𝐽)) supp ∅) ∈
Fin)) |
| 89 | 88, 9 | elrab2 3695 |
. . 3
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ 𝐻 ↔ ((bits ∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫 ℕ0
∩ Fin) ↑m 𝐽) ∧ ((bits ∘ (𝐴 ↾ 𝐽)) supp ∅) ∈
Fin)) |
| 90 | | zex 12622 |
. . . . . 6
⊢ ℤ
∈ V |
| 91 | | fex 7246 |
. . . . . 6
⊢
((bits:ℤ⟶𝒫 ℕ0 ∧ ℤ ∈
V) → bits ∈ V) |
| 92 | 61, 90, 91 | mp2an 692 |
. . . . 5
⊢ bits
∈ V |
| 93 | | resexg 6045 |
. . . . 5
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (𝐴 ↾ 𝐽) ∈ V) |
| 94 | | coexg 7951 |
. . . . 5
⊢ ((bits
∈ V ∧ (𝐴 ↾
𝐽) ∈ V) → (bits
∘ (𝐴 ↾ 𝐽)) ∈ V) |
| 95 | 92, 93, 94 | sylancr 587 |
. . . 4
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)) ∈ V) |
| 96 | | 0ex 5307 |
. . . . . . 7
⊢ ∅
∈ V |
| 97 | | suppimacnv 8199 |
. . . . . . 7
⊢ (((bits
∘ (𝐴 ↾ 𝐽)) ∈ V ∧ ∅ ∈
V) → ((bits ∘ (𝐴
↾ 𝐽)) supp ∅) =
(◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖
{∅}))) |
| 98 | 96, 97 | mpan2 691 |
. . . . . 6
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ V → ((bits
∘ (𝐴 ↾ 𝐽)) supp ∅) = (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖
{∅}))) |
| 99 | 98 | eleq1d 2826 |
. . . . 5
⊢ ((bits
∘ (𝐴 ↾ 𝐽)) ∈ V → (((bits
∘ (𝐴 ↾ 𝐽)) supp ∅) ∈ Fin
↔ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin)) |
| 100 | 99 | anbi2d 630 |
. . . 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 | bitrid 283 |
. 2
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → ((bits ∘ (𝐴 ↾ 𝐽)) ∈ 𝐻 ↔ ((bits ∘ (𝐴 ↾ 𝐽)) ∈ ((𝒫 ℕ0
∩ Fin) ↑m 𝐽) ∧ (◡(bits ∘ (𝐴 ↾ 𝐽)) “ (V ∖ {∅})) ∈
Fin))) |
| 103 | 30, 86, 102 | mpbir2and 713 |
1
⊢ (𝐴 ∈ (𝑇 ∩ 𝑅) → (bits ∘ (𝐴 ↾ 𝐽)) ∈ 𝐻) |