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

Theorem hashmap 13795
 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.
StepHypRef Expression
1 oveq2 7144 . . . . . 6 (𝑥 = ∅ → (𝐴m 𝑥) = (𝐴m ∅))
21fveq2d 6650 . . . . 5 (𝑥 = ∅ → (♯‘(𝐴m 𝑥)) = (♯‘(𝐴m ∅)))
3 fveq2 6646 . . . . . 6 (𝑥 = ∅ → (♯‘𝑥) = (♯‘∅))
43oveq2d 7152 . . . . 5 (𝑥 = ∅ → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘∅)))
52, 4eqeq12d 2814 . . . 4 (𝑥 = ∅ → ((♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴m ∅)) = ((♯‘𝐴)↑(♯‘∅))))
65imbi2d 344 . . 3 (𝑥 = ∅ → ((𝐴 ∈ Fin → (♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴m ∅)) = ((♯‘𝐴)↑(♯‘∅)))))
7 oveq2 7144 . . . . . 6 (𝑥 = 𝑦 → (𝐴m 𝑥) = (𝐴m 𝑦))
87fveq2d 6650 . . . . 5 (𝑥 = 𝑦 → (♯‘(𝐴m 𝑥)) = (♯‘(𝐴m 𝑦)))
9 fveq2 6646 . . . . . 6 (𝑥 = 𝑦 → (♯‘𝑥) = (♯‘𝑦))
109oveq2d 7152 . . . . 5 (𝑥 = 𝑦 → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘𝑦)))
118, 10eqeq12d 2814 . . . 4 (𝑥 = 𝑦 → ((♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦))))
1211imbi2d 344 . . 3 (𝑥 = 𝑦 → ((𝐴 ∈ Fin → (♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)))))
13 oveq2 7144 . . . . . 6 (𝑥 = (𝑦 ∪ {𝑧}) → (𝐴m 𝑥) = (𝐴m (𝑦 ∪ {𝑧})))
1413fveq2d 6650 . . . . 5 (𝑥 = (𝑦 ∪ {𝑧}) → (♯‘(𝐴m 𝑥)) = (♯‘(𝐴m (𝑦 ∪ {𝑧}))))
15 fveq2 6646 . . . . . 6 (𝑥 = (𝑦 ∪ {𝑧}) → (♯‘𝑥) = (♯‘(𝑦 ∪ {𝑧})))
1615oveq2d 7152 . . . . 5 (𝑥 = (𝑦 ∪ {𝑧}) → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))
1714, 16eqeq12d 2814 . . . 4 (𝑥 = (𝑦 ∪ {𝑧}) → ((♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧})))))
1817imbi2d 344 . . 3 (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐴 ∈ Fin → (♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))))
19 oveq2 7144 . . . . . 6 (𝑥 = 𝐵 → (𝐴m 𝑥) = (𝐴m 𝐵))
2019fveq2d 6650 . . . . 5 (𝑥 = 𝐵 → (♯‘(𝐴m 𝑥)) = (♯‘(𝐴m 𝐵)))
21 fveq2 6646 . . . . . 6 (𝑥 = 𝐵 → (♯‘𝑥) = (♯‘𝐵))
2221oveq2d 7152 . . . . 5 (𝑥 = 𝐵 → ((♯‘𝐴)↑(♯‘𝑥)) = ((♯‘𝐴)↑(♯‘𝐵)))
2320, 22eqeq12d 2814 . . . 4 (𝑥 = 𝐵 → ((♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥)) ↔ (♯‘(𝐴m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵))))
2423imbi2d 344 . . 3 (𝑥 = 𝐵 → ((𝐴 ∈ Fin → (♯‘(𝐴m 𝑥)) = ((♯‘𝐴)↑(♯‘𝑥))) ↔ (𝐴 ∈ Fin → (♯‘(𝐴m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵)))))
25 hashcl 13716 . . . . . 6 (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℕ0)
2625nn0cnd 11948 . . . . 5 (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℂ)
2726exp0d 13503 . . . 4 (𝐴 ∈ Fin → ((♯‘𝐴)↑0) = 1)
28 hash0 13727 . . . . . 6 (♯‘∅) = 0
2928oveq2i 7147 . . . . 5 ((♯‘𝐴)↑(♯‘∅)) = ((♯‘𝐴)↑0)
3029a1i 11 . . . 4 (𝐴 ∈ Fin → ((♯‘𝐴)↑(♯‘∅)) = ((♯‘𝐴)↑0))
31 mapdm0 8407 . . . . . 6 (𝐴 ∈ Fin → (𝐴m ∅) = {∅})
3231fveq2d 6650 . . . . 5 (𝐴 ∈ Fin → (♯‘(𝐴m ∅)) = (♯‘{∅}))
33 0ex 5176 . . . . . 6 ∅ ∈ V
34 hashsng 13729 . . . . . 6 (∅ ∈ V → (♯‘{∅}) = 1)
3533, 34mp1i 13 . . . . 5 (𝐴 ∈ Fin → (♯‘{∅}) = 1)
3632, 35eqtrd 2833 . . . 4 (𝐴 ∈ Fin → (♯‘(𝐴m ∅)) = 1)
3727, 30, 363eqtr4rd 2844 . . 3 (𝐴 ∈ Fin → (♯‘(𝐴m ∅)) = ((♯‘𝐴)↑(♯‘∅)))
38 oveq1 7143 . . . . . 6 ((♯‘(𝐴m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)) → ((♯‘(𝐴m 𝑦)) · (♯‘𝐴)) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴)))
39 vex 3444 . . . . . . . . . . 11 𝑦 ∈ V
4039a1i 11 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → 𝑦 ∈ V)
41 snex 5298 . . . . . . . . . . 11 {𝑧} ∈ V
4241a1i 11 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → {𝑧} ∈ V)
43 elex 3459 . . . . . . . . . . 11 (𝐴 ∈ Fin → 𝐴 ∈ V)
4443adantr 484 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → 𝐴 ∈ V)
45 simprr 772 . . . . . . . . . . 11 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ¬ 𝑧𝑦)
46 disjsn 4607 . . . . . . . . . . 11 ((𝑦 ∩ {𝑧}) = ∅ ↔ ¬ 𝑧𝑦)
4745, 46sylibr 237 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (𝑦 ∩ {𝑧}) = ∅)
48 mapunen 8673 . . . . . . . . . 10 (((𝑦 ∈ V ∧ {𝑧} ∈ V ∧ 𝐴 ∈ V) ∧ (𝑦 ∩ {𝑧}) = ∅) → (𝐴m (𝑦 ∪ {𝑧})) ≈ ((𝐴m 𝑦) × (𝐴m {𝑧})))
4940, 42, 44, 47, 48syl31anc 1370 . . . . . . . . 9 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (𝐴m (𝑦 ∪ {𝑧})) ≈ ((𝐴m 𝑦) × (𝐴m {𝑧})))
50 simpl 486 . . . . . . . . . . 11 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → 𝐴 ∈ Fin)
51 simprl 770 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → 𝑦 ∈ Fin)
52 snfi 8580 . . . . . . . . . . . 12 {𝑧} ∈ Fin
53 unfi 8772 . . . . . . . . . . . 12 ((𝑦 ∈ Fin ∧ {𝑧} ∈ Fin) → (𝑦 ∪ {𝑧}) ∈ Fin)
5451, 52, 53sylancl 589 . . . . . . . . . . 11 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (𝑦 ∪ {𝑧}) ∈ Fin)
55 mapfi 8807 . . . . . . . . . . 11 ((𝐴 ∈ Fin ∧ (𝑦 ∪ {𝑧}) ∈ Fin) → (𝐴m (𝑦 ∪ {𝑧})) ∈ Fin)
5650, 54, 55syl2anc 587 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (𝐴m (𝑦 ∪ {𝑧})) ∈ Fin)
57 mapfi 8807 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (𝐴m 𝑦) ∈ Fin)
5857adantrr 716 . . . . . . . . . . 11 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (𝐴m 𝑦) ∈ Fin)
59 mapfi 8807 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ {𝑧} ∈ Fin) → (𝐴m {𝑧}) ∈ Fin)
6050, 52, 59sylancl 589 . . . . . . . . . . 11 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (𝐴m {𝑧}) ∈ Fin)
61 xpfi 8776 . . . . . . . . . . 11 (((𝐴m 𝑦) ∈ Fin ∧ (𝐴m {𝑧}) ∈ Fin) → ((𝐴m 𝑦) × (𝐴m {𝑧})) ∈ Fin)
6258, 60, 61syl2anc 587 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((𝐴m 𝑦) × (𝐴m {𝑧})) ∈ Fin)
63 hashen 13706 . . . . . . . . . 10 (((𝐴m (𝑦 ∪ {𝑧})) ∈ Fin ∧ ((𝐴m 𝑦) × (𝐴m {𝑧})) ∈ Fin) → ((♯‘(𝐴m (𝑦 ∪ {𝑧}))) = (♯‘((𝐴m 𝑦) × (𝐴m {𝑧}))) ↔ (𝐴m (𝑦 ∪ {𝑧})) ≈ ((𝐴m 𝑦) × (𝐴m {𝑧}))))
6456, 62, 63syl2anc 587 . . . . . . . . 9 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘(𝐴m (𝑦 ∪ {𝑧}))) = (♯‘((𝐴m 𝑦) × (𝐴m {𝑧}))) ↔ (𝐴m (𝑦 ∪ {𝑧})) ≈ ((𝐴m 𝑦) × (𝐴m {𝑧}))))
6549, 64mpbird 260 . . . . . . . 8 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (♯‘(𝐴m (𝑦 ∪ {𝑧}))) = (♯‘((𝐴m 𝑦) × (𝐴m {𝑧}))))
66 hashxp 13794 . . . . . . . . 9 (((𝐴m 𝑦) ∈ Fin ∧ (𝐴m {𝑧}) ∈ Fin) → (♯‘((𝐴m 𝑦) × (𝐴m {𝑧}))) = ((♯‘(𝐴m 𝑦)) · (♯‘(𝐴m {𝑧}))))
6758, 60, 66syl2anc 587 . . . . . . . 8 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (♯‘((𝐴m 𝑦) × (𝐴m {𝑧}))) = ((♯‘(𝐴m 𝑦)) · (♯‘(𝐴m {𝑧}))))
68 vex 3444 . . . . . . . . . . . 12 𝑧 ∈ V
6968a1i 11 . . . . . . . . . . 11 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → 𝑧 ∈ V)
7050, 69mapsnend 8574 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (𝐴m {𝑧}) ≈ 𝐴)
71 hashen 13706 . . . . . . . . . . 11 (((𝐴m {𝑧}) ∈ Fin ∧ 𝐴 ∈ Fin) → ((♯‘(𝐴m {𝑧})) = (♯‘𝐴) ↔ (𝐴m {𝑧}) ≈ 𝐴))
7260, 50, 71syl2anc 587 . . . . . . . . . 10 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘(𝐴m {𝑧})) = (♯‘𝐴) ↔ (𝐴m {𝑧}) ≈ 𝐴))
7370, 72mpbird 260 . . . . . . . . 9 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (♯‘(𝐴m {𝑧})) = (♯‘𝐴))
7473oveq2d 7152 . . . . . . . 8 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘(𝐴m 𝑦)) · (♯‘(𝐴m {𝑧}))) = ((♯‘(𝐴m 𝑦)) · (♯‘𝐴)))
7565, 67, 743eqtrd 2837 . . . . . . 7 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (♯‘(𝐴m (𝑦 ∪ {𝑧}))) = ((♯‘(𝐴m 𝑦)) · (♯‘𝐴)))
76 hashunsng 13752 . . . . . . . . . . 11 (𝑧 ∈ V → ((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) → (♯‘(𝑦 ∪ {𝑧})) = ((♯‘𝑦) + 1)))
7776elv 3446 . . . . . . . . . 10 ((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) → (♯‘(𝑦 ∪ {𝑧})) = ((♯‘𝑦) + 1))
7877adantl 485 . . . . . . . . 9 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (♯‘(𝑦 ∪ {𝑧})) = ((♯‘𝑦) + 1))
7978oveq2d 7152 . . . . . . . 8 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑((♯‘𝑦) + 1)))
8026adantr 484 . . . . . . . . 9 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (♯‘𝐴) ∈ ℂ)
81 hashcl 13716 . . . . . . . . . 10 (𝑦 ∈ Fin → (♯‘𝑦) ∈ ℕ0)
8281ad2antrl 727 . . . . . . . . 9 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → (♯‘𝑦) ∈ ℕ0)
8380, 82expp1d 13510 . . . . . . . 8 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘𝐴)↑((♯‘𝑦) + 1)) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴)))
8479, 83eqtrd 2833 . . . . . . 7 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴)))
8575, 84eqeq12d 2814 . . . . . 6 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘(𝐴m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))) ↔ ((♯‘(𝐴m 𝑦)) · (♯‘𝐴)) = (((♯‘𝐴)↑(♯‘𝑦)) · (♯‘𝐴))))
8638, 85syl5ibr 249 . . . . 5 ((𝐴 ∈ Fin ∧ (𝑦 ∈ Fin ∧ ¬ 𝑧𝑦)) → ((♯‘(𝐴m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)) → (♯‘(𝐴m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧})))))
8786expcom 417 . . . 4 ((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) → (𝐴 ∈ Fin → ((♯‘(𝐴m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦)) → (♯‘(𝐴m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))))
8887a2d 29 . . 3 ((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) → ((𝐴 ∈ Fin → (♯‘(𝐴m 𝑦)) = ((♯‘𝐴)↑(♯‘𝑦))) → (𝐴 ∈ Fin → (♯‘(𝐴m (𝑦 ∪ {𝑧}))) = ((♯‘𝐴)↑(♯‘(𝑦 ∪ {𝑧}))))))
896, 12, 18, 24, 37, 88findcard2s 8746 . 2 (𝐵 ∈ Fin → (𝐴 ∈ Fin → (♯‘(𝐴m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵))))
9089impcom 411 1 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (♯‘(𝐴m 𝐵)) = ((♯‘𝐴)↑(♯‘𝐵)))
 Colors of variables: wff setvar class Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 209   ∧ wa 399   = wceq 1538   ∈ wcel 2111  Vcvv 3441   ∪ cun 3879   ∩ cin 3880  ∅c0 4243  {csn 4525   class class class wbr 5031   × cxp 5518  ‘cfv 6325  (class class class)co 7136   ↑m cmap 8392   ≈ cen 8492  Fincfn 8495  ℂcc 10527  0cc0 10529  1c1 10530   + caddc 10532   · cmul 10534  ℕ0cn0 11888  ↑cexp 13428  ♯chash 13689 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 1911  ax-6 1970  ax-7 2015  ax-8 2113  ax-9 2121  ax-10 2142  ax-11 2158  ax-12 2175  ax-ext 2770  ax-sep 5168  ax-nul 5175  ax-pow 5232  ax-pr 5296  ax-un 7444  ax-cnex 10585  ax-resscn 10586  ax-1cn 10587  ax-icn 10588  ax-addcl 10589  ax-addrcl 10590  ax-mulcl 10591  ax-mulrcl 10592  ax-mulcom 10593  ax-addass 10594  ax-mulass 10595  ax-distr 10596  ax-i2m1 10597  ax-1ne0 10598  ax-1rid 10599  ax-rnegex 10600  ax-rrecex 10601  ax-cnre 10602  ax-pre-lttri 10603  ax-pre-lttrn 10604  ax-pre-ltadd 10605  ax-pre-mulgt0 10606 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3or 1085  df-3an 1086  df-tru 1541  df-ex 1782  df-nf 1786  df-sb 2070  df-mo 2598  df-eu 2629  df-clab 2777  df-cleq 2791  df-clel 2870  df-nfc 2938  df-ne 2988  df-nel 3092  df-ral 3111  df-rex 3112  df-reu 3113  df-rab 3115  df-v 3443  df-sbc 3721  df-csb 3829  df-dif 3884  df-un 3886  df-in 3888  df-ss 3898  df-pss 3900  df-nul 4244  df-if 4426  df-pw 4499  df-sn 4526  df-pr 4528  df-tp 4530  df-op 4532  df-uni 4802  df-int 4840  df-iun 4884  df-br 5032  df-opab 5094  df-mpt 5112  df-tr 5138  df-id 5426  df-eprel 5431  df-po 5439  df-so 5440  df-fr 5479  df-we 5481  df-xp 5526  df-rel 5527  df-cnv 5528  df-co 5529  df-dm 5530  df-rn 5531  df-res 5532  df-ima 5533  df-pred 6117  df-ord 6163  df-on 6164  df-lim 6165  df-suc 6166  df-iota 6284  df-fun 6327  df-fn 6328  df-f 6329  df-f1 6330  df-fo 6331  df-f1o 6332  df-fv 6333  df-riota 7094  df-ov 7139  df-oprab 7140  df-mpo 7141  df-om 7564  df-1st 7674  df-2nd 7675  df-wrecs 7933  df-recs 7994  df-rdg 8032  df-1o 8088  df-2o 8089  df-oadd 8092  df-er 8275  df-map 8394  df-pm 8395  df-en 8496  df-dom 8497  df-sdom 8498  df-fin 8499  df-dju 9317  df-card 9355  df-pnf 10669  df-mnf 10670  df-xr 10671  df-ltxr 10672  df-le 10673  df-sub 10864  df-neg 10865  df-nn 11629  df-n0 11889  df-z 11973  df-uz 12235  df-fz 12889  df-seq 13368  df-exp 13429  df-hash 13690 This theorem is referenced by:  hashpw  13796  hashwrdn  13893  prmreclem2  16246  efmndhash  18036  birthdaylem2  25548
 Copyright terms: Public domain W3C validator