Theorem hashbc 14412

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 6892	. . . . . 6 ⊢ (𝑤 = ∅ → (♯‘𝑤) = (♯‘∅))
2	1	oveq1d 7424	. . . . 5 ⊢ (𝑤 = ∅ → ((♯‘𝑤)C𝑘) = ((♯‘∅)C𝑘))
3		pweq 4617	. . . . . . 7 ⊢ (𝑤 = ∅ → 𝒫 𝑤 = 𝒫 ∅)
4	3	rabeqdv 3448	. . . . . 6 ⊢ (𝑤 = ∅ → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
5	4	fveq2d 6896	. . . . 5 ⊢ (𝑤 = ∅ → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
6	2, 5	eqeq12d 2749	. . . 4 ⊢ (𝑤 = ∅ → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})))
7	6	ralbidv 3178	. . 3 ⊢ (𝑤 = ∅ → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})))
8		fveq2 6892	. . . . . 6 ⊢ (𝑤 = 𝑦 → (♯‘𝑤) = (♯‘𝑦))
9	8	oveq1d 7424	. . . . 5 ⊢ (𝑤 = 𝑦 → ((♯‘𝑤)C𝑘) = ((♯‘𝑦)C𝑘))
10		pweq 4617	. . . . . . 7 ⊢ (𝑤 = 𝑦 → 𝒫 𝑤 = 𝒫 𝑦)
11	10	rabeqdv 3448	. . . . . 6 ⊢ (𝑤 = 𝑦 → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})
12	11	fveq2d 6896	. . . . 5 ⊢ (𝑤 = 𝑦 → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}))
13	9, 12	eqeq12d 2749	. . . 4 ⊢ (𝑤 = 𝑦 → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})))
14	13	ralbidv 3178	. . 3 ⊢ (𝑤 = 𝑦 → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})))
15		fveq2 6892	. . . . . 6 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (♯‘𝑤) = (♯‘(𝑦 ∪ {𝑧})))
16	15	oveq1d 7424	. . . . 5 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → ((♯‘𝑤)C𝑘) = ((♯‘(𝑦 ∪ {𝑧}))C𝑘))
17		pweq 4617	. . . . . . 7 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → 𝒫 𝑤 = 𝒫 (𝑦 ∪ {𝑧}))
18	17	rabeqdv 3448	. . . . . 6 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})
19	18	fveq2d 6896	. . . . 5 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘}))
20	16, 19	eqeq12d 2749	. . . 4 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
21	20	ralbidv 3178	. . 3 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
22		fveq2 6892	. . . . . 6 ⊢ (𝑤 = 𝐴 → (♯‘𝑤) = (♯‘𝐴))
23	22	oveq1d 7424	. . . . 5 ⊢ (𝑤 = 𝐴 → ((♯‘𝑤)C𝑘) = ((♯‘𝐴)C𝑘))
24		pweq 4617	. . . . . . 7 ⊢ (𝑤 = 𝐴 → 𝒫 𝑤 = 𝒫 𝐴)
25	24	rabeqdv 3448	. . . . . 6 ⊢ (𝑤 = 𝐴 → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})
26	25	fveq2d 6896	. . . . 5 ⊢ (𝑤 = 𝐴 → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}))
27	23, 26	eqeq12d 2749	. . . 4 ⊢ (𝑤 = 𝐴 → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})))
28	27	ralbidv 3178	. . 3 ⊢ (𝑤 = 𝐴 → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})))
29		hash0 14327	. . . . . . . . . 10 ⊢ (♯‘∅) = 0
30	29	a1i 11	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → (♯‘∅) = 0)
31		elfz1eq 13512	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → 𝑘 = 0)
32	30, 31	oveq12d 7427	. . . . . . . 8 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = (0C0))
33		0nn0 12487	. . . . . . . . 9 ⊢ 0 ∈ ℕ0
34		bcn0 14270	. . . . . . . . 9 ⊢ (0 ∈ ℕ0 → (0C0) = 1)
35	33, 34	ax-mp 5	. . . . . . . 8 ⊢ (0C0) = 1
36	32, 35	eqtrdi 2789	. . . . . . 7 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = 1)
37	31	eqcomd 2739	. . . . . . . . . . . 12 ⊢ (𝑘 ∈ (0...0) → 0 = 𝑘)
38		pw0 4816	. . . . . . . . . . . . . 14 ⊢ 𝒫 ∅ = {∅}
39	38	raleqi 3324	. . . . . . . . . . . . 13 ⊢ (∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘 ↔ ∀𝑥 ∈ {∅} (♯‘𝑥) = 𝑘)
40		0ex 5308	. . . . . . . . . . . . . 14 ⊢ ∅ ∈ V
41		fveq2 6892	. . . . . . . . . . . . . . . 16 ⊢ (𝑥 = ∅ → (♯‘𝑥) = (♯‘∅))
42	41, 29	eqtrdi 2789	. . . . . . . . . . . . . . 15 ⊢ (𝑥 = ∅ → (♯‘𝑥) = 0)
43	42	eqeq1d 2735	. . . . . . . . . . . . . 14 ⊢ (𝑥 = ∅ → ((♯‘𝑥) = 𝑘 ↔ 0 = 𝑘))
44	40, 43	ralsn 4686	. . . . . . . . . . . . 13 ⊢ (∀𝑥 ∈ {∅} (♯‘𝑥) = 𝑘 ↔ 0 = 𝑘)
45	39, 44	bitri 275	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘 ↔ 0 = 𝑘)
46	37, 45	sylibr 233	. . . . . . . . . . 11 ⊢ (𝑘 ∈ (0...0) → ∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘)
47		rabid2 3465	. . . . . . . . . . 11 ⊢ (𝒫 ∅ = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} ↔ ∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘)
48	46, 47	sylibr 233	. . . . . . . . . 10 ⊢ (𝑘 ∈ (0...0) → 𝒫 ∅ = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
49	48, 38	eqtr3di 2788	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = {∅})
50	49	fveq2d 6896	. . . . . . . 8 ⊢ (𝑘 ∈ (0...0) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = (♯‘{∅}))
51		hashsng 14329	. . . . . . . . 9 ⊢ (∅ ∈ V → (♯‘{∅}) = 1)
52	40, 51	ax-mp 5	. . . . . . . 8 ⊢ (♯‘{∅}) = 1
53	50, 52	eqtrdi 2789	. . . . . . 7 ⊢ (𝑘 ∈ (0...0) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = 1)
54	36, 53	eqtr4d 2776	. . . . . 6 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
55	54	adantl 483	. . . . 5 ⊢ ((𝑘 ∈ ℤ ∧ 𝑘 ∈ (0...0)) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
56	29	oveq1i 7419	. . . . . 6 ⊢ ((♯‘∅)C𝑘) = (0C𝑘)
57		bcval3 14266	. . . . . . . 8 ⊢ ((0 ∈ ℕ0 ∧ 𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = 0)
58	33, 57	mp3an1 1449	. . . . . . 7 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = 0)
59		id 22	. . . . . . . . . . . . . 14 ⊢ (0 = 𝑘 → 0 = 𝑘)
60		0z 12569	. . . . . . . . . . . . . . 15 ⊢ 0 ∈ ℤ
61		elfz3 13511	. . . . . . . . . . . . . . 15 ⊢ (0 ∈ ℤ → 0 ∈ (0...0))
62	60, 61	ax-mp 5	. . . . . . . . . . . . . 14 ⊢ 0 ∈ (0...0)
63	59, 62	eqeltrrdi 2843	. . . . . . . . . . . . 13 ⊢ (0 = 𝑘 → 𝑘 ∈ (0...0))
64	63	con3i 154	. . . . . . . . . . . 12 ⊢ (¬ 𝑘 ∈ (0...0) → ¬ 0 = 𝑘)
65	64	adantl 483	. . . . . . . . . . 11 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ¬ 0 = 𝑘)
66	38	raleqi 3324	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘 ↔ ∀𝑥 ∈ {∅} ¬ (♯‘𝑥) = 𝑘)
67	43	notbid 318	. . . . . . . . . . . . 13 ⊢ (𝑥 = ∅ → (¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘))
68	40, 67	ralsn 4686	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ {∅} ¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘)
69	66, 68	bitri 275	. . . . . . . . . . 11 ⊢ (∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘)
70	65, 69	sylibr 233	. . . . . . . . . 10 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘)
71		rabeq0 4385	. . . . . . . . . 10 ⊢ ({𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = ∅ ↔ ∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘)
72	70, 71	sylibr 233	. . . . . . . . 9 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = ∅)
73	72	fveq2d 6896	. . . . . . . 8 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = (♯‘∅))
74	73, 29	eqtrdi 2789	. . . . . . 7 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = 0)
75	58, 74	eqtr4d 2776	. . . . . 6 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
76	56, 75	eqtrid 2785	. . . . 5 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
77	55, 76	pm2.61dan 812	. . . 4 ⊢ (𝑘 ∈ ℤ → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
78	77	rgen 3064	. . 3 ⊢ ∀𝑘 ∈ ℤ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
79		oveq2 7417	. . . . . 6 ⊢ (𝑘 = 𝑗 → ((♯‘𝑦)C𝑘) = ((♯‘𝑦)C𝑗))
80		eqeq2 2745	. . . . . . . . 9 ⊢ (𝑘 = 𝑗 → ((♯‘𝑥) = 𝑘 ↔ (♯‘𝑥) = 𝑗))
81	80	rabbidv 3441	. . . . . . . 8 ⊢ (𝑘 = 𝑗 → {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗})
82		fveqeq2 6901	. . . . . . . . 9 ⊢ (𝑥 = 𝑧 → ((♯‘𝑥) = 𝑗 ↔ (♯‘𝑧) = 𝑗))
83	82	cbvrabv 3443	. . . . . . . 8 ⊢ {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗} = {𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}
84	81, 83	eqtrdi 2789	. . . . . . 7 ⊢ (𝑘 = 𝑗 → {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘} = {𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})
85	84	fveq2d 6896	. . . . . 6 ⊢ (𝑘 = 𝑗 → (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
86	79, 85	eqeq12d 2749	. . . . 5 ⊢ (𝑘 = 𝑗 → (((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})))
87	86	cbvralvw 3235	. . . 4 ⊢ (∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
88		simpll 766	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → 𝑦 ∈ Fin)
89		simplr 768	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ¬ 𝑧 ∈ 𝑦)
90		simprr 772	. . . . . . . 8 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
91	83	fveq2i 6895	. . . . . . . . . 10 ⊢ (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})
92	91	eqeq2i 2746	. . . . . . . . 9 ⊢ (((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) ↔ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
93	92	ralbii 3094	. . . . . . . 8 ⊢ (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) ↔ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
94	90, 93	sylibr 233	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}))
95		simprl 770	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → 𝑘 ∈ ℤ)
96	88, 89, 94, 95	hashbclem 14411	. . . . . 6 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘}))
97	96	expr 458	. . . . 5 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ 𝑘 ∈ ℤ) → (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}) → ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
98	97	ralrimdva 3155	. . . 4 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}) → ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
99	87, 98	biimtrid 241	. . 3 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) → ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
100	7, 14, 21, 28, 78, 99	findcard2s 9165	. 2 ⊢ (𝐴 ∈ Fin → ∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}))
101		oveq2 7417	. . . 4 ⊢ (𝑘 = 𝐾 → ((♯‘𝐴)C𝑘) = ((♯‘𝐴)C𝐾))
102		eqeq2 2745	. . . . . 6 ⊢ (𝑘 = 𝐾 → ((♯‘𝑥) = 𝑘 ↔ (♯‘𝑥) = 𝐾))
103	102	rabbidv 3441	. . . . 5 ⊢ (𝑘 = 𝐾 → {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾})
104	103	fveq2d 6896	. . . 4 ⊢ (𝑘 = 𝐾 → (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))
105	101, 104	eqeq12d 2749	. . 3 ⊢ (𝑘 = 𝐾 → (((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾})))
106	105	rspccva 3612	. 2 ⊢ ((∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) ∧ 𝐾 ∈ ℤ) → ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))
107	100, 106	sylan 581	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐾 ∈ ℤ) → ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 397   = wceq 1542   ∈ wcel 2107  ∀wral 3062  {crab 3433  Vcvv 3475   ∪ cun 3947  ∅c0 4323  𝒫 cpw 4603  {csn 4629  ‘cfv 6544  (class class class)co 7409  Fincfn 8939  0cc0 11110  1c1 11111  ℕ₀cn0 12472  ℤcz 12558  ...cfz 13484  Ccbc 14262  ♯chash 14290

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  ax-5 1914  ax-6 1972  ax-7 2012  ax-8 2109  ax-9 2117  ax-10 2138  ax-11 2155  ax-12 2172  ax-ext 2704  ax-sep 5300  ax-nul 5307  ax-pow 5364  ax-pr 5428  ax-un 7725  ax-cnex 11166  ax-resscn 11167  ax-1cn 11168  ax-icn 11169  ax-addcl 11170  ax-addrcl 11171  ax-mulcl 11172  ax-mulrcl 11173  ax-mulcom 11174  ax-addass 11175  ax-mulass 11176  ax-distr 11177  ax-i2m1 11178  ax-1ne0 11179  ax-1rid 11180  ax-rnegex 11181  ax-rrecex 11182  ax-cnre 11183  ax-pre-lttri 11184  ax-pre-lttrn 11185  ax-pre-ltadd 11186  ax-pre-mulgt0 11187

This theorem depends on definitions:  df-bi 206  df-an 398  df-or 847  df-3or 1089  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1783  df-nf 1787  df-sb 2069  df-mo 2535  df-eu 2564  df-clab 2711  df-cleq 2725  df-clel 2811  df-nfc 2886  df-ne 2942  df-nel 3048  df-ral 3063  df-rex 3072  df-rmo 3377  df-reu 3378  df-rab 3434  df-v 3477  df-sbc 3779  df-csb 3895  df-dif 3952  df-un 3954  df-in 3956  df-ss 3966  df-pss 3968  df-nul 4324  df-if 4530  df-pw 4605  df-sn 4630  df-pr 4632  df-op 4636  df-uni 4910  df-int 4952  df-iun 5000  df-br 5150  df-opab 5212  df-mpt 5233  df-tr 5267  df-id 5575  df-eprel 5581  df-po 5589  df-so 5590  df-fr 5632  df-we 5634  df-xp 5683  df-rel 5684  df-cnv 5685  df-co 5686  df-dm 5687  df-rn 5688  df-res 5689  df-ima 5690  df-pred 6301  df-ord 6368  df-on 6369  df-lim 6370  df-suc 6371  df-iota 6496  df-fun 6546  df-fn 6547  df-f 6548  df-f1 6549  df-fo 6550  df-f1o 6551  df-fv 6552  df-riota 7365  df-ov 7412  df-oprab 7413  df-mpo 7414  df-om 7856  df-1st 7975  df-2nd 7976  df-frecs 8266  df-wrecs 8297  df-recs 8371  df-rdg 8410  df-1o 8466  df-oadd 8470  df-er 8703  df-en 8940  df-dom 8941  df-sdom 8942  df-fin 8943  df-dju 9896  df-card 9934  df-pnf 11250  df-mnf 11251  df-xr 11252  df-ltxr 11253  df-le 11254  df-sub 11446  df-neg 11447  df-div 11872  df-nn 12213  df-n0 12473  df-z 12559  df-uz 12823  df-rp 12975  df-fz 13485  df-seq 13967  df-fac 14234  df-bc 14263  df-hash 14291

This theorem is referenced by:  hashbc2  16939  sylow1lem1  19466  musum  26695  ballotlem1  33516  ballotlem2  33518  sticksstones5  41014