MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  ssfi Unicode version

Theorem ssfi 7083
Description: A subset of a finite set is finite. Corollary 6G of [Enderton] p. 138. (Contributed by NM, 24-Jun-1998.)
Assertion
Ref Expression
ssfi  |-  ( ( A  e.  Fin  /\  B  C_  A )  ->  B  e.  Fin )

Proof of Theorem ssfi
Dummy variables  x  y  z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 isfi 6885 . . 3  |-  ( A  e.  Fin  <->  E. x  e.  om  A  ~~  x
)
2 bren 6871 . . . . 5  |-  ( A 
~~  x  <->  E. z 
z : A -1-1-onto-> x )
3 f1ofo 5479 . . . . . . . . . . 11  |-  ( z : A -1-1-onto-> x  ->  z : A -onto-> x )
4 imassrn 5025 . . . . . . . . . . . 12  |-  ( z
" B )  C_  ran  z
5 forn 5454 . . . . . . . . . . . 12  |-  ( z : A -onto-> x  ->  ran  z  =  x
)
64, 5syl5sseq 3226 . . . . . . . . . . 11  |-  ( z : A -onto-> x  -> 
( z " B
)  C_  x )
73, 6syl 15 . . . . . . . . . 10  |-  ( z : A -1-1-onto-> x  ->  ( z
" B )  C_  x )
8 ssnnfi 7082 . . . . . . . . . . 11  |-  ( ( x  e.  om  /\  ( z " B
)  C_  x )  ->  ( z " B
)  e.  Fin )
9 isfi 6885 . . . . . . . . . . 11  |-  ( ( z " B )  e.  Fin  <->  E. y  e.  om  ( z " B )  ~~  y
)
108, 9sylib 188 . . . . . . . . . 10  |-  ( ( x  e.  om  /\  ( z " B
)  C_  x )  ->  E. y  e.  om  ( z " B
)  ~~  y )
117, 10sylan2 460 . . . . . . . . 9  |-  ( ( x  e.  om  /\  z : A -1-1-onto-> x )  ->  E. y  e.  om  ( z " B )  ~~  y
)
1211adantrr 697 . . . . . . . 8  |-  ( ( x  e.  om  /\  ( z : A -1-1-onto-> x  /\  B  C_  A ) )  ->  E. y  e.  om  ( z " B )  ~~  y
)
13 f1of1 5471 . . . . . . . . . . . . . 14  |-  ( z : A -1-1-onto-> x  ->  z : A -1-1-> x )
14 f1ores 5487 . . . . . . . . . . . . . 14  |-  ( ( z : A -1-1-> x  /\  B  C_  A )  ->  ( z  |`  B ) : B -1-1-onto-> (
z " B ) )
1513, 14sylan 457 . . . . . . . . . . . . 13  |-  ( ( z : A -1-1-onto-> x  /\  B  C_  A )  -> 
( z  |`  B ) : B -1-1-onto-> ( z " B
) )
16 vex 2791 . . . . . . . . . . . . . . . . 17  |-  z  e. 
_V
1716resex 4995 . . . . . . . . . . . . . . . 16  |-  ( z  |`  B )  e.  _V
18 f1oeq1 5463 . . . . . . . . . . . . . . . 16  |-  ( x  =  ( z  |`  B )  ->  (
x : B -1-1-onto-> ( z
" B )  <->  ( z  |`  B ) : B -1-1-onto-> (
z " B ) ) )
1917, 18spcev 2875 . . . . . . . . . . . . . . 15  |-  ( ( z  |`  B ) : B -1-1-onto-> ( z " B
)  ->  E. x  x : B -1-1-onto-> ( z " B
) )
20 bren 6871 . . . . . . . . . . . . . . 15  |-  ( B 
~~  ( z " B )  <->  E. x  x : B -1-1-onto-> ( z " B
) )
2119, 20sylibr 203 . . . . . . . . . . . . . 14  |-  ( ( z  |`  B ) : B -1-1-onto-> ( z " B
)  ->  B  ~~  ( z " B
) )
22 entr 6913 . . . . . . . . . . . . . 14  |-  ( ( B  ~~  ( z
" B )  /\  ( z " B
)  ~~  y )  ->  B  ~~  y )
2321, 22sylan 457 . . . . . . . . . . . . 13  |-  ( ( ( z  |`  B ) : B -1-1-onto-> ( z " B
)  /\  ( z " B )  ~~  y
)  ->  B  ~~  y )
2415, 23sylan 457 . . . . . . . . . . . 12  |-  ( ( ( z : A -1-1-onto-> x  /\  B  C_  A )  /\  ( z " B )  ~~  y
)  ->  B  ~~  y )
2524ex 423 . . . . . . . . . . 11  |-  ( ( z : A -1-1-onto-> x  /\  B  C_  A )  -> 
( ( z " B )  ~~  y  ->  B  ~~  y ) )
2625reximdv 2654 . . . . . . . . . 10  |-  ( ( z : A -1-1-onto-> x  /\  B  C_  A )  -> 
( E. y  e. 
om  ( z " B )  ~~  y  ->  E. y  e.  om  B  ~~  y ) )
27 isfi 6885 . . . . . . . . . 10  |-  ( B  e.  Fin  <->  E. y  e.  om  B  ~~  y
)
2826, 27syl6ibr 218 . . . . . . . . 9  |-  ( ( z : A -1-1-onto-> x  /\  B  C_  A )  -> 
( E. y  e. 
om  ( z " B )  ~~  y  ->  B  e.  Fin )
)
2928adantl 452 . . . . . . . 8  |-  ( ( x  e.  om  /\  ( z : A -1-1-onto-> x  /\  B  C_  A ) )  ->  ( E. y  e.  om  (
z " B ) 
~~  y  ->  B  e.  Fin ) )
3012, 29mpd 14 . . . . . . 7  |-  ( ( x  e.  om  /\  ( z : A -1-1-onto-> x  /\  B  C_  A ) )  ->  B  e.  Fin )
3130exp32 588 . . . . . 6  |-  ( x  e.  om  ->  (
z : A -1-1-onto-> x  -> 
( B  C_  A  ->  B  e.  Fin )
) )
3231exlimdv 1664 . . . . 5  |-  ( x  e.  om  ->  ( E. z  z : A
-1-1-onto-> x  ->  ( B  C_  A  ->  B  e.  Fin ) ) )
332, 32syl5bi 208 . . . 4  |-  ( x  e.  om  ->  ( A  ~~  x  ->  ( B  C_  A  ->  B  e.  Fin ) ) )
3433rexlimiv 2661 . . 3  |-  ( E. x  e.  om  A  ~~  x  ->  ( B 
C_  A  ->  B  e.  Fin ) )
351, 34sylbi 187 . 2  |-  ( A  e.  Fin  ->  ( B  C_  A  ->  B  e.  Fin ) )
3635imp 418 1  |-  ( ( A  e.  Fin  /\  B  C_  A )  ->  B  e.  Fin )
Colors of variables: wff set class
Syntax hints:    -> wi 4    /\ wa 358   E.wex 1528    e. wcel 1684   E.wrex 2544    C_ wss 3152   class class class wbr 4023   omcom 4656   ran crn 4690    |` cres 4691   "cima 4692   -1-1->wf1 5252   -onto->wfo 5253   -1-1-onto->wf1o 5254    ~~ cen 6860   Fincfn 6863
This theorem is referenced by:  domfi  7084  diffi  7089  findcard3  7100  unfir  7125  fnfi  7134  fofinf1o  7137  fidomdm  7138  cnvfi  7140  f1fi  7143  imafi  7148  mapfi  7152  ixpfi  7153  ixpfi2  7154  mptfi  7155  elfiun  7183  marypha1lem  7186  wemapso2  7267  cantnfp1lem1  7380  oemapvali  7386  cantnflem1d  7390  cantnflem1  7391  mapfien  7399  ackbij2lem1  7845  ackbij1lem11  7856  fin23lem26  7951  fin23lem23  7952  fin23lem22  7953  fin23lem21  7965  fin11a  8009  isfin1-3  8012  axcclem  8083  pwfseqlem4  8284  hashun3  11366  hashssdif  11374  hashsslei  11378  hashbclem  11390  hashf1lem2  11394  seqcoll2  11402  isercolllem2  12139  isercoll  12141  fsumss  12198  fsum2dlem  12233  fsumcom2  12237  fsumless  12254  fsumabs  12259  fsumrlim  12269  fsumo1  12270  cvgcmpce  12276  fsumiun  12279  qshash  12285  incexclem  12295  incexc  12296  incexc2  12297  bitsfi  12628  bitsinv1  12633  bitsinvp1  12640  sadcaddlem  12648  sadadd2lem  12650  sadadd3  12652  sadaddlem  12657  sadasslem  12661  sadeq  12663  phicl2  12836  phibnd  12839  hashdvds  12843  phiprmpw  12844  phimullem  12847  eulerthlem2  12850  eulerth  12851  sumhash  12944  prmreclem2  12964  prmreclem3  12965  prmreclem4  12966  prmreclem5  12967  1arith  12974  4sqlem11  13002  vdwlem11  13038  hashbccl  13050  ramlb  13066  0ram  13067  ramub1lem1  13073  ramub1lem2  13074  isstruct2  13157  fisuppfi  14450  lagsubg2  14678  lagsubg  14679  orbsta2  14768  odcl2  14878  oddvds2  14879  sylow1lem2  14910  sylow1lem3  14911  sylow1lem4  14912  sylow1lem5  14913  odcau  14915  pgpssslw  14925  sylow2alem2  14929  sylow2a  14930  sylow2blem1  14931  sylow2blem3  14933  slwhash  14935  fislw  14936  sylow2  14937  sylow3lem1  14938  sylow3lem3  14940  sylow3lem4  14941  sylow3lem6  14943  cyggenod  15171  gsumval3  15191  gsumzadd  15204  gsumzsplit  15206  gsumzinv  15217  gsumsub  15219  gsumunsn  15221  gsumpt  15222  gsum2d  15223  gsum2d2lem  15224  dprdfid  15252  dprdfinv  15254  dprdfadd  15255  dprdsubg  15259  dmdprdsplitlem  15272  dpjidcl  15293  ablfacrplem  15300  ablfacrp2  15302  ablfac1c  15306  ablfac1eulem  15307  ablfac1eu  15308  pgpfac1lem5  15314  pgpfaclem2  15317  pgpfaclem3  15318  ablfaclem3  15322  psrbaglecl  16115  psrbagaddcl  16116  psrbagcon  16117  psrass1lem  16123  psrbas  16124  psrlidm  16148  psrridm  16149  psrass1  16150  psrdi  16151  psrdir  16152  psrcom  16153  psrass23  16154  mvridlem  16164  mplsubg  16181  mpllss  16182  mplsubrglem  16183  mplsubrg  16184  mvrcl  16193  mplmon  16207  mplmonmul  16208  mplcoe1  16209  mplcoe3  16210  mplcoe2  16211  mplbas2  16212  psrbagsn  16236  psrbagev1  16247  evlslem2  16249  psr1baslem  16264  psropprmul  16316  coe1mul2  16346  ply1coe  16368  fctop  16741  restfpw  16910  fincmp  17120  cmpfi  17135  1stckgenlem  17248  ptbasfi  17276  ptcnplem  17315  ptcmpfi  17504  cfinfil  17588  ufinffr  17624  fin1aufil  17627  tsms0  17824  tsmsres  17826  tgptsmscls  17832  xrge0gsumle  18338  xrge0tsms  18339  fsumcn  18374  ovoliunlem1  18861  ovolicc2lem4  18879  ovolicc2lem5  18880  i1fima  19033  i1fd  19036  itg1cl  19040  itg1ge0  19041  i1f0  19042  i1f1  19045  i1fadd  19050  i1fmul  19051  itg1addlem4  19054  i1fmulc  19058  itg1mulc  19059  i1fres  19060  itg10a  19065  itg1ge0a  19066  itg1climres  19069  mbfi1fseqlem4  19073  itgfsum  19181  dvmptfsum  19322  evlslem6  19397  evlslem3  19398  tdeglem4  19446  plypf1  19594  plyexmo  19693  aannenlem2  19709  aalioulem2  19713  tayl0  19741  birthday  20249  jensenlem1  20281  jensenlem2  20282  jensen  20283  wilthlem2  20307  ppifi  20343  prmdvdsfi  20345  0sgm  20382  sgmf  20383  sgmnncl  20385  ppiprm  20389  chtprm  20391  chtdif  20396  efchtdvds  20397  ppidif  20401  ppiltx  20415  mumul  20419  sqff1o  20420  fsumdvdsdiag  20424  fsumdvdscom  20425  dvdsflsumcom  20428  musum  20431  musumsum  20432  muinv  20433  fsumdvdsmul  20435  ppiub  20443  vmasum  20455  logfac2  20456  perfectlem2  20469  dchrfi  20494  dchrabs  20499  dchrptlem1  20503  dchrptlem2  20504  dchrptlem3  20505  dchrpt  20506  lgseisenlem3  20590  lgseisenlem4  20591  lgsquadlem1  20593  lgsquadlem2  20594  lgsquadlem3  20595  chebbnd1lem1  20618  chtppilimlem1  20622  rplogsumlem2  20634  rpvmasumlem  20636  dchrvmasumlem1  20644  dchrisum0ff  20656  rpvmasum2  20661  dchrisum0re  20662  dchrisum0  20669  rplogsum  20676  dirith2  20677  vmalogdivsum2  20687  logsqvma  20691  logsqvma2  20692  selberg  20697  selberg34r  20720  pntsval2  20725  pntrlog2bndlem1  20726  infi  23029  ballotlemfelz  23049  ballotlemfp1  23050  ballotlemfc0  23051  ballotlemfcc  23052  ballotlemiex  23060  ballotlemsup  23063  ballotlemfg  23084  ballotlemfrc  23085  ballotlemfrceq  23087  ballotth  23096  infi1  23169  xrge0tsmsd  23382  hasheuni  23453  coinfliplem  23679  coinflippv  23684  deranglem  23697  subfacp1lem3  23713  subfacp1lem5  23715  subfacp1lem6  23716  erdszelem2  23723  erdszelem8  23729  erdsze2lem2  23735  vdgrf  23891  vdgrun  23893  eupath2lem3  23903  konigsberg  23911  snmlff  23912  unfinsef  25069  stfincomp  25591  finminlem  26231  finptfin  26297  finlocfin  26299  lfinpfin  26303  locfincmp  26304  nnubfi  26460  nninfnub  26461  sstotbnd2  26498  sstotbnd3  26500  cntotbnd  26520  funsnfsup  26762  lcomfsup  26768  rencldnfilem  26903  jm2.22  27088  jm2.23  27089  filnm  27192  dsmmfi  27204  dsmmacl  27207  dsmmsubg  27209  dsmmlss  27210  uvcff  27240  uvcresum  27242  frlmsplit2  27243  frlmsslsp  27248  frlmup1  27250  symgfisg  27409  symggen2  27412  psgnghm2  27438  phisum  27518
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1533  ax-5 1544  ax-17 1603  ax-9 1635  ax-8 1643  ax-13 1686  ax-14 1688  ax-6 1703  ax-7 1708  ax-11 1715  ax-12 1866  ax-ext 2264  ax-sep 4141  ax-nul 4149  ax-pow 4188  ax-pr 4214  ax-un 4512
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1310  df-ex 1529  df-nf 1532  df-sb 1630  df-eu 2147  df-mo 2148  df-clab 2270  df-cleq 2276  df-clel 2279  df-nfc 2408  df-ne 2448  df-ral 2548  df-rex 2549  df-rab 2552  df-v 2790  df-sbc 2992  df-dif 3155  df-un 3157  df-in 3159  df-ss 3166  df-pss 3168  df-nul 3456  df-if 3566  df-pw 3627  df-sn 3646  df-pr 3647  df-tp 3648  df-op 3649  df-uni 3828  df-br 4024  df-opab 4078  df-tr 4114  df-eprel 4305  df-id 4309  df-po 4314  df-so 4315  df-fr 4352  df-we 4354  df-ord 4395  df-on 4396  df-lim 4397  df-suc 4398  df-om 4657  df-xp 4695  df-rel 4696  df-cnv 4697  df-co 4698  df-dm 4699  df-rn 4700  df-res 4701  df-ima 4702  df-fun 5257  df-fn 5258  df-f 5259  df-f1 5260  df-fo 5261  df-f1o 5262  df-er 6660  df-en 6864  df-fin 6867
  Copyright terms: Public domain W3C validator