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

Theorem hashen 13375
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 6418 . . . 4 ((♯‘𝐴) = (♯‘𝐵) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)))
2 eqid 2817 . . . . . 6 (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
32hashginv 13361 . . . . 5 (𝐴 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = (card‘𝐴))
42hashginv 13361 . . . . 5 (𝐵 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)) = (card‘𝐵))
53, 4eqeqan12d 2833 . . . 4 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)) ↔ (card‘𝐴) = (card‘𝐵)))
61, 5syl5ib 235 . . 3 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) → (card‘𝐴) = (card‘𝐵)))
7 fveq2 6418 . . . 4 ((card‘𝐴) = (card‘𝐵) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)))
82hashgval 13360 . . . . 5 (𝐴 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = (♯‘𝐴))
92hashgval 13360 . . . . 5 (𝐵 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
108, 9eqeqan12d 2833 . . . 4 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) ↔ (♯‘𝐴) = (♯‘𝐵)))
117, 10syl5ib 235 . . 3 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) = (card‘𝐵) → (♯‘𝐴) = (♯‘𝐵)))
126, 11impbid 203 . 2 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) ↔ (card‘𝐴) = (card‘𝐵)))
13 finnum 9067 . . 3 (𝐴 ∈ Fin → 𝐴 ∈ dom card)
14 finnum 9067 . . 3 (𝐵 ∈ Fin → 𝐵 ∈ dom card)
15 carden2 9106 . . 3 ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → ((card‘𝐴) = (card‘𝐵) ↔ 𝐴𝐵))
1613, 14, 15syl2an 585 . 2 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) = (card‘𝐵) ↔ 𝐴𝐵))
1712, 16bitrd 270 1 ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) ↔ 𝐴𝐵))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 197  wa 384   = wceq 1637  wcel 2157  Vcvv 3402   class class class wbr 4855  cmpt 4934  ccnv 5323  dom cdm 5324  cres 5326  cfv 6111  (class class class)co 6884  ωcom 7305  reccrdg 7751  cen 8199  Fincfn 8202  cardccrd 9054  0cc0 10231  1c1 10232   + caddc 10234  chash 13357
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 2069  ax-7 2105  ax-8 2159  ax-9 2166  ax-10 2186  ax-11 2202  ax-12 2215  ax-13 2422  ax-ext 2795  ax-sep 4988  ax-nul 4996  ax-pow 5048  ax-pr 5109  ax-un 7189  ax-cnex 10287  ax-resscn 10288  ax-1cn 10289  ax-icn 10290  ax-addcl 10291  ax-addrcl 10292  ax-mulcl 10293  ax-mulrcl 10294  ax-mulcom 10295  ax-addass 10296  ax-mulass 10297  ax-distr 10298  ax-i2m1 10299  ax-1ne0 10300  ax-1rid 10301  ax-rnegex 10302  ax-rrecex 10303  ax-cnre 10304  ax-pre-lttri 10305  ax-pre-lttrn 10306  ax-pre-ltadd 10307  ax-pre-mulgt0 10308
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 2062  df-mo 2635  df-eu 2642  df-clab 2804  df-cleq 2810  df-clel 2813  df-nfc 2948  df-ne 2990  df-nel 3093  df-ral 3112  df-rex 3113  df-reu 3114  df-rab 3116  df-v 3404  df-sbc 3645  df-csb 3740  df-dif 3783  df-un 3785  df-in 3787  df-ss 3794  df-pss 3796  df-nul 4128  df-if 4291  df-pw 4364  df-sn 4382  df-pr 4384  df-tp 4386  df-op 4388  df-uni 4642  df-int 4681  df-iun 4725  df-br 4856  df-opab 4918  df-mpt 4935  df-tr 4958  df-id 5232  df-eprel 5237  df-po 5245  df-so 5246  df-fr 5283  df-we 5285  df-xp 5330  df-rel 5331  df-cnv 5332  df-co 5333  df-dm 5334  df-rn 5335  df-res 5336  df-ima 5337  df-pred 5907  df-ord 5953  df-on 5954  df-lim 5955  df-suc 5956  df-iota 6074  df-fun 6113  df-fn 6114  df-f 6115  df-f1 6116  df-fo 6117  df-f1o 6118  df-fv 6119  df-riota 6845  df-ov 6887  df-oprab 6888  df-mpt2 6889  df-om 7306  df-wrecs 7652  df-recs 7714  df-rdg 7752  df-er 7989  df-en 8203  df-dom 8204  df-sdom 8205  df-fin 8206  df-card 9058  df-pnf 10371  df-mnf 10372  df-xr 10373  df-ltxr 10374  df-le 10375  df-sub 10563  df-neg 10564  df-nn 11316  df-n0 11580  df-z 11664  df-uz 11925  df-hash 13358
This theorem is referenced by:  hasheni  13376  hasheqf1o  13377  isfinite4  13391  hasheq0  13392  hashsng  13397  hashen1  13398  hashsdom  13408  hash1snb  13444  hashxplem  13457  hashmap  13459  hashpw  13460  hashbclem  13473  hash2pr  13488  pr2pwpr  13498  hash3tr  13509  isercolllem2  14639  isercoll  14641  summolem3  14688  summolem2a  14689  mertenslem1  14857  prodmolem3  14904  prodmolem2a  14905  bpolylem  15019  hashdvds  15717  crth  15720  phimullem  15721  eulerth  15725  4sqlem11  15896  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  18692  ablfac1eu  18694  ablfaclem3  18708  fta1blem  24165  vieta1  24304  basellem5  25048  isppw  25077  clwlknon2num  27571  numclwlk1lem2  27573  derangen2  31501  subfacp1lem3  31509  subfacp1lem5  31511  erdsze2lem1  31530  erdsze2lem2  31531  poimirlem9  33750  poimirlem25  33766  poimirlem26  33767  poimirlem27  33768  poimirlem28  33769  eldioph2lem1  37843  frlmpwfi  38187  isnumbasgrplem3  38194  idomsubgmo  38295
  Copyright terms: Public domain W3C validator