Theorem hashkf 14367

Description: The finite part of the size function maps all finite sets to their cardinality, as members of ℕ₀. (Contributed by Mario Carneiro, 13-Sep-2013.) (Revised by Mario Carneiro, 26-Dec-2014.)

Hypotheses

Ref	Expression
hashgval.1	⊢ 𝐺 = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
hashkf.2	⊢ 𝐾 = (𝐺 ∘ card)

Assertion

Ref	Expression
hashkf	⊢ 𝐾:Fin⟶ℕ0

Proof of Theorem hashkf

Dummy variable 𝑦 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		frfnom 8473	. . . . . . 7 ⊢ (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) Fn ω
2		hashgval.1	. . . . . . . 8 ⊢ 𝐺 = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
3	2	fneq1i 6665	. . . . . . 7 ⊢ (𝐺 Fn ω ↔ (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) Fn ω)
4	1, 3	mpbir 231	. . . . . 6 ⊢ 𝐺 Fn ω
5		fnfun 6668	. . . . . 6 ⊢ (𝐺 Fn ω → Fun 𝐺)
6	4, 5	ax-mp 5	. . . . 5 ⊢ Fun 𝐺
7		cardf2 9980	. . . . . 6 ⊢ card:{𝑦 ∣ ∃𝑥 ∈ On 𝑥 ≈ 𝑦}⟶On
8		ffun 6739	. . . . . 6 ⊢ (card:{𝑦 ∣ ∃𝑥 ∈ On 𝑥 ≈ 𝑦}⟶On → Fun card)
9	7, 8	ax-mp 5	. . . . 5 ⊢ Fun card
10		funco 6607	. . . . 5 ⊢ ((Fun 𝐺 ∧ Fun card) → Fun (𝐺 ∘ card))
11	6, 9, 10	mp2an 692	. . . 4 ⊢ Fun (𝐺 ∘ card)
12		dmco 6275	. . . . 5 ⊢ dom (𝐺 ∘ card) = (◡card “ dom 𝐺)
13	4	fndmi 6672	. . . . . 6 ⊢ dom 𝐺 = ω
14	13	imaeq2i 6077	. . . . 5 ⊢ (◡card “ dom 𝐺) = (◡card “ ω)
15		funfn 6597	. . . . . . . . 9 ⊢ (Fun card ↔ card Fn dom card)
16	9, 15	mpbi 230	. . . . . . . 8 ⊢ card Fn dom card
17		elpreima 7077	. . . . . . . 8 ⊢ (card Fn dom card → (𝑦 ∈ (◡card “ ω) ↔ (𝑦 ∈ dom card ∧ (card‘𝑦) ∈ ω)))
18	16, 17	ax-mp 5	. . . . . . 7 ⊢ (𝑦 ∈ (◡card “ ω) ↔ (𝑦 ∈ dom card ∧ (card‘𝑦) ∈ ω))
19		id 22	. . . . . . . . . 10 ⊢ ((card‘𝑦) ∈ ω → (card‘𝑦) ∈ ω)
20		cardid2 9990	. . . . . . . . . . 11 ⊢ (𝑦 ∈ dom card → (card‘𝑦) ≈ 𝑦)
21	20	ensymd 9043	. . . . . . . . . 10 ⊢ (𝑦 ∈ dom card → 𝑦 ≈ (card‘𝑦))
22		breq2 5151	. . . . . . . . . . 11 ⊢ (𝑥 = (card‘𝑦) → (𝑦 ≈ 𝑥 ↔ 𝑦 ≈ (card‘𝑦)))
23	22	rspcev 3621	. . . . . . . . . 10 ⊢ (((card‘𝑦) ∈ ω ∧ 𝑦 ≈ (card‘𝑦)) → ∃𝑥 ∈ ω 𝑦 ≈ 𝑥)
24	19, 21, 23	syl2anr 597	. . . . . . . . 9 ⊢ ((𝑦 ∈ dom card ∧ (card‘𝑦) ∈ ω) → ∃𝑥 ∈ ω 𝑦 ≈ 𝑥)
25		isfi 9014	. . . . . . . . 9 ⊢ (𝑦 ∈ Fin ↔ ∃𝑥 ∈ ω 𝑦 ≈ 𝑥)
26	24, 25	sylibr 234	. . . . . . . 8 ⊢ ((𝑦 ∈ dom card ∧ (card‘𝑦) ∈ ω) → 𝑦 ∈ Fin)
27		finnum 9985	. . . . . . . . 9 ⊢ (𝑦 ∈ Fin → 𝑦 ∈ dom card)
28		ficardom 9998	. . . . . . . . 9 ⊢ (𝑦 ∈ Fin → (card‘𝑦) ∈ ω)
29	27, 28	jca 511	. . . . . . . 8 ⊢ (𝑦 ∈ Fin → (𝑦 ∈ dom card ∧ (card‘𝑦) ∈ ω))
30	26, 29	impbii 209	. . . . . . 7 ⊢ ((𝑦 ∈ dom card ∧ (card‘𝑦) ∈ ω) ↔ 𝑦 ∈ Fin)
31	18, 30	bitri 275	. . . . . 6 ⊢ (𝑦 ∈ (◡card “ ω) ↔ 𝑦 ∈ Fin)
32	31	eqriv 2731	. . . . 5 ⊢ (◡card “ ω) = Fin
33	12, 14, 32	3eqtri 2766	. . . 4 ⊢ dom (𝐺 ∘ card) = Fin
34		df-fn 6565	. . . 4 ⊢ ((𝐺 ∘ card) Fn Fin ↔ (Fun (𝐺 ∘ card) ∧ dom (𝐺 ∘ card) = Fin))
35	11, 33, 34	mpbir2an 711	. . 3 ⊢ (𝐺 ∘ card) Fn Fin
36		hashkf.2	. . . 4 ⊢ 𝐾 = (𝐺 ∘ card)
37	36	fneq1i 6665	. . 3 ⊢ (𝐾 Fn Fin ↔ (𝐺 ∘ card) Fn Fin)
38	35, 37	mpbir 231	. 2 ⊢ 𝐾 Fn Fin
39	36	fveq1i 6907	. . . . 5 ⊢ (𝐾‘𝑦) = ((𝐺 ∘ card)‘𝑦)
40		fvco 7006	. . . . . 6 ⊢ ((Fun card ∧ 𝑦 ∈ dom card) → ((𝐺 ∘ card)‘𝑦) = (𝐺‘(card‘𝑦)))
41	9, 27, 40	sylancr 587	. . . . 5 ⊢ (𝑦 ∈ Fin → ((𝐺 ∘ card)‘𝑦) = (𝐺‘(card‘𝑦)))
42	39, 41	eqtrid 2786	. . . 4 ⊢ (𝑦 ∈ Fin → (𝐾‘𝑦) = (𝐺‘(card‘𝑦)))
43	2	hashgf1o 14008	. . . . . . 7 ⊢ 𝐺:ω–1-1-onto→ℕ0
44		f1of 6848	. . . . . . 7 ⊢ (𝐺:ω–1-1-onto→ℕ0 → 𝐺:ω⟶ℕ0)
45	43, 44	ax-mp 5	. . . . . 6 ⊢ 𝐺:ω⟶ℕ0
46	45	ffvelcdmi 7102	. . . . 5 ⊢ ((card‘𝑦) ∈ ω → (𝐺‘(card‘𝑦)) ∈ ℕ0)
47	28, 46	syl 17	. . . 4 ⊢ (𝑦 ∈ Fin → (𝐺‘(card‘𝑦)) ∈ ℕ0)
48	42, 47	eqeltrd 2838	. . 3 ⊢ (𝑦 ∈ Fin → (𝐾‘𝑦) ∈ ℕ0)
49	48	rgen 3060	. 2 ⊢ ∀𝑦 ∈ Fin (𝐾‘𝑦) ∈ ℕ0
50		ffnfv 7138	. 2 ⊢ (𝐾:Fin⟶ℕ0 ↔ (𝐾 Fn Fin ∧ ∀𝑦 ∈ Fin (𝐾‘𝑦) ∈ ℕ0))
51	38, 49, 50	mpbir2an 711	1 ⊢ 𝐾:Fin⟶ℕ0

Syntax hints:   ↔ wb 206   ∧ wa 395   = wceq 1536   ∈ wcel 2105  {cab 2711  ∀wral 3058  ∃wrex 3067  Vcvv 3477   class class class wbr 5147   ↦ cmpt 5230  ^◡ccnv 5687  dom cdm 5688   ↾ cres 5690   “ cima 5691   ∘ ccom 5692  Oncon0 6385  Fun wfun 6556   Fn wfn 6557  ⟶wf 6558  –1-1-onto→wf1o 6561  ‘cfv 6562  (class class class)co 7430  ωcom 7886  reccrdg 8447   ≈ cen 8980  Fincfn 8983  cardccrd 9972  0cc0 11152  1c1 11153   + caddc 11155  ℕ₀cn0 12523

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1791  ax-4 1805  ax-5 1907  ax-6 1964  ax-7 2004  ax-8 2107  ax-9 2115  ax-10 2138  ax-11 2154  ax-12 2174  ax-ext 2705  ax-sep 5301  ax-nul 5311  ax-pow 5370  ax-pr 5437  ax-un 7753  ax-cnex 11208  ax-resscn 11209  ax-1cn 11210  ax-icn 11211  ax-addcl 11212  ax-addrcl 11213  ax-mulcl 11214  ax-mulrcl 11215  ax-mulcom 11216  ax-addass 11217  ax-mulass 11218  ax-distr 11219  ax-i2m1 11220  ax-1ne0 11221  ax-1rid 11222  ax-rnegex 11223  ax-rrecex 11224  ax-cnre 11225  ax-pre-lttri 11226  ax-pre-lttrn 11227  ax-pre-ltadd 11228  ax-pre-mulgt0 11229

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1539  df-fal 1549  df-ex 1776  df-nf 1780  df-sb 2062  df-mo 2537  df-eu 2566  df-clab 2712  df-cleq 2726  df-clel 2813  df-nfc 2889  df-ne 2938  df-nel 3044  df-ral 3059  df-rex 3068  df-reu 3378  df-rab 3433  df-v 3479  df-sbc 3791  df-csb 3908  df-dif 3965  df-un 3967  df-in 3969  df-ss 3979  df-pss 3982  df-nul 4339  df-if 4531  df-pw 4606  df-sn 4631  df-pr 4633  df-op 4637  df-uni 4912  df-int 4951  df-iun 4997  df-br 5148  df-opab 5210  df-mpt 5231  df-tr 5265  df-id 5582  df-eprel 5588  df-po 5596  df-so 5597  df-fr 5640  df-we 5642  df-xp 5694  df-rel 5695  df-cnv 5696  df-co 5697  df-dm 5698  df-rn 5699  df-res 5700  df-ima 5701  df-pred 6322  df-ord 6388  df-on 6389  df-lim 6390  df-suc 6391  df-iota 6515  df-fun 6564  df-fn 6565  df-f 6566  df-f1 6567  df-fo 6568  df-f1o 6569  df-fv 6570  df-riota 7387  df-ov 7433  df-oprab 7434  df-mpo 7435  df-om 7887  df-2nd 8013  df-frecs 8304  df-wrecs 8335  df-recs 8409  df-rdg 8448  df-1o 8504  df-er 8743  df-en 8984  df-dom 8985  df-sdom 8986  df-fin 8987  df-card 9976  df-pnf 11294  df-mnf 11295  df-xr 11296  df-ltxr 11297  df-le 11298  df-sub 11491  df-neg 11492  df-nn 12264  df-n0 12524  df-z 12611  df-uz 12876

This theorem is referenced by:  hashgval  14368  hashinf  14370  hashfxnn0  14372