Theorem ssfi 4683

Description: A subset of a finite set is finite. Corollary 6G of [Enderton] p. 138.

Assertion

Ref	Expression
ssfi	|- ((A e. Fin /\ B (_ A) -> B e. Fin)

Proof of Theorem ssfi

Step	Hyp	Ref	Expression
1		isfi 4523	. . 3 |- (A e. Fin <-> E.x e. om A ~~ x)
2		breng 4516	. . . . 5 |- (x e. om -> (A ~~ x <-> E.z z:A-1-1-onto->x))
3		ssnnfi 4682	. . . . . . . . . . 11 |- ((x e. om /\ (z"B) (_ x) -> (z"B) e. Fin)
4		isfi 4523	. . . . . . . . . . 11 |- ((z"B) e. Fin <-> E.y e. om (z"B) ~~ y)
5	3, 4	sylib 196	. . . . . . . . . 10 |- ((x e. om /\ (z"B) (_ x) -> E.y e. om (z"B) ~~ y)
6		f1ofo 3803	. . . . . . . . . . 11 |- (z:A-1-1-onto->x -> z:A-onto->x)
7		imassrn 3507	. . . . . . . . . . . 12 |- (z"B) (_ ran z
8		forn 3782	. . . . . . . . . . . . 13 |- (z:A-onto->x -> ran z = x)
9	8	sseq2d 2141	. . . . . . . . . . . 12 |- (z:A-onto->x -> ((z"B) (_ ran z <-> (z"B) (_ x))
10	7, 9	mpbii 191	. . . . . . . . . . 11 |- (z:A-onto->x -> (z"B) (_ x)
11	6, 10	syl 10	. . . . . . . . . 10 |- (z:A-1-1-onto->x -> (z"B) (_ x)
12	5, 11	sylan2 453	. . . . . . . . 9 |- ((x e. om /\ z:A-1-1-onto->x) -> E.y e. om (z"B) ~~ y)
13	12	adantrr 395	. . . . . . . 8 |- ((x e. om /\ (z:A-1-1-onto->x /\ B (_ A)) -> E.y e. om (z"B) ~~ y)
14		entr 4555	. . . . . . . . . . . . . 14 |- ((B ~~ (z"B) /\ (z"B) ~~ y) -> B ~~ y)
15		visset 1859	. . . . . . . . . . . . . . . . 17 |- z e. V
16		resexg 3484	. . . . . . . . . . . . . . . . 17 |- (z e. V -> (z |` B) e. V)
17	15, 16	ax-mp 7	. . . . . . . . . . . . . . . 16 |- (z |` B) e. V
18		f1oeq1 3792	. . . . . . . . . . . . . . . 16 |- (x = (z |` B) -> (x:B-1-1-onto->(z"B) <-> (z |` B):B-1-1-onto->(z"B)))
19	17, 18	cla4ev 1915	. . . . . . . . . . . . . . 15 |- ((z |` B):B-1-1-onto->(z"B) -> E.x x:B-1-1-onto->(z"B))
20		imaexg 3508	. . . . . . . . . . . . . . . . 17 |- (z e. V -> (z"B) e. V)
21	15, 20	ax-mp 7	. . . . . . . . . . . . . . . 16 |- (z"B) e. V
22	21	bren 4518	. . . . . . . . . . . . . . 15 |- (B ~~ (z"B) <-> E.x x:B-1-1-onto->(z"B))
23	19, 22	sylibr 198	. . . . . . . . . . . . . 14 |- ((z |` B):B-1-1-onto->(z"B) -> B ~~ (z"B))
24	14, 23	sylan 450	. . . . . . . . . . . . 13 |- (((z |` B):B-1-1-onto->(z"B) /\ (z"B) ~~ y) -> B ~~ y)
25		f1ores 3811	. . . . . . . . . . . . . 14 |- ((z:A-1-1->x /\ B (_ A) -> (z |` B):B-1-1-onto->(z"B))
26		f1of1 3796	. . . . . . . . . . . . . 14 |- (z:A-1-1-onto->x -> z:A-1-1->x)
27	25, 26	sylan 450	. . . . . . . . . . . . 13 |- ((z:A-1-1-onto->x /\ B (_ A) -> (z |` B):B-1-1-onto->(z"B))
28	24, 27	sylan 450	. . . . . . . . . . . 12 |- (((z:A-1-1-onto->x /\ B (_ A) /\ (z"B) ~~ y) -> B ~~ y)
29	28	ex 371	. . . . . . . . . . 11 |- ((z:A-1-1-onto->x /\ B (_ A) -> ((z"B) ~~ y -> B ~~ y))
30	29	r19.22sdv 1784	. . . . . . . . . 10 |- ((z:A-1-1-onto->x /\ B (_ A) -> (E.y e. om (z"B) ~~ y -> E.y e. om B ~~ y))
31		isfi 4523	. . . . . . . . . 10 |- (B e. Fin <-> E.y e. om B ~~ y)
32	30, 31	syl6ibr 211	. . . . . . . . 9 |- ((z:A-1-1-onto->x /\ B (_ A) -> (E.y e. om (z"B) ~~ y -> B e. Fin))
33	32	adantl 388	. . . . . . . 8 |- ((x e. om /\ (z:A-1-1-onto->x /\ B (_ A)) -> (E.y e. om (z"B) ~~ y -> B e. Fin))
34	13, 33	mpd 26	. . . . . . 7 |- ((x e. om /\ (z:A-1-1-onto->x /\ B (_ A)) -> B e. Fin)
35	34	exp32 377	. . . . . 6 |- (x e. om -> (z:A-1-1-onto->x -> (B (_ A -> B e. Fin)))
36	35	19.23adv 1251	. . . . 5 |- (x e. om -> (E.z z:A-1-1-onto->x -> (B (_ A -> B e. Fin)))
37	2, 36	sylbid 201	. . . 4 |- (x e. om -> (A ~~ x -> (B (_ A -> B e. Fin)))
38	37	r19.23aiv 1789	. . 3 |- (E.x e. om A ~~ x -> (B (_ A -> B e. Fin))
39	1, 38	sylbi 197	. 2 |- (A e. Fin -> (B (_ A -> B e. Fin))
40	39	imp 348	1 |- ((A e. Fin /\ B (_ A) -> B e. Fin)

Syntax hints:   -> wi 3   /\ wa 221   e. wcel 994  E.wex 1016  E.wrex 1692  Vcvv 1857   (_ wss 2099   class class class wbr 2692  omcom 3218  ran crn 3252   |` cres 3253  "cima 3254  -1-1->wf1 3260  -onto->wfo 3261  -1-1-onto->wf1o 3262   ~~ cen 4505  Fincfn 4508

This theorem is referenced by:  domfi 4684  unfi 4697  unfinsef 10775  f1fi 10779  unfin 10797  finfin 10798  cnfilca 11088  rcfpfillem6 11094  fintopcomp 11115  finminlem 11418  elfiun 11421  cptclsscpt 11489  finptfin 11568  finlocfin 11570  lfinpfin 11574  locfincomp 11575  comppfsc 11578  fbunfip 11631  ufinffr 11663  nnubfi 11881  nninfnub 11882  sstotbnd 11992  totbndss 11993  heiborlem18 12028  rrntotbnd 12078

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 998  ax-gen 999  ax-8 1000  ax-9 1001  ax-10 1002  ax-11 1003  ax-12 1004  ax-13 1005  ax-14 1006  ax-17 1007  ax-4 1009  ax-5o 1011  ax-6o 1014  ax-9o 1159  ax-10o 1177  ax-16 1247  ax-11o 1255  ax-ext 1500  ax-rep 2767  ax-sep 2777  ax-nul 2784  ax-pow 2818  ax-pr 2855  ax-un 3089

This theorem depends on definitions:  df-bi 145  df-or 222  df-an 223  df-3or 782  df-3an 783  df-ex 1017  df-sb 1209  df-eu 1421  df-mo 1422  df-clab 1506  df-cleq 1511  df-clel 1514  df-ne 1630  df-ral 1695  df-rex 1696  df-v 1858  df-dif 2101  df-un 2102  df-in 2103  df-ss 2105  df-pss 2107  df-nul 2333  df-if 2416  df-pw 2459  df-sn 2470  df-pr 2471  df-tp 2473  df-op 2474  df-uni 2570  df-br 2693  df-opab 2741  df-tr 2755  df-eprel 2910  df-id 2913  df-po 2918  df-so 2929  df-fr 2947  df-we 2962  df-ord 2978  df-on 2979  df-lim 2980  df-suc 2981  df-om 3219  df-xp 3265  df-rel 3266  df-cnv 3267  df-co 3268  df-dm 3269  df-rn 3270  df-res 3271  df-ima 3272  df-fun 3273  df-fn 3274  df-f 3275  df-f1 3276  df-fo 3277  df-f1o 3278  df-er 4401  df-en 4509  df-fin 4512

Copyright terms: Public domain