Proof of Theorem ballotlemic
Step | Hyp | Ref
| Expression |
1 | | ballotth.m |
. . 3
⊢ 𝑀 ∈ ℕ |
2 | | ballotth.n |
. . 3
⊢ 𝑁 ∈ ℕ |
3 | | ballotth.o |
. . 3
⊢ 𝑂 = {𝑐 ∈ 𝒫 (1...(𝑀 + 𝑁)) ∣ (♯‘𝑐) = 𝑀} |
4 | | ballotth.p |
. . 3
⊢ 𝑃 = (𝑥 ∈ 𝒫 𝑂 ↦ ((♯‘𝑥) / (♯‘𝑂))) |
5 | | ballotth.f |
. . 3
⊢ 𝐹 = (𝑐 ∈ 𝑂 ↦ (𝑖 ∈ ℤ ↦
((♯‘((1...𝑖)
∩ 𝑐)) −
(♯‘((1...𝑖)
∖ 𝑐))))) |
6 | | eldifi 4061 |
. . . 4
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → 𝐶 ∈ 𝑂) |
7 | 6 | ad2antrr 723 |
. . 3
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 𝐶 ∈ 𝑂) |
8 | | ballotth.e |
. . . . . . . . . 10
⊢ 𝐸 = {𝑐 ∈ 𝑂 ∣ ∀𝑖 ∈ (1...(𝑀 + 𝑁))0 < ((𝐹‘𝑐)‘𝑖)} |
9 | | ballotth.mgtn |
. . . . . . . . . 10
⊢ 𝑁 < 𝑀 |
10 | | ballotth.i |
. . . . . . . . . 10
⊢ 𝐼 = (𝑐 ∈ (𝑂 ∖ 𝐸) ↦ inf({𝑘 ∈ (1...(𝑀 + 𝑁)) ∣ ((𝐹‘𝑐)‘𝑘) = 0}, ℝ, < )) |
11 | 1, 2, 3, 4, 5, 8, 9, 10 | ballotlemiex 32468 |
. . . . . . . . 9
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((𝐼‘𝐶) ∈ (1...(𝑀 + 𝑁)) ∧ ((𝐹‘𝐶)‘(𝐼‘𝐶)) = 0)) |
12 | 11 | simpld 495 |
. . . . . . . 8
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝐼‘𝐶) ∈ (1...(𝑀 + 𝑁))) |
13 | | elfznn 13285 |
. . . . . . . 8
⊢ ((𝐼‘𝐶) ∈ (1...(𝑀 + 𝑁)) → (𝐼‘𝐶) ∈ ℕ) |
14 | 12, 13 | syl 17 |
. . . . . . 7
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝐼‘𝐶) ∈ ℕ) |
15 | 14 | adantr 481 |
. . . . . 6
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → (𝐼‘𝐶) ∈ ℕ) |
16 | 1, 2, 3, 4, 5, 8, 9, 10 | ballotlemi1 32469 |
. . . . . 6
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → (𝐼‘𝐶) ≠ 1) |
17 | | eluz2b3 12662 |
. . . . . 6
⊢ ((𝐼‘𝐶) ∈ (ℤ≥‘2)
↔ ((𝐼‘𝐶) ∈ ℕ ∧ (𝐼‘𝐶) ≠ 1)) |
18 | 15, 16, 17 | sylanbrc 583 |
. . . . 5
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → (𝐼‘𝐶) ∈
(ℤ≥‘2)) |
19 | | uz2m1nn 12663 |
. . . . 5
⊢ ((𝐼‘𝐶) ∈ (ℤ≥‘2)
→ ((𝐼‘𝐶) − 1) ∈
ℕ) |
20 | 18, 19 | syl 17 |
. . . 4
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → ((𝐼‘𝐶) − 1) ∈
ℕ) |
21 | 20 | adantr 481 |
. . 3
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((𝐼‘𝐶) − 1) ∈
ℕ) |
22 | | elnnuz 12622 |
. . . . . . 7
⊢ (((𝐼‘𝐶) − 1) ∈ ℕ ↔ ((𝐼‘𝐶) − 1) ∈
(ℤ≥‘1)) |
23 | 22 | biimpi 215 |
. . . . . 6
⊢ (((𝐼‘𝐶) − 1) ∈ ℕ → ((𝐼‘𝐶) − 1) ∈
(ℤ≥‘1)) |
24 | | eluzfz1 13263 |
. . . . . 6
⊢ (((𝐼‘𝐶) − 1) ∈
(ℤ≥‘1) → 1 ∈ (1...((𝐼‘𝐶) − 1))) |
25 | 20, 23, 24 | 3syl 18 |
. . . . 5
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → 1 ∈ (1...((𝐼‘𝐶) − 1))) |
26 | 25 | adantr 481 |
. . . 4
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 1 ∈ (1...((𝐼‘𝐶) − 1))) |
27 | | 1nn 11984 |
. . . . . . . . . . 11
⊢ 1 ∈
ℕ |
28 | 27 | a1i 11 |
. . . . . . . . . 10
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → 1 ∈ ℕ) |
29 | 1, 2, 3, 4, 5, 6, 28 | ballotlemfp1 32458 |
. . . . . . . . 9
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((¬ 1 ∈ 𝐶 → ((𝐹‘𝐶)‘1) = (((𝐹‘𝐶)‘(1 − 1)) − 1)) ∧ (1
∈ 𝐶 → ((𝐹‘𝐶)‘1) = (((𝐹‘𝐶)‘(1 − 1)) +
1)))) |
30 | 29 | simpld 495 |
. . . . . . . 8
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (¬ 1 ∈ 𝐶 → ((𝐹‘𝐶)‘1) = (((𝐹‘𝐶)‘(1 − 1)) −
1))) |
31 | 30 | imp 407 |
. . . . . . 7
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → ((𝐹‘𝐶)‘1) = (((𝐹‘𝐶)‘(1 − 1)) −
1)) |
32 | | 1m1e0 12045 |
. . . . . . . . . 10
⊢ (1
− 1) = 0 |
33 | 32 | fveq2i 6777 |
. . . . . . . . 9
⊢ ((𝐹‘𝐶)‘(1 − 1)) = ((𝐹‘𝐶)‘0) |
34 | 33 | oveq1i 7285 |
. . . . . . . 8
⊢ (((𝐹‘𝐶)‘(1 − 1)) − 1) = (((𝐹‘𝐶)‘0) − 1) |
35 | 34 | a1i 11 |
. . . . . . 7
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → (((𝐹‘𝐶)‘(1 − 1)) − 1) = (((𝐹‘𝐶)‘0) − 1)) |
36 | 1, 2, 3, 4, 5 | ballotlemfval0 32462 |
. . . . . . . . . 10
⊢ (𝐶 ∈ 𝑂 → ((𝐹‘𝐶)‘0) = 0) |
37 | 6, 36 | syl 17 |
. . . . . . . . 9
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((𝐹‘𝐶)‘0) = 0) |
38 | 37 | adantr 481 |
. . . . . . . 8
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → ((𝐹‘𝐶)‘0) = 0) |
39 | 38 | oveq1d 7290 |
. . . . . . 7
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → (((𝐹‘𝐶)‘0) − 1) = (0 −
1)) |
40 | 31, 35, 39 | 3eqtrrd 2783 |
. . . . . 6
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → (0 − 1) = ((𝐹‘𝐶)‘1)) |
41 | | 0le1 11498 |
. . . . . . 7
⊢ 0 ≤
1 |
42 | | 0re 10977 |
. . . . . . . 8
⊢ 0 ∈
ℝ |
43 | | 1re 10975 |
. . . . . . . 8
⊢ 1 ∈
ℝ |
44 | | suble0 11489 |
. . . . . . . 8
⊢ ((0
∈ ℝ ∧ 1 ∈ ℝ) → ((0 − 1) ≤ 0 ↔ 0
≤ 1)) |
45 | 42, 43, 44 | mp2an 689 |
. . . . . . 7
⊢ ((0
− 1) ≤ 0 ↔ 0 ≤ 1) |
46 | 41, 45 | mpbir 230 |
. . . . . 6
⊢ (0
− 1) ≤ 0 |
47 | 40, 46 | eqbrtrrdi 5114 |
. . . . 5
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → ((𝐹‘𝐶)‘1) ≤ 0) |
48 | 47 | adantr 481 |
. . . 4
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((𝐹‘𝐶)‘1) ≤ 0) |
49 | | fveq2 6774 |
. . . . . 6
⊢ (𝑖 = 1 → ((𝐹‘𝐶)‘𝑖) = ((𝐹‘𝐶)‘1)) |
50 | 49 | breq1d 5084 |
. . . . 5
⊢ (𝑖 = 1 → (((𝐹‘𝐶)‘𝑖) ≤ 0 ↔ ((𝐹‘𝐶)‘1) ≤ 0)) |
51 | 50 | rspcev 3561 |
. . . 4
⊢ ((1
∈ (1...((𝐼‘𝐶) − 1)) ∧ ((𝐹‘𝐶)‘1) ≤ 0) → ∃𝑖 ∈ (1...((𝐼‘𝐶) − 1))((𝐹‘𝐶)‘𝑖) ≤ 0) |
52 | 26, 48, 51 | syl2anc 584 |
. . 3
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ∃𝑖 ∈ (1...((𝐼‘𝐶) − 1))((𝐹‘𝐶)‘𝑖) ≤ 0) |
53 | | 0lt1 11497 |
. . . . 5
⊢ 0 <
1 |
54 | | 1p0e1 12097 |
. . . . . 6
⊢ (1 + 0) =
1 |
55 | 1, 2, 3, 4, 5, 6, 14 | ballotlemfp1 32458 |
. . . . . . . . . 10
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((¬ (𝐼‘𝐶) ∈ 𝐶 → ((𝐹‘𝐶)‘(𝐼‘𝐶)) = (((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) − 1)) ∧ ((𝐼‘𝐶) ∈ 𝐶 → ((𝐹‘𝐶)‘(𝐼‘𝐶)) = (((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) + 1)))) |
56 | 55 | simpld 495 |
. . . . . . . . 9
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (¬ (𝐼‘𝐶) ∈ 𝐶 → ((𝐹‘𝐶)‘(𝐼‘𝐶)) = (((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) − 1))) |
57 | 56 | imp 407 |
. . . . . . . 8
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((𝐹‘𝐶)‘(𝐼‘𝐶)) = (((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) − 1)) |
58 | 11 | simprd 496 |
. . . . . . . . 9
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((𝐹‘𝐶)‘(𝐼‘𝐶)) = 0) |
59 | 58 | adantr 481 |
. . . . . . . 8
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((𝐹‘𝐶)‘(𝐼‘𝐶)) = 0) |
60 | 57, 59 | eqtr3d 2780 |
. . . . . . 7
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → (((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) − 1) =
0) |
61 | 6 | adantr 481 |
. . . . . . . . . 10
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 𝐶 ∈ 𝑂) |
62 | 14 | nnzd 12425 |
. . . . . . . . . . . 12
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝐼‘𝐶) ∈ ℤ) |
63 | 62 | adantr 481 |
. . . . . . . . . . 11
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → (𝐼‘𝐶) ∈ ℤ) |
64 | | 1zzd 12351 |
. . . . . . . . . . 11
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 1 ∈ ℤ) |
65 | 63, 64 | zsubcld 12431 |
. . . . . . . . . 10
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((𝐼‘𝐶) − 1) ∈
ℤ) |
66 | 1, 2, 3, 4, 5, 61,
65 | ballotlemfelz 32457 |
. . . . . . . . 9
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) ∈
ℤ) |
67 | 66 | zcnd 12427 |
. . . . . . . 8
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) ∈
ℂ) |
68 | | 1cnd 10970 |
. . . . . . . 8
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 1 ∈ ℂ) |
69 | | 0cnd 10968 |
. . . . . . . 8
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 0 ∈ ℂ) |
70 | 67, 68, 69 | subaddd 11350 |
. . . . . . 7
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ((((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)) − 1) = 0 ↔ (1 + 0)
= ((𝐹‘𝐶)‘((𝐼‘𝐶) − 1)))) |
71 | 60, 70 | mpbid 231 |
. . . . . 6
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → (1 + 0) = ((𝐹‘𝐶)‘((𝐼‘𝐶) − 1))) |
72 | 54, 71 | eqtr3id 2792 |
. . . . 5
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 1 = ((𝐹‘𝐶)‘((𝐼‘𝐶) − 1))) |
73 | 53, 72 | breqtrid 5111 |
. . . 4
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 0 < ((𝐹‘𝐶)‘((𝐼‘𝐶) − 1))) |
74 | 73 | adantlr 712 |
. . 3
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → 0 < ((𝐹‘𝐶)‘((𝐼‘𝐶) − 1))) |
75 | 1, 2, 3, 4, 5, 7, 21, 52, 74 | ballotlemfc0 32459 |
. 2
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ∃𝑘 ∈ (1...((𝐼‘𝐶) − 1))((𝐹‘𝐶)‘𝑘) = 0) |
76 | 1, 2, 3, 4, 5, 8, 9, 10 | ballotlemimin 32472 |
. . 3
⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ¬ ∃𝑘 ∈ (1...((𝐼‘𝐶) − 1))((𝐹‘𝐶)‘𝑘) = 0) |
77 | 76 | ad2antrr 723 |
. 2
⊢ (((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) ∧ ¬ (𝐼‘𝐶) ∈ 𝐶) → ¬ ∃𝑘 ∈ (1...((𝐼‘𝐶) − 1))((𝐹‘𝐶)‘𝑘) = 0) |
78 | 75, 77 | condan 815 |
1
⊢ ((𝐶 ∈ (𝑂 ∖ 𝐸) ∧ ¬ 1 ∈ 𝐶) → (𝐼‘𝐶) ∈ 𝐶) |