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

Theorem hashdom 14339
Description: Dominance relation for the size function. (Contributed by Mario Carneiro, 22-Sep-2013.) (Revised by Mario Carneiro, 22-Apr-2015.)
Assertion
Ref Expression
hashdom ((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) β†’ ((β™―β€˜π΄) ≀ (β™―β€˜π΅) ↔ 𝐴 β‰Ό 𝐡))

Proof of Theorem hashdom
Dummy variables π‘₯ 𝑓 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 fzfi 13937 . . . . . . . 8 (1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))) ∈ Fin
2 ficardom 9956 . . . . . . . 8 ((1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))) ∈ Fin β†’ (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) ∈ Ο‰)
31, 2ax-mp 5 . . . . . . 7 (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) ∈ Ο‰
4 eqid 2733 . . . . . . . . . . . . . 14 (rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰) = (rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)
54hashgval 14293 . . . . . . . . . . . . 13 (𝐴 ∈ Fin β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) = (β™―β€˜π΄))
65ad2antrr 725 . . . . . . . . . . . 12 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) = (β™―β€˜π΄))
74hashgval 14293 . . . . . . . . . . . . . 14 ((1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))) ∈ Fin β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) = (β™―β€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))
81, 7ax-mp 5 . . . . . . . . . . . . 13 ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) = (β™―β€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))
9 hashcl 14316 . . . . . . . . . . . . . . . 16 (𝐴 ∈ Fin β†’ (β™―β€˜π΄) ∈ β„•0)
109ad2antrr 725 . . . . . . . . . . . . . . 15 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (β™―β€˜π΄) ∈ β„•0)
11 hashcl 14316 . . . . . . . . . . . . . . . 16 (𝐡 ∈ Fin β†’ (β™―β€˜π΅) ∈ β„•0)
1211ad2antlr 726 . . . . . . . . . . . . . . 15 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (β™―β€˜π΅) ∈ β„•0)
13 simpr 486 . . . . . . . . . . . . . . 15 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅))
14 nn0sub2 12623 . . . . . . . . . . . . . . 15 (((β™―β€˜π΄) ∈ β„•0 ∧ (β™―β€˜π΅) ∈ β„•0 ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)) ∈ β„•0)
1510, 12, 13, 14syl3anc 1372 . . . . . . . . . . . . . 14 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)) ∈ β„•0)
16 hashfz1 14306 . . . . . . . . . . . . . 14 (((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)) ∈ β„•0 β†’ (β™―β€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) = ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))
1715, 16syl 17 . . . . . . . . . . . . 13 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (β™―β€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) = ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))
188, 17eqtrid 2785 . . . . . . . . . . . 12 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) = ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))
196, 18oveq12d 7427 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) + ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))) = ((β™―β€˜π΄) + ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))
209nn0cnd 12534 . . . . . . . . . . . . 13 (𝐴 ∈ Fin β†’ (β™―β€˜π΄) ∈ β„‚)
2111nn0cnd 12534 . . . . . . . . . . . . 13 (𝐡 ∈ Fin β†’ (β™―β€˜π΅) ∈ β„‚)
22 pncan3 11468 . . . . . . . . . . . . 13 (((β™―β€˜π΄) ∈ β„‚ ∧ (β™―β€˜π΅) ∈ β„‚) β†’ ((β™―β€˜π΄) + ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))) = (β™―β€˜π΅))
2320, 21, 22syl2an 597 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) β†’ ((β™―β€˜π΄) + ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))) = (β™―β€˜π΅))
2423adantr 482 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((β™―β€˜π΄) + ((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))) = (β™―β€˜π΅))
2519, 24eqtrd 2773 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) + ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))) = (β™―β€˜π΅))
26 ficardom 9956 . . . . . . . . . . . 12 (𝐴 ∈ Fin β†’ (cardβ€˜π΄) ∈ Ο‰)
2726ad2antrr 725 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (cardβ€˜π΄) ∈ Ο‰)
284hashgadd 14337 . . . . . . . . . . 11 (((cardβ€˜π΄) ∈ Ο‰ ∧ (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) ∈ Ο‰) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))) = (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) + ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))))
2927, 3, 28sylancl 587 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))) = (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) + ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))))
304hashgval 14293 . . . . . . . . . . 11 (𝐡 ∈ Fin β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)) = (β™―β€˜π΅))
3130ad2antlr 726 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)) = (β™―β€˜π΅))
3225, 29, 313eqtr4d 2783 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))))) = ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)))
3332fveq2d 6896 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (β—‘(rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))))) = (β—‘(rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅))))
344hashgf1o 13936 . . . . . . . . 9 (rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰):ω–1-1-ontoβ†’β„•0
35 nnacl 8611 . . . . . . . . . 10 (((cardβ€˜π΄) ∈ Ο‰ ∧ (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) ∈ Ο‰) β†’ ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) ∈ Ο‰)
3627, 3, 35sylancl 587 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) ∈ Ο‰)
37 f1ocnvfv1 7274 . . . . . . . . 9 (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰):ω–1-1-ontoβ†’β„•0 ∧ ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) ∈ Ο‰) β†’ (β—‘(rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))))) = ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))))
3834, 36, 37sylancr 588 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (β—‘(rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))))) = ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))))
39 ficardom 9956 . . . . . . . . . 10 (𝐡 ∈ Fin β†’ (cardβ€˜π΅) ∈ Ο‰)
4039ad2antlr 726 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (cardβ€˜π΅) ∈ Ο‰)
41 f1ocnvfv1 7274 . . . . . . . . 9 (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰):ω–1-1-ontoβ†’β„•0 ∧ (cardβ€˜π΅) ∈ Ο‰) β†’ (β—‘(rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅))) = (cardβ€˜π΅))
4234, 40, 41sylancr 588 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ (β—‘(rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅))) = (cardβ€˜π΅))
4333, 38, 423eqtr3d 2781 . . . . . . 7 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) = (cardβ€˜π΅))
44 oveq2 7417 . . . . . . . . 9 (𝑦 = (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) β†’ ((cardβ€˜π΄) +o 𝑦) = ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))))
4544eqeq1d 2735 . . . . . . . 8 (𝑦 = (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) β†’ (((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅) ↔ ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) = (cardβ€˜π΅)))
4645rspcev 3613 . . . . . . 7 (((cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄)))) ∈ Ο‰ ∧ ((cardβ€˜π΄) +o (cardβ€˜(1...((β™―β€˜π΅) βˆ’ (β™―β€˜π΄))))) = (cardβ€˜π΅)) β†’ βˆƒπ‘¦ ∈ Ο‰ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅))
473, 43, 46sylancr 588 . . . . . 6 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ (β™―β€˜π΄) ≀ (β™―β€˜π΅)) β†’ βˆƒπ‘¦ ∈ Ο‰ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅))
4847ex 414 . . . . 5 ((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) β†’ ((β™―β€˜π΄) ≀ (β™―β€˜π΅) β†’ βˆƒπ‘¦ ∈ Ο‰ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅)))
49 cardnn 9958 . . . . . . . . . 10 (𝑦 ∈ Ο‰ β†’ (cardβ€˜π‘¦) = 𝑦)
5049adantl 483 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Ο‰) β†’ (cardβ€˜π‘¦) = 𝑦)
5150oveq2d 7425 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Ο‰) β†’ ((cardβ€˜π΄) +o (cardβ€˜π‘¦)) = ((cardβ€˜π΄) +o 𝑦))
5251eqeq1d 2735 . . . . . . 7 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Ο‰) β†’ (((cardβ€˜π΄) +o (cardβ€˜π‘¦)) = (cardβ€˜π΅) ↔ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅)))
53 fveq2 6892 . . . . . . . 8 (((cardβ€˜π΄) +o (cardβ€˜π‘¦)) = (cardβ€˜π΅) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)))
54 nnfi 9167 . . . . . . . . 9 (𝑦 ∈ Ο‰ β†’ 𝑦 ∈ Fin)
55 ficardom 9956 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin β†’ (cardβ€˜π‘¦) ∈ Ο‰)
564hashgadd 14337 . . . . . . . . . . . . . 14 (((cardβ€˜π΄) ∈ Ο‰ ∧ (cardβ€˜π‘¦) ∈ Ο‰) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) + ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π‘¦))))
5726, 55, 56syl2an 597 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) + ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π‘¦))))
584hashgval 14293 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π‘¦)) = (β™―β€˜π‘¦))
595, 58oveqan12d 7428 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) β†’ (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΄)) + ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π‘¦))) = ((β™―β€˜π΄) + (β™―β€˜π‘¦)))
6057, 59eqtrd 2773 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = ((β™―β€˜π΄) + (β™―β€˜π‘¦)))
6160adantlr 714 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Fin) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = ((β™―β€˜π΄) + (β™―β€˜π‘¦)))
6230ad2antlr 726 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Fin) β†’ ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)) = (β™―β€˜π΅))
6361, 62eqeq12d 2749 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Fin) β†’ (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)) ↔ ((β™―β€˜π΄) + (β™―β€˜π‘¦)) = (β™―β€˜π΅)))
64 hashcl 14316 . . . . . . . . . . . . . . 15 (𝑦 ∈ Fin β†’ (β™―β€˜π‘¦) ∈ β„•0)
6564nn0ge0d 12535 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin β†’ 0 ≀ (β™―β€˜π‘¦))
6665adantl 483 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) β†’ 0 ≀ (β™―β€˜π‘¦))
679nn0red 12533 . . . . . . . . . . . . . 14 (𝐴 ∈ Fin β†’ (β™―β€˜π΄) ∈ ℝ)
6864nn0red 12533 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin β†’ (β™―β€˜π‘¦) ∈ ℝ)
69 addge01 11724 . . . . . . . . . . . . . 14 (((β™―β€˜π΄) ∈ ℝ ∧ (β™―β€˜π‘¦) ∈ ℝ) β†’ (0 ≀ (β™―β€˜π‘¦) ↔ (β™―β€˜π΄) ≀ ((β™―β€˜π΄) + (β™―β€˜π‘¦))))
7067, 68, 69syl2an 597 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) β†’ (0 ≀ (β™―β€˜π‘¦) ↔ (β™―β€˜π΄) ≀ ((β™―β€˜π΄) + (β™―β€˜π‘¦))))
7166, 70mpbid 231 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) β†’ (β™―β€˜π΄) ≀ ((β™―β€˜π΄) + (β™―β€˜π‘¦)))
7271adantlr 714 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Fin) β†’ (β™―β€˜π΄) ≀ ((β™―β€˜π΄) + (β™―β€˜π‘¦)))
73 breq2 5153 . . . . . . . . . . 11 (((β™―β€˜π΄) + (β™―β€˜π‘¦)) = (β™―β€˜π΅) β†’ ((β™―β€˜π΄) ≀ ((β™―β€˜π΄) + (β™―β€˜π‘¦)) ↔ (β™―β€˜π΄) ≀ (β™―β€˜π΅)))
7472, 73syl5ibcom 244 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Fin) β†’ (((β™―β€˜π΄) + (β™―β€˜π‘¦)) = (β™―β€˜π΅) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅)))
7563, 74sylbid 239 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Fin) β†’ (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅)))
7654, 75sylan2 594 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Ο‰) β†’ (((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜((cardβ€˜π΄) +o (cardβ€˜π‘¦))) = ((rec((π‘₯ ∈ V ↦ (π‘₯ + 1)), 0) β†Ύ Ο‰)β€˜(cardβ€˜π΅)) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅)))
7753, 76syl5 34 . . . . . . 7 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Ο‰) β†’ (((cardβ€˜π΄) +o (cardβ€˜π‘¦)) = (cardβ€˜π΅) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅)))
7852, 77sylbird 260 . . . . . 6 (((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) ∧ 𝑦 ∈ Ο‰) β†’ (((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅)))
7978rexlimdva 3156 . . . . 5 ((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) β†’ (βˆƒπ‘¦ ∈ Ο‰ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅)))
8048, 79impbid 211 . . . 4 ((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) β†’ ((β™―β€˜π΄) ≀ (β™―β€˜π΅) ↔ βˆƒπ‘¦ ∈ Ο‰ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅)))
81 nnawordex 8637 . . . . 5 (((cardβ€˜π΄) ∈ Ο‰ ∧ (cardβ€˜π΅) ∈ Ο‰) β†’ ((cardβ€˜π΄) βŠ† (cardβ€˜π΅) ↔ βˆƒπ‘¦ ∈ Ο‰ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅)))
8226, 39, 81syl2an 597 . . . 4 ((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) β†’ ((cardβ€˜π΄) βŠ† (cardβ€˜π΅) ↔ βˆƒπ‘¦ ∈ Ο‰ ((cardβ€˜π΄) +o 𝑦) = (cardβ€˜π΅)))
83 finnum 9943 . . . . 5 (𝐴 ∈ Fin β†’ 𝐴 ∈ dom card)
84 finnum 9943 . . . . 5 (𝐡 ∈ Fin β†’ 𝐡 ∈ dom card)
85 carddom2 9972 . . . . 5 ((𝐴 ∈ dom card ∧ 𝐡 ∈ dom card) β†’ ((cardβ€˜π΄) βŠ† (cardβ€˜π΅) ↔ 𝐴 β‰Ό 𝐡))
8683, 84, 85syl2an 597 . . . 4 ((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) β†’ ((cardβ€˜π΄) βŠ† (cardβ€˜π΅) ↔ 𝐴 β‰Ό 𝐡))
8780, 82, 863bitr2d 307 . . 3 ((𝐴 ∈ Fin ∧ 𝐡 ∈ Fin) β†’ ((β™―β€˜π΄) ≀ (β™―β€˜π΅) ↔ 𝐴 β‰Ό 𝐡))
8887adantlr 714 . 2 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ 𝐡 ∈ Fin) β†’ ((β™―β€˜π΄) ≀ (β™―β€˜π΅) ↔ 𝐴 β‰Ό 𝐡))
89 hashxrcl 14317 . . . . . 6 (𝐴 ∈ Fin β†’ (β™―β€˜π΄) ∈ ℝ*)
9089ad2antrr 725 . . . . 5 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ (β™―β€˜π΄) ∈ ℝ*)
91 pnfge 13110 . . . . 5 ((β™―β€˜π΄) ∈ ℝ* β†’ (β™―β€˜π΄) ≀ +∞)
9290, 91syl 17 . . . 4 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ (β™―β€˜π΄) ≀ +∞)
93 hashinf 14295 . . . . 5 ((𝐡 ∈ 𝑉 ∧ Β¬ 𝐡 ∈ Fin) β†’ (β™―β€˜π΅) = +∞)
9493adantll 713 . . . 4 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ (β™―β€˜π΅) = +∞)
9592, 94breqtrrd 5177 . . 3 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ (β™―β€˜π΄) ≀ (β™―β€˜π΅))
96 isinffi 9987 . . . . . 6 ((Β¬ 𝐡 ∈ Fin ∧ 𝐴 ∈ Fin) β†’ βˆƒπ‘“ 𝑓:𝐴–1-1→𝐡)
9796ancoms 460 . . . . 5 ((𝐴 ∈ Fin ∧ Β¬ 𝐡 ∈ Fin) β†’ βˆƒπ‘“ 𝑓:𝐴–1-1→𝐡)
9897adantlr 714 . . . 4 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ βˆƒπ‘“ 𝑓:𝐴–1-1→𝐡)
99 brdomg 8952 . . . . 5 (𝐡 ∈ 𝑉 β†’ (𝐴 β‰Ό 𝐡 ↔ βˆƒπ‘“ 𝑓:𝐴–1-1→𝐡))
10099ad2antlr 726 . . . 4 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ (𝐴 β‰Ό 𝐡 ↔ βˆƒπ‘“ 𝑓:𝐴–1-1→𝐡))
10198, 100mpbird 257 . . 3 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ 𝐴 β‰Ό 𝐡)
10295, 1012thd 265 . 2 (((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) ∧ Β¬ 𝐡 ∈ Fin) β†’ ((β™―β€˜π΄) ≀ (β™―β€˜π΅) ↔ 𝐴 β‰Ό 𝐡))
10388, 102pm2.61dan 812 1 ((𝐴 ∈ Fin ∧ 𝐡 ∈ 𝑉) β†’ ((β™―β€˜π΄) ≀ (β™―β€˜π΅) ↔ 𝐴 β‰Ό 𝐡))
Colors of variables: wff setvar class
Syntax hints:  Β¬ wn 3   β†’ wi 4   ↔ wb 205   ∧ wa 397   = wceq 1542  βˆƒwex 1782   ∈ wcel 2107  βˆƒwrex 3071  Vcvv 3475   βŠ† wss 3949   class class class wbr 5149   ↦ cmpt 5232  β—‘ccnv 5676  dom cdm 5677   β†Ύ cres 5679  β€“1-1β†’wf1 6541  β€“1-1-ontoβ†’wf1o 6543  β€˜cfv 6544  (class class class)co 7409  Ο‰com 7855  reccrdg 8409   +o coa 8463   β‰Ό cdom 8937  Fincfn 8939  cardccrd 9930  β„‚cc 11108  β„cr 11109  0cc0 11110  1c1 11111   + caddc 11113  +∞cpnf 11245  β„*cxr 11247   ≀ cle 11249   βˆ’ cmin 11444  β„•0cn0 12472  ...cfz 13484  β™―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-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-card 9934  df-pnf 11250  df-mnf 11251  df-xr 11252  df-ltxr 11253  df-le 11254  df-sub 11446  df-neg 11447  df-nn 12213  df-n0 12473  df-xnn0 12545  df-z 12559  df-uz 12823  df-fz 13485  df-hash 14291
This theorem is referenced by:  hashdomi  14340  hashsdom  14341  hashun2  14343  hashss  14369  hashsslei  14386  hashfun  14397  hashf1  14418  hashge3el3dif  14447  isercoll  15614  phicl2  16701  phibnd  16704  prmreclem2  16850  prmreclem3  16851  4sqlem11  16888  vdwlem11  16924  ramub2  16947  0ram  16953  ram0  16955  sylow1lem4  19469  pgpssslw  19482  fislw  19493  znfld  21116  znidomb  21117  fta1blem  25686  birthdaylem3  26458  basellem4  26588  ppiwordi  26666  musum  26695  ppiub  26707  chpub  26723  lgsqrlem4  26852  upgrex  28352  sizusglecusg  28720  derangenlem  34162  subfaclefac  34167  erdsze2lem1  34194  snmlff  34320  idomsubgmo  41940  aacllem  47848
  Copyright terms: Public domain W3C validator