hashmap - Metamath Proof Explorer

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

Theorem hashmap 14360

Description: The size of the set exponential of two finite sets is the exponential of their sizes. (This is the original motivation behind the notation for set exponentiation.) (Contributed by Mario Carneiro, 5-Aug-2014.) (Proof shortened by AV, 18-Jul-2022.)

**Assertion**
Ref	Expression
hashmap	⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (♯‘(𝐴 ↑_m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵)))

Proof of Theorem hashmap Dummy variables 𝑥 𝑦 𝑧 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		oveq2 7361	. . . . . 6 ⊢ (𝑥 = ∅ → (𝐴 ↑_m 𝑥) = (𝐴 ↑_m ∅))
2	1	fveq2d 6830	. . . . 5 ⊢ (𝑥 = ∅ → (♯‘(𝐴 ↑_m 𝑥)) = (♯‘(𝐴 ↑_m ∅)))
3		fveq2 6826	. . . . . 6 ⊢ (𝑥 = ∅ → (♯‘𝑥) = (♯‘∅))
4	3	oveq2d 7369	. . . . 5 ⊢ (𝑥 = ∅ → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘∅)))
5	2, 4	eqeq12d 2745	. . . 4 ⊢ (𝑥 = ∅ → ((♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴 ↑_m ∅)) = ((♯‘𝐴)↑(♯‘∅))))
6	5	imbi2d 340	. . 3 ⊢ (𝑥 = ∅ → ((𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m ∅)) = ((♯‘𝐴)↑(♯‘∅)))))
7		oveq2 7361	. . . . . 6 ⊢ (𝑥 = 𝑦 → (𝐴 ↑_m 𝑥) = (𝐴 ↑_m 𝑦))
8	7	fveq2d 6830	. . . . 5 ⊢ (𝑥 = 𝑦 → (♯‘(𝐴 ↑_m 𝑥)) = (♯‘(𝐴 ↑_m 𝑦)))
9		fveq2 6826	. . . . . 6 ⊢ (𝑥 = 𝑦 → (♯‘𝑥) = (♯‘𝑦))
10	9	oveq2d 7369	. . . . 5 ⊢ (𝑥 = 𝑦 → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘𝑦)))
11	8, 10	eqeq12d 2745	. . . 4 ⊢ (𝑥 = 𝑦 → ((♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴 ↑_m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦))))
12	11	imbi2d 340	. . 3 ⊢ (𝑥 = 𝑦 → ((𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)))))
13		oveq2 7361	. . . . . 6 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → (𝐴 ↑_m 𝑥) = (𝐴 ↑_m (𝑦 ∪ {𝑧})))
14	13	fveq2d 6830	. . . . 5 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → (♯‘(𝐴 ↑_m 𝑥)) = (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))))
15		fveq2 6826	. . . . . 6 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → (♯‘𝑥) = (♯‘(𝑦 ∪ {𝑧})))
16	15	oveq2d 7369	. . . . 5 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))
17	14, 16	eqeq12d 2745	. . . 4 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → ((♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧})))))
18	17	imbi2d 340	. . 3 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))))
19		oveq2 7361	. . . . . 6 ⊢ (𝑥 = 𝐵 → (𝐴 ↑_m 𝑥) = (𝐴 ↑_m 𝐵))
20	19	fveq2d 6830	. . . . 5 ⊢ (𝑥 = 𝐵 → (♯‘(𝐴 ↑_m 𝑥)) = (♯‘(𝐴 ↑_m 𝐵)))
21		fveq2 6826	. . . . . 6 ⊢ (𝑥 = 𝐵 → (♯‘𝑥) = (♯‘𝐵))
22	21	oveq2d 7369	. . . . 5 ⊢ (𝑥 = 𝐵 → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘𝐵)))
23	20, 22	eqeq12d 2745	. . . 4 ⊢ (𝑥 = 𝐵 → ((♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴 ↑_m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵))))
24	23	imbi2d 340	. . 3 ⊢ (𝑥 = 𝐵 → ((𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵)))))
25		hashcl 14281	. . . . . 6 ⊢ (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℕ₀)
26	25	nn0cnd 12465	. . . . 5 ⊢ (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℂ)
27	26	exp0d 14065	. . . 4 ⊢ (𝐴 ∈ Fin → ((♯‘𝐴)↑0) = 1)
28		hash0 14292	. . . . . 6 ⊢ (♯‘∅) = 0
29	28	oveq2i 7364	. . . . 5 ⊢ ((♯‘𝐴)↑(♯‘∅)) = ((♯‘𝐴)↑0)
30	29	a1i 11	. . . 4 ⊢ (𝐴 ∈ Fin → ((♯‘𝐴)↑(♯‘∅)) = ((♯‘𝐴)↑0))
31		mapdm0 8776	. . . . . 6 ⊢ (𝐴 ∈ Fin → (𝐴 ↑_m ∅) = {∅})
32	31	fveq2d 6830	. . . . 5 ⊢ (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m ∅)) = (♯‘{∅}))
33		0ex 5249	. . . . . 6 ⊢ ∅ ∈ V
34		hashsng 14294	. . . . . 6 ⊢ (∅ ∈ V → (♯‘{∅}) = 1)
35	33, 34	mp1i 13	. . . . 5 ⊢ (𝐴 ∈ Fin → (♯‘{∅}) = 1)
36	32, 35	eqtrd 2764	. . . 4 ⊢ (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m ∅)) = 1)
37	27, 30, 36	3eqtr4rd 2775	. . 3 ⊢ (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m ∅)) = ((♯‘𝐴)↑(♯‘∅)))
38		oveq1 7360	. . . . . 6 ⊢ ((♯‘(𝐴 ↑_m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)) → ((♯‘(𝐴 ↑_m 𝑦)) · (♯‘𝐴)) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴)))
39		vex 3442	. . . . . . . . . . 11 ⊢ 𝑦 ∈ V
40	39	a1i 11	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → 𝑦 ∈ V)
41		vsnex 5376	. . . . . . . . . . 11 ⊢ {𝑧} ∈ V
42	41	a1i 11	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → {𝑧} ∈ V)
43		elex 3459	. . . . . . . . . . 11 ⊢ (𝐴 ∈ Fin → 𝐴 ∈ V)
44	43	adantr 480	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → 𝐴 ∈ V)
45		simprr 772	. . . . . . . . . . 11 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ¬ 𝑧 ∈ 𝑦)
46		disjsn 4665	. . . . . . . . . . 11 ⊢ ((𝑦 ∩ {𝑧}) = ∅ ↔ ¬ 𝑧 ∈ 𝑦)
47	45, 46	sylibr 234	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (𝑦 ∩ {𝑧}) = ∅)
48		mapunen 9070	. . . . . . . . . 10 ⊢ (((𝑦 ∈ V ∧ {𝑧} ∈ V ∧ 𝐴 ∈ V) ∧ (𝑦 ∩ {𝑧}) = ∅) → (𝐴 ↑_m (𝑦 ∪ {𝑧})) ≈ ((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧})))
49	40, 42, 44, 47, 48	syl31anc 1375	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (𝐴 ↑_m (𝑦 ∪ {𝑧})) ≈ ((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧})))
50		simpl 482	. . . . . . . . . . 11 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → 𝐴 ∈ Fin)
51		simprl 770	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → 𝑦 ∈ Fin)
52		snfi 8975	. . . . . . . . . . . 12 ⊢ {𝑧} ∈ Fin
53		unfi 9095	. . . . . . . . . . . 12 ⊢ ((𝑦 ∈ Fin ∧ {𝑧} ∈ Fin) → (𝑦 ∪ {𝑧}) ∈ Fin)
54	51, 52, 53	sylancl 586	. . . . . . . . . . 11 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (𝑦 ∪ {𝑧}) ∈ Fin)
55		mapfi 9257	. . . . . . . . . . 11 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∪ {𝑧}) ∈ Fin) → (𝐴 ↑_m (𝑦 ∪ {𝑧})) ∈ Fin)
56	50, 54, 55	syl2anc 584	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (𝐴 ↑_m (𝑦 ∪ {𝑧})) ∈ Fin)
57		mapfi 9257	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (𝐴 ↑_m 𝑦) ∈ Fin)
58	57	adantrr 717	. . . . . . . . . . 11 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (𝐴 ↑_m 𝑦) ∈ Fin)
59		mapfi 9257	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ Fin ∧ {𝑧} ∈ Fin) → (𝐴 ↑_m {𝑧}) ∈ Fin)
60	50, 52, 59	sylancl 586	. . . . . . . . . . 11 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (𝐴 ↑_m {𝑧}) ∈ Fin)
61		xpfi 9227	. . . . . . . . . . 11 ⊢ (((𝐴 ↑_m 𝑦) ∈ Fin ∧ (𝐴 ↑_m {𝑧}) ∈ Fin) → ((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧})) ∈ Fin)
62	58, 60, 61	syl2anc 584	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧})) ∈ Fin)
63		hashen 14272	. . . . . . . . . 10 ⊢ (((𝐴 ↑_m (𝑦 ∪ {𝑧})) ∈ Fin ∧ ((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧})) ∈ Fin) → ((♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = (♯‘((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧}))) ↔ (𝐴 ↑_m (𝑦 ∪ {𝑧})) ≈ ((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧}))))
64	56, 62, 63	syl2anc 584	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = (♯‘((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧}))) ↔ (𝐴 ↑_m (𝑦 ∪ {𝑧})) ≈ ((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧}))))
65	49, 64	mpbird 257	. . . . . . . 8 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = (♯‘((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧}))))
66		hashxp 14359	. . . . . . . . 9 ⊢ (((𝐴 ↑_m 𝑦) ∈ Fin ∧ (𝐴 ↑_m {𝑧}) ∈ Fin) → (♯‘((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧}))) = ((♯‘(𝐴 ↑_m 𝑦)) · (♯‘(𝐴 ↑_m {𝑧}))))
67	58, 60, 66	syl2anc 584	. . . . . . . 8 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (♯‘((𝐴 ↑_m 𝑦) × (𝐴 ↑_m {𝑧}))) = ((♯‘(𝐴 ↑_m 𝑦)) · (♯‘(𝐴 ↑_m {𝑧}))))
68		vex 3442	. . . . . . . . . . . 12 ⊢ 𝑧 ∈ V
69	68	a1i 11	. . . . . . . . . . 11 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → 𝑧 ∈ V)
70	50, 69	mapsnend 8968	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (𝐴 ↑_m {𝑧}) ≈ 𝐴)
71		hashen 14272	. . . . . . . . . . 11 ⊢ (((𝐴 ↑_m {𝑧}) ∈ Fin ∧ 𝐴 ∈ Fin) → ((♯‘(𝐴 ↑_m {𝑧})) = (♯‘𝐴) ↔ (𝐴 ↑_m {𝑧}) ≈ 𝐴))
72	60, 50, 71	syl2anc 584	. . . . . . . . . 10 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘(𝐴 ↑_m {𝑧})) = (♯‘𝐴) ↔ (𝐴 ↑_m {𝑧}) ≈ 𝐴))
73	70, 72	mpbird 257	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (♯‘(𝐴 ↑_m {𝑧})) = (♯‘𝐴))
74	73	oveq2d 7369	. . . . . . . 8 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘(𝐴 ↑_m 𝑦)) · (♯‘(𝐴 ↑_m {𝑧}))) = ((♯‘(𝐴 ↑_m 𝑦)) · (♯‘𝐴)))
75	65, 67, 74	3eqtrd 2768	. . . . . . 7 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = ((♯‘(𝐴 ↑_m 𝑦)) · (♯‘𝐴)))
76		hashunsng 14317	. . . . . . . . . . 11 ⊢ (𝑧 ∈ V → ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (♯‘(𝑦 ∪ {𝑧})) = ((♯‘𝑦) + 1)))
77	76	elv 3443	. . . . . . . . . 10 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (♯‘(𝑦 ∪ {𝑧})) = ((♯‘𝑦) + 1))
78	77	adantl 481	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (♯‘(𝑦 ∪ {𝑧})) = ((♯‘𝑦) + 1))
79	78	oveq2d 7369	. . . . . . . 8 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑((♯‘𝑦) + 1)))
80	26	adantr 480	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (♯‘𝐴) ∈ ℂ)
81		hashcl 14281	. . . . . . . . . 10 ⊢ (𝑦 ∈ Fin → (♯‘𝑦) ∈ ℕ₀)
82	81	ad2antrl 728	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → (♯‘𝑦) ∈ ℕ₀)
83	80, 82	expp1d 14072	. . . . . . . 8 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘𝐴)↑((♯‘𝑦) + 1)) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴)))
84	79, 83	eqtrd 2764	. . . . . . 7 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴)))
85	75, 84	eqeq12d 2745	. . . . . 6 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))) ↔ ((♯‘(𝐴 ↑_m 𝑦)) · (♯‘𝐴)) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴))))
86	38, 85	imbitrrid 246	. . . . 5 ⊢ ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦)) → ((♯‘(𝐴 ↑_m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)) → (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧})))))
87	86	expcom 413	. . . 4 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (𝐴 ∈ Fin → ((♯‘(𝐴 ↑_m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)) → (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))))
88	87	a2d 29	. . 3 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → ((𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦))) → (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))))
89	6, 12, 18, 24, 37, 88	findcard2s 9089	. 2 ⊢ (𝐵 ∈ Fin → (𝐴 ∈ Fin → (♯‘(𝐴 ↑_m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵))))
90	89	impcom 407	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (♯‘(𝐴 ↑_m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵)))

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 → wi 4 ↔ wb 206 ∧ wa 395 = wceq 1540 ∈ wcel 2109 Vcvv 3438 ∪ cun 3903 ∩ cin 3904 ∅c0 4286 {csn 4579 class class class wbr 5095 × cxp 5621 ‘cfv 6486 (class class class)co 7353 ↑_m cmap 8760 ≈ cen 8876 Fincfn 8879 ℂcc 11026 0cc0 11028 1c1 11029 + caddc 11031 · cmul 11033 ℕ₀cn0 12402 ↑cexp 13986 ♯chash 14255

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1795 ax-4 1809 ax-5 1910 ax-6 1967 ax-7 2008 ax-8 2111 ax-9 2119 ax-10 2142 ax-11 2158 ax-12 2178 ax-ext 2701 ax-sep 5238 ax-nul 5248 ax-pow 5307 ax-pr 5374 ax-un 7675 ax-cnex 11084 ax-resscn 11085 ax-1cn 11086 ax-icn 11087 ax-addcl 11088 ax-addrcl 11089 ax-mulcl 11090 ax-mulrcl 11091 ax-mulcom 11092 ax-addass 11093 ax-mulass 11094 ax-distr 11095 ax-i2m1 11096 ax-1ne0 11097 ax-1rid 11098 ax-rnegex 11099 ax-rrecex 11100 ax-cnre 11101 ax-pre-lttri 11102 ax-pre-lttrn 11103 ax-pre-ltadd 11104 ax-pre-mulgt0 11105

This theorem depends on definitions: df-bi 207 df-an 396 df-or 848 df-3or 1087 df-3an 1088 df-tru 1543 df-fal 1553 df-ex 1780 df-nf 1784 df-sb 2066 df-mo 2533 df-eu 2562 df-clab 2708 df-cleq 2721 df-clel 2803 df-nfc 2878 df-ne 2926 df-nel 3030 df-ral 3045 df-rex 3054 df-reu 3346 df-rab 3397 df-v 3440 df-sbc 3745 df-csb 3854 df-dif 3908 df-un 3910 df-in 3912 df-ss 3922 df-pss 3925 df-nul 4287 df-if 4479 df-pw 4555 df-sn 4580 df-pr 4582 df-op 4586 df-uni 4862 df-int 4900 df-iun 4946 df-br 5096 df-opab 5158 df-mpt 5177 df-tr 5203 df-id 5518 df-eprel 5523 df-po 5531 df-so 5532 df-fr 5576 df-we 5578 df-xp 5629 df-rel 5630 df-cnv 5631 df-co 5632 df-dm 5633 df-rn 5634 df-res 5635 df-ima 5636 df-pred 6253 df-ord 6314 df-on 6315 df-lim 6316 df-suc 6317 df-iota 6442 df-fun 6488 df-fn 6489 df-f 6490 df-f1 6491 df-fo 6492 df-f1o 6493 df-fv 6494 df-riota 7310 df-ov 7356 df-oprab 7357 df-mpo 7358 df-om 7807 df-1st 7931 df-2nd 7932 df-frecs 8221 df-wrecs 8252 df-recs 8301 df-rdg 8339 df-1o 8395 df-oadd 8399 df-er 8632 df-map 8762 df-pm 8763 df-en 8880 df-dom 8881 df-sdom 8882 df-fin 8883 df-dju 9816 df-card 9854 df-pnf 11170 df-mnf 11171 df-xr 11172 df-ltxr 11173 df-le 11174 df-sub 11367 df-neg 11368 df-nn 12147 df-n0 12403 df-z 12490 df-uz 12754 df-fz 13429 df-seq 13927 df-exp 13987 df-hash 14256

This theorem is referenced by: hashpw 14361 hashwrdn 14472 prmreclem2 16847 efmndhash 18768 birthdaylem2 26878

W3C validator