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

Theorem fnfi 8395
Description: A version of fnex 6637 for finite sets that does not require Replacement. (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.
StepHypRef Expression
1 fnresdm 6153 . . 3 (𝐹 Fn 𝐴 → (𝐹𝐴) = 𝐹)
21adantr 472 . 2 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝐴) = 𝐹)
3 reseq2 5538 . . . . . 6 (𝑥 = ∅ → (𝐹𝑥) = (𝐹 ↾ ∅))
43eleq1d 2816 . . . . 5 (𝑥 = ∅ → ((𝐹𝑥) ∈ Fin ↔ (𝐹 ↾ ∅) ∈ Fin))
54imbi2d 329 . . . 4 (𝑥 = ∅ → (((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ ∅) ∈ Fin)))
6 reseq2 5538 . . . . . 6 (𝑥 = 𝑦 → (𝐹𝑥) = (𝐹𝑦))
76eleq1d 2816 . . . . 5 (𝑥 = 𝑦 → ((𝐹𝑥) ∈ Fin ↔ (𝐹𝑦) ∈ Fin))
87imbi2d 329 . . . 4 (𝑥 = 𝑦 → (((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝑦) ∈ Fin)))
9 reseq2 5538 . . . . . 6 (𝑥 = (𝑦 ∪ {𝑧}) → (𝐹𝑥) = (𝐹 ↾ (𝑦 ∪ {𝑧})))
109eleq1d 2816 . . . . 5 (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐹𝑥) ∈ Fin ↔ (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
1110imbi2d 329 . . . 4 (𝑥 = (𝑦 ∪ {𝑧}) → (((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin)))
12 reseq2 5538 . . . . . 6 (𝑥 = 𝐴 → (𝐹𝑥) = (𝐹𝐴))
1312eleq1d 2816 . . . . 5 (𝑥 = 𝐴 → ((𝐹𝑥) ∈ Fin ↔ (𝐹𝐴) ∈ Fin))
1413imbi2d 329 . . . 4 (𝑥 = 𝐴 → (((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝑥) ∈ Fin) ↔ ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝐴) ∈ Fin)))
15 res0 5547 . . . . . 6 (𝐹 ↾ ∅) = ∅
16 0fin 8345 . . . . . 6 ∅ ∈ Fin
1715, 16eqeltri 2827 . . . . 5 (𝐹 ↾ ∅) ∈ Fin
1817a1i 11 . . . 4 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ ∅) ∈ Fin)
19 resundi 5560 . . . . . . . 8 (𝐹 ↾ (𝑦 ∪ {𝑧})) = ((𝐹𝑦) ∪ (𝐹 ↾ {𝑧}))
20 snfi 8195 . . . . . . . . . 10 {⟨𝑧, (𝐹𝑧)⟩} ∈ Fin
21 fnfun 6141 . . . . . . . . . . . 12 (𝐹 Fn 𝐴 → Fun 𝐹)
22 funressn 6581 . . . . . . . . . . . 12 (Fun 𝐹 → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹𝑧)⟩})
2321, 22syl 17 . . . . . . . . . . 11 (𝐹 Fn 𝐴 → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹𝑧)⟩})
2423adantr 472 . . . . . . . . . 10 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹𝑧)⟩})
25 ssfi 8337 . . . . . . . . . 10 (({⟨𝑧, (𝐹𝑧)⟩} ∈ Fin ∧ (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹𝑧)⟩}) → (𝐹 ↾ {𝑧}) ∈ Fin)
2620, 24, 25sylancr 698 . . . . . . . . 9 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ {𝑧}) ∈ Fin)
27 unfi 8384 . . . . . . . . 9 (((𝐹𝑦) ∈ Fin ∧ (𝐹 ↾ {𝑧}) ∈ Fin) → ((𝐹𝑦) ∪ (𝐹 ↾ {𝑧})) ∈ Fin)
2826, 27sylan2 492 . . . . . . . 8 (((𝐹𝑦) ∈ Fin ∧ (𝐹 Fn 𝐴𝐴 ∈ Fin)) → ((𝐹𝑦) ∪ (𝐹 ↾ {𝑧})) ∈ Fin)
2919, 28syl5eqel 2835 . . . . . . 7 (((𝐹𝑦) ∈ Fin ∧ (𝐹 Fn 𝐴𝐴 ∈ Fin)) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin)
3029expcom 450 . . . . . 6 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → ((𝐹𝑦) ∈ Fin → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
3130a2i 14 . . . . 5 (((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝑦) ∈ Fin) → ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
3231a1i 11 . . . 4 (𝑦 ∈ Fin → (((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝑦) ∈ Fin) → ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin)))
335, 8, 11, 14, 18, 32findcard2 8357 . . 3 (𝐴 ∈ Fin → ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝐴) ∈ Fin))
3433anabsi7 895 . 2 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝐴) ∈ Fin)
352, 34eqeltrrd 2832 1 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → 𝐹 ∈ Fin)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 383   = wceq 1624  wcel 2131  cun 3705  wss 3707  c0 4050  {csn 4313  cop 4319  cres 5260  Fun wfun 6035   Fn wfn 6036  cfv 6041  Fincfn 8113
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1863  ax-4 1878  ax-5 1980  ax-6 2046  ax-7 2082  ax-8 2133  ax-9 2140  ax-10 2160  ax-11 2175  ax-12 2188  ax-13 2383  ax-ext 2732  ax-sep 4925  ax-nul 4933  ax-pow 4984  ax-pr 5047  ax-un 7106
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1627  df-ex 1846  df-nf 1851  df-sb 2039  df-eu 2603  df-mo 2604  df-clab 2739  df-cleq 2745  df-clel 2748  df-nfc 2883  df-ne 2925  df-ral 3047  df-rex 3048  df-reu 3049  df-rab 3051  df-v 3334  df-sbc 3569  df-csb 3667  df-dif 3710  df-un 3712  df-in 3714  df-ss 3721  df-pss 3723  df-nul 4051  df-if 4223  df-pw 4296  df-sn 4314  df-pr 4316  df-tp 4318  df-op 4320  df-uni 4581  df-int 4620  df-iun 4666  df-br 4797  df-opab 4857  df-mpt 4874  df-tr 4897  df-id 5166  df-eprel 5171  df-po 5179  df-so 5180  df-fr 5217  df-we 5219  df-xp 5264  df-rel 5265  df-cnv 5266  df-co 5267  df-dm 5268  df-rn 5269  df-res 5270  df-ima 5271  df-pred 5833  df-ord 5879  df-on 5880  df-lim 5881  df-suc 5882  df-iota 6004  df-fun 6043  df-fn 6044  df-f 6045  df-f1 6046  df-fo 6047  df-f1o 6048  df-fv 6049  df-ov 6808  df-oprab 6809  df-mpt2 6810  df-om 7223  df-wrecs 7568  df-recs 7629  df-rdg 7667  df-1o 7721  df-oadd 7725  df-er 7903  df-en 8114  df-fin 8117
This theorem is referenced by:  fundmfibi  8402  resfnfinfin  8403  unirnffid  8415  mptfi  8422  seqf1olem2  13027  seqf1o  13028  wrdfin  13501  isstruct2  16061  xpsfrnel  16417  cmpcref  30218  carsggect  30681  ptrecube  33714  ftc1anclem3  33792  sstotbnd2  33878  prdstotbnd  33898  ffi  39845  stoweidlem59  40771  fourierdlem42  40861  fourierdlem54  40872
  Copyright terms: Public domain W3C validator