Theorem hashen 14246

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.

Step	Hyp	Ref	Expression
1		fveq2 6817	. . . 4 ⊢ ((♯‘𝐴) = (♯‘𝐵) → (◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = (◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)))
2		eqid 2730	. . . . . 6 ⊢ (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω) = (rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)
3	2	hashginv 14233	. . . . 5 ⊢ (𝐴 ∈ Fin → (◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = (card‘𝐴))
4	2	hashginv 14233	. . . . 5 ⊢ (𝐵 ∈ Fin → (◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)) = (card‘𝐵))
5	3, 4	eqeqan12d 2744	. . . 4 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐴)) = (◡(rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(♯‘𝐵)) ↔ (card‘𝐴) = (card‘𝐵)))
6	1, 5	imbitrid 244	. . 3 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) → (card‘𝐴) = (card‘𝐵)))
7		fveq2 6817	. . . 4 ⊢ ((card‘𝐴) = (card‘𝐵) → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)))
8	2	hashgval 14232	. . . . 5 ⊢ (𝐴 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = (♯‘𝐴))
9	2	hashgval 14232	. . . . 5 ⊢ (𝐵 ∈ Fin → ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) = (♯‘𝐵))
10	8, 9	eqeqan12d 2744	. . . 4 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐴)) = ((rec((𝑥 ∈ V ↦ (𝑥 + 1)), 0) ↾ ω)‘(card‘𝐵)) ↔ (♯‘𝐴) = (♯‘𝐵)))
11	7, 10	imbitrid 244	. . 3 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) = (card‘𝐵) → (♯‘𝐴) = (♯‘𝐵)))
12	6, 11	impbid 212	. 2 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) ↔ (card‘𝐴) = (card‘𝐵)))
13		finnum 9833	. . 3 ⊢ (𝐴 ∈ Fin → 𝐴 ∈ dom card)
14		finnum 9833	. . 3 ⊢ (𝐵 ∈ Fin → 𝐵 ∈ dom card)
15		carden2 9872	. . 3 ⊢ ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → ((card‘𝐴) = (card‘𝐵) ↔ 𝐴 ≈ 𝐵))
16	13, 14, 15	syl2an 596	. 2 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((card‘𝐴) = (card‘𝐵) ↔ 𝐴 ≈ 𝐵))
17	12, 16	bitrd 279	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → ((♯‘𝐴) = (♯‘𝐵) ↔ 𝐴 ≈ 𝐵))

Syntax hints:   → wi 4   ↔ wb 206   ∧ wa 395   = wceq 1541   ∈ wcel 2110  Vcvv 3434   class class class wbr 5089   ↦ cmpt 5170  ^◡ccnv 5613  dom cdm 5614   ↾ cres 5616  ‘cfv 6477  (class class class)co 7341  ωcom 7791  reccrdg 8323   ≈ cen 8861  Fincfn 8864  cardccrd 9820  0cc0 10998  1c1 10999   + caddc 11001  ♯chash 14229

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1968  ax-7 2009  ax-8 2112  ax-9 2120  ax-10 2143  ax-11 2159  ax-12 2179  ax-ext 2702  ax-sep 5232  ax-nul 5242  ax-pow 5301  ax-pr 5368  ax-un 7663  ax-cnex 11054  ax-resscn 11055  ax-1cn 11056  ax-icn 11057  ax-addcl 11058  ax-addrcl 11059  ax-mulcl 11060  ax-mulrcl 11061  ax-mulcom 11062  ax-addass 11063  ax-mulass 11064  ax-distr 11065  ax-i2m1 11066  ax-1ne0 11067  ax-1rid 11068  ax-rnegex 11069  ax-rrecex 11070  ax-cnre 11071  ax-pre-lttri 11072  ax-pre-lttrn 11073  ax-pre-ltadd 11074  ax-pre-mulgt0 11075

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2067  df-mo 2534  df-eu 2563  df-clab 2709  df-cleq 2722  df-clel 2804  df-nfc 2879  df-ne 2927  df-nel 3031  df-ral 3046  df-rex 3055  df-reu 3345  df-rab 3394  df-v 3436  df-sbc 3740  df-csb 3849  df-dif 3903  df-un 3905  df-in 3907  df-ss 3917  df-pss 3920  df-nul 4282  df-if 4474  df-pw 4550  df-sn 4575  df-pr 4577  df-op 4581  df-uni 4858  df-int 4896  df-iun 4941  df-br 5090  df-opab 5152  df-mpt 5171  df-tr 5197  df-id 5509  df-eprel 5514  df-po 5522  df-so 5523  df-fr 5567  df-we 5569  df-xp 5620  df-rel 5621  df-cnv 5622  df-co 5623  df-dm 5624  df-rn 5625  df-res 5626  df-ima 5627  df-pred 6244  df-ord 6305  df-on 6306  df-lim 6307  df-suc 6308  df-iota 6433  df-fun 6479  df-fn 6480  df-f 6481  df-f1 6482  df-fo 6483  df-f1o 6484  df-fv 6485  df-riota 7298  df-ov 7344  df-oprab 7345  df-mpo 7346  df-om 7792  df-2nd 7917  df-frecs 8206  df-wrecs 8237  df-recs 8286  df-rdg 8324  df-1o 8380  df-er 8617  df-en 8865  df-dom 8866  df-sdom 8867  df-fin 8868  df-card 9824  df-pnf 11140  df-mnf 11141  df-xr 11142  df-ltxr 11143  df-le 11144  df-sub 11338  df-neg 11339  df-nn 12118  df-n0 12374  df-z 12461  df-uz 12725  df-hash 14230

This theorem is referenced by:  hasheni  14247  hasheqf1o  14248  isfinite4  14261  hasheq0  14262  hashsng  14268  hashen1  14269  hashsdom  14280  hash1snb  14318  hashxplem  14332  hashmap  14334  hashpw  14335  hashbclem  14351  phphashd  14365  hash2pr  14368  pr2pwpr  14378  hash3tr  14390  tpf1o  14400  s7f1o  14865  isercolllem2  15565  isercoll  15567  summolem3  15613  mertenslem1  15783  prodmolem3  15832  bpolylem  15947  hashdvds  16678  crth  16681  phimullem  16682  eulerth  16686  4sqlem11  16859  lagsubg2  19099  dfod2  19469  sylow1lem2  19504  sylow2alem2  19523  slwhash  19529  sylow2  19531  sylow3lem1  19532  cyggenod  19789  lt6abl  19800  ablfac1c  19978  ablfac1eu  19980  ablfaclem3  19994  fta1blem  26096  vieta1  26240  isppw  27044  clwlknon2num  30338  numclwlk1lem2  30340  hashpss  32781  fisshasheq  35127  derangen2  35186  erdsze2lem1  35215  erdsze2lem2  35216  poimirlem9  37648  poimirlem25  37664  poimirlem26  37665  poimirlem27  37666  poimirlem28  37667  eldioph2lem1  42772  frlmpwfi  43110  isnumbasgrplem3  43117  idomsubgmo  43205  gpg5grlic  48104