Theorem f1domfi 9151

Description: If the codomain of a one-to-one function is finite, then the function's domain is dominated by its codomain. This theorem is proved without using the Axiom of Replacement or the Axiom of Power Sets (unlike f1domg 8954). (Contributed by BTernaryTau, 25-Sep-2024.)

Assertion

Ref	Expression
f1domfi	⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐴 ≼ 𝐵)

Proof of Theorem f1domfi

Step	Hyp	Ref	Expression
1		f1cnv 6833	. . . 4 ⊢ (𝐹:𝐴–1-1→𝐵 → ◡𝐹:ran 𝐹–1-1-onto→𝐴)
2		f1f 6762	. . . . . 6 ⊢ (𝐹:𝐴–1-1→𝐵 → 𝐹:𝐴⟶𝐵)
3	2	frnd 6702	. . . . 5 ⊢ (𝐹:𝐴–1-1→𝐵 → ran 𝐹 ⊆ 𝐵)
4		ssfi 9143	. . . . 5 ⊢ ((𝐵 ∈ Fin ∧ ran 𝐹 ⊆ 𝐵) → ran 𝐹 ∈ Fin)
5	3, 4	sylan2 602	. . . 4 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → ran 𝐹 ∈ Fin)
6		f1ofn 6809	. . . . 5 ⊢ (◡𝐹:ran 𝐹–1-1-onto→𝐴 → ◡𝐹 Fn ran 𝐹)
7		fnfi 9148	. . . . 5 ⊢ ((◡𝐹 Fn ran 𝐹 ∧ ran 𝐹 ∈ Fin) → ◡𝐹 ∈ Fin)
8	6, 7	sylan 589	. . . 4 ⊢ ((◡𝐹:ran 𝐹–1-1-onto→𝐴 ∧ ran 𝐹 ∈ Fin) → ◡𝐹 ∈ Fin)
9	1, 5, 8	syl2an2 696	. . 3 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → ◡𝐹 ∈ Fin)
10		cnvfi 9146	. . . 4 ⊢ (◡𝐹 ∈ Fin → ◡◡𝐹 ∈ Fin)
11		f1rel 6766	. . . . . . 7 ⊢ (𝐹:𝐴–1-1→𝐵 → Rel 𝐹)
12		dfrel2 6177	. . . . . . 7 ⊢ (Rel 𝐹 ↔ ◡◡𝐹 = 𝐹)
13	11, 12	sylib 220	. . . . . 6 ⊢ (𝐹:𝐴–1-1→𝐵 → ◡◡𝐹 = 𝐹)
14	13	eleq1d 2849	. . . . 5 ⊢ (𝐹:𝐴–1-1→𝐵 → (◡◡𝐹 ∈ Fin ↔ 𝐹 ∈ Fin))
15	14	biimpac 482	. . . 4 ⊢ ((◡◡𝐹 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐹 ∈ Fin)
16	10, 15	sylan 589	. . 3 ⊢ ((◡𝐹 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐹 ∈ Fin)
17	9, 16	sylancom 597	. 2 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐹 ∈ Fin)
18		f1dom3g 8950	. . 3 ⊢ ((𝐹 ∈ Fin ∧ 𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐴 ≼ 𝐵)
19	18	3expib 1136	. 2 ⊢ (𝐹 ∈ Fin → ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐴 ≼ 𝐵))
20	17, 19	mpcom 38	1 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐴 ≼ 𝐵)

Syntax hints:   → wi 4   ∧ wa 399   = wceq 1562   ∈ wcel 2144   ⊆ wss 3906   class class class wbr 5102  ^◡ccnv 5648  ran crn 5650  Rel wrel 5654   Fn wfn 6518  –1-1→wf1 6520  –1-1-onto→wf1o 6522   ≼ cdom 8927  Fincfn 8929

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1817  ax-4 1831  ax-5 1932  ax-6 1989  ax-7 2030  ax-8 2146  ax-9 2154  ax-10 2177  ax-11 2193  ax-12 2214  ax-ext 2736  ax-sep 5248  ax-nul 5258  ax-pr 5392  ax-un 7720

This theorem depends on definitions:  df-bi 209  df-an 400  df-or 859  df-3or 1100  df-3an 1101  df-tru 1565  df-fal 1575  df-ex 1802  df-nf 1806  df-sb 2093  df-mo 2568  df-eu 2598  df-clab 2743  df-cleq 2756  df-clel 2839  df-nfc 2913  df-ne 2960  df-ral 3079  df-rex 3089  df-reu 3370  df-rab 3417  df-v 3458  df-sbc 3747  df-dif 3909  df-un 3911  df-in 3913  df-ss 3923  df-pss 3926  df-nul 4288  df-if 4483  df-pw 4559  df-sn 4585  df-pr 4587  df-op 4591  df-uni 4868  df-br 5103  df-opab 5165  df-tr 5210  df-id 5544  df-eprel 5549  df-po 5557  df-so 5558  df-fr 5602  df-we 5604  df-xp 5655  df-rel 5656  df-cnv 5657  df-co 5658  df-dm 5659  df-rn 5660  df-res 5661  df-ima 5662  df-ord 6351  df-on 6352  df-lim 6353  df-suc 6354  df-iota 6479  df-fun 6525  df-fn 6526  df-f 6527  df-f1 6528  df-fo 6529  df-f1o 6530  df-fv 6531  df-om 7849  df-1o 8439  df-en 8930  df-dom 8931  df-fin 8933

This theorem is referenced by:  ssdomfi  9166