Theorem ssfi 8180

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.

Step	Hyp	Ref	Expression
1		isfi 7979	. . 3 ⊢ (𝐴 ∈ Fin ↔ ∃𝑥 ∈ ω 𝐴 ≈ 𝑥)
2		bren 7964	. . . . 5 ⊢ (𝐴 ≈ 𝑥 ↔ ∃𝑧 𝑧:𝐴–1-1-onto→𝑥)
3		f1ofo 6144	. . . . . . . . . . 11 ⊢ (𝑧:𝐴–1-1-onto→𝑥 → 𝑧:𝐴–onto→𝑥)
4		imassrn 5477	. . . . . . . . . . . 12 ⊢ (𝑧 “ 𝐵) ⊆ ran 𝑧
5		forn 6118	. . . . . . . . . . . 12 ⊢ (𝑧:𝐴–onto→𝑥 → ran 𝑧 = 𝑥)
6	4, 5	syl5sseq 3653	. . . . . . . . . . 11 ⊢ (𝑧:𝐴–onto→𝑥 → (𝑧 “ 𝐵) ⊆ 𝑥)
7	3, 6	syl 17	. . . . . . . . . 10 ⊢ (𝑧:𝐴–1-1-onto→𝑥 → (𝑧 “ 𝐵) ⊆ 𝑥)
8		ssnnfi 8179	. . . . . . . . . . 11 ⊢ ((𝑥 ∈ ω ∧ (𝑧 “ 𝐵) ⊆ 𝑥) → (𝑧 “ 𝐵) ∈ Fin)
9		isfi 7979	. . . . . . . . . . 11 ⊢ ((𝑧 “ 𝐵) ∈ Fin ↔ ∃𝑦 ∈ ω (𝑧 “ 𝐵) ≈ 𝑦)
10	8, 9	sylib 208	. . . . . . . . . 10 ⊢ ((𝑥 ∈ ω ∧ (𝑧 “ 𝐵) ⊆ 𝑥) → ∃𝑦 ∈ ω (𝑧 “ 𝐵) ≈ 𝑦)
11	7, 10	sylan2 491	. . . . . . . . 9 ⊢ ((𝑥 ∈ ω ∧ 𝑧:𝐴–1-1-onto→𝑥) → ∃𝑦 ∈ ω (𝑧 “ 𝐵) ≈ 𝑦)
12	11	adantrr 753	. . . . . . . 8 ⊢ ((𝑥 ∈ ω ∧ (𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴)) → ∃𝑦 ∈ ω (𝑧 “ 𝐵) ≈ 𝑦)
13		f1of1 6136	. . . . . . . . . . . . . 14 ⊢ (𝑧:𝐴–1-1-onto→𝑥 → 𝑧:𝐴–1-1→𝑥)
14		f1ores 6151	. . . . . . . . . . . . . 14 ⊢ ((𝑧:𝐴–1-1→𝑥 ∧ 𝐵 ⊆ 𝐴) → (𝑧 ↾ 𝐵):𝐵–1-1-onto→(𝑧 “ 𝐵))
15	13, 14	sylan 488	. . . . . . . . . . . . 13 ⊢ ((𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴) → (𝑧 ↾ 𝐵):𝐵–1-1-onto→(𝑧 “ 𝐵))
16		vex 3203	. . . . . . . . . . . . . . . . 17 ⊢ 𝑧 ∈ V
17	16	resex 5443	. . . . . . . . . . . . . . . 16 ⊢ (𝑧 ↾ 𝐵) ∈ V
18		f1oeq1 6127	. . . . . . . . . . . . . . . 16 ⊢ (𝑥 = (𝑧 ↾ 𝐵) → (𝑥:𝐵–1-1-onto→(𝑧 “ 𝐵) ↔ (𝑧 ↾ 𝐵):𝐵–1-1-onto→(𝑧 “ 𝐵)))
19	17, 18	spcev 3300	. . . . . . . . . . . . . . 15 ⊢ ((𝑧 ↾ 𝐵):𝐵–1-1-onto→(𝑧 “ 𝐵) → ∃𝑥 𝑥:𝐵–1-1-onto→(𝑧 “ 𝐵))
20		bren 7964	. . . . . . . . . . . . . . 15 ⊢ (𝐵 ≈ (𝑧 “ 𝐵) ↔ ∃𝑥 𝑥:𝐵–1-1-onto→(𝑧 “ 𝐵))
21	19, 20	sylibr 224	. . . . . . . . . . . . . 14 ⊢ ((𝑧 ↾ 𝐵):𝐵–1-1-onto→(𝑧 “ 𝐵) → 𝐵 ≈ (𝑧 “ 𝐵))
22		entr 8008	. . . . . . . . . . . . . 14 ⊢ ((𝐵 ≈ (𝑧 “ 𝐵) ∧ (𝑧 “ 𝐵) ≈ 𝑦) → 𝐵 ≈ 𝑦)
23	21, 22	sylan 488	. . . . . . . . . . . . 13 ⊢ (((𝑧 ↾ 𝐵):𝐵–1-1-onto→(𝑧 “ 𝐵) ∧ (𝑧 “ 𝐵) ≈ 𝑦) → 𝐵 ≈ 𝑦)
24	15, 23	sylan 488	. . . . . . . . . . . 12 ⊢ (((𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴) ∧ (𝑧 “ 𝐵) ≈ 𝑦) → 𝐵 ≈ 𝑦)
25	24	ex 450	. . . . . . . . . . 11 ⊢ ((𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴) → ((𝑧 “ 𝐵) ≈ 𝑦 → 𝐵 ≈ 𝑦))
26	25	reximdv 3016	. . . . . . . . . 10 ⊢ ((𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴) → (∃𝑦 ∈ ω (𝑧 “ 𝐵) ≈ 𝑦 → ∃𝑦 ∈ ω 𝐵 ≈ 𝑦))
27		isfi 7979	. . . . . . . . . 10 ⊢ (𝐵 ∈ Fin ↔ ∃𝑦 ∈ ω 𝐵 ≈ 𝑦)
28	26, 27	syl6ibr 242	. . . . . . . . 9 ⊢ ((𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴) → (∃𝑦 ∈ ω (𝑧 “ 𝐵) ≈ 𝑦 → 𝐵 ∈ Fin))
29	28	adantl 482	. . . . . . . 8 ⊢ ((𝑥 ∈ ω ∧ (𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴)) → (∃𝑦 ∈ ω (𝑧 “ 𝐵) ≈ 𝑦 → 𝐵 ∈ Fin))
30	12, 29	mpd 15	. . . . . . 7 ⊢ ((𝑥 ∈ ω ∧ (𝑧:𝐴–1-1-onto→𝑥 ∧ 𝐵 ⊆ 𝐴)) → 𝐵 ∈ Fin)
31	30	exp32 631	. . . . . 6 ⊢ (𝑥 ∈ ω → (𝑧:𝐴–1-1-onto→𝑥 → (𝐵 ⊆ 𝐴 → 𝐵 ∈ Fin)))
32	31	exlimdv 1861	. . . . 5 ⊢ (𝑥 ∈ ω → (∃𝑧 𝑧:𝐴–1-1-onto→𝑥 → (𝐵 ⊆ 𝐴 → 𝐵 ∈ Fin)))
33	2, 32	syl5bi 232	. . . 4 ⊢ (𝑥 ∈ ω → (𝐴 ≈ 𝑥 → (𝐵 ⊆ 𝐴 → 𝐵 ∈ Fin)))
34	33	rexlimiv 3027	. . 3 ⊢ (∃𝑥 ∈ ω 𝐴 ≈ 𝑥 → (𝐵 ⊆ 𝐴 → 𝐵 ∈ Fin))
35	1, 34	sylbi 207	. 2 ⊢ (𝐴 ∈ Fin → (𝐵 ⊆ 𝐴 → 𝐵 ∈ Fin))
36	35	imp 445	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐵 ⊆ 𝐴) → 𝐵 ∈ Fin)

Syntax hints:   → wi 4   ∧ wa 384  ∃wex 1704   ∈ wcel 1990  ∃wrex 2913   ⊆ wss 3574   class class class wbr 4653  ran crn 5115   ↾ cres 5116   “ cima 5117  –1-1→wf1 5885  –onto→wfo 5886  –1-1-onto→wf1o 5887  ωcom 7065   ≈ cen 7952  Fincfn 7955

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1722  ax-4 1737  ax-5 1839  ax-6 1888  ax-7 1935  ax-8 1992  ax-9 1999  ax-10 2019  ax-11 2034  ax-12 2047  ax-13 2246  ax-ext 2602  ax-sep 4781  ax-nul 4789  ax-pow 4843  ax-pr 4906  ax-un 6949

This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1038  df-3an 1039  df-tru 1486  df-ex 1705  df-nf 1710  df-sb 1881  df-eu 2474  df-mo 2475  df-clab 2609  df-cleq 2615  df-clel 2618  df-nfc 2753  df-ne 2795  df-ral 2917  df-rex 2918  df-rab 2921  df-v 3202  df-sbc 3436  df-dif 3577  df-un 3579  df-in 3581  df-ss 3588  df-pss 3590  df-nul 3916  df-if 4087  df-pw 4160  df-sn 4178  df-pr 4180  df-tp 4182  df-op 4184  df-uni 4437  df-br 4654  df-opab 4713  df-tr 4753  df-id 5024  df-eprel 5029  df-po 5035  df-so 5036  df-fr 5073  df-we 5075  df-xp 5120  df-rel 5121  df-cnv 5122  df-co 5123  df-dm 5124  df-rn 5125  df-res 5126  df-ima 5127  df-ord 5726  df-on 5727  df-lim 5728  df-suc 5729  df-fun 5890  df-fn 5891  df-f 5892  df-f1 5893  df-fo 5894  df-f1o 5895  df-om 7066  df-er 7742  df-en 7956  df-fin 7959

This theorem is referenced by:  domfi  8181  ssfid  8183  infi  8184  finresfin  8186  diffi  8192  findcard3  8203  unfir  8228  fnfi  8238  fofinf1o  8241  cnvfi  8248  f1fi  8253  imafi  8259  mapfi  8262  ixpfi  8263  ixpfi2  8264  mptfi  8265  cnvimamptfin  8267  fisuppfi  8283  suppssfifsupp  8290  fsuppunbi  8296  snopfsupp  8298  fsuppres  8300  ressuppfi  8301  fsuppmptif  8305  fsuppco2  8308  fsuppcor  8309  sniffsupp  8315  elfiun  8336  wemapso2lem  8457  cantnfp1lem1  8575  oemapvali  8581  ackbij2lem1  9041  ackbij1lem11  9052  fin23lem26  9147  fin23lem23  9148  fin23lem21  9161  fin11a  9205  isfin1-3  9208  axcclem  9279  ssnn0fi  12784  hashun3  13173  hashss  13197  hashssdif  13200  hashsslei  13213  hashreshashfun  13226  hashbclem  13236  hashf1lem2  13240  seqcoll2  13249  pr2pwpr  13261  isercolllem2  14396  isercoll  14398  fsum2dlem  14501  fsumcom2OLD  14506  fsumless  14528  fsumabs  14533  fsumrlim  14543  fsumo1  14544  cvgcmpce  14550  fsumiun  14553  qshash  14559  incexclem  14568  incexc  14569  incexc2  14570  fprod2dlem  14710  fprodcom2OLD  14715  fprodmodd  14728  sumeven  15110  sumodd  15111  bitsfi  15159  bitsinv1  15164  bitsinvp1  15171  sadcaddlem  15179  sadadd2lem  15181  sadadd3  15183  sadaddlem  15188  sadasslem  15192  sadeq  15194  phicl2  15473  phibnd  15476  hashdvds  15480  phiprmpw  15481  phimullem  15484  eulerthlem2  15487  eulerth  15488  phisum  15495  sumhash  15600  prmreclem2  15621  prmreclem3  15622  prmreclem4  15623  prmreclem5  15624  1arith  15631  4sqlem11  15659  vdwlem11  15695  hashbccl  15707  ramlb  15723  0ram  15724  ramub1lem1  15730  ramub1lem2  15731  prmgaplem3  15757  prmgaplem4  15758  isstruct2  15867  lagsubg2  17655  lagsubg  17656  orbsta2  17747  symgbasfi  17806  symgfisg  17888  symggen2  17891  odcl2  17982  oddvds2  17983  sylow1lem2  18014  sylow1lem3  18015  sylow1lem4  18016  sylow1lem5  18017  odcau  18019  pgpssslw  18029  sylow2alem2  18033  sylow2a  18034  sylow2blem1  18035  sylow2blem3  18037  slwhash  18039  fislw  18040  sylow2  18041  sylow3lem1  18042  sylow3lem3  18044  sylow3lem4  18045  sylow3lem6  18047  cyggenod  18286  gsumval3lem1  18306  gsumval3lem2  18307  gsumval3  18308  gsumzadd  18322  gsumpt  18361  gsum2dlem1  18369  gsum2dlem2  18370  gsum2d  18371  gsum2d2lem  18372  dprdfadd  18419  ablfacrplem  18464  ablfacrp2  18466  ablfac1c  18470  ablfac1eulem  18471  ablfac1eu  18472  pgpfac1lem5  18478  pgpfaclem2  18481  pgpfaclem3  18482  ablfaclem3  18486  lcomfsupp  18903  psrbaglecl  19369  psrbagaddcl  19370  psrbagcon  19371  mplsubg  19437  mpllss  19438  mplcoe5  19468  psrbagsn  19495  psr1baslem  19555  dsmmfi  20082  dsmmacl  20085  dsmmsubg  20087  dsmmlss  20088  frlmsslsp  20135  mamures  20196  submabas  20384  mdetdiaglem  20404  mdetrlin  20408  mdetrsca  20409  mdetralt  20414  maducoeval2  20446  madugsum  20449  fctop  20808  restfpw  20983  fincmp  21196  cmpfi  21211  bwth  21213  finlocfin  21323  lfinpfin  21327  locfincmp  21329  1stckgenlem  21356  ptbasfi  21384  ptcnplem  21424  ptcmpfi  21616  cfinfil  21697  ufinffr  21733  fin1aufil  21736  tsmsres  21947  xrge0gsumle  22636  xrge0tsms  22637  fsumcn  22673  rrxcph  23180  rrxmval  23188  ovoliunlem1  23270  ovolicc2lem4  23288  ovolicc2lem5  23289  i1fima  23445  i1fd  23448  itg1cl  23452  itg1ge0  23453  i1f0  23454  i1f1  23457  i1fadd  23462  i1fmul  23463  itg1addlem4  23466  i1fmulc  23470  itg1mulc  23471  i1fres  23472  itg10a  23477  itg1ge0a  23478  itg1climres  23481  mbfi1fseqlem4  23485  itgfsum  23593  dvmptfsum  23738  plyexmo  24068  aannenlem2  24084  aalioulem2  24088  birthday  24681  jensenlem1  24713  jensenlem2  24714  jensen  24715  wilthlem2  24795  ppifi  24832  prmdvdsfi  24833  0sgm  24870  sgmf  24871  sgmnncl  24873  ppiprm  24877  chtprm  24879  chtdif  24884  efchtdvds  24885  ppidif  24889  ppiltx  24903  mumul  24907  sqff1o  24908  fsumdvdsdiag  24910  fsumdvdscom  24911  dvdsflsumcom  24914  musum  24917  musumsum  24918  muinv  24919  fsumdvdsmul  24921  ppiub  24929  vmasum  24941  logfac2  24942  perfectlem2  24955  dchrfi  24980  dchrabs  24985  dchrptlem1  24989  dchrptlem2  24990  dchrpt  24992  lgsquadlem1  25105  lgsquadlem2  25106  lgsquadlem3  25107  chebbnd1lem1  25158  chtppilimlem1  25162  rplogsumlem2  25174  rpvmasumlem  25176  dchrvmasumlem1  25184  dchrisum0ff  25196  rpvmasum2  25201  dchrisum0re  25202  dchrisum0  25209  rplogsum  25216  dirith2  25217  vmalogdivsum2  25227  logsqvma  25231  logsqvma2  25232  selberg  25237  selberg34r  25260  pntsval2  25265  pntrlog2bndlem1  25266  cusgrfi  26354  wwlksnfi  26801  hashwwlksnext  26809  relfi  29415  imafi2  29489  unifi3  29490  ffsrn  29504  gsumle  29779  xrge0tsmsd  29785  hasheuni  30147  carsgclctunlem1  30379  sibfof  30402  sitgclg  30404  oddpwdc  30416  eulerpartlems  30422  eulerpartlemb  30430  eulerpartlemmf  30437  eulerpartlemgf  30441  eulerpartlemgs2  30442  coinfliplem  30540  coinflippv  30545  ballotlemfelz  30552  ballotlemfp1  30553  ballotlemfc0  30554  ballotlemfcc  30555  ballotlemiex  30563  ballotlemsup  30566  ballotlemfg  30587  ballotlemfrc  30588  ballotlemfrceq  30590  ballotth  30599  breprexpnat  30712  hgt750lemb  30734  hgt750leme  30736  deranglem  31148  subfacp1lem3  31164  subfacp1lem5  31166  subfacp1lem6  31167  erdszelem2  31174  erdszelem8  31180  erdsze2lem2  31186  snmlff  31311  mvrsfpw  31403  finminlem  32312  topdifinffinlem  33195  matunitlindflem1  33405  poimirlem9  33418  poimirlem26  33435  poimirlem27  33436  poimirlem28  33437  poimirlem30  33439  poimirlem32  33441  itg2addnclem2  33462  nnubfi  33546  nninfnub  33547  sstotbnd2  33573  cntotbnd  33595  rencldnfilem  37384  jm2.22  37562  jm2.23  37563  filnm  37660  pwssfi  39211  disjinfi  39380  fsumiunss  39807  fprodexp  39826  fprodabs2  39827  mccllem  39829  sumnnodd  39862  fprodcncf  40114  dvmptfprod  40160  dvnprodlem1  40161  dvnprodlem2  40162  fourierdlem25  40349  fourierdlem37  40361  fourierdlem51  40374  fourierdlem79  40402  fouriersw  40448  etransclem16  40467  etransclem24  40475  etransclem33  40484  etransclem44  40495  sge0resplit  40623  sge0iunmptlemfi  40630  sge0iunmptlemre  40632  carageniuncllem2  40736  hsphoidmvle2  40799  hsphoidmvle  40800  hoidmvlelem4  40812  hoidmvlelem5  40813  fmtnoinf  41448  perfectALTVlem2  41631  rmsuppfi  42154  mndpsuppfi  42156  scmsuppfi  42158  suppmptcfin  42160