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

Theorem hashdom 14321
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 13919 . . . . . . . 8 (1...((♯‘𝐵) − (♯‘𝐴))) ∈ Fin
2 ficardom 9938 . . . . . . . 8 ((1...((♯‘𝐵) − (♯‘𝐴))) ∈ Fin → (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω)
31, 2ax-mp 5 . . . . . . 7 (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω
4 eqid 2731 . . . . . . . . . . . . . 14 (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
54hashgval 14275 . . . . . . . . . . . . 13 (𝐴 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = (♯‘𝐴))
65ad2antrr 724 . . . . . . . . . . . 12 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = (♯‘𝐴))
74hashgval 14275 . . . . . . . . . . . . . 14 ((1...((♯‘𝐵) − (♯‘𝐴))) ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (♯‘(1...((♯‘𝐵) − (♯‘𝐴)))))
81, 7ax-mp 5 . . . . . . . . . . . . 13 ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (♯‘(1...((♯‘𝐵) − (♯‘𝐴))))
9 hashcl 14298 . . . . . . . . . . . . . . . 16 (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℕ0)
109ad2antrr 724 . . . . . . . . . . . . . . 15 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘𝐴) ∈ ℕ0)
11 hashcl 14298 . . . . . . . . . . . . . . . 16 (𝐵 ∈ Fin → (♯‘𝐵) ∈ ℕ0)
1211ad2antlr 725 . . . . . . . . . . . . . . 15 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘𝐵) ∈ ℕ0)
13 simpr 485 . . . . . . . . . . . . . . 15 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘𝐴) ≤ (♯‘𝐵))
14 nn0sub2 12605 . . . . . . . . . . . . . . 15 (((♯‘𝐴) ∈ ℕ0 ∧ (♯‘𝐵) ∈ ℕ0 ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((♯‘𝐵) − (♯‘𝐴)) ∈ ℕ0)
1510, 12, 13, 14syl3anc 1371 . . . . . . . . . . . . . 14 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((♯‘𝐵) − (♯‘𝐴)) ∈ ℕ0)
16 hashfz1 14288 . . . . . . . . . . . . . 14 (((♯‘𝐵) − (♯‘𝐴)) ∈ ℕ0 → (♯‘(1...((♯‘𝐵) − (♯‘𝐴)))) = ((♯‘𝐵) − (♯‘𝐴)))
1715, 16syl 17 . . . . . . . . . . . . 13 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘(1...((♯‘𝐵) − (♯‘𝐴)))) = ((♯‘𝐵) − (♯‘𝐴)))
188, 17eqtrid 2783 . . . . . . . . . . . 12 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = ((♯‘𝐵) − (♯‘𝐴)))
196, 18oveq12d 7411 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))))
209nn0cnd 12516 . . . . . . . . . . . . 13 (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℂ)
2111nn0cnd 12516 . . . . . . . . . . . . 13 (𝐵 ∈ Fin → (♯‘𝐵) ∈ ℂ)
22 pncan3 11450 . . . . . . . . . . . . 13 (((♯‘𝐴) ∈ ℂ ∧ (♯‘𝐵) ∈ ℂ) → ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))) = (♯‘𝐵))
2320, 21, 22syl2an 596 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))) = (♯‘𝐵))
2423adantr 481 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))) = (♯‘𝐵))
2519, 24eqtrd 2771 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = (♯‘𝐵))
26 ficardom 9938 . . . . . . . . . . . 12 (𝐴 ∈ Fin → (card‘𝐴) ∈ ω)
2726ad2antrr 724 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (card‘𝐴) ∈ ω)
284hashgadd 14319 . . . . . . . . . . 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 586 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴)))))))
304hashgval 14275 . . . . . . . . . . 11 (𝐵 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
3130ad2antlr 725 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
3225, 29, 313eqtr4d 2781 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)))
3332fveq2d 6882 . . . . . . . 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 13918 . . . . . . . . 9 (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω):ω–1-1-onto→ℕ0
35 nnacl 8594 . . . . . . . . . 10 (((card‘𝐴) ∈ ω ∧ (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω) → ((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) ∈ ω)
3627, 3, 35sylancl 586 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) ∈ ω)
37 f1ocnvfv1 7258 . . . . . . . . 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 587 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))) = ((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))
39 ficardom 9938 . . . . . . . . . 10 (𝐵 ∈ Fin → (card‘𝐵) ∈ ω)
4039ad2antlr 725 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (card‘𝐵) ∈ ω)
41 f1ocnvfv1 7258 . . . . . . . . 9 (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω):ω–1-1-onto→ℕ0 ∧ (card‘𝐵) ∈ ω) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵))) = (card‘𝐵))
4234, 40, 41sylancr 587 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵))) = (card‘𝐵))
4333, 38, 423eqtr3d 2779 . . . . . . 7 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (card‘𝐵))
44 oveq2 7401 . . . . . . . . 9 (𝑦 = (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) → ((card‘𝐴) +o 𝑦) = ((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))
4544eqeq1d 2733 . . . . . . . 8 (𝑦 = (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) → (((card‘𝐴) +o 𝑦) = (card‘𝐵) ↔ ((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (card‘𝐵)))
4645rspcev 3609 . . . . . . 7 (((card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω ∧ ((card‘𝐴) +o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (card‘𝐵)) → ∃𝑦 ∈ ω ((card‘𝐴) +o 𝑦) = (card‘𝐵))
473, 43, 46sylancr 587 . . . . . 6 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ∃𝑦 ∈ ω ((card‘𝐴) +o 𝑦) = (card‘𝐵))
4847ex 413 . . . . 5 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) → ∃𝑦 ∈ ω ((card‘𝐴) +o 𝑦) = (card‘𝐵)))
49 cardnn 9940 . . . . . . . . . 10 (𝑦 ∈ ω → (card‘𝑦) = 𝑦)
5049adantl 482 . . . . . . . . 9 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (card‘𝑦) = 𝑦)
5150oveq2d 7409 . . . . . . . 8 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → ((card‘𝐴) +o (card‘𝑦)) = ((card‘𝐴) +o 𝑦))
5251eqeq1d 2733 . . . . . . 7 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (((card‘𝐴) +o (card‘𝑦)) = (card‘𝐵) ↔ ((card‘𝐴) +o 𝑦) = (card‘𝐵)))
53 fveq2 6878 . . . . . . . 8 (((card‘𝐴) +o (card‘𝑦)) = (card‘𝐵) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘𝑦))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)))
54 nnfi 9150 . . . . . . . . 9 (𝑦 ∈ ω → 𝑦 ∈ Fin)
55 ficardom 9938 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin → (card‘𝑦) ∈ ω)
564hashgadd 14319 . . . . . . . . . . . . . 14 (((card‘𝐴) ∈ ω ∧ (card‘𝑦) ∈ ω) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘𝑦))) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦))))
5726, 55, 56syl2an 596 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘𝑦))) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦))))
584hashgval 14275 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦)) = (♯‘𝑦))
595, 58oveqan12d 7412 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦))) = ((♯‘𝐴) + (♯‘𝑦)))
6057, 59eqtrd 2771 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘𝑦))) = ((♯‘𝐴) + (♯‘𝑦)))
6160adantlr 713 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘𝑦))) = ((♯‘𝐴) + (♯‘𝑦)))
6230ad2antlr 725 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
6361, 62eqeq12d 2747 . . . . . . . . . 10 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +o (card‘𝑦))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) ↔ ((♯‘𝐴) + (♯‘𝑦)) = (♯‘𝐵)))
64 hashcl 14298 . . . . . . . . . . . . . . 15 (𝑦 ∈ Fin → (♯‘𝑦) ∈ ℕ0)
6564nn0ge0d 12517 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin → 0 ≤ (♯‘𝑦))
6665adantl 482 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → 0 ≤ (♯‘𝑦))
679nn0red 12515 . . . . . . . . . . . . . 14 (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℝ)
6864nn0red 12515 . . . . . . . . . . . . . 14 (𝑦 ∈ Fin → (♯‘𝑦) ∈ ℝ)
69 addge01 11706 . . . . . . . . . . . . . 14 (((♯‘𝐴) ∈ ℝ ∧ (♯‘𝑦) ∈ ℝ) → (0 ≤ (♯‘𝑦) ↔ (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦))))
7067, 68, 69syl2an 596 . . . . . . . . . . . . 13 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (0 ≤ (♯‘𝑦) ↔ (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦))))
7166, 70mpbid 231 . . . . . . . . . . . 12 ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦)))
7271adantlr 713 . . . . . . . . . . 11 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦)))
73 breq2 5145 . . . . . . . . . . 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 593 . . . . . . . 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 259 . . . . . 6 (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (((card‘𝐴) +o 𝑦) = (card‘𝐵) → (♯‘𝐴) ≤ (♯‘𝐵)))
7978rexlimdva 3154 . . . . 5 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (∃𝑦 ∈ ω ((card‘𝐴) +o 𝑦) = (card‘𝐵) → (♯‘𝐴) ≤ (♯‘𝐵)))
8048, 79impbid 211 . . . 4 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ ∃𝑦 ∈ ω ((card‘𝐴) +o 𝑦) = (card‘𝐵)))
81 nnawordex 8620 . . . . 5 (((card‘𝐴) ∈ ω ∧ (card‘𝐵) ∈ ω) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ ∃𝑦 ∈ ω ((card‘𝐴) +o 𝑦) = (card‘𝐵)))
8226, 39, 81syl2an 596 . . . 4 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ ∃𝑦 ∈ ω ((card‘𝐴) +o 𝑦) = (card‘𝐵)))
83 finnum 9925 . . . . 5 (𝐴 ∈ Fin → 𝐴 ∈ dom card)
84 finnum 9925 . . . . 5 (𝐵 ∈ Fin → 𝐵 ∈ dom card)
85 carddom2 9954 . . . . 5 ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ 𝐴𝐵))
8683, 84, 85syl2an 596 . . . 4 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ 𝐴𝐵))
8780, 82, 863bitr2d 306 . . 3 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴𝐵))
8887adantlr 713 . 2 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴𝐵))
89 hashxrcl 14299 . . . . . 6 (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℝ*)
9089ad2antrr 724 . . . . 5 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐴) ∈ ℝ*)
91 pnfge 13092 . . . . 5 ((♯‘𝐴) ∈ ℝ* → (♯‘𝐴) ≤ +∞)
9290, 91syl 17 . . . 4 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐴) ≤ +∞)
93 hashinf 14277 . . . . 5 ((𝐵𝑉 ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐵) = +∞)
9493adantll 712 . . . 4 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐵) = +∞)
9592, 94breqtrrd 5169 . . 3 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐴) ≤ (♯‘𝐵))
96 isinffi 9969 . . . . . 6 ((¬ 𝐵 ∈ Fin ∧ 𝐴 ∈ Fin) → ∃𝑓 𝑓:𝐴1-1𝐵)
9796ancoms 459 . . . . 5 ((𝐴 ∈ Fin ∧ ¬ 𝐵 ∈ Fin) → ∃𝑓 𝑓:𝐴1-1𝐵)
9897adantlr 713 . . . 4 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → ∃𝑓 𝑓:𝐴1-1𝐵)
99 brdomg 8935 . . . . 5 (𝐵𝑉 → (𝐴𝐵 ↔ ∃𝑓 𝑓:𝐴1-1𝐵))
10099ad2antlr 725 . . . 4 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → (𝐴𝐵 ↔ ∃𝑓 𝑓:𝐴1-1𝐵))
10198, 100mpbird 256 . . 3 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → 𝐴𝐵)
10295, 1012thd 264 . 2 (((𝐴 ∈ Fin ∧ 𝐵𝑉) ∧ ¬ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴𝐵))
10388, 102pm2.61dan 811 1 ((𝐴 ∈ Fin ∧ 𝐵𝑉) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴𝐵))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 205  wa 396   = wceq 1541  wex 1781  wcel 2106  wrex 3069  Vcvv 3473  wss 3944   class class class wbr 5141  cmpt 5224  ccnv 5668  dom cdm 5669  cres 5671  1-1wf1 6529  1-1-ontowf1o 6531  cfv 6532  (class class class)co 7393  ωcom 7838  reccrdg 8391   +o coa 8445  cdom 8920  Fincfn 8922  cardccrd 9912  cc 11090  cr 11091  0cc0 11092  1c1 11093   + caddc 11095  +∞cpnf 11227  *cxr 11229  cle 11231  cmin 11426  0cn0 12454  ...cfz 13466  chash 14272
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 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2702  ax-sep 5292  ax-nul 5299  ax-pow 5356  ax-pr 5420  ax-un 7708  ax-cnex 11148  ax-resscn 11149  ax-1cn 11150  ax-icn 11151  ax-addcl 11152  ax-addrcl 11153  ax-mulcl 11154  ax-mulrcl 11155  ax-mulcom 11156  ax-addass 11157  ax-mulass 11158  ax-distr 11159  ax-i2m1 11160  ax-1ne0 11161  ax-1rid 11162  ax-rnegex 11163  ax-rrecex 11164  ax-cnre 11165  ax-pre-lttri 11166  ax-pre-lttrn 11167  ax-pre-ltadd 11168  ax-pre-mulgt0 11169
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3or 1088  df-3an 1089  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2533  df-eu 2562  df-clab 2709  df-cleq 2723  df-clel 2809  df-nfc 2884  df-ne 2940  df-nel 3046  df-ral 3061  df-rex 3070  df-reu 3376  df-rab 3432  df-v 3475  df-sbc 3774  df-csb 3890  df-dif 3947  df-un 3949  df-in 3951  df-ss 3961  df-pss 3963  df-nul 4319  df-if 4523  df-pw 4598  df-sn 4623  df-pr 4625  df-op 4629  df-uni 4902  df-int 4944  df-iun 4992  df-br 5142  df-opab 5204  df-mpt 5225  df-tr 5259  df-id 5567  df-eprel 5573  df-po 5581  df-so 5582  df-fr 5624  df-we 5626  df-xp 5675  df-rel 5676  df-cnv 5677  df-co 5678  df-dm 5679  df-rn 5680  df-res 5681  df-ima 5682  df-pred 6289  df-ord 6356  df-on 6357  df-lim 6358  df-suc 6359  df-iota 6484  df-fun 6534  df-fn 6535  df-f 6536  df-f1 6537  df-fo 6538  df-f1o 6539  df-fv 6540  df-riota 7349  df-ov 7396  df-oprab 7397  df-mpo 7398  df-om 7839  df-1st 7957  df-2nd 7958  df-frecs 8248  df-wrecs 8279  df-recs 8353  df-rdg 8392  df-1o 8448  df-oadd 8452  df-er 8686  df-en 8923  df-dom 8924  df-sdom 8925  df-fin 8926  df-card 9916  df-pnf 11232  df-mnf 11233  df-xr 11234  df-ltxr 11235  df-le 11236  df-sub 11428  df-neg 11429  df-nn 12195  df-n0 12455  df-xnn0 12527  df-z 12541  df-uz 12805  df-fz 13467  df-hash 14273
This theorem is referenced by:  hashdomi  14322  hashsdom  14323  hashun2  14325  hashss  14351  hashsslei  14368  hashfun  14379  hashf1  14400  hashge3el3dif  14429  isercoll  15596  phicl2  16683  phibnd  16686  prmreclem2  16832  prmreclem3  16833  4sqlem11  16870  vdwlem11  16906  ramub2  16929  0ram  16935  ram0  16937  sylow1lem4  19433  pgpssslw  19446  fislw  19457  znfld  21049  znidomb  21050  fta1blem  25615  birthdaylem3  26385  basellem4  26515  ppiwordi  26593  musum  26622  ppiub  26634  chpub  26650  lgsqrlem4  26779  upgrex  28217  sizusglecusg  28585  derangenlem  33991  subfaclefac  33996  erdsze2lem1  34023  snmlff  34149  idomsubgmo  41709  aacllem  47494
  Copyright terms: Public domain W3C validator