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

Theorem ssfi 8042
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 ((𝐴 ∈ Fin ∧ 𝐵𝐴) → 𝐵 ∈ Fin)

Proof of Theorem ssfi
Dummy variables 𝑥 𝑦 𝑧 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 isfi 7842 . . 3 (𝐴 ∈ Fin ↔ ∃𝑥 ∈ ω 𝐴𝑥)
2 bren 7827 . . . . 5 (𝐴𝑥 ↔ ∃𝑧 𝑧:𝐴1-1-onto𝑥)
3 f1ofo 6042 . . . . . . . . . . 11 (𝑧:𝐴1-1-onto𝑥𝑧:𝐴onto𝑥)
4 imassrn 5383 . . . . . . . . . . . 12 (𝑧𝐵) ⊆ ran 𝑧
5 forn 6016 . . . . . . . . . . . 12 (𝑧:𝐴onto𝑥 → ran 𝑧 = 𝑥)
64, 5syl5sseq 3615 . . . . . . . . . . 11 (𝑧:𝐴onto𝑥 → (𝑧𝐵) ⊆ 𝑥)
73, 6syl 17 . . . . . . . . . 10 (𝑧:𝐴1-1-onto𝑥 → (𝑧𝐵) ⊆ 𝑥)
8 ssnnfi 8041 . . . . . . . . . . 11 ((𝑥 ∈ ω ∧ (𝑧𝐵) ⊆ 𝑥) → (𝑧𝐵) ∈ Fin)
9 isfi 7842 . . . . . . . . . . 11 ((𝑧𝐵) ∈ Fin ↔ ∃𝑦 ∈ ω (𝑧𝐵) ≈ 𝑦)
108, 9sylib 206 . . . . . . . . . 10 ((𝑥 ∈ ω ∧ (𝑧𝐵) ⊆ 𝑥) → ∃𝑦 ∈ ω (𝑧𝐵) ≈ 𝑦)
117, 10sylan2 489 . . . . . . . . 9 ((𝑥 ∈ ω ∧ 𝑧:𝐴1-1-onto𝑥) → ∃𝑦 ∈ ω (𝑧𝐵) ≈ 𝑦)
1211adantrr 748 . . . . . . . 8 ((𝑥 ∈ ω ∧ (𝑧:𝐴1-1-onto𝑥𝐵𝐴)) → ∃𝑦 ∈ ω (𝑧𝐵) ≈ 𝑦)
13 f1of1 6034 . . . . . . . . . . . . . 14 (𝑧:𝐴1-1-onto𝑥𝑧:𝐴1-1𝑥)
14 f1ores 6049 . . . . . . . . . . . . . 14 ((𝑧:𝐴1-1𝑥𝐵𝐴) → (𝑧𝐵):𝐵1-1-onto→(𝑧𝐵))
1513, 14sylan 486 . . . . . . . . . . . . 13 ((𝑧:𝐴1-1-onto𝑥𝐵𝐴) → (𝑧𝐵):𝐵1-1-onto→(𝑧𝐵))
16 vex 3175 . . . . . . . . . . . . . . . . 17 𝑧 ∈ V
1716resex 5350 . . . . . . . . . . . . . . . 16 (𝑧𝐵) ∈ V
18 f1oeq1 6025 . . . . . . . . . . . . . . . 16 (𝑥 = (𝑧𝐵) → (𝑥:𝐵1-1-onto→(𝑧𝐵) ↔ (𝑧𝐵):𝐵1-1-onto→(𝑧𝐵)))
1917, 18spcev 3272 . . . . . . . . . . . . . . 15 ((𝑧𝐵):𝐵1-1-onto→(𝑧𝐵) → ∃𝑥 𝑥:𝐵1-1-onto→(𝑧𝐵))
20 bren 7827 . . . . . . . . . . . . . . 15 (𝐵 ≈ (𝑧𝐵) ↔ ∃𝑥 𝑥:𝐵1-1-onto→(𝑧𝐵))
2119, 20sylibr 222 . . . . . . . . . . . . . 14 ((𝑧𝐵):𝐵1-1-onto→(𝑧𝐵) → 𝐵 ≈ (𝑧𝐵))
22 entr 7871 . . . . . . . . . . . . . 14 ((𝐵 ≈ (𝑧𝐵) ∧ (𝑧𝐵) ≈ 𝑦) → 𝐵𝑦)
2321, 22sylan 486 . . . . . . . . . . . . 13 (((𝑧𝐵):𝐵1-1-onto→(𝑧𝐵) ∧ (𝑧𝐵) ≈ 𝑦) → 𝐵𝑦)
2415, 23sylan 486 . . . . . . . . . . . 12 (((𝑧:𝐴1-1-onto𝑥𝐵𝐴) ∧ (𝑧𝐵) ≈ 𝑦) → 𝐵𝑦)
2524ex 448 . . . . . . . . . . 11 ((𝑧:𝐴1-1-onto𝑥𝐵𝐴) → ((𝑧𝐵) ≈ 𝑦𝐵𝑦))
2625reximdv 2998 . . . . . . . . . 10 ((𝑧:𝐴1-1-onto𝑥𝐵𝐴) → (∃𝑦 ∈ ω (𝑧𝐵) ≈ 𝑦 → ∃𝑦 ∈ ω 𝐵𝑦))
27 isfi 7842 . . . . . . . . . 10 (𝐵 ∈ Fin ↔ ∃𝑦 ∈ ω 𝐵𝑦)
2826, 27syl6ibr 240 . . . . . . . . 9 ((𝑧:𝐴1-1-onto𝑥𝐵𝐴) → (∃𝑦 ∈ ω (𝑧𝐵) ≈ 𝑦𝐵 ∈ Fin))
2928adantl 480 . . . . . . . 8 ((𝑥 ∈ ω ∧ (𝑧:𝐴1-1-onto𝑥𝐵𝐴)) → (∃𝑦 ∈ ω (𝑧𝐵) ≈ 𝑦𝐵 ∈ Fin))
3012, 29mpd 15 . . . . . . 7 ((𝑥 ∈ ω ∧ (𝑧:𝐴1-1-onto𝑥𝐵𝐴)) → 𝐵 ∈ Fin)
3130exp32 628 . . . . . 6 (𝑥 ∈ ω → (𝑧:𝐴1-1-onto𝑥 → (𝐵𝐴𝐵 ∈ Fin)))
3231exlimdv 1847 . . . . 5 (𝑥 ∈ ω → (∃𝑧 𝑧:𝐴1-1-onto𝑥 → (𝐵𝐴𝐵 ∈ Fin)))
332, 32syl5bi 230 . . . 4 (𝑥 ∈ ω → (𝐴𝑥 → (𝐵𝐴𝐵 ∈ Fin)))
3433rexlimiv 3008 . . 3 (∃𝑥 ∈ ω 𝐴𝑥 → (𝐵𝐴𝐵 ∈ Fin))
351, 34sylbi 205 . 2 (𝐴 ∈ Fin → (𝐵𝐴𝐵 ∈ Fin))
3635imp 443 1 ((𝐴 ∈ Fin ∧ 𝐵𝐴) → 𝐵 ∈ Fin)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 382  wex 1694  wcel 1976  wrex 2896  wss 3539   class class class wbr 4577  ran crn 5029  cres 5030  cima 5031  1-1wf1 5787  ontowfo 5788  1-1-ontowf1o 5789  ωcom 6934  cen 7815  Fincfn 7818
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1712  ax-4 1727  ax-5 1826  ax-6 1874  ax-7 1921  ax-8 1978  ax-9 1985  ax-10 2005  ax-11 2020  ax-12 2033  ax-13 2233  ax-ext 2589  ax-sep 4703  ax-nul 4712  ax-pow 4764  ax-pr 4828  ax-un 6824
This theorem depends on definitions:  df-bi 195  df-or 383  df-an 384  df-3or 1031  df-3an 1032  df-tru 1477  df-ex 1695  df-nf 1700  df-sb 1867  df-eu 2461  df-mo 2462  df-clab 2596  df-cleq 2602  df-clel 2605  df-nfc 2739  df-ne 2781  df-ral 2900  df-rex 2901  df-rab 2904  df-v 3174  df-sbc 3402  df-dif 3542  df-un 3544  df-in 3546  df-ss 3553  df-pss 3555  df-nul 3874  df-if 4036  df-pw 4109  df-sn 4125  df-pr 4127  df-tp 4129  df-op 4131  df-uni 4367  df-br 4578  df-opab 4638  df-tr 4675  df-eprel 4939  df-id 4943  df-po 4949  df-so 4950  df-fr 4987  df-we 4989  df-xp 5034  df-rel 5035  df-cnv 5036  df-co 5037  df-dm 5038  df-rn 5039  df-res 5040  df-ima 5041  df-ord 5629  df-on 5630  df-lim 5631  df-suc 5632  df-fun 5792  df-fn 5793  df-f 5794  df-f1 5795  df-fo 5796  df-f1o 5797  df-om 6935  df-er 7606  df-en 7819  df-fin 7822
This theorem is referenced by:  domfi  8043  ssfid  8045  infi  8046  finresfin  8048  diffi  8054  findcard3  8065  unfir  8090  fnfi  8100  fofinf1o  8103  cnvfi  8108  f1fi  8113  imafi  8119  mapfi  8122  ixpfi  8123  ixpfi2  8124  mptfi  8125  cnvimamptfin  8127  fisuppfi  8143  suppssfifsupp  8150  fsuppunbi  8156  snopfsupp  8158  fsuppres  8160  ressuppfi  8161  fsuppmptif  8165  fsuppco2  8168  fsuppcor  8169  sniffsupp  8175  elfiun  8196  wemapso2lem  8317  cantnfp1lem1  8435  oemapvali  8441  ackbij2lem1  8901  ackbij1lem11  8912  fin23lem26  9007  fin23lem23  9008  fin23lem21  9021  fin11a  9065  isfin1-3  9068  axcclem  9139  ssnn0fi  12601  hashun3  12986  hashss  13010  hashssdif  13013  hashsslei  13025  hashbclem  13045  hashf1lem2  13049  seqcoll2  13058  pr2pwpr  13066  isercolllem2  14190  isercoll  14192  fsum2dlem  14289  fsumcom2OLD  14294  fsumless  14315  fsumabs  14320  fsumrlim  14330  fsumo1  14331  cvgcmpce  14337  fsumiun  14340  qshash  14344  incexclem  14353  incexc  14354  incexc2  14355  fprod2dlem  14495  fprodcom2OLD  14500  fprodmodd  14513  sumeven  14894  sumodd  14895  bitsfi  14943  bitsinv1  14948  bitsinvp1  14955  sadcaddlem  14963  sadadd2lem  14965  sadadd3  14967  sadaddlem  14972  sadasslem  14976  sadeq  14978  phicl2  15257  phibnd  15260  hashdvds  15264  phiprmpw  15265  phimullem  15268  eulerthlem2  15271  eulerth  15272  phisum  15279  sumhash  15384  prmreclem2  15405  prmreclem3  15406  prmreclem4  15407  prmreclem5  15408  1arith  15415  4sqlem11  15443  vdwlem11  15479  hashbccl  15491  ramlb  15507  0ram  15508  ramub1lem1  15514  ramub1lem2  15515  prmgaplem3  15541  prmgaplem4  15542  isstruct2  15650  lagsubg2  17424  lagsubg  17425  orbsta2  17516  symgbasfi  17575  symgfisg  17657  symggen2  17660  odcl2  17751  oddvds2  17752  sylow1lem2  17783  sylow1lem3  17784  sylow1lem4  17785  sylow1lem5  17786  odcau  17788  pgpssslw  17798  sylow2alem2  17802  sylow2a  17803  sylow2blem1  17804  sylow2blem3  17806  slwhash  17808  fislw  17809  sylow2  17810  sylow3lem1  17811  sylow3lem3  17813  sylow3lem4  17814  sylow3lem6  17816  cyggenod  18055  gsumval3lem1  18075  gsumval3lem2  18076  gsumval3  18077  gsumzadd  18091  gsumpt  18130  gsum2dlem1  18138  gsum2dlem2  18139  gsum2d  18140  gsum2d2lem  18141  dprdfadd  18188  ablfacrplem  18233  ablfacrp2  18235  ablfac1c  18239  ablfac1eulem  18240  ablfac1eu  18241  pgpfac1lem5  18247  pgpfaclem2  18250  pgpfaclem3  18251  ablfaclem3  18255  lcomfsupp  18672  psrbaglecl  19136  psrbagaddcl  19137  psrbagcon  19138  mplsubg  19204  mpllss  19205  mplcoe5  19235  psrbagsn  19262  psr1baslem  19322  dsmmfi  19843  dsmmacl  19846  dsmmsubg  19848  dsmmlss  19849  frlmsslsp  19896  mamures  19957  submabas  20145  mdetdiaglem  20165  mdetrlin  20169  mdetrsca  20170  mdetralt  20175  maducoeval2  20207  madugsum  20210  fctop  20560  restfpw  20735  fincmp  20948  cmpfi  20963  bwth  20965  finlocfin  21075  lfinpfin  21079  locfincmp  21081  1stckgenlem  21108  ptbasfi  21136  ptcnplem  21176  ptcmpfi  21368  cfinfil  21449  ufinffr  21485  fin1aufil  21488  tsmsres  21699  xrge0gsumle  22376  xrge0tsms  22377  fsumcn  22412  rrxcph  22905  rrxmval  22913  ovoliunlem1  22994  ovolicc2lem4  23012  ovolicc2lem5  23013  i1fima  23168  i1fd  23171  itg1cl  23175  itg1ge0  23176  i1f0  23177  i1f1  23180  i1fadd  23185  i1fmul  23186  itg1addlem4  23189  i1fmulc  23193  itg1mulc  23194  i1fres  23195  itg10a  23200  itg1ge0a  23201  itg1climres  23204  mbfi1fseqlem4  23208  itgfsum  23316  dvmptfsum  23459  plyexmo  23789  aannenlem2  23805  aalioulem2  23809  birthday  24398  jensenlem1  24430  jensenlem2  24431  jensen  24432  wilthlem2  24512  ppifi  24549  prmdvdsfi  24550  0sgm  24587  sgmf  24588  sgmnncl  24590  ppiprm  24594  chtprm  24596  chtdif  24601  efchtdvds  24602  ppidif  24606  ppiltx  24620  mumul  24624  sqff1o  24625  fsumdvdsdiag  24627  fsumdvdscom  24628  dvdsflsumcom  24631  musum  24634  musumsum  24635  muinv  24636  fsumdvdsmul  24638  ppiub  24646  vmasum  24658  logfac2  24659  perfectlem2  24672  dchrfi  24697  dchrabs  24702  dchrptlem1  24706  dchrptlem2  24707  dchrpt  24709  lgsquadlem1  24822  lgsquadlem2  24823  lgsquadlem3  24824  chebbnd1lem1  24875  chtppilimlem1  24879  rplogsumlem2  24891  rpvmasumlem  24893  dchrvmasumlem1  24901  dchrisum0ff  24913  rpvmasum2  24918  dchrisum0re  24919  dchrisum0  24926  rplogsum  24933  dirith2  24934  vmalogdivsum2  24944  logsqvma  24948  logsqvma2  24949  selberg  24954  selberg34r  24977  pntsval2  24982  pntrlog2bndlem1  24983  cusgrafi  25776  wwlknfi  26032  hashwwlkext  26040  clwwlknfi  26072  qerclwwlknfi  26123  vdgrfiun  26195  eupath2lem3  26272  konigsberg  26280  relfi  28603  imafi2  28678  unifi3  28679  ffsrn  28698  gsumle  28916  xrge0tsmsd  28922  hasheuni  29280  carsgclctunlem1  29512  sibfof  29535  sitgclg  29537  oddpwdc  29549  eulerpartlems  29555  eulerpartlemb  29563  eulerpartlemmf  29570  eulerpartlemgf  29574  eulerpartlemgs2  29575  coinfliplem  29673  coinflippv  29678  ballotlemfelz  29685  ballotlemfp1  29686  ballotlemfc0  29687  ballotlemfcc  29688  ballotlemiex  29696  ballotlemsup  29699  ballotlemfg  29720  ballotlemfrc  29721  ballotlemfrceq  29723  ballotth  29732  deranglem  30208  subfacp1lem3  30224  subfacp1lem5  30226  subfacp1lem6  30227  erdszelem2  30234  erdszelem8  30240  erdsze2lem2  30246  snmlff  30371  mvrsfpw  30463  finminlem  31288  topdifinffinlem  32167  matunitlindflem1  32371  poimirlem9  32384  poimirlem26  32401  poimirlem27  32402  poimirlem28  32403  poimirlem30  32405  poimirlem32  32407  itg2addnclem2  32428  nnubfi  32512  nninfnub  32513  sstotbnd2  32539  cntotbnd  32561  rencldnfilem  36198  jm2.22  36376  jm2.23  36377  filnm  36474  pwssfi  38032  disjinfi  38171  fsumiunss  38439  fprodexp  38458  fprodabs2  38459  mccllem  38461  sumnnodd  38494  fprodcncf  38584  dvmptfprod  38632  dvnprodlem1  38633  dvnprodlem2  38634  fourierdlem25  38822  fourierdlem37  38834  fourierdlem51  38847  fourierdlem79  38875  fouriersw  38921  etransclem16  38940  etransclem24  38948  etransclem33  38957  etransclem44  38968  sge0resplit  39096  sge0iunmptlemfi  39103  sge0iunmptlemre  39105  carageniuncllem2  39209  hsphoidmvle2  39272  hsphoidmvle  39273  hoidmvlelem4  39285  hoidmvlelem5  39286  fmtnoinf  39784  perfectALTVlem2  39963  cusgrfi  40669  wwlksnfi  41107  hashwwlksnext  41115  rmsuppfi  41943  mndpsuppfi  41945  scmsuppfi  41947  suppmptcfin  41949
  Copyright terms: Public domain W3C validator