ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  fnfi GIF version

Theorem fnfi 6936
Description: A version of fnex 5739 for finite 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.
StepHypRef Expression
1 fnresdm 5326 . . 3 (𝐹 Fn 𝐴 → (𝐹𝐴) = 𝐹)
21adantr 276 . 2 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝐴) = 𝐹)
3 reseq2 4903 . . . 4 (𝑤 = ∅ → (𝐹𝑤) = (𝐹 ↾ ∅))
43eleq1d 2246 . . 3 (𝑤 = ∅ → ((𝐹𝑤) ∈ Fin ↔ (𝐹 ↾ ∅) ∈ Fin))
5 reseq2 4903 . . . 4 (𝑤 = 𝑦 → (𝐹𝑤) = (𝐹𝑦))
65eleq1d 2246 . . 3 (𝑤 = 𝑦 → ((𝐹𝑤) ∈ Fin ↔ (𝐹𝑦) ∈ Fin))
7 reseq2 4903 . . . 4 (𝑤 = (𝑦 ∪ {𝑧}) → (𝐹𝑤) = (𝐹 ↾ (𝑦 ∪ {𝑧})))
87eleq1d 2246 . . 3 (𝑤 = (𝑦 ∪ {𝑧}) → ((𝐹𝑤) ∈ Fin ↔ (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
9 reseq2 4903 . . . 4 (𝑤 = 𝐴 → (𝐹𝑤) = (𝐹𝐴))
109eleq1d 2246 . . 3 (𝑤 = 𝐴 → ((𝐹𝑤) ∈ Fin ↔ (𝐹𝐴) ∈ Fin))
11 res0 4912 . . . . 5 (𝐹 ↾ ∅) = ∅
12 0fin 6884 . . . . 5 ∅ ∈ Fin
1311, 12eqeltri 2250 . . . 4 (𝐹 ↾ ∅) ∈ Fin
1413a1i 9 . . 3 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹 ↾ ∅) ∈ Fin)
15 resundi 4921 . . . . 5 (𝐹 ↾ (𝑦 ∪ {𝑧})) = ((𝐹𝑦) ∪ (𝐹 ↾ {𝑧}))
16 simp-4l 541 . . . . . . . 8 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → 𝐹 Fn 𝐴)
17 simplrr 536 . . . . . . . . 9 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → 𝑧 ∈ (𝐴𝑦))
1817eldifad 3141 . . . . . . . 8 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → 𝑧𝐴)
19 fnressn 5703 . . . . . . . 8 ((𝐹 Fn 𝐴𝑧𝐴) → (𝐹 ↾ {𝑧}) = {⟨𝑧, (𝐹𝑧)⟩})
2016, 18, 19syl2anc 411 . . . . . . 7 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → (𝐹 ↾ {𝑧}) = {⟨𝑧, (𝐹𝑧)⟩})
2120uneq2d 3290 . . . . . 6 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → ((𝐹𝑦) ∪ (𝐹 ↾ {𝑧})) = ((𝐹𝑦) ∪ {⟨𝑧, (𝐹𝑧)⟩}))
22 simpr 110 . . . . . . 7 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → (𝐹𝑦) ∈ Fin)
2317elexd 2751 . . . . . . . 8 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → 𝑧 ∈ V)
24 funfvex 5533 . . . . . . . . . 10 ((Fun 𝐹𝑧 ∈ dom 𝐹) → (𝐹𝑧) ∈ V)
2524funfni 5317 . . . . . . . . 9 ((𝐹 Fn 𝐴𝑧𝐴) → (𝐹𝑧) ∈ V)
2616, 18, 25syl2anc 411 . . . . . . . 8 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → (𝐹𝑧) ∈ V)
27 opexg 4229 . . . . . . . 8 ((𝑧 ∈ V ∧ (𝐹𝑧) ∈ V) → ⟨𝑧, (𝐹𝑧)⟩ ∈ V)
2823, 26, 27syl2anc 411 . . . . . . 7 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → ⟨𝑧, (𝐹𝑧)⟩ ∈ V)
2917eldifbd 3142 . . . . . . . 8 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → ¬ 𝑧𝑦)
30 opeldmg 4833 . . . . . . . . . . 11 ((𝑧𝐴 ∧ (𝐹𝑧) ∈ V) → (⟨𝑧, (𝐹𝑧)⟩ ∈ (𝐹𝑦) → 𝑧 ∈ dom (𝐹𝑦)))
3118, 26, 30syl2anc 411 . . . . . . . . . 10 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → (⟨𝑧, (𝐹𝑧)⟩ ∈ (𝐹𝑦) → 𝑧 ∈ dom (𝐹𝑦)))
32 dmres 4929 . . . . . . . . . . 11 dom (𝐹𝑦) = (𝑦 ∩ dom 𝐹)
3332eleq2i 2244 . . . . . . . . . 10 (𝑧 ∈ dom (𝐹𝑦) ↔ 𝑧 ∈ (𝑦 ∩ dom 𝐹))
3431, 33imbitrdi 161 . . . . . . . . 9 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → (⟨𝑧, (𝐹𝑧)⟩ ∈ (𝐹𝑦) → 𝑧 ∈ (𝑦 ∩ dom 𝐹)))
35 elin 3319 . . . . . . . . . 10 (𝑧 ∈ (𝑦 ∩ dom 𝐹) ↔ (𝑧𝑦𝑧 ∈ dom 𝐹))
3635simplbi 274 . . . . . . . . 9 (𝑧 ∈ (𝑦 ∩ dom 𝐹) → 𝑧𝑦)
3734, 36syl6 33 . . . . . . . 8 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → (⟨𝑧, (𝐹𝑧)⟩ ∈ (𝐹𝑦) → 𝑧𝑦))
3829, 37mtod 663 . . . . . . 7 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → ¬ ⟨𝑧, (𝐹𝑧)⟩ ∈ (𝐹𝑦))
39 unsnfi 6918 . . . . . . 7 (((𝐹𝑦) ∈ Fin ∧ ⟨𝑧, (𝐹𝑧)⟩ ∈ V ∧ ¬ ⟨𝑧, (𝐹𝑧)⟩ ∈ (𝐹𝑦)) → ((𝐹𝑦) ∪ {⟨𝑧, (𝐹𝑧)⟩}) ∈ Fin)
4022, 28, 38, 39syl3anc 1238 . . . . . 6 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → ((𝐹𝑦) ∪ {⟨𝑧, (𝐹𝑧)⟩}) ∈ Fin)
4121, 40eqeltrd 2254 . . . . 5 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → ((𝐹𝑦) ∪ (𝐹 ↾ {𝑧})) ∈ Fin)
4215, 41eqeltrid 2264 . . . 4 (((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) ∧ (𝐹𝑦) ∈ Fin) → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin)
4342ex 115 . . 3 ((((𝐹 Fn 𝐴𝐴 ∈ Fin) ∧ 𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) → ((𝐹𝑦) ∈ Fin → (𝐹 ↾ (𝑦 ∪ {𝑧})) ∈ Fin))
44 simpr 110 . . 3 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → 𝐴 ∈ Fin)
454, 6, 8, 10, 14, 43, 44findcard2sd 6892 . 2 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → (𝐹𝐴) ∈ Fin)
462, 45eqeltrrd 2255 1 ((𝐹 Fn 𝐴𝐴 ∈ Fin) → 𝐹 ∈ Fin)
Colors of variables: wff set class
Syntax hints:  ¬ wn 3  wi 4  wa 104   = wceq 1353  wcel 2148  Vcvv 2738  cdif 3127  cun 3128  cin 3129  wss 3130  c0 3423  {csn 3593  cop 3596  dom cdm 4627  cres 4629   Fn wfn 5212  cfv 5217  Fincfn 6740
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 614  ax-in2 615  ax-io 709  ax-5 1447  ax-7 1448  ax-gen 1449  ax-ie1 1493  ax-ie2 1494  ax-8 1504  ax-10 1505  ax-11 1506  ax-i12 1507  ax-bndl 1509  ax-4 1510  ax-17 1526  ax-i9 1530  ax-ial 1534  ax-i5r 1535  ax-13 2150  ax-14 2151  ax-ext 2159  ax-coll 4119  ax-sep 4122  ax-nul 4130  ax-pow 4175  ax-pr 4210  ax-un 4434  ax-setind 4537  ax-iinf 4588
This theorem depends on definitions:  df-bi 117  df-dc 835  df-3or 979  df-3an 980  df-tru 1356  df-fal 1359  df-nf 1461  df-sb 1763  df-eu 2029  df-mo 2030  df-clab 2164  df-cleq 2170  df-clel 2173  df-nfc 2308  df-ne 2348  df-ral 2460  df-rex 2461  df-reu 2462  df-rab 2464  df-v 2740  df-sbc 2964  df-csb 3059  df-dif 3132  df-un 3134  df-in 3136  df-ss 3143  df-nul 3424  df-if 3536  df-pw 3578  df-sn 3599  df-pr 3600  df-op 3602  df-uni 3811  df-int 3846  df-iun 3889  df-br 4005  df-opab 4066  df-mpt 4067  df-tr 4103  df-id 4294  df-iord 4367  df-on 4369  df-suc 4372  df-iom 4591  df-xp 4633  df-rel 4634  df-cnv 4635  df-co 4636  df-dm 4637  df-rn 4638  df-res 4639  df-ima 4640  df-iota 5179  df-fun 5219  df-fn 5220  df-f 5221  df-f1 5222  df-fo 5223  df-f1o 5224  df-fv 5225  df-1o 6417  df-er 6535  df-en 6741  df-fin 6743
This theorem is referenced by:  fundmfibi  6938  resfnfinfinss  6939  fihashf1rn  10768  fihashfn  10780  xpsfrnel  12763
  Copyright terms: Public domain W3C validator