ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  hashennn GIF version

Theorem hashennn 10085
Description: The size of a set equinumerous to an element of ω. (Contributed by Jim Kingdon, 21-Feb-2022.)
Assertion
Ref Expression
hashennn ((𝑁 ∈ ω ∧ 𝑁𝐴) → (♯‘𝐴) = (frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0)‘𝑁))
Distinct variable groups:   𝑥,𝐴   𝑥,𝑁

Proof of Theorem hashennn
Dummy variables 𝑦 𝑧 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 df-ihash 10081 . . . . 5 ♯ = ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩}) ∘ (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}))
21fveq1i 5269 . . . 4 (♯‘𝐴) = (((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩}) ∘ (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}))‘𝐴)
3 funmpt 5017 . . . . 5 Fun (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})
4 hashennnuni 10084 . . . . . . . . 9 ((𝑁 ∈ ω ∧ 𝑁𝐴) → {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴} = 𝑁)
54eqcomd 2090 . . . . . . . 8 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝑁 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴})
6 nnfi 6540 . . . . . . . . . . 11 (𝑁 ∈ ω → 𝑁 ∈ Fin)
76adantr 270 . . . . . . . . . 10 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝑁 ∈ Fin)
8 simpr 108 . . . . . . . . . . 11 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝑁𝐴)
98ensymd 6452 . . . . . . . . . 10 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝐴𝑁)
10 enfii 6542 . . . . . . . . . 10 ((𝑁 ∈ Fin ∧ 𝐴𝑁) → 𝐴 ∈ Fin)
117, 9, 10syl2anc 403 . . . . . . . . 9 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝐴 ∈ Fin)
12 simpl 107 . . . . . . . . 9 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝑁 ∈ ω)
13 simpr 108 . . . . . . . . . . 11 ((𝑥 = 𝐴𝑧 = 𝑁) → 𝑧 = 𝑁)
14 breq2 3824 . . . . . . . . . . . . . 14 (𝑥 = 𝐴 → (𝑦𝑥𝑦𝐴))
1514adantr 270 . . . . . . . . . . . . 13 ((𝑥 = 𝐴𝑧 = 𝑁) → (𝑦𝑥𝑦𝐴))
1615rabbidv 2604 . . . . . . . . . . . 12 ((𝑥 = 𝐴𝑧 = 𝑁) → {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥} = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴})
1716unieqd 3647 . . . . . . . . . . 11 ((𝑥 = 𝐴𝑧 = 𝑁) → {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥} = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴})
1813, 17eqeq12d 2099 . . . . . . . . . 10 ((𝑥 = 𝐴𝑧 = 𝑁) → (𝑧 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥} ↔ 𝑁 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴}))
1918opelopabga 4064 . . . . . . . . 9 ((𝐴 ∈ Fin ∧ 𝑁 ∈ ω) → (⟨𝐴, 𝑁⟩ ∈ {⟨𝑥, 𝑧⟩ ∣ 𝑧 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}} ↔ 𝑁 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴}))
2011, 12, 19syl2anc 403 . . . . . . . 8 ((𝑁 ∈ ω ∧ 𝑁𝐴) → (⟨𝐴, 𝑁⟩ ∈ {⟨𝑥, 𝑧⟩ ∣ 𝑧 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}} ↔ 𝑁 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴}))
215, 20mpbird 165 . . . . . . 7 ((𝑁 ∈ ω ∧ 𝑁𝐴) → ⟨𝐴, 𝑁⟩ ∈ {⟨𝑥, 𝑧⟩ ∣ 𝑧 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}})
22 mptv 3910 . . . . . . 7 (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}) = {⟨𝑥, 𝑧⟩ ∣ 𝑧 = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}}
2321, 22syl6eleqr 2178 . . . . . 6 ((𝑁 ∈ ω ∧ 𝑁𝐴) → ⟨𝐴, 𝑁⟩ ∈ (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}))
24 opeldmg 4609 . . . . . . 7 ((𝐴 ∈ Fin ∧ 𝑁 ∈ ω) → (⟨𝐴, 𝑁⟩ ∈ (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}) → 𝐴 ∈ dom (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})))
2511, 12, 24syl2anc 403 . . . . . 6 ((𝑁 ∈ ω ∧ 𝑁𝐴) → (⟨𝐴, 𝑁⟩ ∈ (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}) → 𝐴 ∈ dom (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})))
2623, 25mpd 13 . . . . 5 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝐴 ∈ dom (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}))
27 fvco 5337 . . . . 5 ((Fun (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}) ∧ 𝐴 ∈ dom (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})) → (((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩}) ∘ (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}))‘𝐴) = ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘((𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})‘𝐴)))
283, 26, 27sylancr 405 . . . 4 ((𝑁 ∈ ω ∧ 𝑁𝐴) → (((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩}) ∘ (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}))‘𝐴) = ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘((𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})‘𝐴)))
292, 28syl5eq 2129 . . 3 ((𝑁 ∈ ω ∧ 𝑁𝐴) → (♯‘𝐴) = ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘((𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})‘𝐴)))
3011elexd 2626 . . . . . 6 ((𝑁 ∈ ω ∧ 𝑁𝐴) → 𝐴 ∈ V)
314, 12eqeltrd 2161 . . . . . 6 ((𝑁 ∈ ω ∧ 𝑁𝐴) → {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴} ∈ ω)
3214rabbidv 2604 . . . . . . . 8 (𝑥 = 𝐴 → {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥} = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴})
3332unieqd 3647 . . . . . . 7 (𝑥 = 𝐴 {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥} = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴})
34 eqid 2085 . . . . . . 7 (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥}) = (𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})
3533, 34fvmptg 5343 . . . . . 6 ((𝐴 ∈ V ∧ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴} ∈ ω) → ((𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})‘𝐴) = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴})
3630, 31, 35syl2anc 403 . . . . 5 ((𝑁 ∈ ω ∧ 𝑁𝐴) → ((𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})‘𝐴) = {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝐴})
3736, 4eqtrd 2117 . . . 4 ((𝑁 ∈ ω ∧ 𝑁𝐴) → ((𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})‘𝐴) = 𝑁)
3837fveq2d 5272 . . 3 ((𝑁 ∈ ω ∧ 𝑁𝐴) → ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘((𝑥 ∈ V ↦ {𝑦 ∈ (ω ∪ {ω}) ∣ 𝑦𝑥})‘𝐴)) = ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘𝑁))
3929, 38eqtrd 2117 . 2 ((𝑁 ∈ ω ∧ 𝑁𝐴) → (♯‘𝐴) = ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘𝑁))
40 ordom 4394 . . . . . . 7 Ord ω
41 ordirr 4331 . . . . . . 7 (Ord ω → ¬ ω ∈ ω)
4240, 41ax-mp 7 . . . . . 6 ¬ ω ∈ ω
43 eleq1 2147 . . . . . 6 (ω = 𝑁 → (ω ∈ ω ↔ 𝑁 ∈ ω))
4442, 43mtbii 632 . . . . 5 (ω = 𝑁 → ¬ 𝑁 ∈ ω)
4544necon2ai 2305 . . . 4 (𝑁 ∈ ω → ω ≠ 𝑁)
46 fvunsng 5454 . . . 4 ((𝑁 ∈ ω ∧ ω ≠ 𝑁) → ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘𝑁) = (frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0)‘𝑁))
4745, 46mpdan 412 . . 3 (𝑁 ∈ ω → ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘𝑁) = (frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0)‘𝑁))
4847adantr 270 . 2 ((𝑁 ∈ ω ∧ 𝑁𝐴) → ((frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0) ∪ {⟨ω, +∞⟩})‘𝑁) = (frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0)‘𝑁))
4939, 48eqtrd 2117 1 ((𝑁 ∈ ω ∧ 𝑁𝐴) → (♯‘𝐴) = (frec((𝑥 ∈ ℤ ↦ (𝑥 + 1)), 0)‘𝑁))
Colors of variables: wff set class
Syntax hints:  ¬ wn 3  wi 4  wa 102  wb 103   = wceq 1287  wcel 1436  wne 2251  {crab 2359  Vcvv 2615  cun 2986  {csn 3431  cop 3434   cuni 3636   class class class wbr 3820  {copab 3873  cmpt 3874  Ord word 4163  ωcom 4378  dom cdm 4411  ccom 4415  Fun wfun 4975  cfv 4981  (class class class)co 5613  freccfrec 6109  cen 6407  cdom 6408  Fincfn 6409  0cc0 7294  1c1 7295   + caddc 7297  +∞cpnf 7463  cz 8683  chash 10080
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 577  ax-in2 578  ax-io 663  ax-5 1379  ax-7 1380  ax-gen 1381  ax-ie1 1425  ax-ie2 1426  ax-8 1438  ax-10 1439  ax-11 1440  ax-i12 1441  ax-bndl 1442  ax-4 1443  ax-13 1447  ax-14 1448  ax-17 1462  ax-i9 1466  ax-ial 1470  ax-i5r 1471  ax-ext 2067  ax-sep 3932  ax-nul 3940  ax-pow 3984  ax-pr 4010  ax-un 4234  ax-setind 4326  ax-iinf 4376
This theorem depends on definitions:  df-bi 115  df-dc 779  df-3or 923  df-3an 924  df-tru 1290  df-fal 1293  df-nf 1393  df-sb 1690  df-eu 1948  df-mo 1949  df-clab 2072  df-cleq 2078  df-clel 2081  df-nfc 2214  df-ne 2252  df-ral 2360  df-rex 2361  df-rab 2364  df-v 2617  df-sbc 2830  df-dif 2990  df-un 2992  df-in 2994  df-ss 3001  df-nul 3276  df-pw 3417  df-sn 3437  df-pr 3438  df-op 3440  df-uni 3637  df-int 3672  df-br 3821  df-opab 3875  df-mpt 3876  df-tr 3912  df-id 4094  df-iord 4167  df-on 4169  df-suc 4172  df-iom 4379  df-xp 4417  df-rel 4418  df-cnv 4419  df-co 4420  df-dm 4421  df-rn 4422  df-res 4423  df-ima 4424  df-iota 4946  df-fun 4983  df-fn 4984  df-f 4985  df-f1 4986  df-fo 4987  df-f1o 4988  df-fv 4989  df-er 6244  df-en 6410  df-dom 6411  df-fin 6412  df-ihash 10081
This theorem is referenced by:  hashcl  10086  hashfz1  10088  hashen  10089  fihashdom  10108  hashun  10110
  Copyright terms: Public domain W3C validator