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

Theorem hashgval 13340
Description: The value of the function in terms of the mapping 𝐺 from ω to 0. The proof avoids the use of ax-ac 9566. (Contributed by Paul Chapman, 22-Jun-2011.) (Revised by Mario Carneiro, 26-Dec-2014.)
Hypothesis
Ref Expression
hashgval.1 𝐺 = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
Assertion
Ref Expression
hashgval (𝐴 ∈ Fin → (𝐺‘(card‘𝐴)) = (♯‘𝐴))
Distinct variable group:   𝑥,𝐴
Allowed substitution hint:   𝐺(𝑥)

Proof of Theorem hashgval
Dummy variable 𝑦 is distinct from all other variables.
StepHypRef Expression
1 resundir 5615 . . . . . 6 ((((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ∪ ((V ∖ Fin) × {+∞})) ↾ Fin) = ((((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ↾ Fin) ∪ (((V ∖ Fin) × {+∞}) ↾ Fin))
2 eqid 2806 . . . . . . . . . 10 (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
3 eqid 2806 . . . . . . . . . 10 ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card)
42, 3hashkf 13339 . . . . . . . . 9 ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card):Fin⟶ℕ0
5 ffn 6256 . . . . . . . . 9 (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card):Fin⟶ℕ0 → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) Fn Fin)
6 fnresdm 6211 . . . . . . . . 9 (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) Fn Fin → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ↾ Fin) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card))
74, 5, 6mp2b 10 . . . . . . . 8 (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ↾ Fin) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card)
8 incom 4004 . . . . . . . . . 10 ((V ∖ Fin) ∩ Fin) = (Fin ∩ (V ∖ Fin))
9 disjdif 4236 . . . . . . . . . 10 (Fin ∩ (V ∖ Fin)) = ∅
108, 9eqtri 2828 . . . . . . . . 9 ((V ∖ Fin) ∩ Fin) = ∅
11 pnfex 10378 . . . . . . . . . . 11 +∞ ∈ V
1211fconst 6306 . . . . . . . . . 10 ((V ∖ Fin) × {+∞}):(V ∖ Fin)⟶{+∞}
13 ffn 6256 . . . . . . . . . 10 (((V ∖ Fin) × {+∞}):(V ∖ Fin)⟶{+∞} → ((V ∖ Fin) × {+∞}) Fn (V ∖ Fin))
14 fnresdisj 6212 . . . . . . . . . 10 (((V ∖ Fin) × {+∞}) Fn (V ∖ Fin) → (((V ∖ Fin) ∩ Fin) = ∅ ↔ (((V ∖ Fin) × {+∞}) ↾ Fin) = ∅))
1512, 13, 14mp2b 10 . . . . . . . . 9 (((V ∖ Fin) ∩ Fin) = ∅ ↔ (((V ∖ Fin) × {+∞}) ↾ Fin) = ∅)
1610, 15mpbi 221 . . . . . . . 8 (((V ∖ Fin) × {+∞}) ↾ Fin) = ∅
177, 16uneq12i 3964 . . . . . . 7 ((((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ↾ Fin) ∪ (((V ∖ Fin) × {+∞}) ↾ Fin)) = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ∪ ∅)
18 un0 4165 . . . . . . 7 (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ∪ ∅) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card)
1917, 18eqtri 2828 . . . . . 6 ((((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ↾ Fin) ∪ (((V ∖ Fin) × {+∞}) ↾ Fin)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card)
201, 19eqtri 2828 . . . . 5 ((((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ∪ ((V ∖ Fin) × {+∞})) ↾ Fin) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card)
21 df-hash 13338 . . . . . 6 ♯ = (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ∪ ((V ∖ Fin) × {+∞}))
2221reseq1i 5593 . . . . 5 (♯ ↾ Fin) = ((((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card) ∪ ((V ∖ Fin) × {+∞})) ↾ Fin)
23 hashgval.1 . . . . . 6 𝐺 = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
2423coeq1i 5483 . . . . 5 (𝐺 ∘ card) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) ∘ card)
2520, 22, 243eqtr4i 2838 . . . 4 (♯ ↾ Fin) = (𝐺 ∘ card)
2625fveq1i 6409 . . 3 ((♯ ↾ Fin)‘𝐴) = ((𝐺 ∘ card)‘𝐴)
27 cardf2 9052 . . . . 5 card:{𝑥 ∣ ∃𝑦 ∈ On 𝑦𝑥}⟶On
28 ffun 6259 . . . . 5 (card:{𝑥 ∣ ∃𝑦 ∈ On 𝑦𝑥}⟶On → Fun card)
2927, 28ax-mp 5 . . . 4 Fun card
30 finnum 9057 . . . 4 (𝐴 ∈ Fin → 𝐴 ∈ dom card)
31 fvco 6495 . . . 4 ((Fun card ∧ 𝐴 ∈ dom card) → ((𝐺 ∘ card)‘𝐴) = (𝐺‘(card‘𝐴)))
3229, 30, 31sylancr 577 . . 3 (𝐴 ∈ Fin → ((𝐺 ∘ card)‘𝐴) = (𝐺‘(card‘𝐴)))
3326, 32syl5eq 2852 . 2 (𝐴 ∈ Fin → ((♯ ↾ Fin)‘𝐴) = (𝐺‘(card‘𝐴)))
34 fvres 6427 . 2 (𝐴 ∈ Fin → ((♯ ↾ Fin)‘𝐴) = (♯‘𝐴))
3533, 34eqtr3d 2842 1 (𝐴 ∈ Fin → (𝐺‘(card‘𝐴)) = (♯‘𝐴))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 197   = wceq 1637  wcel 2156  {cab 2792  wrex 3097  Vcvv 3391  cdif 3766  cun 3767  cin 3768  c0 4116  {csn 4370   class class class wbr 4844  cmpt 4923   × cxp 5309  dom cdm 5311  cres 5313  ccom 5315  Oncon0 5936  Fun wfun 6095   Fn wfn 6096  wf 6097  cfv 6101  (class class class)co 6874  ωcom 7295  reccrdg 7741  cen 8189  Fincfn 8192  cardccrd 9044  0cc0 10221  1c1 10222   + caddc 10224  +∞cpnf 10356  0cn0 11559  chash 13337
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2068  ax-7 2104  ax-8 2158  ax-9 2165  ax-10 2185  ax-11 2201  ax-12 2214  ax-13 2420  ax-ext 2784  ax-sep 4975  ax-nul 4983  ax-pow 5035  ax-pr 5096  ax-un 7179  ax-cnex 10277  ax-resscn 10278  ax-1cn 10279  ax-icn 10280  ax-addcl 10281  ax-addrcl 10282  ax-mulcl 10283  ax-mulrcl 10284  ax-mulcom 10285  ax-addass 10286  ax-mulass 10287  ax-distr 10288  ax-i2m1 10289  ax-1ne0 10290  ax-1rid 10291  ax-rnegex 10292  ax-rrecex 10293  ax-cnre 10294  ax-pre-lttri 10295  ax-pre-lttrn 10296  ax-pre-ltadd 10297  ax-pre-mulgt0 10298
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2061  df-eu 2634  df-mo 2635  df-clab 2793  df-cleq 2799  df-clel 2802  df-nfc 2937  df-ne 2979  df-nel 3082  df-ral 3101  df-rex 3102  df-reu 3103  df-rab 3105  df-v 3393  df-sbc 3634  df-csb 3729  df-dif 3772  df-un 3774  df-in 3776  df-ss 3783  df-pss 3785  df-nul 4117  df-if 4280  df-pw 4353  df-sn 4371  df-pr 4373  df-tp 4375  df-op 4377  df-uni 4631  df-int 4670  df-iun 4714  df-br 4845  df-opab 4907  df-mpt 4924  df-tr 4947  df-id 5219  df-eprel 5224  df-po 5232  df-so 5233  df-fr 5270  df-we 5272  df-xp 5317  df-rel 5318  df-cnv 5319  df-co 5320  df-dm 5321  df-rn 5322  df-res 5323  df-ima 5324  df-pred 5893  df-ord 5939  df-on 5940  df-lim 5941  df-suc 5942  df-iota 6064  df-fun 6103  df-fn 6104  df-f 6105  df-f1 6106  df-fo 6107  df-f1o 6108  df-fv 6109  df-riota 6835  df-ov 6877  df-oprab 6878  df-mpt2 6879  df-om 7296  df-wrecs 7642  df-recs 7704  df-rdg 7742  df-er 7979  df-en 8193  df-dom 8194  df-sdom 8195  df-fin 8196  df-card 9048  df-pnf 10361  df-mnf 10362  df-xr 10363  df-ltxr 10364  df-le 10365  df-sub 10553  df-neg 10554  df-nn 11306  df-n0 11560  df-z 11644  df-uz 11905  df-hash 13338
This theorem is referenced by:  hashginv  13341  hashfz1  13354  hashen  13355  hashcard  13364  hashcl  13365  hashgval2  13385  hashdom  13386  hashun  13389  fz1isolem  13462
  Copyright terms: Public domain W3C validator