Theorem hashbc 14415

Description: The binomial coefficient counts the number of subsets of a finite set of a given size. This is Metamath 100 proof #58 (formula for the number of combinations). (Contributed by Mario Carneiro, 13-Jul-2014.)

Assertion

Ref	Expression
hashbc	⊢ ((𝐴 ∈ Fin ∧ 𝐾 ∈ ℤ) → ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))

Distinct variable groups:   𝑥,𝐴   𝑥,𝐾

Proof of Theorem hashbc

Dummy variables 𝑗 𝑘 𝑤 𝑦 𝑧 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		fveq2 6840	. . . . . 6 ⊢ (𝑤 = ∅ → (♯‘𝑤) = (♯‘∅))
2	1	oveq1d 7382	. . . . 5 ⊢ (𝑤 = ∅ → ((♯‘𝑤)C𝑘) = ((♯‘∅)C𝑘))
3		pweq 4555	. . . . . . 7 ⊢ (𝑤 = ∅ → 𝒫 𝑤 = 𝒫 ∅)
4	3	rabeqdv 3404	. . . . . 6 ⊢ (𝑤 = ∅ → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
5	4	fveq2d 6844	. . . . 5 ⊢ (𝑤 = ∅ → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
6	2, 5	eqeq12d 2752	. . . 4 ⊢ (𝑤 = ∅ → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})))
7	6	ralbidv 3160	. . 3 ⊢ (𝑤 = ∅ → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})))
8		fveq2 6840	. . . . . 6 ⊢ (𝑤 = 𝑦 → (♯‘𝑤) = (♯‘𝑦))
9	8	oveq1d 7382	. . . . 5 ⊢ (𝑤 = 𝑦 → ((♯‘𝑤)C𝑘) = ((♯‘𝑦)C𝑘))
10		pweq 4555	. . . . . . 7 ⊢ (𝑤 = 𝑦 → 𝒫 𝑤 = 𝒫 𝑦)
11	10	rabeqdv 3404	. . . . . 6 ⊢ (𝑤 = 𝑦 → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})
12	11	fveq2d 6844	. . . . 5 ⊢ (𝑤 = 𝑦 → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}))
13	9, 12	eqeq12d 2752	. . . 4 ⊢ (𝑤 = 𝑦 → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})))
14	13	ralbidv 3160	. . 3 ⊢ (𝑤 = 𝑦 → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})))
15		fveq2 6840	. . . . . 6 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (♯‘𝑤) = (♯‘(𝑦 ∪ {𝑧})))
16	15	oveq1d 7382	. . . . 5 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → ((♯‘𝑤)C𝑘) = ((♯‘(𝑦 ∪ {𝑧}))C𝑘))
17		pweq 4555	. . . . . . 7 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → 𝒫 𝑤 = 𝒫 (𝑦 ∪ {𝑧}))
18	17	rabeqdv 3404	. . . . . 6 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})
19	18	fveq2d 6844	. . . . 5 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘}))
20	16, 19	eqeq12d 2752	. . . 4 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
21	20	ralbidv 3160	. . 3 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
22		fveq2 6840	. . . . . 6 ⊢ (𝑤 = 𝐴 → (♯‘𝑤) = (♯‘𝐴))
23	22	oveq1d 7382	. . . . 5 ⊢ (𝑤 = 𝐴 → ((♯‘𝑤)C𝑘) = ((♯‘𝐴)C𝑘))
24		pweq 4555	. . . . . . 7 ⊢ (𝑤 = 𝐴 → 𝒫 𝑤 = 𝒫 𝐴)
25	24	rabeqdv 3404	. . . . . 6 ⊢ (𝑤 = 𝐴 → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})
26	25	fveq2d 6844	. . . . 5 ⊢ (𝑤 = 𝐴 → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}))
27	23, 26	eqeq12d 2752	. . . 4 ⊢ (𝑤 = 𝐴 → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})))
28	27	ralbidv 3160	. . 3 ⊢ (𝑤 = 𝐴 → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})))
29		hash0 14329	. . . . . . . . . 10 ⊢ (♯‘∅) = 0
30	29	a1i 11	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → (♯‘∅) = 0)
31		elfz1eq 13489	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → 𝑘 = 0)
32	30, 31	oveq12d 7385	. . . . . . . 8 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = (0C0))
33		0nn0 12452	. . . . . . . . 9 ⊢ 0 ∈ ℕ0
34		bcn0 14272	. . . . . . . . 9 ⊢ (0 ∈ ℕ0 → (0C0) = 1)
35	33, 34	ax-mp 5	. . . . . . . 8 ⊢ (0C0) = 1
36	32, 35	eqtrdi 2787	. . . . . . 7 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = 1)
37	31	eqcomd 2742	. . . . . . . . . . . 12 ⊢ (𝑘 ∈ (0...0) → 0 = 𝑘)
38		pw0 4755	. . . . . . . . . . . . . 14 ⊢ 𝒫 ∅ = {∅}
39	38	raleqi 3293	. . . . . . . . . . . . 13 ⊢ (∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘 ↔ ∀𝑥 ∈ {∅} (♯‘𝑥) = 𝑘)
40		0ex 5242	. . . . . . . . . . . . . 14 ⊢ ∅ ∈ V
41		fveq2 6840	. . . . . . . . . . . . . . . 16 ⊢ (𝑥 = ∅ → (♯‘𝑥) = (♯‘∅))
42	41, 29	eqtrdi 2787	. . . . . . . . . . . . . . 15 ⊢ (𝑥 = ∅ → (♯‘𝑥) = 0)
43	42	eqeq1d 2738	. . . . . . . . . . . . . 14 ⊢ (𝑥 = ∅ → ((♯‘𝑥) = 𝑘 ↔ 0 = 𝑘))
44	40, 43	ralsn 4625	. . . . . . . . . . . . 13 ⊢ (∀𝑥 ∈ {∅} (♯‘𝑥) = 𝑘 ↔ 0 = 𝑘)
45	39, 44	bitri 275	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘 ↔ 0 = 𝑘)
46	37, 45	sylibr 234	. . . . . . . . . . 11 ⊢ (𝑘 ∈ (0...0) → ∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘)
47		rabid2 3422	. . . . . . . . . . 11 ⊢ (𝒫 ∅ = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} ↔ ∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘)
48	46, 47	sylibr 234	. . . . . . . . . 10 ⊢ (𝑘 ∈ (0...0) → 𝒫 ∅ = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
49	48, 38	eqtr3di 2786	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = {∅})
50	49	fveq2d 6844	. . . . . . . 8 ⊢ (𝑘 ∈ (0...0) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = (♯‘{∅}))
51		hashsng 14331	. . . . . . . . 9 ⊢ (∅ ∈ V → (♯‘{∅}) = 1)
52	40, 51	ax-mp 5	. . . . . . . 8 ⊢ (♯‘{∅}) = 1
53	50, 52	eqtrdi 2787	. . . . . . 7 ⊢ (𝑘 ∈ (0...0) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = 1)
54	36, 53	eqtr4d 2774	. . . . . 6 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
55	54	adantl 481	. . . . 5 ⊢ ((𝑘 ∈ ℤ ∧ 𝑘 ∈ (0...0)) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
56	29	oveq1i 7377	. . . . . 6 ⊢ ((♯‘∅)C𝑘) = (0C𝑘)
57		bcval3 14268	. . . . . . . 8 ⊢ ((0 ∈ ℕ0 ∧ 𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = 0)
58	33, 57	mp3an1 1451	. . . . . . 7 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = 0)
59		id 22	. . . . . . . . . . . . . 14 ⊢ (0 = 𝑘 → 0 = 𝑘)
60		0z 12535	. . . . . . . . . . . . . . 15 ⊢ 0 ∈ ℤ
61		elfz3 13488	. . . . . . . . . . . . . . 15 ⊢ (0 ∈ ℤ → 0 ∈ (0...0))
62	60, 61	ax-mp 5	. . . . . . . . . . . . . 14 ⊢ 0 ∈ (0...0)
63	59, 62	eqeltrrdi 2845	. . . . . . . . . . . . 13 ⊢ (0 = 𝑘 → 𝑘 ∈ (0...0))
64	63	con3i 154	. . . . . . . . . . . 12 ⊢ (¬ 𝑘 ∈ (0...0) → ¬ 0 = 𝑘)
65	64	adantl 481	. . . . . . . . . . 11 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ¬ 0 = 𝑘)
66	38	raleqi 3293	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘 ↔ ∀𝑥 ∈ {∅} ¬ (♯‘𝑥) = 𝑘)
67	43	notbid 318	. . . . . . . . . . . . 13 ⊢ (𝑥 = ∅ → (¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘))
68	40, 67	ralsn 4625	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ {∅} ¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘)
69	66, 68	bitri 275	. . . . . . . . . . 11 ⊢ (∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘)
70	65, 69	sylibr 234	. . . . . . . . . 10 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘)
71		rabeq0 4328	. . . . . . . . . 10 ⊢ ({𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = ∅ ↔ ∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘)
72	70, 71	sylibr 234	. . . . . . . . 9 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = ∅)
73	72	fveq2d 6844	. . . . . . . 8 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = (♯‘∅))
74	73, 29	eqtrdi 2787	. . . . . . 7 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = 0)
75	58, 74	eqtr4d 2774	. . . . . 6 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
76	56, 75	eqtrid 2783	. . . . 5 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
77	55, 76	pm2.61dan 813	. . . 4 ⊢ (𝑘 ∈ ℤ → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
78	77	rgen 3053	. . 3 ⊢ ∀𝑘 ∈ ℤ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
79		oveq2 7375	. . . . . 6 ⊢ (𝑘 = 𝑗 → ((♯‘𝑦)C𝑘) = ((♯‘𝑦)C𝑗))
80		eqeq2 2748	. . . . . . . . 9 ⊢ (𝑘 = 𝑗 → ((♯‘𝑥) = 𝑘 ↔ (♯‘𝑥) = 𝑗))
81	80	rabbidv 3396	. . . . . . . 8 ⊢ (𝑘 = 𝑗 → {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗})
82		fveqeq2 6849	. . . . . . . . 9 ⊢ (𝑥 = 𝑧 → ((♯‘𝑥) = 𝑗 ↔ (♯‘𝑧) = 𝑗))
83	82	cbvrabv 3399	. . . . . . . 8 ⊢ {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗} = {𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}
84	81, 83	eqtrdi 2787	. . . . . . 7 ⊢ (𝑘 = 𝑗 → {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘} = {𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})
85	84	fveq2d 6844	. . . . . 6 ⊢ (𝑘 = 𝑗 → (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
86	79, 85	eqeq12d 2752	. . . . 5 ⊢ (𝑘 = 𝑗 → (((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})))
87	86	cbvralvw 3215	. . . 4 ⊢ (∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
88		simpll 767	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → 𝑦 ∈ Fin)
89		simplr 769	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ¬ 𝑧 ∈ 𝑦)
90		simprr 773	. . . . . . . 8 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
91	83	fveq2i 6843	. . . . . . . . . 10 ⊢ (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})
92	91	eqeq2i 2749	. . . . . . . . 9 ⊢ (((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) ↔ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
93	92	ralbii 3083	. . . . . . . 8 ⊢ (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) ↔ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
94	90, 93	sylibr 234	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}))
95		simprl 771	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → 𝑘 ∈ ℤ)
96	88, 89, 94, 95	hashbclem 14414	. . . . . 6 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘}))
97	96	expr 456	. . . . 5 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ 𝑘 ∈ ℤ) → (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}) → ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
98	97	ralrimdva 3137	. . . 4 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}) → ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
99	87, 98	biimtrid 242	. . 3 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) → ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
100	7, 14, 21, 28, 78, 99	findcard2s 9100	. 2 ⊢ (𝐴 ∈ Fin → ∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}))
101		oveq2 7375	. . . 4 ⊢ (𝑘 = 𝐾 → ((♯‘𝐴)C𝑘) = ((♯‘𝐴)C𝐾))
102		eqeq2 2748	. . . . . 6 ⊢ (𝑘 = 𝐾 → ((♯‘𝑥) = 𝑘 ↔ (♯‘𝑥) = 𝐾))
103	102	rabbidv 3396	. . . . 5 ⊢ (𝑘 = 𝐾 → {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾})
104	103	fveq2d 6844	. . . 4 ⊢ (𝑘 = 𝐾 → (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))
105	101, 104	eqeq12d 2752	. . 3 ⊢ (𝑘 = 𝐾 → (((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾})))
106	105	rspccva 3563	. 2 ⊢ ((∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) ∧ 𝐾 ∈ ℤ) → ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))
107	100, 106	sylan 581	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐾 ∈ ℤ) → ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 395   = wceq 1542   ∈ wcel 2114  ∀wral 3051  {crab 3389  Vcvv 3429   ∪ cun 3887  ∅c0 4273  𝒫 cpw 4541  {csn 4567  ‘cfv 6498  (class class class)co 7367  Fincfn 8893  0cc0 11038  1c1 11039  ℕ₀cn0 12437  ℤcz 12524  ...cfz 13461  Ccbc 14264  ♯chash 14292

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1912  ax-6 1969  ax-7 2010  ax-8 2116  ax-9 2124  ax-10 2147  ax-11 2163  ax-12 2185  ax-ext 2708  ax-sep 5231  ax-nul 5241  ax-pow 5307  ax-pr 5375  ax-un 7689  ax-cnex 11094  ax-resscn 11095  ax-1cn 11096  ax-icn 11097  ax-addcl 11098  ax-addrcl 11099  ax-mulcl 11100  ax-mulrcl 11101  ax-mulcom 11102  ax-addass 11103  ax-mulass 11104  ax-distr 11105  ax-i2m1 11106  ax-1ne0 11107  ax-1rid 11108  ax-rnegex 11109  ax-rrecex 11110  ax-cnre 11111  ax-pre-lttri 11112  ax-pre-lttrn 11113  ax-pre-ltadd 11114  ax-pre-mulgt0 11115

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3or 1088  df-3an 1089  df-tru 1545  df-fal 1555  df-ex 1782  df-nf 1786  df-sb 2069  df-mo 2539  df-eu 2569  df-clab 2715  df-cleq 2728  df-clel 2811  df-nfc 2885  df-ne 2933  df-nel 3037  df-ral 3052  df-rex 3062  df-rmo 3342  df-reu 3343  df-rab 3390  df-v 3431  df-sbc 3729  df-csb 3838  df-dif 3892  df-un 3894  df-in 3896  df-ss 3906  df-pss 3909  df-nul 4274  df-if 4467  df-pw 4543  df-sn 4568  df-pr 4570  df-op 4574  df-uni 4851  df-int 4890  df-iun 4935  df-br 5086  df-opab 5148  df-mpt 5167  df-tr 5193  df-id 5526  df-eprel 5531  df-po 5539  df-so 5540  df-fr 5584  df-we 5586  df-xp 5637  df-rel 5638  df-cnv 5639  df-co 5640  df-dm 5641  df-rn 5642  df-res 5643  df-ima 5644  df-pred 6265  df-ord 6326  df-on 6327  df-lim 6328  df-suc 6329  df-iota 6454  df-fun 6500  df-fn 6501  df-f 6502  df-f1 6503  df-fo 6504  df-f1o 6505  df-fv 6506  df-riota 7324  df-ov 7370  df-oprab 7371  df-mpo 7372  df-om 7818  df-1st 7942  df-2nd 7943  df-frecs 8231  df-wrecs 8262  df-recs 8311  df-rdg 8349  df-1o 8405  df-oadd 8409  df-er 8643  df-en 8894  df-dom 8895  df-sdom 8896  df-fin 8897  df-dju 9825  df-card 9863  df-pnf 11181  df-mnf 11182  df-xr 11183  df-ltxr 11184  df-le 11185  df-sub 11379  df-neg 11380  df-div 11808  df-nn 12175  df-n0 12438  df-z 12525  df-uz 12789  df-rp 12943  df-fz 13462  df-seq 13964  df-fac 14236  df-bc 14265  df-hash 14293

This theorem is referenced by:  hashbc2  16977  sylow1lem1  19573  musum  27154  esplympl  33711  ballotlem1  34631  ballotlem2  34633  sticksstones5  42589