ballotlemro - Mathbox for Thierry Arnoux

	Mathbox for Thierry Arnoux		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > Mathboxes > ballotlemro		Structured version Visualization version GIF version

Theorem ballotlemro 34764

Description: Range of 𝑅 is included in 𝑂. (Contributed by Thierry Arnoux, 17-Apr-2017.)

**Hypotheses**
Ref	Expression
ballotth.m	⊢ 𝑀 ∈ ℕ
ballotth.n	⊢ 𝑁 ∈ ℕ
ballotth.o	⊢ 𝑂 = {𝑐 ∈ 𝒫 (1...(𝑀 + 𝑁)) ∣ (♯‘𝑐) = 𝑀}
ballotth.p	⊢ 𝑃 = (𝑥 ∈ 𝒫 𝑂 ↦ ((♯‘𝑥) / (♯‘𝑂)))
ballotth.f	⊢ 𝐹 = (𝑐 ∈ 𝑂 ↦ (𝑖 ∈ ℤ ↦ ((♯‘((1...𝑖) ∩ 𝑐)) − (♯‘((1...𝑖) ∖ 𝑐)))))
ballotth.e	⊢ 𝐸 = {𝑐 ∈ 𝑂 ∣ ∀𝑖 ∈ (1...(𝑀 + 𝑁))0 < ((𝐹‘𝑐)‘𝑖)}
ballotth.mgtn	⊢ 𝑁 < 𝑀
ballotth.i	⊢ 𝐼 = (𝑐 ∈ (𝑂 ∖ 𝐸) ↦ inf({𝑘 ∈ (1...(𝑀 + 𝑁)) ∣ ((𝐹‘𝑐)‘𝑘) = 0}, ℝ, < ))
ballotth.s	⊢ 𝑆 = (𝑐 ∈ (𝑂 ∖ 𝐸) ↦ (𝑖 ∈ (1...(𝑀 + 𝑁)) ↦ if(𝑖 ≤ (𝐼‘𝑐), (((𝐼‘𝑐) + 1) − 𝑖), 𝑖)))
ballotth.r	⊢ 𝑅 = (𝑐 ∈ (𝑂 ∖ 𝐸) ↦ ((𝑆‘𝑐) “ 𝑐))

**Assertion**
Ref	Expression
ballotlemro	⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝑅‘𝐶) ∈ 𝑂)

Distinct variable groups: 𝑀,𝑐 𝑁,𝑐 𝑂,𝑐 𝑖,𝑀 𝑖,𝑁 𝑖,𝑂 𝑘,𝑀 𝑘,𝑁 𝑘,𝑂 𝑖,𝑐,𝐹,𝑘 𝐶,𝑖,𝑘 𝑖,𝐸,𝑘 𝐶,𝑘 𝑘,𝐼,𝑐 𝐸,𝑐 𝑖,𝐼,𝑐 𝑆,𝑘,𝑖,𝑐 Allowed substitution hints: 𝐶(𝑥,𝑐) 𝑃(𝑥,𝑖,𝑘,𝑐) 𝑅(𝑥,𝑖,𝑘,𝑐) 𝑆(𝑥) 𝐸(𝑥) 𝐹(𝑥) 𝐼(𝑥) 𝑀(𝑥) 𝑁(𝑥) 𝑂(𝑥)

**Proof of Theorem ballotlemro**
Step	Hyp	Ref	Expression
1		ballotth.m	. . . 4 ⊢ 𝑀 ∈ ℕ
2		ballotth.n	. . . 4 ⊢ 𝑁 ∈ ℕ
3		ballotth.o	. . . 4 ⊢ 𝑂 = {𝑐 ∈ 𝒫 (1...(𝑀 + 𝑁)) ∣ (♯‘𝑐) = 𝑀}
4		ballotth.p	. . . 4 ⊢ 𝑃 = (𝑥 ∈ 𝒫 𝑂 ↦ ((♯‘𝑥) / (♯‘𝑂)))
5		ballotth.f	. . . 4 ⊢ 𝐹 = (𝑐 ∈ 𝑂 ↦ (𝑖 ∈ ℤ ↦ ((♯‘((1...𝑖) ∩ 𝑐)) − (♯‘((1...𝑖) ∖ 𝑐)))))
6		ballotth.e	. . . 4 ⊢ 𝐸 = {𝑐 ∈ 𝑂 ∣ ∀𝑖 ∈ (1...(𝑀 + 𝑁))0 < ((𝐹‘𝑐)‘𝑖)}
7		ballotth.mgtn	. . . 4 ⊢ 𝑁 < 𝑀
8		ballotth.i	. . . 4 ⊢ 𝐼 = (𝑐 ∈ (𝑂 ∖ 𝐸) ↦ inf({𝑘 ∈ (1...(𝑀 + 𝑁)) ∣ ((𝐹‘𝑐)‘𝑘) = 0}, ℝ, < ))
9		ballotth.s	. . . 4 ⊢ 𝑆 = (𝑐 ∈ (𝑂 ∖ 𝐸) ↦ (𝑖 ∈ (1...(𝑀 + 𝑁)) ↦ if(𝑖 ≤ (𝐼‘𝑐), (((𝐼‘𝑐) + 1) − 𝑖), 𝑖)))
10		ballotth.r	. . . 4 ⊢ 𝑅 = (𝑐 ∈ (𝑂 ∖ 𝐸) ↦ ((𝑆‘𝑐) “ 𝑐))
11	1, 2, 3, 4, 5, 6, 7, 8, 9, 10	ballotlemrval 34759	. . 3 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝑅‘𝐶) = ((𝑆‘𝐶) “ 𝐶))
12		imassrn 6046	. . . 4 ⊢ ((𝑆‘𝐶) “ 𝐶) ⊆ ran (𝑆‘𝐶)
13	1, 2, 3, 4, 5, 6, 7, 8, 9	ballotlemsf1o 34755	. . . . . 6 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((𝑆‘𝐶):(1...(𝑀 + 𝑁))–1-1-onto→(1...(𝑀 + 𝑁)) ∧ ^◡(𝑆‘𝐶) = (𝑆‘𝐶)))
14	13	simpld 497	. . . . 5 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝑆‘𝐶):(1...(𝑀 + 𝑁))–1-1-onto→(1...(𝑀 + 𝑁)))
15		f1ofo 6799	. . . . 5 ⊢ ((𝑆‘𝐶):(1...(𝑀 + 𝑁))–1-1-onto→(1...(𝑀 + 𝑁)) → (𝑆‘𝐶):(1...(𝑀 + 𝑁))–onto→(1...(𝑀 + 𝑁)))
16		forn 6766	. . . . 5 ⊢ ((𝑆‘𝐶):(1...(𝑀 + 𝑁))–onto→(1...(𝑀 + 𝑁)) → ran (𝑆‘𝐶) = (1...(𝑀 + 𝑁)))
17	14, 15, 16	3syl 18	. . . 4 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ran (𝑆‘𝐶) = (1...(𝑀 + 𝑁)))
18	12, 17	sseqtrid 3969	. . 3 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((𝑆‘𝐶) “ 𝐶) ⊆ (1...(𝑀 + 𝑁)))
19	11, 18	eqsstrd 3961	. 2 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝑅‘𝐶) ⊆ (1...(𝑀 + 𝑁)))
20		f1of1 6790	. . . . . . 7 ⊢ ((𝑆‘𝐶):(1...(𝑀 + 𝑁))–1-1-onto→(1...(𝑀 + 𝑁)) → (𝑆‘𝐶):(1...(𝑀 + 𝑁))–1-1→(1...(𝑀 + 𝑁)))
21	14, 20	syl 17	. . . . . 6 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝑆‘𝐶):(1...(𝑀 + 𝑁))–1-1→(1...(𝑀 + 𝑁)))
22		eldifi 4075	. . . . . . . 8 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → 𝐶 ∈ 𝑂)
23	1, 2, 3	ballotlemelo 34729	. . . . . . . 8 ⊢ (𝐶 ∈ 𝑂 ↔ (𝐶 ⊆ (1...(𝑀 + 𝑁)) ∧ (♯‘𝐶) = 𝑀))
24	22, 23	sylib 220	. . . . . . 7 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝐶 ⊆ (1...(𝑀 + 𝑁)) ∧ (♯‘𝐶) = 𝑀))
25	24	simpld 497	. . . . . 6 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → 𝐶 ⊆ (1...(𝑀 + 𝑁)))
26		id 22	. . . . . 6 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → 𝐶 ∈ (𝑂 ∖ 𝐸))
27		f1imaeng 8980	. . . . . 6 ⊢ (((𝑆‘𝐶):(1...(𝑀 + 𝑁))–1-1→(1...(𝑀 + 𝑁)) ∧ 𝐶 ⊆ (1...(𝑀 + 𝑁)) ∧ 𝐶 ∈ (𝑂 ∖ 𝐸)) → ((𝑆‘𝐶) “ 𝐶) ≈ 𝐶)
28	21, 25, 26, 27	syl3anc 1382	. . . . 5 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → ((𝑆‘𝐶) “ 𝐶) ≈ 𝐶)
29	11, 28	eqbrtrd 5112	. . . 4 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝑅‘𝐶) ≈ 𝐶)
30		hasheni 14347	. . . 4 ⊢ ((𝑅‘𝐶) ≈ 𝐶 → (♯‘(𝑅‘𝐶)) = (♯‘𝐶))
31	29, 30	syl 17	. . 3 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (♯‘(𝑅‘𝐶)) = (♯‘𝐶))
32	24	simprd 498	. . 3 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (♯‘𝐶) = 𝑀)
33	31, 32	eqtrd 2787	. 2 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (♯‘(𝑅‘𝐶)) = 𝑀)
34	1, 2, 3	ballotlemelo 34729	. 2 ⊢ ((𝑅‘𝐶) ∈ 𝑂 ↔ ((𝑅‘𝐶) ⊆ (1...(𝑀 + 𝑁)) ∧ (♯‘(𝑅‘𝐶)) = 𝑀))
35	19, 33, 34	sylanbrc 591	1 ⊢ (𝐶 ∈ (𝑂 ∖ 𝐸) → (𝑅‘𝐶) ∈ 𝑂)

Colors of variables: wff setvar class

Syntax hints: → wi 4 ∧ wa 398 = wceq 1550 ∈ wcel 2132 ∀wral 3066 {crab 3404 ∖ cdif 3892 ∩ cin 3894 ⊆ wss 3895 ifcif 4470 𝒫 cpw 4545 class class class wbr 5090 ↦ cmpt 5171 ^◡ccnv 5635 ran crn 5637 “ cima 5639 –1-1→wf1 6503 –onto→wfo 6504 –1-1-onto→wf1o 6505 ‘cfv 6506 (class class class)co 7381 ≈ cen 8909 infcinf 9373 ℝcr 11058 0cc0 11059 1c1 11060 + caddc 11062 < clt 11202 ≤ cle 11203 − cmin 11400 / cdiv 11830 ℕcn 12196 ℤcz 12554 ...cfz 13498 ♯chash 14329

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1805 ax-4 1819 ax-5 1920 ax-6 1977 ax-7 2018 ax-8 2134 ax-9 2142 ax-10 2165 ax-11 2181 ax-12 2202 ax-ext 2724 ax-rep 5217 ax-sep 5236 ax-nul 5246 ax-pow 5312 ax-pr 5380 ax-un 7703 ax-cnex 11115 ax-resscn 11116 ax-1cn 11117 ax-icn 11118 ax-addcl 11119 ax-addrcl 11120 ax-mulcl 11121 ax-mulrcl 11122 ax-mulcom 11123 ax-addass 11124 ax-mulass 11125 ax-distr 11126 ax-i2m1 11127 ax-1ne0 11128 ax-1rid 11129 ax-rnegex 11130 ax-rrecex 11131 ax-cnre 11132 ax-pre-lttri 11133 ax-pre-lttrn 11134 ax-pre-ltadd 11135 ax-pre-mulgt0 11136

This theorem depends on definitions: df-bi 209 df-an 399 df-or 857 df-3or 1096 df-3an 1097 df-tru 1553 df-fal 1563 df-ex 1790 df-nf 1794 df-sb 2081 df-mo 2556 df-eu 2586 df-clab 2731 df-cleq 2744 df-clel 2827 df-nfc 2901 df-ne 2948 df-nel 3052 df-ral 3067 df-rex 3077 df-rmo 3357 df-reu 3358 df-rab 3405 df-v 3446 df-sbc 3736 df-csb 3844 df-dif 3898 df-un 3900 df-in 3902 df-ss 3912 df-pss 3915 df-nul 4277 df-if 4471 df-pw 4547 df-sn 4573 df-pr 4575 df-op 4579 df-uni 4856 df-int 4896 df-iun 4941 df-br 5091 df-opab 5153 df-mpt 5172 df-tr 5198 df-id 5531 df-eprel 5536 df-po 5544 df-so 5545 df-fr 5589 df-we 5591 df-xp 5642 df-rel 5643 df-cnv 5644 df-co 5645 df-dm 5646 df-rn 5647 df-res 5648 df-ima 5649 df-pred 6273 df-ord 6334 df-on 6335 df-lim 6336 df-suc 6337 df-iota 6462 df-fun 6508 df-fn 6509 df-f 6510 df-f1 6511 df-fo 6512 df-f1o 6513 df-fv 6514 df-riota 7338 df-ov 7384 df-oprab 7385 df-mpo 7386 df-om 7832 df-1st 7955 df-2nd 7956 df-frecs 8246 df-wrecs 8277 df-recs 8326 df-rdg 8365 df-1o 8421 df-oadd 8425 df-er 8662 df-en 8913 df-dom 8914 df-sdom 8915 df-fin 8916 df-sup 9374 df-inf 9375 df-dju 9845 df-card 9883 df-pnf 11204 df-mnf 11205 df-xr 11206 df-ltxr 11207 df-le 11208 df-sub 11402 df-neg 11403 df-nn 12197 df-2 12266 df-n0 12468 df-z 12555 df-uz 12826 df-rp 12980 df-fz 13499 df-hash 14330

This theorem is referenced by: ballotlemfrc 34768 ballotlemfrceq 34770 ballotlemfrcn0 34771 ballotlemrc 34772

W3C validator