hashdom - Metamath Proof Explorer

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

Theorem hashdom 14351

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.

Step	Hyp	Ref	Expression
1		fzfi 13944	. . . . . . . 8 ⊢ (1...((♯‘𝐵) − (♯‘𝐴))) ∈ Fin
2		ficardom 9921	. . . . . . . 8 ⊢ ((1...((♯‘𝐵) − (♯‘𝐴))) ∈ Fin → (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω)
3	1, 2	ax-mp 5	. . . . . . 7 ⊢ (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω
4		eqid 2730	. . . . . . . . . . . . . 14 ⊢ (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
5	4	hashgval 14305	. . . . . . . . . . . . 13 ⊢ (𝐴 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = (♯‘𝐴))
6	5	ad2antrr 726	. . . . . . . . . . . 12 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = (♯‘𝐴))
7	4	hashgval 14305	. . . . . . . . . . . . . 14 ⊢ ((1...((♯‘𝐵) − (♯‘𝐴))) ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (♯‘(1...((♯‘𝐵) − (♯‘𝐴)))))
8	1, 7	ax-mp 5	. . . . . . . . . . . . 13 ⊢ ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (♯‘(1...((♯‘𝐵) − (♯‘𝐴))))
9		hashcl 14328	. . . . . . . . . . . . . . . 16 ⊢ (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℕ₀)
10	9	ad2antrr 726	. . . . . . . . . . . . . . 15 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘𝐴) ∈ ℕ₀)
11		hashcl 14328	. . . . . . . . . . . . . . . 16 ⊢ (𝐵 ∈ Fin → (♯‘𝐵) ∈ ℕ₀)
12	11	ad2antlr 727	. . . . . . . . . . . . . . 15 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘𝐵) ∈ ℕ₀)
13		simpr 484	. . . . . . . . . . . . . . 15 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘𝐴) ≤ (♯‘𝐵))
14		nn0sub2 12602	. . . . . . . . . . . . . . 15 ⊢ (((♯‘𝐴) ∈ ℕ₀ ∧ (♯‘𝐵) ∈ ℕ₀ ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((♯‘𝐵) − (♯‘𝐴)) ∈ ℕ₀)
15	10, 12, 13, 14	syl3anc 1373	. . . . . . . . . . . . . 14 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((♯‘𝐵) − (♯‘𝐴)) ∈ ℕ₀)
16		hashfz1 14318	. . . . . . . . . . . . . 14 ⊢ (((♯‘𝐵) − (♯‘𝐴)) ∈ ℕ₀ → (♯‘(1...((♯‘𝐵) − (♯‘𝐴)))) = ((♯‘𝐵) − (♯‘𝐴)))
17	15, 16	syl 17	. . . . . . . . . . . . 13 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (♯‘(1...((♯‘𝐵) − (♯‘𝐴)))) = ((♯‘𝐵) − (♯‘𝐴)))
18	8, 17	eqtrid 2777	. . . . . . . . . . . 12 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = ((♯‘𝐵) − (♯‘𝐴)))
19	6, 18	oveq12d 7408	. . . . . . . . . . 11 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))))
20	9	nn0cnd 12512	. . . . . . . . . . . . 13 ⊢ (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℂ)
21	11	nn0cnd 12512	. . . . . . . . . . . . 13 ⊢ (𝐵 ∈ Fin → (♯‘𝐵) ∈ ℂ)
22		pncan3 11436	. . . . . . . . . . . . 13 ⊢ (((♯‘𝐴) ∈ ℂ ∧ (♯‘𝐵) ∈ ℂ) → ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))) = (♯‘𝐵))
23	20, 21, 22	syl2an 596	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))) = (♯‘𝐵))
24	23	adantr 480	. . . . . . . . . . 11 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((♯‘𝐴) + ((♯‘𝐵) − (♯‘𝐴))) = (♯‘𝐵))
25	19, 24	eqtrd 2765	. . . . . . . . . 10 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = (♯‘𝐵))
26		ficardom 9921	. . . . . . . . . . . 12 ⊢ (𝐴 ∈ Fin → (card‘𝐴) ∈ ω)
27	26	ad2antrr 726	. . . . . . . . . . 11 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (card‘𝐴) ∈ ω)
28	4	hashgadd 14349	. . . . . . . . . . 11 ⊢ (((card‘𝐴) ∈ ω ∧ (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴)))))))
29	27, 3, 28	sylancl 586	. . . . . . . . . 10 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘(1...((♯‘𝐵) − (♯‘𝐴)))))))
30	4	hashgval 14305	. . . . . . . . . . 11 ⊢ (𝐵 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
31	30	ad2antlr 727	. . . . . . . . . 10 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
32	25, 29, 31	3eqtr4d 2775	. . . . . . . . 9 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴)))))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)))
33	32	fveq2d 6865	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (^◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))) = (^◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵))))
34	4	hashgf1o 13943	. . . . . . . . 9 ⊢ (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω):ω–1-1-onto→ℕ₀
35		nnacl 8578	. . . . . . . . . 10 ⊢ (((card‘𝐴) ∈ ω ∧ (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω) → ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) ∈ ω)
36	27, 3, 35	sylancl 586	. . . . . . . . 9 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) ∈ ω)
37		f1ocnvfv1 7254	. . . . . . . . 9 ⊢ (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω):ω–1-1-onto→ℕ₀ ∧ ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) ∈ ω) → (^◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))) = ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))
38	34, 36, 37	sylancr 587	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (^◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))) = ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))
39		ficardom 9921	. . . . . . . . . 10 ⊢ (𝐵 ∈ Fin → (card‘𝐵) ∈ ω)
40	39	ad2antlr 727	. . . . . . . . 9 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (card‘𝐵) ∈ ω)
41		f1ocnvfv1 7254	. . . . . . . . 9 ⊢ (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω):ω–1-1-onto→ℕ₀ ∧ (card‘𝐵) ∈ ω) → (^◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵))) = (card‘𝐵))
42	34, 40, 41	sylancr 587	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → (^◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵))) = (card‘𝐵))
43	33, 38, 42	3eqtr3d 2773	. . . . . . 7 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (card‘𝐵))
44		oveq2 7398	. . . . . . . . 9 ⊢ (𝑦 = (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) → ((card‘𝐴) +_o 𝑦) = ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))))
45	44	eqeq1d 2732	. . . . . . . 8 ⊢ (𝑦 = (card‘(1...((♯‘𝐵) − (♯‘𝐴)))) → (((card‘𝐴) +_o 𝑦) = (card‘𝐵) ↔ ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (card‘𝐵)))
46	45	rspcev 3591	. . . . . . 7 ⊢ (((card‘(1...((♯‘𝐵) − (♯‘𝐴)))) ∈ ω ∧ ((card‘𝐴) +_o (card‘(1...((♯‘𝐵) − (♯‘𝐴))))) = (card‘𝐵)) → ∃𝑦 ∈ ω ((card‘𝐴) +_o 𝑦) = (card‘𝐵))
47	3, 43, 46	sylancr 587	. . . . . 6 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (♯‘𝐴) ≤ (♯‘𝐵)) → ∃𝑦 ∈ ω ((card‘𝐴) +_o 𝑦) = (card‘𝐵))
48	47	ex 412	. . . . 5 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) → ∃𝑦 ∈ ω ((card‘𝐴) +_o 𝑦) = (card‘𝐵)))
49		cardnn 9923	. . . . . . . . . 10 ⊢ (𝑦 ∈ ω → (card‘𝑦) = 𝑦)
50	49	adantl 481	. . . . . . . . 9 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (card‘𝑦) = 𝑦)
51	50	oveq2d 7406	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → ((card‘𝐴) +_o (card‘𝑦)) = ((card‘𝐴) +_o 𝑦))
52	51	eqeq1d 2732	. . . . . . 7 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (((card‘𝐴) +_o (card‘𝑦)) = (card‘𝐵) ↔ ((card‘𝐴) +_o 𝑦) = (card‘𝐵)))
53		fveq2 6861	. . . . . . . 8 ⊢ (((card‘𝐴) +_o (card‘𝑦)) = (card‘𝐵) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)))
54		nnfi 9137	. . . . . . . . 9 ⊢ (𝑦 ∈ ω → 𝑦 ∈ Fin)
55		ficardom 9921	. . . . . . . . . . . . . 14 ⊢ (𝑦 ∈ Fin → (card‘𝑦) ∈ ω)
56	4	hashgadd 14349	. . . . . . . . . . . . . 14 ⊢ (((card‘𝐴) ∈ ω ∧ (card‘𝑦) ∈ ω) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦))))
57	26, 55, 56	syl2an 596	. . . . . . . . . . . . 13 ⊢ ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦))))
58	4	hashgval 14305	. . . . . . . . . . . . . 14 ⊢ (𝑦 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦)) = (♯‘𝑦))
59	5, 58	oveqan12d 7409	. . . . . . . . . . . . 13 ⊢ ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) + ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝑦))) = ((♯‘𝐴) + (♯‘𝑦)))
60	57, 59	eqtrd 2765	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = ((♯‘𝐴) + (♯‘𝑦)))
61	60	adantlr 715	. . . . . . . . . . 11 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = ((♯‘𝐴) + (♯‘𝑦)))
62	30	ad2antlr 727	. . . . . . . . . . 11 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
63	61, 62	eqeq12d 2746	. . . . . . . . . 10 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) ↔ ((♯‘𝐴) + (♯‘𝑦)) = (♯‘𝐵)))
64		hashcl 14328	. . . . . . . . . . . . . . 15 ⊢ (𝑦 ∈ Fin → (♯‘𝑦) ∈ ℕ₀)
65	64	nn0ge0d 12513	. . . . . . . . . . . . . 14 ⊢ (𝑦 ∈ Fin → 0 ≤ (♯‘𝑦))
66	65	adantl 481	. . . . . . . . . . . . 13 ⊢ ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → 0 ≤ (♯‘𝑦))
67	9	nn0red 12511	. . . . . . . . . . . . . 14 ⊢ (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℝ)
68	64	nn0red 12511	. . . . . . . . . . . . . 14 ⊢ (𝑦 ∈ Fin → (♯‘𝑦) ∈ ℝ)
69		addge01 11695	. . . . . . . . . . . . . 14 ⊢ (((♯‘𝐴) ∈ ℝ ∧ (♯‘𝑦) ∈ ℝ) → (0 ≤ (♯‘𝑦) ↔ (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦))))
70	67, 68, 69	syl2an 596	. . . . . . . . . . . . 13 ⊢ ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (0 ≤ (♯‘𝑦) ↔ (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦))))
71	66, 70	mpbid 232	. . . . . . . . . . . 12 ⊢ ((𝐴 ∈ Fin ∧ 𝑦 ∈ Fin) → (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦)))
72	71	adantlr 715	. . . . . . . . . . 11 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → (♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦)))
73		breq2 5114	. . . . . . . . . . 11 ⊢ (((♯‘𝐴) + (♯‘𝑦)) = (♯‘𝐵) → ((♯‘𝐴) ≤ ((♯‘𝐴) + (♯‘𝑦)) ↔ (♯‘𝐴) ≤ (♯‘𝐵)))
74	72, 73	syl5ibcom 245	. . . . . . . . . 10 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → (((♯‘𝐴) + (♯‘𝑦)) = (♯‘𝐵) → (♯‘𝐴) ≤ (♯‘𝐵)))
75	63, 74	sylbid 240	. . . . . . . . 9 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) → (♯‘𝐴) ≤ (♯‘𝐵)))
76	54, 75	sylan2 593	. . . . . . . 8 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘((card‘𝐴) +_o (card‘𝑦))) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) → (♯‘𝐴) ≤ (♯‘𝐵)))
77	53, 76	syl5 34	. . . . . . 7 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (((card‘𝐴) +_o (card‘𝑦)) = (card‘𝐵) → (♯‘𝐴) ≤ (♯‘𝐵)))
78	52, 77	sylbird 260	. . . . . 6 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ 𝑦 ∈ ω) → (((card‘𝐴) +_o 𝑦) = (card‘𝐵) → (♯‘𝐴) ≤ (♯‘𝐵)))
79	78	rexlimdva 3135	. . . . 5 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (∃𝑦 ∈ ω ((card‘𝐴) +_o 𝑦) = (card‘𝐵) → (♯‘𝐴) ≤ (♯‘𝐵)))
80	48, 79	impbid 212	. . . 4 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ ∃𝑦 ∈ ω ((card‘𝐴) +_o 𝑦) = (card‘𝐵)))
81		nnawordex 8604	. . . . 5 ⊢ (((card‘𝐴) ∈ ω ∧ (card‘𝐵) ∈ ω) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ ∃𝑦 ∈ ω ((card‘𝐴) +_o 𝑦) = (card‘𝐵)))
82	26, 39, 81	syl2an 596	. . . 4 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ ∃𝑦 ∈ ω ((card‘𝐴) +_o 𝑦) = (card‘𝐵)))
83		finnum 9908	. . . . 5 ⊢ (𝐴 ∈ Fin → 𝐴 ∈ dom card)
84		finnum 9908	. . . . 5 ⊢ (𝐵 ∈ Fin → 𝐵 ∈ dom card)
85		carddom2 9937	. . . . 5 ⊢ ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ 𝐴 ≼ 𝐵))
86	83, 84, 85	syl2an 596	. . . 4 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) ⊆ (card‘𝐵) ↔ 𝐴 ≼ 𝐵))
87	80, 82, 86	3bitr2d 307	. . 3 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴 ≼ 𝐵))
88	87	adantlr 715	. 2 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴 ≼ 𝐵))
89		hashxrcl 14329	. . . . . 6 ⊢ (𝐴 ∈ Fin → (♯‘𝐴) ∈ ℝ^*)
90	89	ad2antrr 726	. . . . 5 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐴) ∈ ℝ^*)
91		pnfge 13097	. . . . 5 ⊢ ((♯‘𝐴) ∈ ℝ^* → (♯‘𝐴) ≤ +∞)
92	90, 91	syl 17	. . . 4 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐴) ≤ +∞)
93		hashinf 14307	. . . . 5 ⊢ ((𝐵 ∈ 𝑉 ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐵) = +∞)
94	93	adantll 714	. . . 4 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐵) = +∞)
95	92, 94	breqtrrd 5138	. . 3 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → (♯‘𝐴) ≤ (♯‘𝐵))
96		isinffi 9952	. . . . . 6 ⊢ ((¬ 𝐵 ∈ Fin ∧ 𝐴 ∈ Fin) → ∃𝑓 𝑓:𝐴–1-1→𝐵)
97	96	ancoms 458	. . . . 5 ⊢ ((𝐴 ∈ Fin ∧ ¬ 𝐵 ∈ Fin) → ∃𝑓 𝑓:𝐴–1-1→𝐵)
98	97	adantlr 715	. . . 4 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → ∃𝑓 𝑓:𝐴–1-1→𝐵)
99		brdomg 8933	. . . . 5 ⊢ (𝐵 ∈ 𝑉 → (𝐴 ≼ 𝐵 ↔ ∃𝑓 𝑓:𝐴–1-1→𝐵))
100	99	ad2antlr 727	. . . 4 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → (𝐴 ≼ 𝐵 ↔ ∃𝑓 𝑓:𝐴–1-1→𝐵))
101	98, 100	mpbird 257	. . 3 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → 𝐴 ≼ 𝐵)
102	95, 101	2thd 265	. 2 ⊢ (((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) ∧ ¬ 𝐵 ∈ Fin) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴 ≼ 𝐵))
103	88, 102	pm2.61dan 812	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ 𝑉) → ((♯‘𝐴) ≤ (♯‘𝐵) ↔ 𝐴 ≼ 𝐵))

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 → wi 4 ↔ wb 206 ∧ wa 395 = wceq 1540 ∃wex 1779 ∈ wcel 2109 ∃wrex 3054 Vcvv 3450 ⊆ wss 3917 class class class wbr 5110 ↦ cmpt 5191 ^◡ccnv 5640 dom cdm 5641 ↾ cres 5643 –1-1→wf1 6511 –1-1-onto→wf1o 6513 ‘cfv 6514 (class class class)co 7390 ωcom 7845 reccrdg 8380 +_o coa 8434 ≼ cdom 8919 Fincfn 8921 cardccrd 9895 ℂcc 11073 ℝcr 11074 0cc0 11075 1c1 11076 + caddc 11078 +∞cpnf 11212 ℝ^*cxr 11214 ≤ cle 11216 − cmin 11412 ℕ₀cn0 12449 ...cfz 13475 ♯chash 14302

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 2702 ax-sep 5254 ax-nul 5264 ax-pow 5323 ax-pr 5390 ax-un 7714 ax-cnex 11131 ax-resscn 11132 ax-1cn 11133 ax-icn 11134 ax-addcl 11135 ax-addrcl 11136 ax-mulcl 11137 ax-mulrcl 11138 ax-mulcom 11139 ax-addass 11140 ax-mulass 11141 ax-distr 11142 ax-i2m1 11143 ax-1ne0 11144 ax-1rid 11145 ax-rnegex 11146 ax-rrecex 11147 ax-cnre 11148 ax-pre-lttri 11149 ax-pre-lttrn 11150 ax-pre-ltadd 11151 ax-pre-mulgt0 11152

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 2534 df-eu 2563 df-clab 2709 df-cleq 2722 df-clel 2804 df-nfc 2879 df-ne 2927 df-nel 3031 df-ral 3046 df-rex 3055 df-reu 3357 df-rab 3409 df-v 3452 df-sbc 3757 df-csb 3866 df-dif 3920 df-un 3922 df-in 3924 df-ss 3934 df-pss 3937 df-nul 4300 df-if 4492 df-pw 4568 df-sn 4593 df-pr 4595 df-op 4599 df-uni 4875 df-int 4914 df-iun 4960 df-br 5111 df-opab 5173 df-mpt 5192 df-tr 5218 df-id 5536 df-eprel 5541 df-po 5549 df-so 5550 df-fr 5594 df-we 5596 df-xp 5647 df-rel 5648 df-cnv 5649 df-co 5650 df-dm 5651 df-rn 5652 df-res 5653 df-ima 5654 df-pred 6277 df-ord 6338 df-on 6339 df-lim 6340 df-suc 6341 df-iota 6467 df-fun 6516 df-fn 6517 df-f 6518 df-f1 6519 df-fo 6520 df-f1o 6521 df-fv 6522 df-riota 7347 df-ov 7393 df-oprab 7394 df-mpo 7395 df-om 7846 df-1st 7971 df-2nd 7972 df-frecs 8263 df-wrecs 8294 df-recs 8343 df-rdg 8381 df-1o 8437 df-oadd 8441 df-er 8674 df-en 8922 df-dom 8923 df-sdom 8924 df-fin 8925 df-card 9899 df-pnf 11217 df-mnf 11218 df-xr 11219 df-ltxr 11220 df-le 11221 df-sub 11414 df-neg 11415 df-nn 12194 df-n0 12450 df-xnn0 12523 df-z 12537 df-uz 12801 df-fz 13476 df-hash 14303

This theorem is referenced by: hashdomi 14352 hashsdom 14353 hashun2 14355 hashss 14381 hashsslei 14398 hashfun 14409 hashf1 14429 hashge3el3dif 14459 isercoll 15641 phicl2 16745 phibnd 16748 prmreclem2 16895 prmreclem3 16896 4sqlem11 16933 vdwlem11 16969 ramub2 16992 0ram 16998 ram0 17000 sylow1lem4 19538 pgpssslw 19551 fislw 19562 znfld 21477 znidomb 21478 fta1blem 26083 birthdaylem3 26870 basellem4 27001 ppiwordi 27079 musum 27108 ppiub 27122 chpub 27138 lgsqrlem4 27267 upgrex 29026 sizusglecusg 29398 derangenlem 35165 subfaclefac 35170 erdsze2lem1 35197 snmlff 35323 hashnexinj 42123 idomsubgmo 43189 aacllem 49794

W3C validator