Theorem ssfiOLD 4548

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

Assertion

Ref	Expression
ssfiOLD	⊢ ((∃x ∈ ω A ≈ x ⋀ B ⊆ A) → ∃x ∈ ω B ≈ x)

Distinct variable groups:   x,A   x,B

Proof of Theorem ssfiOLD

Step	Hyp	Ref	Expression
1		breng 4381	. . . . 5 ⊢ (x ∈ ω → (A ≈ x ↔ ∃z z:A–1-1-onto→x))
2		ssnnfiOLD 4546	. . . . . . . . . 10 ⊢ ((x ∈ ω ⋀ (z “ B) ⊆ x) → ∃y ∈ ω (z “ B) ≈ y)
3		f1ofo 3701	. . . . . . . . . . 11 ⊢ (z:A–1-1-onto→x → z:A–onto→x)
4		imassrn 3421	. . . . . . . . . . . 12 ⊢ (z “ B) ⊆ ran z
5		forn 3680	. . . . . . . . . . . . 13 ⊢ (z:A–onto→x → ran z = x)
6	5	sseq2d 2092	. . . . . . . . . . . 12 ⊢ (z:A–onto→x → ((z “ B) ⊆ ran z ↔ (z “ B) ⊆ x))
7	4, 6	mpbii 193	. . . . . . . . . . 11 ⊢ (z:A–onto→x → (z “ B) ⊆ x)
8	3, 7	syl 10	. . . . . . . . . 10 ⊢ (z:A–1-1-onto→x → (z “ B) ⊆ x)
9	2, 8	sylan2 453	. . . . . . . . 9 ⊢ ((x ∈ ω ⋀ z:A–1-1-onto→x) → ∃y ∈ ω (z “ B) ≈ y)
10	9	adantrr 397	. . . . . . . 8 ⊢ ((x ∈ ω ⋀ (z:A–1-1-onto→x ⋀ B ⊆ A)) → ∃y ∈ ω (z “ B) ≈ y)
11		entrt 4420	. . . . . . . . . . . . 13 ⊢ ((B ≈ (z “ B) ⋀ (z “ B) ≈ y) → B ≈ y)
12		visset 1816	. . . . . . . . . . . . . . . 16 ⊢ z ∈ V
13		resexg 3400	. . . . . . . . . . . . . . . 16 ⊢ (z ∈ V → (z ↾ B) ∈ V)
14	12, 13	ax-mp 7	. . . . . . . . . . . . . . 15 ⊢ (z ↾ B) ∈ V
15		f1oeq1 3690	. . . . . . . . . . . . . . 15 ⊢ (x = (z ↾ B) → (x:B–1-1-onto→(z “ B) ↔ (z ↾ B):B–1-1-onto→(z “ B)))
16	14, 15	cla4ev 1872	. . . . . . . . . . . . . 14 ⊢ ((z ↾ B):B–1-1-onto→(z “ B) → ∃x x:B–1-1-onto→(z “ B))
17		imaexg 3422	. . . . . . . . . . . . . . . 16 ⊢ (z ∈ V → (z “ B) ∈ V)
18	12, 17	ax-mp 7	. . . . . . . . . . . . . . 15 ⊢ (z “ B) ∈ V
19	18	bren 4383	. . . . . . . . . . . . . 14 ⊢ (B ≈ (z “ B) ↔ ∃x x:B–1-1-onto→(z “ B))
20	16, 19	sylibr 200	. . . . . . . . . . . . 13 ⊢ ((z ↾ B):B–1-1-onto→(z “ B) → B ≈ (z “ B))
21	11, 20	sylan 450	. . . . . . . . . . . 12 ⊢ (((z ↾ B):B–1-1-onto→(z “ B) ⋀ (z “ B) ≈ y) → B ≈ y)
22		f1ores 3709	. . . . . . . . . . . . 13 ⊢ ((z:A–1-1→x ⋀ B ⊆ A) → (z ↾ B):B–1-1-onto→(z “ B))
23		f1of1 3694	. . . . . . . . . . . . 13 ⊢ (z:A–1-1-onto→x → z:A–1-1→x)
24	22, 23	sylan 450	. . . . . . . . . . . 12 ⊢ ((z:A–1-1-onto→x ⋀ B ⊆ A) → (z ↾ B):B–1-1-onto→(z “ B))
25	21, 24	sylan 450	. . . . . . . . . . 11 ⊢ (((z:A–1-1-onto→x ⋀ B ⊆ A) ⋀ (z “ B) ≈ y) → B ≈ y)
26	25	ex 373	. . . . . . . . . 10 ⊢ ((z:A–1-1-onto→x ⋀ B ⊆ A) → ((z “ B) ≈ y → B ≈ y))
27	26	r19.22sdv 1741	. . . . . . . . 9 ⊢ ((z:A–1-1-onto→x ⋀ B ⊆ A) → (∃y ∈ ω (z “ B) ≈ y → ∃y ∈ ω B ≈ y))
28	27	adantl 390	. . . . . . . 8 ⊢ ((x ∈ ω ⋀ (z:A–1-1-onto→x ⋀ B ⊆ A)) → (∃y ∈ ω (z “ B) ≈ y → ∃y ∈ ω B ≈ y))
29	10, 28	mpd 26	. . . . . . 7 ⊢ ((x ∈ ω ⋀ (z:A–1-1-onto→x ⋀ B ⊆ A)) → ∃y ∈ ω B ≈ y)
30	29	exp32 379	. . . . . 6 ⊢ (x ∈ ω → (z:A–1-1-onto→x → (B ⊆ A → ∃y ∈ ω B ≈ y)))
31	30	19.23adv 1216	. . . . 5 ⊢ (x ∈ ω → (∃z z:A–1-1-onto→x → (B ⊆ A → ∃y ∈ ω B ≈ y)))
32	1, 31	sylbid 203	. . . 4 ⊢ (x ∈ ω → (A ≈ x → (B ⊆ A → ∃y ∈ ω B ≈ y)))
33	32	r19.23aiv 1746	. . 3 ⊢ (∃x ∈ ω A ≈ x → (B ⊆ A → ∃y ∈ ω B ≈ y))
34	33	imp 350	. 2 ⊢ ((∃x ∈ ω A ≈ x ⋀ B ⊆ A) → ∃y ∈ ω B ≈ y)
35		breq2 2628	. . 3 ⊢ (y = x → (B ≈ y ↔ B ≈ x))
36	35	cbvrexv 1804	. 2 ⊢ (∃y ∈ ω B ≈ y ↔ ∃x ∈ ω B ≈ x)
37	34, 36	sylib 198	1 ⊢ ((∃x ∈ ω A ≈ x ⋀ B ⊆ A) → ∃x ∈ ω B ≈ x)

Syntax hints:   → wi 3   ⋀ wa 223   ∈ wcel 960  ∃wex 982  ∃wrex 1649  Vcvv 1814   ⊆ wss 2050   class class class wbr 2624  ωcom 3137  ran crn 3177   ↾ cres 3178   “ cima 3179  –1-1→wf1 3185  –onto→wfo 3186  –1-1-onto→wf1o 3187   ≈ cen 4370

This theorem is referenced by:  domfiOLD 4550  unfiOLD 4564  fctopOLD 7647

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 964  ax-gen 965  ax-8 966  ax-9 967  ax-10 968  ax-11 969  ax-12 970  ax-13 971  ax-14 972  ax-17 973  ax-4 975  ax-5o 977  ax-6o 980  ax-9o 1125  ax-10o 1142  ax-16 1212  ax-11o 1220  ax-ext 1462  ax-rep 2698  ax-sep 2708  ax-nul 2715  ax-pow 2748  ax-pr 2785  ax-un 2872

This theorem depends on definitions:  df-bi 147  df-or 224  df-an 225  df-3or 778  df-3an 779  df-ex 983  df-sb 1174  df-eu 1384  df-mo 1385  df-clab 1467  df-cleq 1472  df-clel 1475  df-ne 1590  df-ral 1652  df-rex 1653  df-v 1815  df-dif 2052  df-un 2053  df-in 2054  df-ss 2056  df-pss 2058  df-nul 2284  df-if 2366  df-pw 2406  df-sn 2416  df-pr 2417  df-tp 2419  df-op 2420  df-uni 2508  df-br 2625  df-opab 2672  df-tr 2686  df-eprel 2838  df-id 2841  df-po 2846  df-so 2856  df-fr 2923  df-we 2940  df-ord 2957  df-on 2958  df-lim 2959  df-suc 2960  df-om 3138  df-xp 3190  df-rel 3191  df-cnv 3192  df-co 3193  df-dm 3194  df-rn 3195  df-res 3196  df-ima 3197  df-fun 3198  df-fn 3199  df-f 3200  df-f1 3201  df-fo 3202  df-f1o 3203  df-er 4267  df-en 4374

Copyright terms: Public domain