![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > hashen | Structured version Visualization version GIF version |
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.) |
Ref | Expression |
---|---|
hashen | β’ ((π΄ β Fin β§ π΅ β Fin) β ((β―βπ΄) = (β―βπ΅) β π΄ β π΅)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | fveq2 6843 | . . . 4 β’ ((β―βπ΄) = (β―βπ΅) β (β‘(rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(β―βπ΄)) = (β‘(rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(β―βπ΅))) | |
2 | eqid 2733 | . . . . . 6 β’ (rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο) = (rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο) | |
3 | 2 | hashginv 14240 | . . . . 5 β’ (π΄ β Fin β (β‘(rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(β―βπ΄)) = (cardβπ΄)) |
4 | 2 | hashginv 14240 | . . . . 5 β’ (π΅ β Fin β (β‘(rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(β―βπ΅)) = (cardβπ΅)) |
5 | 3, 4 | eqeqan12d 2747 | . . . 4 β’ ((π΄ β Fin β§ π΅ β Fin) β ((β‘(rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(β―βπ΄)) = (β‘(rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(β―βπ΅)) β (cardβπ΄) = (cardβπ΅))) |
6 | 1, 5 | imbitrid 243 | . . 3 β’ ((π΄ β Fin β§ π΅ β Fin) β ((β―βπ΄) = (β―βπ΅) β (cardβπ΄) = (cardβπ΅))) |
7 | fveq2 6843 | . . . 4 β’ ((cardβπ΄) = (cardβπ΅) β ((rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(cardβπ΄)) = ((rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(cardβπ΅))) | |
8 | 2 | hashgval 14239 | . . . . 5 β’ (π΄ β Fin β ((rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(cardβπ΄)) = (β―βπ΄)) |
9 | 2 | hashgval 14239 | . . . . 5 β’ (π΅ β Fin β ((rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(cardβπ΅)) = (β―βπ΅)) |
10 | 8, 9 | eqeqan12d 2747 | . . . 4 β’ ((π΄ β Fin β§ π΅ β Fin) β (((rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(cardβπ΄)) = ((rec((π₯ β V β¦ (π₯ + 1)), 0) βΎ Ο)β(cardβπ΅)) β (β―βπ΄) = (β―βπ΅))) |
11 | 7, 10 | imbitrid 243 | . . 3 β’ ((π΄ β Fin β§ π΅ β Fin) β ((cardβπ΄) = (cardβπ΅) β (β―βπ΄) = (β―βπ΅))) |
12 | 6, 11 | impbid 211 | . 2 β’ ((π΄ β Fin β§ π΅ β Fin) β ((β―βπ΄) = (β―βπ΅) β (cardβπ΄) = (cardβπ΅))) |
13 | finnum 9889 | . . 3 β’ (π΄ β Fin β π΄ β dom card) | |
14 | finnum 9889 | . . 3 β’ (π΅ β Fin β π΅ β dom card) | |
15 | carden2 9928 | . . 3 β’ ((π΄ β dom card β§ π΅ β dom card) β ((cardβπ΄) = (cardβπ΅) β π΄ β π΅)) | |
16 | 13, 14, 15 | syl2an 597 | . 2 β’ ((π΄ β Fin β§ π΅ β Fin) β ((cardβπ΄) = (cardβπ΅) β π΄ β π΅)) |
17 | 12, 16 | bitrd 279 | 1 β’ ((π΄ β Fin β§ π΅ β Fin) β ((β―βπ΄) = (β―βπ΅) β π΄ β π΅)) |
Colors of variables: wff setvar class |
Syntax hints: β wi 4 β wb 205 β§ wa 397 = wceq 1542 β wcel 2107 Vcvv 3444 class class class wbr 5106 β¦ cmpt 5189 β‘ccnv 5633 dom cdm 5634 βΎ cres 5636 βcfv 6497 (class class class)co 7358 Οcom 7803 reccrdg 8356 β cen 8883 Fincfn 8886 cardccrd 9876 0cc0 11056 1c1 11057 + caddc 11059 β―chash 14236 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1798 ax-4 1812 ax-5 1914 ax-6 1972 ax-7 2012 ax-8 2109 ax-9 2117 ax-10 2138 ax-11 2155 ax-12 2172 ax-ext 2704 ax-sep 5257 ax-nul 5264 ax-pow 5321 ax-pr 5385 ax-un 7673 ax-cnex 11112 ax-resscn 11113 ax-1cn 11114 ax-icn 11115 ax-addcl 11116 ax-addrcl 11117 ax-mulcl 11118 ax-mulrcl 11119 ax-mulcom 11120 ax-addass 11121 ax-mulass 11122 ax-distr 11123 ax-i2m1 11124 ax-1ne0 11125 ax-1rid 11126 ax-rnegex 11127 ax-rrecex 11128 ax-cnre 11129 ax-pre-lttri 11130 ax-pre-lttrn 11131 ax-pre-ltadd 11132 ax-pre-mulgt0 11133 |
This theorem depends on definitions: df-bi 206 df-an 398 df-or 847 df-3or 1089 df-3an 1090 df-tru 1545 df-fal 1555 df-ex 1783 df-nf 1787 df-sb 2069 df-mo 2535 df-eu 2564 df-clab 2711 df-cleq 2725 df-clel 2811 df-nfc 2886 df-ne 2941 df-nel 3047 df-ral 3062 df-rex 3071 df-reu 3353 df-rab 3407 df-v 3446 df-sbc 3741 df-csb 3857 df-dif 3914 df-un 3916 df-in 3918 df-ss 3928 df-pss 3930 df-nul 4284 df-if 4488 df-pw 4563 df-sn 4588 df-pr 4590 df-op 4594 df-uni 4867 df-int 4909 df-iun 4957 df-br 5107 df-opab 5169 df-mpt 5190 df-tr 5224 df-id 5532 df-eprel 5538 df-po 5546 df-so 5547 df-fr 5589 df-we 5591 df-xp 5640 df-rel 5641 df-cnv 5642 df-co 5643 df-dm 5644 df-rn 5645 df-res 5646 df-ima 5647 df-pred 6254 df-ord 6321 df-on 6322 df-lim 6323 df-suc 6324 df-iota 6449 df-fun 6499 df-fn 6500 df-f 6501 df-f1 6502 df-fo 6503 df-f1o 6504 df-fv 6505 df-riota 7314 df-ov 7361 df-oprab 7362 df-mpo 7363 df-om 7804 df-2nd 7923 df-frecs 8213 df-wrecs 8244 df-recs 8318 df-rdg 8357 df-1o 8413 df-er 8651 df-en 8887 df-dom 8888 df-sdom 8889 df-fin 8890 df-card 9880 df-pnf 11196 df-mnf 11197 df-xr 11198 df-ltxr 11199 df-le 11200 df-sub 11392 df-neg 11393 df-nn 12159 df-n0 12419 df-z 12505 df-uz 12769 df-hash 14237 |
This theorem is referenced by: hasheni 14254 hasheqf1o 14255 isfinite4 14268 hasheq0 14269 hashsng 14275 hashen1 14276 hashsdom 14287 hash1snb 14325 hashxplem 14339 hashmap 14341 hashpw 14342 hashbclem 14355 phphashd 14371 hash2pr 14374 pr2pwpr 14384 hash3tr 14395 isercolllem2 15556 isercoll 15558 summolem3 15604 mertenslem1 15774 prodmolem3 15821 bpolylem 15936 hashdvds 16652 crth 16655 phimullem 16656 eulerth 16660 4sqlem11 16832 lagsubg2 18996 dfod2 19351 sylow1lem2 19386 sylow2alem2 19405 slwhash 19411 sylow2 19413 sylow3lem1 19414 cyggenod 19666 lt6abl 19677 ablfac1c 19855 ablfac1eu 19857 ablfaclem3 19871 fta1blem 25549 vieta1 25688 isppw 26479 clwlknon2num 29354 numclwlk1lem2 29356 fisshasheq 33762 derangen2 33825 erdsze2lem1 33854 erdsze2lem2 33855 poimirlem9 36133 poimirlem25 36149 poimirlem26 36150 poimirlem27 36151 poimirlem28 36152 eldioph2lem1 41126 frlmpwfi 41468 isnumbasgrplem3 41475 idomsubgmo 41568 |
Copyright terms: Public domain | W3C validator |