Theorem fodomfib 9208

Description: Equivalence of an onto mapping and dominance for a nonempty finite set. Unlike fodomb 10409 for arbitrary sets, this theorem does not require the Axiom of Replacement nor the Axiom of Power Sets nor the Axiom of Choice for its proof. (Contributed by NM, 23-Mar-2006.) Avoid ax-pow 5301. (Revised by BTernaryTau, 23-Jun-2025.)

Assertion

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

Distinct variable groups:   𝐴,𝑓   𝐵,𝑓

Proof of Theorem fodomfib

Step	Hyp	Ref	Expression
1		fof 6731	. . . . . . . . . . . . 13 ⊢ (𝑓:𝐴–onto→𝐵 → 𝑓:𝐴⟶𝐵)
2	1	fdmd 6657	. . . . . . . . . . . 12 ⊢ (𝑓:𝐴–onto→𝐵 → dom 𝑓 = 𝐴)
3	2	eqeq1d 2732	. . . . . . . . . . 11 ⊢ (𝑓:𝐴–onto→𝐵 → (dom 𝑓 = ∅ ↔ 𝐴 = ∅))
4		dm0rn0 5862	. . . . . . . . . . . 12 ⊢ (dom 𝑓 = ∅ ↔ ran 𝑓 = ∅)
5		forn 6734	. . . . . . . . . . . . 13 ⊢ (𝑓:𝐴–onto→𝐵 → ran 𝑓 = 𝐵)
6	5	eqeq1d 2732	. . . . . . . . . . . 12 ⊢ (𝑓:𝐴–onto→𝐵 → (ran 𝑓 = ∅ ↔ 𝐵 = ∅))
7	4, 6	bitrid 283	. . . . . . . . . . 11 ⊢ (𝑓:𝐴–onto→𝐵 → (dom 𝑓 = ∅ ↔ 𝐵 = ∅))
8	3, 7	bitr3d 281	. . . . . . . . . 10 ⊢ (𝑓:𝐴–onto→𝐵 → (𝐴 = ∅ ↔ 𝐵 = ∅))
9	8	necon3bid 2970	. . . . . . . . 9 ⊢ (𝑓:𝐴–onto→𝐵 → (𝐴 ≠ ∅ ↔ 𝐵 ≠ ∅))
10	9	biimpac 478	. . . . . . . 8 ⊢ ((𝐴 ≠ ∅ ∧ 𝑓:𝐴–onto→𝐵) → 𝐵 ≠ ∅)
11	10	adantll 714	. . . . . . 7 ⊢ (((𝐴 ∈ Fin ∧ 𝐴 ≠ ∅) ∧ 𝑓:𝐴–onto→𝐵) → 𝐵 ≠ ∅)
12		vex 3438	. . . . . . . . . . . 12 ⊢ 𝑓 ∈ V
13	12	rnex 7835	. . . . . . . . . . 11 ⊢ ran 𝑓 ∈ V
14	5, 13	eqeltrrdi 2838	. . . . . . . . . 10 ⊢ (𝑓:𝐴–onto→𝐵 → 𝐵 ∈ V)
15	14	adantl 481	. . . . . . . . 9 ⊢ ((𝐴 ∈ Fin ∧ 𝑓:𝐴–onto→𝐵) → 𝐵 ∈ V)
16		0sdomg 9014	. . . . . . . . 9 ⊢ (𝐵 ∈ V → (∅ ≺ 𝐵 ↔ 𝐵 ≠ ∅))
17	15, 16	syl 17	. . . . . . . 8 ⊢ ((𝐴 ∈ Fin ∧ 𝑓:𝐴–onto→𝐵) → (∅ ≺ 𝐵 ↔ 𝐵 ≠ ∅))
18	17	adantlr 715	. . . . . . 7 ⊢ (((𝐴 ∈ Fin ∧ 𝐴 ≠ ∅) ∧ 𝑓:𝐴–onto→𝐵) → (∅ ≺ 𝐵 ↔ 𝐵 ≠ ∅))
19	11, 18	mpbird 257	. . . . . 6 ⊢ (((𝐴 ∈ Fin ∧ 𝐴 ≠ ∅) ∧ 𝑓:𝐴–onto→𝐵) → ∅ ≺ 𝐵)
20	19	ex 412	. . . . 5 ⊢ ((𝐴 ∈ Fin ∧ 𝐴 ≠ ∅) → (𝑓:𝐴–onto→𝐵 → ∅ ≺ 𝐵))
21		fodomfi 9191	. . . . . . 7 ⊢ ((𝐴 ∈ Fin ∧ 𝑓:𝐴–onto→𝐵) → 𝐵 ≼ 𝐴)
22	21	ex 412	. . . . . 6 ⊢ (𝐴 ∈ Fin → (𝑓:𝐴–onto→𝐵 → 𝐵 ≼ 𝐴))
23	22	adantr 480	. . . . 5 ⊢ ((𝐴 ∈ Fin ∧ 𝐴 ≠ ∅) → (𝑓:𝐴–onto→𝐵 → 𝐵 ≼ 𝐴))
24	20, 23	jcad 512	. . . 4 ⊢ ((𝐴 ∈ Fin ∧ 𝐴 ≠ ∅) → (𝑓:𝐴–onto→𝐵 → (∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴)))
25	24	exlimdv 1934	. . 3 ⊢ ((𝐴 ∈ Fin ∧ 𝐴 ≠ ∅) → (∃𝑓 𝑓:𝐴–onto→𝐵 → (∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴)))
26	25	expimpd 453	. 2 ⊢ (𝐴 ∈ Fin → ((𝐴 ≠ ∅ ∧ ∃𝑓 𝑓:𝐴–onto→𝐵) → (∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴)))
27		0fi 8959	. . . . 5 ⊢ ∅ ∈ Fin
28		sdomdomtrfi 9105	. . . . 5 ⊢ ((∅ ∈ Fin ∧ ∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴) → ∅ ≺ 𝐴)
29	27, 28	mp3an1 1450	. . . 4 ⊢ ((∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴) → ∅ ≺ 𝐴)
30		0sdomg 9014	. . . 4 ⊢ (𝐴 ∈ Fin → (∅ ≺ 𝐴 ↔ 𝐴 ≠ ∅))
31	29, 30	imbitrid 244	. . 3 ⊢ (𝐴 ∈ Fin → ((∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴) → 𝐴 ≠ ∅))
32		fodomfir 9207	. . . 4 ⊢ ((𝐴 ∈ Fin ∧ ∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴) → ∃𝑓 𝑓:𝐴–onto→𝐵)
33	32	3expib 1122	. . 3 ⊢ (𝐴 ∈ Fin → ((∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴) → ∃𝑓 𝑓:𝐴–onto→𝐵))
34	31, 33	jcad 512	. 2 ⊢ (𝐴 ∈ Fin → ((∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴) → (𝐴 ≠ ∅ ∧ ∃𝑓 𝑓:𝐴–onto→𝐵)))
35	26, 34	impbid 212	1 ⊢ (𝐴 ∈ Fin → ((𝐴 ≠ ∅ ∧ ∃𝑓 𝑓:𝐴–onto→𝐵) ↔ (∅ ≺ 𝐵 ∧ 𝐵 ≼ 𝐴)))

Syntax hints:   → wi 4   ↔ wb 206   ∧ wa 395   = wceq 1541  ∃wex 1780   ∈ wcel 2110   ≠ wne 2926  Vcvv 3434  ∅c0 4281   class class class wbr 5089  dom cdm 5614  ran crn 5615  –onto→wfo 6475   ≼ cdom 8862   ≺ csdm 8863  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 2112  ax-9 2120  ax-10 2143  ax-11 2159  ax-12 2179  ax-ext 2702  ax-sep 5232  ax-nul 5242  ax-pr 5368  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 2067  df-mo 2534  df-eu 2563  df-clab 2709  df-cleq 2722  df-clel 2804  df-nfc 2879  df-ne 2927  df-ral 3046  df-rex 3055  df-reu 3345  df-rab 3394  df-v 3436  df-sbc 3740  df-dif 3903  df-un 3905  df-in 3907  df-ss 3917  df-pss 3920  df-nul 4282  df-if 4474  df-pw 4550  df-sn 4575  df-pr 4577  df-op 4581  df-uni 4858  df-br 5090  df-opab 5152  df-mpt 5171  df-tr 5197  df-id 5509  df-eprel 5514  df-po 5522  df-so 5523  df-fr 5567  df-we 5569  df-xp 5620  df-rel 5621  df-cnv 5622  df-co 5623  df-dm 5624  df-rn 5625  df-res 5626  df-ima 5627  df-ord 6305  df-on 6306  df-lim 6307  df-suc 6308  df-iota 6433  df-fun 6479  df-fn 6480  df-f 6481  df-f1 6482  df-fo 6483  df-f1o 6484  df-fv 6485  df-om 7792  df-1o 8380  df-en 8865  df-dom 8866  df-sdom 8867  df-fin 8868

This theorem is referenced by: (None)