Theorem fnfi 9082

Description: A version of fnex 7146 for finite sets that does not require Replacement or Power Sets. (Contributed by Mario Carneiro, 16-Nov-2014.) (Revised by Mario Carneiro, 24-Jun-2015.)

Assertion

Ref	Expression
fnfi	⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → 𝐹 ∈ Fin)

Proof of Theorem fnfi

Dummy variables 𝑥 𝑦 𝑧 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		fnresdm 6595	. . 3 ⊢ (𝐹 Fn 𝐴 → (𝐹 ↾ 𝐴) = 𝐹)
2	1	adantr 480	. 2 ⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝐴) = 𝐹)
3		reseq2 5918	. . . . . 6 ⊢ (𝑥 = ∅ → (𝐹 ↾ 𝑥) = (𝐹 ↾ ∅))
4	3	eleq1d 2816	. . . . 5 ⊢ (𝑥 = ∅ → ((𝐹 ↾ 𝑥) ∈ Fin ↔ (𝐹 ↾ ∅) ∈ Fin))
5	4	imbi2d 340	. . . 4 ⊢ (𝑥 = ∅ → (((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ ∅) ∈ Fin)))
6		reseq2 5918	. . . . . 6 ⊢ (𝑥 = 𝑦 → (𝐹 ↾ 𝑥) = (𝐹 ↾ 𝑦))
7	6	eleq1d 2816	. . . . 5 ⊢ (𝑥 = 𝑦 → ((𝐹 ↾ 𝑥) ∈ Fin ↔ (𝐹 ↾ 𝑦) ∈ Fin))
8	7	imbi2d 340	. . . 4 ⊢ (𝑥 = 𝑦 → (((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝑦) ∈ Fin)))
9		reseq2 5918	. . . . . 6 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → (𝐹 ↾ 𝑥) = (𝐹 ↾ (𝑦 ∪ {𝑧})))
10	9	eleq1d 2816	. . . . 5 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐹 ↾ 𝑥) ∈ Fin ↔ (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
11	10	imbi2d 340	. . . 4 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → (((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin)))
12		reseq2 5918	. . . . . 6 ⊢ (𝑥 = 𝐴 → (𝐹 ↾ 𝑥) = (𝐹 ↾ 𝐴))
13	12	eleq1d 2816	. . . . 5 ⊢ (𝑥 = 𝐴 → ((𝐹 ↾ 𝑥) ∈ Fin ↔ (𝐹 ↾ 𝐴) ∈ Fin))
14	13	imbi2d 340	. . . 4 ⊢ (𝑥 = 𝐴 → (((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝐴) ∈ Fin)))
15		res0 5927	. . . . . 6 ⊢ (𝐹 ↾ ∅) = ∅
16		0fi 8959	. . . . . 6 ⊢ ∅ ∈ Fin
17	15, 16	eqeltri 2827	. . . . 5 ⊢ (𝐹 ↾ ∅) ∈ Fin
18	17	a1i 11	. . . 4 ⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ ∅) ∈ Fin)
19		resundi 5937	. . . . . . . 8 ⊢ (𝐹 ↾ (𝑦 ∪ {𝑧})) = ((𝐹 ↾ 𝑦) ∪ (𝐹 ↾ {𝑧}))
20		snfi 8960	. . . . . . . . . 10 ⊢ {⟨𝑧, (𝐹‘𝑧)⟩} ∈ Fin
21		fnfun 6576	. . . . . . . . . . . 12 ⊢ (𝐹 Fn 𝐴 → Fun 𝐹)
22		funressn 7087	. . . . . . . . . . . 12 ⊢ (Fun 𝐹 → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹‘𝑧)⟩})
23	21, 22	syl 17	. . . . . . . . . . 11 ⊢ (𝐹 Fn 𝐴 → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹‘𝑧)⟩})
24	23	adantr 480	. . . . . . . . . 10 ⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹‘𝑧)⟩})
25		ssfi 9077	. . . . . . . . . 10 ⊢ (({⟨𝑧, (𝐹‘𝑧)⟩} ∈ Fin ∧ (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹‘𝑧)⟩}) → (𝐹 ↾ {𝑧}) ∈ Fin)
26	20, 24, 25	sylancr 587	. . . . . . . . 9 ⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ {𝑧}) ∈ Fin)
27		unfi 9075	. . . . . . . . 9 ⊢ (((𝐹 ↾ 𝑦) ∈ Fin ∧ (𝐹 ↾ {𝑧}) ∈ Fin) → ((𝐹 ↾ 𝑦) ∪ (𝐹 ↾ {𝑧})) ∈ Fin)
28	26, 27	sylan2 593	. . . . . . . 8 ⊢ (((𝐹 ↾ 𝑦) ∈ Fin ∧ (𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin)) → ((𝐹 ↾ 𝑦) ∪ (𝐹 ↾ {𝑧})) ∈ Fin)
29	19, 28	eqeltrid 2835	. . . . . . 7 ⊢ (((𝐹 ↾ 𝑦) ∈ Fin ∧ (𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin)) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin)
30	29	expcom 413	. . . . . 6 ⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → ((𝐹 ↾ 𝑦) ∈ Fin → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
31	30	a2i 14	. . . . 5 ⊢ (((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝑦) ∈ Fin) → ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
32	31	a1i 11	. . . 4 ⊢ (𝑦 ∈ Fin → (((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝑦) ∈ Fin) → ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin)))
33	5, 8, 11, 14, 18, 32	findcard2 9069	. . 3 ⊢ (𝐴 ∈ Fin → ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝐴) ∈ Fin))
34	33	anabsi7 671	. 2 ⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → (𝐹 ↾ 𝐴) ∈ Fin)
35	2, 34	eqeltrrd 2832	1 ⊢ ((𝐹 Fn 𝐴 ∧ 𝐴 ∈ Fin) → 𝐹 ∈ Fin)

Syntax hints:   → wi 4   ∧ wa 395   = wceq 1541   ∈ wcel 2111   ∪ cun 3895   ⊆ wss 3897  ∅c0 4278  {csn 4571  ⟨cop 4577   ↾ cres 5613  Fun wfun 6470   Fn wfn 6471  ‘cfv 6476  Fincfn 8864

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1968  ax-7 2009  ax-8 2113  ax-9 2121  ax-10 2144  ax-11 2160  ax-12 2180  ax-ext 2703  ax-sep 5229  ax-nul 5239  ax-pr 5365  ax-un 7663

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2068  df-mo 2535  df-eu 2564  df-clab 2710  df-cleq 2723  df-clel 2806  df-nfc 2881  df-ne 2929  df-ral 3048  df-rex 3057  df-reu 3347  df-rab 3396  df-v 3438  df-sbc 3737  df-dif 3900  df-un 3902  df-in 3904  df-ss 3914  df-pss 3917  df-nul 4279  df-if 4471  df-pw 4547  df-sn 4572  df-pr 4574  df-op 4578  df-uni 4855  df-br 5087  df-opab 5149  df-tr 5194  df-id 5506  df-eprel 5511  df-po 5519  df-so 5520  df-fr 5564  df-we 5566  df-xp 5617  df-rel 5618  df-cnv 5619  df-co 5620  df-dm 5621  df-rn 5622  df-res 5623  df-ima 5624  df-ord 6304  df-on 6305  df-lim 6306  df-suc 6307  df-iota 6432  df-fun 6478  df-fn 6479  df-f 6480  df-f1 6481  df-fo 6482  df-f1o 6483  df-fv 6484  df-om 7792  df-1o 8380  df-en 8865  df-fin 8868

This theorem is referenced by:  f1oenfi  9083  f1oenfirn  9084  f1domfi  9085  f1domfi2  9086  sbthfilem  9102  fodomfir  9207  fundmfibi  9215  resfnfinfin  9216  unirnffid  9226  mptfi  9230  seqf1olem2  13944  seqf1o  13945  wrdfin  14434  isstruct2  17055  xpsfrnel  17461  cyclnumvtx  29773  cmpcref  33855  carsggect  34323  ptrecube  37660  ftc1anclem3  37735  sstotbnd2  37814  prdstotbnd  37834  cantnfub  43354  cantnfub2  43355  ffi  45210  stoweidlem59  46097  fourierdlem42  46187  fourierdlem54  46198