hashbc - Metamath Proof Explorer

	Metamath Proof Explorer		< Previous Next > Nearby theorems
Mirrors > Home > MPE Home > Th. List > hashbc		Structured version Visualization version GIF version

Theorem hashbc 14453

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 6896	. . . . . 6 ⊢ (𝑤 = ∅ → (♯‘𝑤) = (♯‘∅))
2	1	oveq1d 7434	. . . . 5 ⊢ (𝑤 = ∅ → ((♯‘𝑤)C𝑘) = ((♯‘∅)C𝑘))
3		pweq 4618	. . . . . . 7 ⊢ (𝑤 = ∅ → 𝒫 𝑤 = 𝒫 ∅)
4	3	rabeqdv 3434	. . . . . 6 ⊢ (𝑤 = ∅ → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
5	4	fveq2d 6900	. . . . 5 ⊢ (𝑤 = ∅ → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
6	2, 5	eqeq12d 2741	. . . 4 ⊢ (𝑤 = ∅ → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})))
7	6	ralbidv 3167	. . 3 ⊢ (𝑤 = ∅ → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})))
8		fveq2 6896	. . . . . 6 ⊢ (𝑤 = 𝑦 → (♯‘𝑤) = (♯‘𝑦))
9	8	oveq1d 7434	. . . . 5 ⊢ (𝑤 = 𝑦 → ((♯‘𝑤)C𝑘) = ((♯‘𝑦)C𝑘))
10		pweq 4618	. . . . . . 7 ⊢ (𝑤 = 𝑦 → 𝒫 𝑤 = 𝒫 𝑦)
11	10	rabeqdv 3434	. . . . . 6 ⊢ (𝑤 = 𝑦 → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})
12	11	fveq2d 6900	. . . . 5 ⊢ (𝑤 = 𝑦 → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}))
13	9, 12	eqeq12d 2741	. . . 4 ⊢ (𝑤 = 𝑦 → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})))
14	13	ralbidv 3167	. . 3 ⊢ (𝑤 = 𝑦 → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘})))
15		fveq2 6896	. . . . . 6 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (♯‘𝑤) = (♯‘(𝑦 ∪ {𝑧})))
16	15	oveq1d 7434	. . . . 5 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → ((♯‘𝑤)C𝑘) = ((♯‘(𝑦 ∪ {𝑧}))C𝑘))
17		pweq 4618	. . . . . . 7 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → 𝒫 𝑤 = 𝒫 (𝑦 ∪ {𝑧}))
18	17	rabeqdv 3434	. . . . . 6 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})
19	18	fveq2d 6900	. . . . 5 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘}))
20	16, 19	eqeq12d 2741	. . . 4 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
21	20	ralbidv 3167	. . 3 ⊢ (𝑤 = (𝑦 ∪ {𝑧}) → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
22		fveq2 6896	. . . . . 6 ⊢ (𝑤 = 𝐴 → (♯‘𝑤) = (♯‘𝐴))
23	22	oveq1d 7434	. . . . 5 ⊢ (𝑤 = 𝐴 → ((♯‘𝑤)C𝑘) = ((♯‘𝐴)C𝑘))
24		pweq 4618	. . . . . . 7 ⊢ (𝑤 = 𝐴 → 𝒫 𝑤 = 𝒫 𝐴)
25	24	rabeqdv 3434	. . . . . 6 ⊢ (𝑤 = 𝐴 → {𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})
26	25	fveq2d 6900	. . . . 5 ⊢ (𝑤 = 𝐴 → (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}))
27	23, 26	eqeq12d 2741	. . . 4 ⊢ (𝑤 = 𝐴 → (((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})))
28	27	ralbidv 3167	. . 3 ⊢ (𝑤 = 𝐴 → (∀𝑘 ∈ ℤ ((♯‘𝑤)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑤 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘})))
29		hash0 14367	. . . . . . . . . 10 ⊢ (♯‘∅) = 0
30	29	a1i 11	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → (♯‘∅) = 0)
31		elfz1eq 13552	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → 𝑘 = 0)
32	30, 31	oveq12d 7437	. . . . . . . 8 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = (0C0))
33		0nn0 12525	. . . . . . . . 9 ⊢ 0 ∈ ℕ₀
34		bcn0 14310	. . . . . . . . 9 ⊢ (0 ∈ ℕ₀ → (0C0) = 1)
35	33, 34	ax-mp 5	. . . . . . . 8 ⊢ (0C0) = 1
36	32, 35	eqtrdi 2781	. . . . . . 7 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = 1)
37	31	eqcomd 2731	. . . . . . . . . . . 12 ⊢ (𝑘 ∈ (0...0) → 0 = 𝑘)
38		pw0 4817	. . . . . . . . . . . . . 14 ⊢ 𝒫 ∅ = {∅}
39	38	raleqi 3312	. . . . . . . . . . . . 13 ⊢ (∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘 ↔ ∀𝑥 ∈ {∅} (♯‘𝑥) = 𝑘)
40		0ex 5308	. . . . . . . . . . . . . 14 ⊢ ∅ ∈ V
41		fveq2 6896	. . . . . . . . . . . . . . . 16 ⊢ (𝑥 = ∅ → (♯‘𝑥) = (♯‘∅))
42	41, 29	eqtrdi 2781	. . . . . . . . . . . . . . 15 ⊢ (𝑥 = ∅ → (♯‘𝑥) = 0)
43	42	eqeq1d 2727	. . . . . . . . . . . . . 14 ⊢ (𝑥 = ∅ → ((♯‘𝑥) = 𝑘 ↔ 0 = 𝑘))
44	40, 43	ralsn 4687	. . . . . . . . . . . . 13 ⊢ (∀𝑥 ∈ {∅} (♯‘𝑥) = 𝑘 ↔ 0 = 𝑘)
45	39, 44	bitri 274	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘 ↔ 0 = 𝑘)
46	37, 45	sylibr 233	. . . . . . . . . . 11 ⊢ (𝑘 ∈ (0...0) → ∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘)
47		rabid2 3452	. . . . . . . . . . 11 ⊢ (𝒫 ∅ = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} ↔ ∀𝑥 ∈ 𝒫 ∅(♯‘𝑥) = 𝑘)
48	46, 47	sylibr 233	. . . . . . . . . 10 ⊢ (𝑘 ∈ (0...0) → 𝒫 ∅ = {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
49	48, 38	eqtr3di 2780	. . . . . . . . 9 ⊢ (𝑘 ∈ (0...0) → {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = {∅})
50	49	fveq2d 6900	. . . . . . . 8 ⊢ (𝑘 ∈ (0...0) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = (♯‘{∅}))
51		hashsng 14369	. . . . . . . . 9 ⊢ (∅ ∈ V → (♯‘{∅}) = 1)
52	40, 51	ax-mp 5	. . . . . . . 8 ⊢ (♯‘{∅}) = 1
53	50, 52	eqtrdi 2781	. . . . . . 7 ⊢ (𝑘 ∈ (0...0) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = 1)
54	36, 53	eqtr4d 2768	. . . . . 6 ⊢ (𝑘 ∈ (0...0) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
55	54	adantl 480	. . . . 5 ⊢ ((𝑘 ∈ ℤ ∧ 𝑘 ∈ (0...0)) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
56	29	oveq1i 7429	. . . . . 6 ⊢ ((♯‘∅)C𝑘) = (0C𝑘)
57		bcval3 14306	. . . . . . . 8 ⊢ ((0 ∈ ℕ₀ ∧ 𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = 0)
58	33, 57	mp3an1 1444	. . . . . . 7 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = 0)
59		id 22	. . . . . . . . . . . . . 14 ⊢ (0 = 𝑘 → 0 = 𝑘)
60		0z 12607	. . . . . . . . . . . . . . 15 ⊢ 0 ∈ ℤ
61		elfz3 13551	. . . . . . . . . . . . . . 15 ⊢ (0 ∈ ℤ → 0 ∈ (0...0))
62	60, 61	ax-mp 5	. . . . . . . . . . . . . 14 ⊢ 0 ∈ (0...0)
63	59, 62	eqeltrrdi 2834	. . . . . . . . . . . . 13 ⊢ (0 = 𝑘 → 𝑘 ∈ (0...0))
64	63	con3i 154	. . . . . . . . . . . 12 ⊢ (¬ 𝑘 ∈ (0...0) → ¬ 0 = 𝑘)
65	64	adantl 480	. . . . . . . . . . 11 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ¬ 0 = 𝑘)
66	38	raleqi 3312	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘 ↔ ∀𝑥 ∈ {∅} ¬ (♯‘𝑥) = 𝑘)
67	43	notbid 317	. . . . . . . . . . . . 13 ⊢ (𝑥 = ∅ → (¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘))
68	40, 67	ralsn 4687	. . . . . . . . . . . 12 ⊢ (∀𝑥 ∈ {∅} ¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘)
69	66, 68	bitri 274	. . . . . . . . . . 11 ⊢ (∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘 ↔ ¬ 0 = 𝑘)
70	65, 69	sylibr 233	. . . . . . . . . 10 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘)
71		rabeq0 4386	. . . . . . . . . 10 ⊢ ({𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = ∅ ↔ ∀𝑥 ∈ 𝒫 ∅ ¬ (♯‘𝑥) = 𝑘)
72	70, 71	sylibr 233	. . . . . . . . 9 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → {𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘} = ∅)
73	72	fveq2d 6900	. . . . . . . 8 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = (♯‘∅))
74	73, 29	eqtrdi 2781	. . . . . . 7 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}) = 0)
75	58, 74	eqtr4d 2768	. . . . . 6 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → (0C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
76	56, 75	eqtrid 2777	. . . . 5 ⊢ ((𝑘 ∈ ℤ ∧ ¬ 𝑘 ∈ (0...0)) → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
77	55, 76	pm2.61dan 811	. . . 4 ⊢ (𝑘 ∈ ℤ → ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘}))
78	77	rgen 3052	. . 3 ⊢ ∀𝑘 ∈ ℤ ((♯‘∅)C𝑘) = (♯‘{𝑥 ∈ 𝒫 ∅ ∣ (♯‘𝑥) = 𝑘})
79		oveq2 7427	. . . . . 6 ⊢ (𝑘 = 𝑗 → ((♯‘𝑦)C𝑘) = ((♯‘𝑦)C𝑗))
80		eqeq2 2737	. . . . . . . . 9 ⊢ (𝑘 = 𝑗 → ((♯‘𝑥) = 𝑘 ↔ (♯‘𝑥) = 𝑗))
81	80	rabbidv 3426	. . . . . . . 8 ⊢ (𝑘 = 𝑗 → {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗})
82		fveqeq2 6905	. . . . . . . . 9 ⊢ (𝑥 = 𝑧 → ((♯‘𝑥) = 𝑗 ↔ (♯‘𝑧) = 𝑗))
83	82	cbvrabv 3429	. . . . . . . 8 ⊢ {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗} = {𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}
84	81, 83	eqtrdi 2781	. . . . . . 7 ⊢ (𝑘 = 𝑗 → {𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘} = {𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})
85	84	fveq2d 6900	. . . . . 6 ⊢ (𝑘 = 𝑗 → (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
86	79, 85	eqeq12d 2741	. . . . 5 ⊢ (𝑘 = 𝑗 → (((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})))
87	86	cbvralvw 3224	. . . 4 ⊢ (∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) ↔ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
88		simpll 765	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → 𝑦 ∈ Fin)
89		simplr 767	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ¬ 𝑧 ∈ 𝑦)
90		simprr 771	. . . . . . . 8 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
91	83	fveq2i 6899	. . . . . . . . . 10 ⊢ (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗})
92	91	eqeq2i 2738	. . . . . . . . 9 ⊢ (((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) ↔ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
93	92	ralbii 3082	. . . . . . . 8 ⊢ (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}) ↔ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))
94	90, 93	sylibr 233	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑗}))
95		simprl 769	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → 𝑘 ∈ ℤ)
96	88, 89, 94, 95	hashbclem 14452	. . . . . 6 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝑘 ∈ ℤ ∧ ∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}))) → ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘}))
97	96	expr 455	. . . . 5 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ 𝑘 ∈ ℤ) → (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}) → ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
98	97	ralrimdva 3143	. . . 4 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (∀𝑗 ∈ ℤ ((♯‘𝑦)C𝑗) = (♯‘{𝑧 ∈ 𝒫 𝑦 ∣ (♯‘𝑧) = 𝑗}) → ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
99	87, 98	biimtrid 241	. . 3 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (∀𝑘 ∈ ℤ ((♯‘𝑦)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝑦 ∣ (♯‘𝑥) = 𝑘}) → ∀𝑘 ∈ ℤ ((♯‘(𝑦 ∪ {𝑧}))C𝑘) = (♯‘{𝑥 ∈ 𝒫 (𝑦 ∪ {𝑧}) ∣ (♯‘𝑥) = 𝑘})))
100	7, 14, 21, 28, 78, 99	findcard2s 9193	. 2 ⊢ (𝐴 ∈ Fin → ∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}))
101		oveq2 7427	. . . 4 ⊢ (𝑘 = 𝐾 → ((♯‘𝐴)C𝑘) = ((♯‘𝐴)C𝐾))
102		eqeq2 2737	. . . . . 6 ⊢ (𝑘 = 𝐾 → ((♯‘𝑥) = 𝑘 ↔ (♯‘𝑥) = 𝐾))
103	102	rabbidv 3426	. . . . 5 ⊢ (𝑘 = 𝐾 → {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘} = {𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾})
104	103	fveq2d 6900	. . . 4 ⊢ (𝑘 = 𝐾 → (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))
105	101, 104	eqeq12d 2741	. . 3 ⊢ (𝑘 = 𝐾 → (((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) ↔ ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾})))
106	105	rspccva 3605	. 2 ⊢ ((∀𝑘 ∈ ℤ ((♯‘𝐴)C𝑘) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝑘}) ∧ 𝐾 ∈ ℤ) → ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))
107	100, 106	sylan 578	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐾 ∈ ℤ) → ((♯‘𝐴)C𝐾) = (♯‘{𝑥 ∈ 𝒫 𝐴 ∣ (♯‘𝑥) = 𝐾}))

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 → wi 4 ∧ wa 394 = wceq 1533 ∈ wcel 2098 ∀wral 3050 {crab 3418 Vcvv 3461 ∪ cun 3942 ∅c0 4322 𝒫 cpw 4604 {csn 4630 ‘cfv 6549 (class class class)co 7419 Fincfn 8964 0cc0 11145 1c1 11146 ℕ₀cn0 12510 ℤcz 12596 ...cfz 13524 Ccbc 14302 ♯chash 14330

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1789 ax-4 1803 ax-5 1905 ax-6 1963 ax-7 2003 ax-8 2100 ax-9 2108 ax-10 2129 ax-11 2146 ax-12 2166 ax-ext 2696 ax-sep 5300 ax-nul 5307 ax-pow 5365 ax-pr 5429 ax-un 7741 ax-cnex 11201 ax-resscn 11202 ax-1cn 11203 ax-icn 11204 ax-addcl 11205 ax-addrcl 11206 ax-mulcl 11207 ax-mulrcl 11208 ax-mulcom 11209 ax-addass 11210 ax-mulass 11211 ax-distr 11212 ax-i2m1 11213 ax-1ne0 11214 ax-1rid 11215 ax-rnegex 11216 ax-rrecex 11217 ax-cnre 11218 ax-pre-lttri 11219 ax-pre-lttrn 11220 ax-pre-ltadd 11221 ax-pre-mulgt0 11222

This theorem depends on definitions: df-bi 206 df-an 395 df-or 846 df-3or 1085 df-3an 1086 df-tru 1536 df-fal 1546 df-ex 1774 df-nf 1778 df-sb 2060 df-mo 2528 df-eu 2557 df-clab 2703 df-cleq 2717 df-clel 2802 df-nfc 2877 df-ne 2930 df-nel 3036 df-ral 3051 df-rex 3060 df-rmo 3363 df-reu 3364 df-rab 3419 df-v 3463 df-sbc 3774 df-csb 3890 df-dif 3947 df-un 3949 df-in 3951 df-ss 3961 df-pss 3964 df-nul 4323 df-if 4531 df-pw 4606 df-sn 4631 df-pr 4633 df-op 4637 df-uni 4910 df-int 4951 df-iun 4999 df-br 5150 df-opab 5212 df-mpt 5233 df-tr 5267 df-id 5576 df-eprel 5582 df-po 5590 df-so 5591 df-fr 5633 df-we 5635 df-xp 5684 df-rel 5685 df-cnv 5686 df-co 5687 df-dm 5688 df-rn 5689 df-res 5690 df-ima 5691 df-pred 6307 df-ord 6374 df-on 6375 df-lim 6376 df-suc 6377 df-iota 6501 df-fun 6551 df-fn 6552 df-f 6553 df-f1 6554 df-fo 6555 df-f1o 6556 df-fv 6557 df-riota 7375 df-ov 7422 df-oprab 7423 df-mpo 7424 df-om 7872 df-1st 7994 df-2nd 7995 df-frecs 8287 df-wrecs 8318 df-recs 8392 df-rdg 8431 df-1o 8487 df-oadd 8491 df-er 8725 df-en 8965 df-dom 8966 df-sdom 8967 df-fin 8968 df-dju 9931 df-card 9969 df-pnf 11287 df-mnf 11288 df-xr 11289 df-ltxr 11290 df-le 11291 df-sub 11483 df-neg 11484 df-div 11909 df-nn 12251 df-n0 12511 df-z 12597 df-uz 12861 df-rp 13015 df-fz 13525 df-seq 14008 df-fac 14274 df-bc 14303 df-hash 14331

This theorem is referenced by: hashbc2 16983 sylow1lem1 19570 musum 27173 ballotlem1 34239 ballotlem2 34241 sticksstones5 41755

W3C validator