Metamath Proof Explorer


Theorem fodomfib

Description: Equivalence of an onto mapping and dominance for a nonempty finite set. Unlike fodomb for arbitrary sets, this theorem does not require the Axiom of Choice for its proof. (Contributed by NM, 23-Mar-2006)

Ref Expression
Assertion fodomfib ( 𝐴 ∈ Fin → ( ( 𝐴 ≠ ∅ ∧ ∃ 𝑓 𝑓 : 𝐴onto𝐵 ) ↔ ( ∅ ≺ 𝐵𝐵𝐴 ) ) )

Proof

Step Hyp Ref Expression
1 fof ( 𝑓 : 𝐴onto𝐵𝑓 : 𝐴𝐵 )
2 1 fdmd ( 𝑓 : 𝐴onto𝐵 → dom 𝑓 = 𝐴 )
3 2 eqeq1d ( 𝑓 : 𝐴onto𝐵 → ( dom 𝑓 = ∅ ↔ 𝐴 = ∅ ) )
4 dm0rn0 ( dom 𝑓 = ∅ ↔ ran 𝑓 = ∅ )
5 forn ( 𝑓 : 𝐴onto𝐵 → ran 𝑓 = 𝐵 )
6 5 eqeq1d ( 𝑓 : 𝐴onto𝐵 → ( ran 𝑓 = ∅ ↔ 𝐵 = ∅ ) )
7 4 6 bitrid ( 𝑓 : 𝐴onto𝐵 → ( dom 𝑓 = ∅ ↔ 𝐵 = ∅ ) )
8 3 7 bitr3d ( 𝑓 : 𝐴onto𝐵 → ( 𝐴 = ∅ ↔ 𝐵 = ∅ ) )
9 8 necon3bid ( 𝑓 : 𝐴onto𝐵 → ( 𝐴 ≠ ∅ ↔ 𝐵 ≠ ∅ ) )
10 9 biimpac ( ( 𝐴 ≠ ∅ ∧ 𝑓 : 𝐴onto𝐵 ) → 𝐵 ≠ ∅ )
11 10 adantll ( ( ( 𝐴 ∈ Fin ∧ 𝐴 ≠ ∅ ) ∧ 𝑓 : 𝐴onto𝐵 ) → 𝐵 ≠ ∅ )
12 vex 𝑓 ∈ V
13 12 rnex ran 𝑓 ∈ V
14 5 13 eqeltrrdi ( 𝑓 : 𝐴onto𝐵𝐵 ∈ V )
15 14 adantl ( ( 𝐴 ∈ Fin ∧ 𝑓 : 𝐴onto𝐵 ) → 𝐵 ∈ V )
16 0sdomg ( 𝐵 ∈ V → ( ∅ ≺ 𝐵𝐵 ≠ ∅ ) )
17 15 16 syl ( ( 𝐴 ∈ Fin ∧ 𝑓 : 𝐴onto𝐵 ) → ( ∅ ≺ 𝐵𝐵 ≠ ∅ ) )
18 17 adantlr ( ( ( 𝐴 ∈ Fin ∧ 𝐴 ≠ ∅ ) ∧ 𝑓 : 𝐴onto𝐵 ) → ( ∅ ≺ 𝐵𝐵 ≠ ∅ ) )
19 11 18 mpbird ( ( ( 𝐴 ∈ Fin ∧ 𝐴 ≠ ∅ ) ∧ 𝑓 : 𝐴onto𝐵 ) → ∅ ≺ 𝐵 )
20 19 ex ( ( 𝐴 ∈ Fin ∧ 𝐴 ≠ ∅ ) → ( 𝑓 : 𝐴onto𝐵 → ∅ ≺ 𝐵 ) )
21 fodomfi ( ( 𝐴 ∈ Fin ∧ 𝑓 : 𝐴onto𝐵 ) → 𝐵𝐴 )
22 21 ex ( 𝐴 ∈ Fin → ( 𝑓 : 𝐴onto𝐵𝐵𝐴 ) )
23 22 adantr ( ( 𝐴 ∈ Fin ∧ 𝐴 ≠ ∅ ) → ( 𝑓 : 𝐴onto𝐵𝐵𝐴 ) )
24 20 23 jcad ( ( 𝐴 ∈ Fin ∧ 𝐴 ≠ ∅ ) → ( 𝑓 : 𝐴onto𝐵 → ( ∅ ≺ 𝐵𝐵𝐴 ) ) )
25 24 exlimdv ( ( 𝐴 ∈ Fin ∧ 𝐴 ≠ ∅ ) → ( ∃ 𝑓 𝑓 : 𝐴onto𝐵 → ( ∅ ≺ 𝐵𝐵𝐴 ) ) )
26 25 expimpd ( 𝐴 ∈ Fin → ( ( 𝐴 ≠ ∅ ∧ ∃ 𝑓 𝑓 : 𝐴onto𝐵 ) → ( ∅ ≺ 𝐵𝐵𝐴 ) ) )
27 sdomdomtr ( ( ∅ ≺ 𝐵𝐵𝐴 ) → ∅ ≺ 𝐴 )
28 0sdomg ( 𝐴 ∈ Fin → ( ∅ ≺ 𝐴𝐴 ≠ ∅ ) )
29 27 28 syl5ib ( 𝐴 ∈ Fin → ( ( ∅ ≺ 𝐵𝐵𝐴 ) → 𝐴 ≠ ∅ ) )
30 fodomr ( ( ∅ ≺ 𝐵𝐵𝐴 ) → ∃ 𝑓 𝑓 : 𝐴onto𝐵 )
31 29 30 jca2 ( 𝐴 ∈ Fin → ( ( ∅ ≺ 𝐵𝐵𝐴 ) → ( 𝐴 ≠ ∅ ∧ ∃ 𝑓 𝑓 : 𝐴onto𝐵 ) ) )
32 26 31 impbid ( 𝐴 ∈ Fin → ( ( 𝐴 ≠ ∅ ∧ ∃ 𝑓 𝑓 : 𝐴onto𝐵 ) ↔ ( ∅ ≺ 𝐵𝐵𝐴 ) ) )