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

Theorem fodomfi 8785
 Description: An onto function implies dominance of domain over range, for finite sets. Unlike fodom 9938 for arbitrary sets, this theorem does not require the Axiom of Choice for its proof. (Contributed by NM, 23-Mar-2006.) (Proof shortened by Mario Carneiro, 16-Nov-2014.)
Assertion
Ref Expression
fodomfi ((𝐴 ∈ Fin ∧ 𝐹:𝐴onto𝐵) → 𝐵𝐴)

Proof of Theorem fodomfi
Dummy variables 𝑥 𝑦 𝑧 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 foima 6574 . . 3 (𝐹:𝐴onto𝐵 → (𝐹𝐴) = 𝐵)
21adantl 485 . 2 ((𝐴 ∈ Fin ∧ 𝐹:𝐴onto𝐵) → (𝐹𝐴) = 𝐵)
3 imaeq2 5896 . . . . . . 7 (𝑥 = ∅ → (𝐹𝑥) = (𝐹 “ ∅))
4 ima0 5916 . . . . . . 7 (𝐹 “ ∅) = ∅
53, 4eqtrdi 2852 . . . . . 6 (𝑥 = ∅ → (𝐹𝑥) = ∅)
6 id 22 . . . . . 6 (𝑥 = ∅ → 𝑥 = ∅)
75, 6breq12d 5046 . . . . 5 (𝑥 = ∅ → ((𝐹𝑥) ≼ 𝑥 ↔ ∅ ≼ ∅))
87imbi2d 344 . . . 4 (𝑥 = ∅ → ((𝐹 Fn 𝐴 → (𝐹𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → ∅ ≼ ∅)))
9 imaeq2 5896 . . . . . 6 (𝑥 = 𝑦 → (𝐹𝑥) = (𝐹𝑦))
10 id 22 . . . . . 6 (𝑥 = 𝑦𝑥 = 𝑦)
119, 10breq12d 5046 . . . . 5 (𝑥 = 𝑦 → ((𝐹𝑥) ≼ 𝑥 ↔ (𝐹𝑦) ≼ 𝑦))
1211imbi2d 344 . . . 4 (𝑥 = 𝑦 → ((𝐹 Fn 𝐴 → (𝐹𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → (𝐹𝑦) ≼ 𝑦)))
13 imaeq2 5896 . . . . . 6 (𝑥 = (𝑦 ∪ {𝑧}) → (𝐹𝑥) = (𝐹 “ (𝑦 ∪ {𝑧})))
14 id 22 . . . . . 6 (𝑥 = (𝑦 ∪ {𝑧}) → 𝑥 = (𝑦 ∪ {𝑧}))
1513, 14breq12d 5046 . . . . 5 (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐹𝑥) ≼ 𝑥 ↔ (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧})))
1615imbi2d 344 . . . 4 (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐹 Fn 𝐴 → (𝐹𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))))
17 imaeq2 5896 . . . . . 6 (𝑥 = 𝐴 → (𝐹𝑥) = (𝐹𝐴))
18 id 22 . . . . . 6 (𝑥 = 𝐴𝑥 = 𝐴)
1917, 18breq12d 5046 . . . . 5 (𝑥 = 𝐴 → ((𝐹𝑥) ≼ 𝑥 ↔ (𝐹𝐴) ≼ 𝐴))
2019imbi2d 344 . . . 4 (𝑥 = 𝐴 → ((𝐹 Fn 𝐴 → (𝐹𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → (𝐹𝐴) ≼ 𝐴)))
21 0ex 5178 . . . . . 6 ∅ ∈ V
22210dom 8635 . . . . 5 ∅ ≼ ∅
2322a1i 11 . . . 4 (𝐹 Fn 𝐴 → ∅ ≼ ∅)
24 fnfun 6427 . . . . . . . . . . . . . 14 (𝐹 Fn 𝐴 → Fun 𝐹)
2524ad2antrl 727 . . . . . . . . . . . . 13 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → Fun 𝐹)
26 funressn 6902 . . . . . . . . . . . . 13 (Fun 𝐹 → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹𝑧)⟩})
27 rnss 5777 . . . . . . . . . . . . 13 ((𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹𝑧)⟩} → ran (𝐹 ↾ {𝑧}) ⊆ ran {⟨𝑧, (𝐹𝑧)⟩})
2825, 26, 273syl 18 . . . . . . . . . . . 12 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → ran (𝐹 ↾ {𝑧}) ⊆ ran {⟨𝑧, (𝐹𝑧)⟩})
29 df-ima 5536 . . . . . . . . . . . 12 (𝐹 “ {𝑧}) = ran (𝐹 ↾ {𝑧})
30 vex 3447 . . . . . . . . . . . . . 14 𝑧 ∈ V
3130rnsnop 6052 . . . . . . . . . . . . 13 ran {⟨𝑧, (𝐹𝑧)⟩} = {(𝐹𝑧)}
3231eqcomi 2810 . . . . . . . . . . . 12 {(𝐹𝑧)} = ran {⟨𝑧, (𝐹𝑧)⟩}
3328, 29, 323sstr4g 3963 . . . . . . . . . . 11 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ⊆ {(𝐹𝑧)})
34 snex 5300 . . . . . . . . . . 11 {(𝐹𝑧)} ∈ V
35 ssexg 5194 . . . . . . . . . . 11 (((𝐹 “ {𝑧}) ⊆ {(𝐹𝑧)} ∧ {(𝐹𝑧)} ∈ V) → (𝐹 “ {𝑧}) ∈ V)
3633, 34, 35sylancl 589 . . . . . . . . . 10 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ∈ V)
37 fvi 6719 . . . . . . . . . 10 ((𝐹 “ {𝑧}) ∈ V → ( I ‘(𝐹 “ {𝑧})) = (𝐹 “ {𝑧}))
3836, 37syl 17 . . . . . . . . 9 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → ( I ‘(𝐹 “ {𝑧})) = (𝐹 “ {𝑧}))
3938uneq2d 4093 . . . . . . . 8 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → ((𝐹𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) = ((𝐹𝑦) ∪ (𝐹 “ {𝑧})))
40 imaundi 5979 . . . . . . . 8 (𝐹 “ (𝑦 ∪ {𝑧})) = ((𝐹𝑦) ∪ (𝐹 “ {𝑧}))
4139, 40eqtr4di 2854 . . . . . . 7 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → ((𝐹𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) = (𝐹 “ (𝑦 ∪ {𝑧})))
42 simprr 772 . . . . . . . 8 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → (𝐹𝑦) ≼ 𝑦)
43 ssdomg 8542 . . . . . . . . . . 11 ({(𝐹𝑧)} ∈ V → ((𝐹 “ {𝑧}) ⊆ {(𝐹𝑧)} → (𝐹 “ {𝑧}) ≼ {(𝐹𝑧)}))
4434, 33, 43mpsyl 68 . . . . . . . . . 10 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ≼ {(𝐹𝑧)})
45 fvex 6662 . . . . . . . . . . . 12 (𝐹𝑧) ∈ V
4645ensn1 8560 . . . . . . . . . . 11 {(𝐹𝑧)} ≈ 1o
4730ensn1 8560 . . . . . . . . . . 11 {𝑧} ≈ 1o
4846, 47entr4i 8553 . . . . . . . . . 10 {(𝐹𝑧)} ≈ {𝑧}
49 domentr 8555 . . . . . . . . . 10 (((𝐹 “ {𝑧}) ≼ {(𝐹𝑧)} ∧ {(𝐹𝑧)} ≈ {𝑧}) → (𝐹 “ {𝑧}) ≼ {𝑧})
5044, 48, 49sylancl 589 . . . . . . . . 9 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ≼ {𝑧})
5138, 50eqbrtrd 5055 . . . . . . . 8 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → ( I ‘(𝐹 “ {𝑧})) ≼ {𝑧})
52 simplr 768 . . . . . . . . 9 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → ¬ 𝑧𝑦)
53 disjsn 4610 . . . . . . . . 9 ((𝑦 ∩ {𝑧}) = ∅ ↔ ¬ 𝑧𝑦)
5452, 53sylibr 237 . . . . . . . 8 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → (𝑦 ∩ {𝑧}) = ∅)
55 undom 8592 . . . . . . . 8 ((((𝐹𝑦) ≼ 𝑦 ∧ ( I ‘(𝐹 “ {𝑧})) ≼ {𝑧}) ∧ (𝑦 ∩ {𝑧}) = ∅) → ((𝐹𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) ≼ (𝑦 ∪ {𝑧}))
5642, 51, 54, 55syl21anc 836 . . . . . . 7 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → ((𝐹𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) ≼ (𝑦 ∪ {𝑧}))
5741, 56eqbrtrrd 5057 . . . . . 6 (((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹𝑦) ≼ 𝑦)) → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))
5857exp32 424 . . . . 5 ((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) → (𝐹 Fn 𝐴 → ((𝐹𝑦) ≼ 𝑦 → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))))
5958a2d 29 . . . 4 ((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) → ((𝐹 Fn 𝐴 → (𝐹𝑦) ≼ 𝑦) → (𝐹 Fn 𝐴 → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))))
608, 12, 16, 20, 23, 59findcard2s 8747 . . 3 (𝐴 ∈ Fin → (𝐹 Fn 𝐴 → (𝐹𝐴) ≼ 𝐴))
61 fofn 6571 . . 3 (𝐹:𝐴onto𝐵𝐹 Fn 𝐴)
6260, 61impel 509 . 2 ((𝐴 ∈ Fin ∧ 𝐹:𝐴onto𝐵) → (𝐹𝐴) ≼ 𝐴)
632, 62eqbrtrrd 5057 1 ((𝐴 ∈ Fin ∧ 𝐹:𝐴onto𝐵) → 𝐵𝐴)
 Colors of variables: wff setvar class Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 399   = wceq 1538   ∈ wcel 2112  Vcvv 3444   ∪ cun 3882   ∩ cin 3883   ⊆ wss 3884  ∅c0 4246  {csn 4528  ⟨cop 4534   class class class wbr 5033   I cid 5427  ran crn 5524   ↾ cres 5525   “ cima 5526  Fun wfun 6322   Fn wfn 6323  –onto→wfo 6326  ‘cfv 6328  1oc1o 8082   ≈ cen 8493   ≼ cdom 8494  Fincfn 8496 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2114  ax-9 2122  ax-10 2143  ax-11 2159  ax-12 2176  ax-ext 2773  ax-sep 5170  ax-nul 5177  ax-pow 5234  ax-pr 5298  ax-un 7445 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3or 1085  df-3an 1086  df-tru 1541  df-ex 1782  df-nf 1786  df-sb 2070  df-mo 2601  df-eu 2632  df-clab 2780  df-cleq 2794  df-clel 2873  df-nfc 2941  df-ne 2991  df-ral 3114  df-rex 3115  df-reu 3116  df-rab 3118  df-v 3446  df-sbc 3724  df-dif 3887  df-un 3889  df-in 3891  df-ss 3901  df-pss 3903  df-nul 4247  df-if 4429  df-pw 4502  df-sn 4529  df-pr 4531  df-tp 4533  df-op 4535  df-uni 4804  df-br 5034  df-opab 5096  df-tr 5140  df-id 5428  df-eprel 5433  df-po 5442  df-so 5443  df-fr 5482  df-we 5484  df-xp 5529  df-rel 5530  df-cnv 5531  df-co 5532  df-dm 5533  df-rn 5534  df-res 5535  df-ima 5536  df-ord 6166  df-on 6167  df-lim 6168  df-suc 6169  df-iota 6287  df-fun 6330  df-fn 6331  df-f 6332  df-f1 6333  df-fo 6334  df-f1o 6335  df-fv 6336  df-om 7565  df-1o 8089  df-er 8276  df-en 8497  df-dom 8498  df-fin 8500 This theorem is referenced by:  fodomfib  8786  fofinf1o  8787  fidomdm  8789  fofi  8798  pwfilem  8806  cmpsub  22008  alexsubALT  22659  phpreu  35034  poimirlem26  35076
 Copyright terms: Public domain W3C validator