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

Theorem hashen 13350
 Description: Two finite sets have the same number of elements iff they are equinumerous. (Contributed by Paul Chapman, 22-Jun-2011.) (Revised by Mario Carneiro, 15-Sep-2013.)
Assertion
Ref Expression
hashen ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) ↔ 𝐴𝐵))

Proof of Theorem hashen
Dummy variable 𝑥 is distinct from all other variables.
StepHypRef Expression
1 fveq2 6354 . . . 4 ((♯‘𝐴) = (♯‘𝐵) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)))
2 eqid 2761 . . . . . 6 (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
32hashginv 13336 . . . . 5 (𝐴 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = (card‘𝐴))
42hashginv 13336 . . . . 5 (𝐵 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)) = (card‘𝐵))
53, 4eqeqan12d 2777 . . . 4 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)) ↔ (card‘𝐴) = (card‘𝐵)))
61, 5syl5ib 234 . . 3 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) → (card‘𝐴) = (card‘𝐵)))
7 fveq2 6354 . . . 4 ((card‘𝐴) = (card‘𝐵) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)))
82hashgval 13335 . . . . 5 (𝐴 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = (♯‘𝐴))
92hashgval 13335 . . . . 5 (𝐵 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
108, 9eqeqan12d 2777 . . . 4 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) ↔ (♯‘𝐴) = (♯‘𝐵)))
117, 10syl5ib 234 . . 3 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) = (card‘𝐵) → (♯‘𝐴) = (♯‘𝐵)))
126, 11impbid 202 . 2 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) ↔ (card‘𝐴) = (card‘𝐵)))
13 finnum 8985 . . 3 (𝐴 ∈ Fin → 𝐴 ∈ dom card)
14 finnum 8985 . . 3 (𝐵 ∈ Fin → 𝐵 ∈ dom card)
15 carden2 9024 . . 3 ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → ((card‘𝐴) = (card‘𝐵) ↔ 𝐴𝐵))
1613, 14, 15syl2an 495 . 2 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) = (card‘𝐵) ↔ 𝐴𝐵))
1712, 16bitrd 268 1 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) ↔ 𝐴𝐵))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 196   ∧ wa 383   = wceq 1632   ∈ wcel 2140  Vcvv 3341   class class class wbr 4805   ↦ cmpt 4882  ◡ccnv 5266  dom cdm 5267   ↾ cres 5269  ‘cfv 6050  (class class class)co 6815  ωcom 7232  reccrdg 7676   ≈ cen 8121  Fincfn 8124  cardccrd 8972  0cc0 10149  1c1 10150   + caddc 10152  ♯chash 13332 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1871  ax-4 1886  ax-5 1989  ax-6 2055  ax-7 2091  ax-8 2142  ax-9 2149  ax-10 2169  ax-11 2184  ax-12 2197  ax-13 2392  ax-ext 2741  ax-sep 4934  ax-nul 4942  ax-pow 4993  ax-pr 5056  ax-un 7116  ax-cnex 10205  ax-resscn 10206  ax-1cn 10207  ax-icn 10208  ax-addcl 10209  ax-addrcl 10210  ax-mulcl 10211  ax-mulrcl 10212  ax-mulcom 10213  ax-addass 10214  ax-mulass 10215  ax-distr 10216  ax-i2m1 10217  ax-1ne0 10218  ax-1rid 10219  ax-rnegex 10220  ax-rrecex 10221  ax-cnre 10222  ax-pre-lttri 10223  ax-pre-lttrn 10224  ax-pre-ltadd 10225  ax-pre-mulgt0 10226 This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1635  df-ex 1854  df-nf 1859  df-sb 2048  df-eu 2612  df-mo 2613  df-clab 2748  df-cleq 2754  df-clel 2757  df-nfc 2892  df-ne 2934  df-nel 3037  df-ral 3056  df-rex 3057  df-reu 3058  df-rab 3060  df-v 3343  df-sbc 3578  df-csb 3676  df-dif 3719  df-un 3721  df-in 3723  df-ss 3730  df-pss 3732  df-nul 4060  df-if 4232  df-pw 4305  df-sn 4323  df-pr 4325  df-tp 4327  df-op 4329  df-uni 4590  df-int 4629  df-iun 4675  df-br 4806  df-opab 4866  df-mpt 4883  df-tr 4906  df-id 5175  df-eprel 5180  df-po 5188  df-so 5189  df-fr 5226  df-we 5228  df-xp 5273  df-rel 5274  df-cnv 5275  df-co 5276  df-dm 5277  df-rn 5278  df-res 5279  df-ima 5280  df-pred 5842  df-ord 5888  df-on 5889  df-lim 5890  df-suc 5891  df-iota 6013  df-fun 6052  df-fn 6053  df-f 6054  df-f1 6055  df-fo 6056  df-f1o 6057  df-fv 6058  df-riota 6776  df-ov 6818  df-oprab 6819  df-mpt2 6820  df-om 7233  df-wrecs 7578  df-recs 7639  df-rdg 7677  df-er 7914  df-en 8125  df-dom 8126  df-sdom 8127  df-fin 8128  df-card 8976  df-pnf 10289  df-mnf 10290  df-xr 10291  df-ltxr 10292  df-le 10293  df-sub 10481  df-neg 10482  df-nn 11234  df-n0 11506  df-z 11591  df-uz 11901  df-hash 13333 This theorem is referenced by:  hasheni  13351  hasheqf1o  13352  isfinite4  13366  hasheq0  13367  hashsng  13372  hashen1  13373  hashsdom  13383  hash1snb  13420  hashxplem  13433  hashmap  13435  hashpw  13436  hashbclem  13449  hash2pr  13464  pr2pwpr  13474  hash3tr  13485  isercolllem2  14616  isercoll  14618  summolem3  14665  summolem2a  14666  mertenslem1  14836  prodmolem3  14883  prodmolem2a  14884  bpolylem  14999  hashdvds  15703  crth  15706  phimullem  15707  eulerth  15711  4sqlem11  15882  lagsubg2  17877  orbsta2  17968  dfod2  18202  sylow1lem2  18235  sylow2alem2  18254  sylow2a  18255  slwhash  18260  sylow2  18262  sylow3lem1  18263  cyggenod  18507  lt6abl  18517  gsumval3lem1  18527  gsumval3lem2  18528  gsumval3  18529  ablfac1c  18691  ablfac1eu  18693  ablfaclem3  18707  fta1blem  24148  vieta1  24287  basellem5  25032  isppw  25061  clwlknon2num  27551  numclwlk1lem2  27553  derangen2  31485  subfacp1lem3  31493  subfacp1lem5  31495  erdsze2lem1  31514  erdsze2lem2  31515  poimirlem9  33750  poimirlem25  33766  poimirlem26  33767  poimirlem27  33768  poimirlem28  33769  eldioph2lem1  37844  frlmpwfi  38189  isnumbasgrplem3  38196  idomsubgmo  38297
 Copyright terms: Public domain W3C validator