Theorem fodomfi 9351

Description: An onto function implies dominance of domain over range, for finite sets. Unlike fodomg 10563 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.) (Proof shortened by Mario Carneiro, 16-Nov-2014.) Avoid ax-pow 5364. (Revised by BTernaryTau, 20-Jun-2025.)

Assertion

Ref	Expression
fodomfi	⊢ ((𝐴 ∈ Fin ∧ 𝐹:𝐴–onto→𝐵) → 𝐵 ≼ 𝐴)

Proof of Theorem fodomfi

Dummy variables 𝑥 𝑦 𝑧 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		foima 6824	. . 3 ⊢ (𝐹:𝐴–onto→𝐵 → (𝐹 “ 𝐴) = 𝐵)
2	1	adantl 481	. 2 ⊢ ((𝐴 ∈ Fin ∧ 𝐹:𝐴–onto→𝐵) → (𝐹 “ 𝐴) = 𝐵)
3		imaeq2 6073	. . . . . . 7 ⊢ (𝑥 = ∅ → (𝐹 “ 𝑥) = (𝐹 “ ∅))
4		ima0 6094	. . . . . . 7 ⊢ (𝐹 “ ∅) = ∅
5	3, 4	eqtrdi 2792	. . . . . 6 ⊢ (𝑥 = ∅ → (𝐹 “ 𝑥) = ∅)
6		id 22	. . . . . 6 ⊢ (𝑥 = ∅ → 𝑥 = ∅)
7	5, 6	breq12d 5155	. . . . 5 ⊢ (𝑥 = ∅ → ((𝐹 “ 𝑥) ≼ 𝑥 ↔ ∅ ≼ ∅))
8	7	imbi2d 340	. . . 4 ⊢ (𝑥 = ∅ → ((𝐹 Fn 𝐴 → (𝐹 “ 𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → ∅ ≼ ∅)))
9		imaeq2 6073	. . . . . 6 ⊢ (𝑥 = 𝑦 → (𝐹 “ 𝑥) = (𝐹 “ 𝑦))
10		id 22	. . . . . 6 ⊢ (𝑥 = 𝑦 → 𝑥 = 𝑦)
11	9, 10	breq12d 5155	. . . . 5 ⊢ (𝑥 = 𝑦 → ((𝐹 “ 𝑥) ≼ 𝑥 ↔ (𝐹 “ 𝑦) ≼ 𝑦))
12	11	imbi2d 340	. . . 4 ⊢ (𝑥 = 𝑦 → ((𝐹 Fn 𝐴 → (𝐹 “ 𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → (𝐹 “ 𝑦) ≼ 𝑦)))
13		imaeq2 6073	. . . . . 6 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → (𝐹 “ 𝑥) = (𝐹 “ (𝑦 ∪ {𝑧})))
14		id 22	. . . . . 6 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → 𝑥 = (𝑦 ∪ {𝑧}))
15	13, 14	breq12d 5155	. . . . 5 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐹 “ 𝑥) ≼ 𝑥 ↔ (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧})))
16	15	imbi2d 340	. . . 4 ⊢ (𝑥 = (𝑦 ∪ {𝑧}) → ((𝐹 Fn 𝐴 → (𝐹 “ 𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))))
17		imaeq2 6073	. . . . . 6 ⊢ (𝑥 = 𝐴 → (𝐹 “ 𝑥) = (𝐹 “ 𝐴))
18		id 22	. . . . . 6 ⊢ (𝑥 = 𝐴 → 𝑥 = 𝐴)
19	17, 18	breq12d 5155	. . . . 5 ⊢ (𝑥 = 𝐴 → ((𝐹 “ 𝑥) ≼ 𝑥 ↔ (𝐹 “ 𝐴) ≼ 𝐴))
20	19	imbi2d 340	. . . 4 ⊢ (𝑥 = 𝐴 → ((𝐹 Fn 𝐴 → (𝐹 “ 𝑥) ≼ 𝑥) ↔ (𝐹 Fn 𝐴 → (𝐹 “ 𝐴) ≼ 𝐴)))
21		0ex 5306	. . . . . 6 ⊢ ∅ ∈ V
22	21	0dom 9147	. . . . 5 ⊢ ∅ ≼ ∅
23	22	a1i 11	. . . 4 ⊢ (𝐹 Fn 𝐴 → ∅ ≼ ∅)
24		fnfun 6667	. . . . . . . . . . . . . 14 ⊢ (𝐹 Fn 𝐴 → Fun 𝐹)
25	24	ad2antrl 728	. . . . . . . . . . . . 13 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → Fun 𝐹)
26		funressn 7178	. . . . . . . . . . . . 13 ⊢ (Fun 𝐹 → (𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹‘𝑧)⟩})
27		rnss 5949	. . . . . . . . . . . . 13 ⊢ ((𝐹 ↾ {𝑧}) ⊆ {⟨𝑧, (𝐹‘𝑧)⟩} → ran (𝐹 ↾ {𝑧}) ⊆ ran {⟨𝑧, (𝐹‘𝑧)⟩})
28	25, 26, 27	3syl 18	. . . . . . . . . . . 12 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → ran (𝐹 ↾ {𝑧}) ⊆ ran {⟨𝑧, (𝐹‘𝑧)⟩})
29		df-ima 5697	. . . . . . . . . . . 12 ⊢ (𝐹 “ {𝑧}) = ran (𝐹 ↾ {𝑧})
30		vex 3483	. . . . . . . . . . . . . 14 ⊢ 𝑧 ∈ V
31	30	rnsnop 6243	. . . . . . . . . . . . 13 ⊢ ran {⟨𝑧, (𝐹‘𝑧)⟩} = {(𝐹‘𝑧)}
32	31	eqcomi 2745	. . . . . . . . . . . 12 ⊢ {(𝐹‘𝑧)} = ran {⟨𝑧, (𝐹‘𝑧)⟩}
33	28, 29, 32	3sstr4g 4036	. . . . . . . . . . 11 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ⊆ {(𝐹‘𝑧)})
34		snfi 9084	. . . . . . . . . . 11 ⊢ {(𝐹‘𝑧)} ∈ Fin
35		ssexg 5322	. . . . . . . . . . 11 ⊢ (((𝐹 “ {𝑧}) ⊆ {(𝐹‘𝑧)} ∧ {(𝐹‘𝑧)} ∈ Fin) → (𝐹 “ {𝑧}) ∈ V)
36	33, 34, 35	sylancl 586	. . . . . . . . . 10 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ∈ V)
37		fvi 6984	. . . . . . . . . 10 ⊢ ((𝐹 “ {𝑧}) ∈ V → ( I ‘(𝐹 “ {𝑧})) = (𝐹 “ {𝑧}))
38	36, 37	syl 17	. . . . . . . . 9 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → ( I ‘(𝐹 “ {𝑧})) = (𝐹 “ {𝑧}))
39	38	uneq2d 4167	. . . . . . . 8 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → ((𝐹 “ 𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) = ((𝐹 “ 𝑦) ∪ (𝐹 “ {𝑧})))
40		imaundi 6168	. . . . . . . 8 ⊢ (𝐹 “ (𝑦 ∪ {𝑧})) = ((𝐹 “ 𝑦) ∪ (𝐹 “ {𝑧}))
41	39, 40	eqtr4di 2794	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → ((𝐹 “ 𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) = (𝐹 “ (𝑦 ∪ {𝑧})))
42		simprr 772	. . . . . . . 8 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → (𝐹 “ 𝑦) ≼ 𝑦)
43		ssdomfi 9237	. . . . . . . . . . 11 ⊢ ({(𝐹‘𝑧)} ∈ Fin → ((𝐹 “ {𝑧}) ⊆ {(𝐹‘𝑧)} → (𝐹 “ {𝑧}) ≼ {(𝐹‘𝑧)}))
44	34, 33, 43	mpsyl 68	. . . . . . . . . 10 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ≼ {(𝐹‘𝑧)})
45		fvex 6918	. . . . . . . . . . 11 ⊢ (𝐹‘𝑧) ∈ V
46		en2sn 9082	. . . . . . . . . . 11 ⊢ (((𝐹‘𝑧) ∈ V ∧ 𝑧 ∈ V) → {(𝐹‘𝑧)} ≈ {𝑧})
47	45, 30, 46	mp2an 692	. . . . . . . . . 10 ⊢ {(𝐹‘𝑧)} ≈ {𝑧}
48		endom 9020	. . . . . . . . . . 11 ⊢ ({(𝐹‘𝑧)} ≈ {𝑧} → {(𝐹‘𝑧)} ≼ {𝑧})
49		domtrfi 9234	. . . . . . . . . . . 12 ⊢ (({(𝐹‘𝑧)} ∈ Fin ∧ (𝐹 “ {𝑧}) ≼ {(𝐹‘𝑧)} ∧ {(𝐹‘𝑧)} ≼ {𝑧}) → (𝐹 “ {𝑧}) ≼ {𝑧})
50	34, 49	mp3an1 1449	. . . . . . . . . . 11 ⊢ (((𝐹 “ {𝑧}) ≼ {(𝐹‘𝑧)} ∧ {(𝐹‘𝑧)} ≼ {𝑧}) → (𝐹 “ {𝑧}) ≼ {𝑧})
51	48, 50	sylan2 593	. . . . . . . . . 10 ⊢ (((𝐹 “ {𝑧}) ≼ {(𝐹‘𝑧)} ∧ {(𝐹‘𝑧)} ≈ {𝑧}) → (𝐹 “ {𝑧}) ≼ {𝑧})
52	44, 47, 51	sylancl 586	. . . . . . . . 9 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → (𝐹 “ {𝑧}) ≼ {𝑧})
53	38, 52	eqbrtrd 5164	. . . . . . . 8 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → ( I ‘(𝐹 “ {𝑧})) ≼ {𝑧})
54		simplr 768	. . . . . . . . 9 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → ¬ 𝑧 ∈ 𝑦)
55		disjsn 4710	. . . . . . . . 9 ⊢ ((𝑦 ∩ {𝑧}) = ∅ ↔ ¬ 𝑧 ∈ 𝑦)
56	54, 55	sylibr 234	. . . . . . . 8 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → (𝑦 ∩ {𝑧}) = ∅)
57		undom 9100	. . . . . . . 8 ⊢ ((((𝐹 “ 𝑦) ≼ 𝑦 ∧ ( I ‘(𝐹 “ {𝑧})) ≼ {𝑧}) ∧ (𝑦 ∩ {𝑧}) = ∅) → ((𝐹 “ 𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) ≼ (𝑦 ∪ {𝑧}))
58	42, 53, 56, 57	syl21anc 837	. . . . . . 7 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → ((𝐹 “ 𝑦) ∪ ( I ‘(𝐹 “ {𝑧}))) ≼ (𝑦 ∪ {𝑧}))
59	41, 58	eqbrtrrd 5166	. . . . . 6 ⊢ (((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) ∧ (𝐹 Fn 𝐴 ∧ (𝐹 “ 𝑦) ≼ 𝑦)) → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))
60	59	exp32 420	. . . . 5 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → (𝐹 Fn 𝐴 → ((𝐹 “ 𝑦) ≼ 𝑦 → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))))
61	60	a2d 29	. . . 4 ⊢ ((𝑦 ∈ Fin ∧ ¬ 𝑧 ∈ 𝑦) → ((𝐹 Fn 𝐴 → (𝐹 “ 𝑦) ≼ 𝑦) → (𝐹 Fn 𝐴 → (𝐹 “ (𝑦 ∪ {𝑧})) ≼ (𝑦 ∪ {𝑧}))))
62	8, 12, 16, 20, 23, 61	findcard2s 9206	. . 3 ⊢ (𝐴 ∈ Fin → (𝐹 Fn 𝐴 → (𝐹 “ 𝐴) ≼ 𝐴))
63		fofn 6821	. . 3 ⊢ (𝐹:𝐴–onto→𝐵 → 𝐹 Fn 𝐴)
64	62, 63	impel 505	. 2 ⊢ ((𝐴 ∈ Fin ∧ 𝐹:𝐴–onto→𝐵) → (𝐹 “ 𝐴) ≼ 𝐴)
65	2, 64	eqbrtrrd 5166	1 ⊢ ((𝐴 ∈ Fin ∧ 𝐹:𝐴–onto→𝐵) → 𝐵 ≼ 𝐴)

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 395   = wceq 1539   ∈ wcel 2107  Vcvv 3479   ∪ cun 3948   ∩ cin 3949   ⊆ wss 3950  ∅c0 4332  {csn 4625  ⟨cop 4631   class class class wbr 5142   I cid 5576  ran crn 5685   ↾ cres 5686   “ cima 5687  Fun wfun 6554   Fn wfn 6555  –onto→wfo 6558  ‘cfv 6560   ≈ cen 8983   ≼ cdom 8984  Fincfn 8986

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1794  ax-4 1808  ax-5 1909  ax-6 1966  ax-7 2006  ax-8 2109  ax-9 2117  ax-10 2140  ax-11 2156  ax-12 2176  ax-ext 2707  ax-sep 5295  ax-nul 5305  ax-pr 5431  ax-un 7756

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1779  df-nf 1783  df-sb 2064  df-mo 2539  df-eu 2568  df-clab 2714  df-cleq 2728  df-clel 2815  df-nfc 2891  df-ne 2940  df-ral 3061  df-rex 3070  df-reu 3380  df-rab 3436  df-v 3481  df-sbc 3788  df-dif 3953  df-un 3955  df-in 3957  df-ss 3967  df-pss 3970  df-nul 4333  df-if 4525  df-pw 4601  df-sn 4626  df-pr 4628  df-op 4632  df-uni 4907  df-br 5143  df-opab 5205  df-tr 5259  df-id 5577  df-eprel 5583  df-po 5591  df-so 5592  df-fr 5636  df-we 5638  df-xp 5690  df-rel 5691  df-cnv 5692  df-co 5693  df-dm 5694  df-rn 5695  df-res 5696  df-ima 5697  df-ord 6386  df-on 6387  df-lim 6388  df-suc 6389  df-iota 6513  df-fun 6562  df-fn 6563  df-f 6564  df-f1 6565  df-fo 6566  df-f1o 6567  df-fv 6568  df-om 7889  df-1o 8507  df-en 8987  df-dom 8988  df-fin 8990

This theorem is referenced by:  fofi  9352  fodomfib  9370  fodomfibOLD  9372  fofinf1o  9373  fidomdm  9375  cmpsub  23409  alexsubALT  24060  phpreu  37612  poimirlem26  37654  imadomfi  42004