Theorem f1domfi 9168

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 8971). (Contributed by BTernaryTau, 25-Sep-2024.)

Assertion

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

Proof of Theorem f1domfi

Step	Hyp	Ref	Expression
1		f1cnv 6849	. . . 4 ⊢ (𝐹:𝐴–1-1→𝐵 → ◡𝐹:ran 𝐹–1-1-onto→𝐴)
2		f1f 6778	. . . . . 6 ⊢ (𝐹:𝐴–1-1→𝐵 → 𝐹:𝐴⟶𝐵)
3	2	frnd 6718	. . . . 5 ⊢ (𝐹:𝐴–1-1→𝐵 → ran 𝐹 ⊆ 𝐵)
4		ssfi 9160	. . . . 5 ⊢ ((𝐵 ∈ Fin ∧ ran 𝐹 ⊆ 𝐵) → ran 𝐹 ∈ Fin)
5	3, 4	sylan2 604	. . . 4 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → ran 𝐹 ∈ Fin)
6		f1ofn 6825	. . . . 5 ⊢ (◡𝐹:ran 𝐹–1-1-onto→𝐴 → ◡𝐹 Fn ran 𝐹)
7		fnfi 9165	. . . . 5 ⊢ ((◡𝐹 Fn ran 𝐹 ∧ ran 𝐹 ∈ Fin) → ◡𝐹 ∈ Fin)
8	6, 7	sylan 591	. . . 4 ⊢ ((◡𝐹:ran 𝐹–1-1-onto→𝐴 ∧ ran 𝐹 ∈ Fin) → ◡𝐹 ∈ Fin)
9	1, 5, 8	syl2an2 698	. . 3 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → ◡𝐹 ∈ Fin)
10		cnvfi 9163	. . . 4 ⊢ (◡𝐹 ∈ Fin → ◡◡𝐹 ∈ Fin)
11		f1rel 6782	. . . . . . 7 ⊢ (𝐹:𝐴–1-1→𝐵 → Rel 𝐹)
12		dfrel2 6191	. . . . . . 7 ⊢ (Rel 𝐹 ↔ ◡◡𝐹 = 𝐹)
13	11, 12	sylib 221	. . . . . 6 ⊢ (𝐹:𝐴–1-1→𝐵 → ◡◡𝐹 = 𝐹)
14	13	eleq1d 2855	. . . . 5 ⊢ (𝐹:𝐴–1-1→𝐵 → (◡◡𝐹 ∈ Fin ↔ 𝐹 ∈ Fin))
15	14	biimpac 483	. . . 4 ⊢ ((◡◡𝐹 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐹 ∈ Fin)
16	10, 15	sylan 591	. . 3 ⊢ ((◡𝐹 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐹 ∈ Fin)
17	9, 16	sylancom 599	. 2 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐹 ∈ Fin)
18		f1dom3g 8967	. . 3 ⊢ ((𝐹 ∈ Fin ∧ 𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐴 ≼ 𝐵)
19	18	3expib 1138	. 2 ⊢ (𝐹 ∈ Fin → ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐴 ≼ 𝐵))
20	17, 19	mpcom 39	1 ⊢ ((𝐵 ∈ Fin ∧ 𝐹:𝐴–1-1→𝐵) → 𝐴 ≼ 𝐵)

Syntax hints:   → wi 4   ∧ wa 400   = wceq 1568   ∈ wcel 2150   ⊆ wss 3913   class class class wbr 5114  ^◡ccnv 5664  ran crn 5666  Rel wrel 5670   Fn wfn 6535  –1-1→wf1 6537  –1-1-onto→wf1o 6539   ≼ cdom 8944  Fincfn 8946

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1823  ax-4 1837  ax-5 1938  ax-6 1995  ax-7 2036  ax-8 2152  ax-9 2160  ax-10 2183  ax-11 2199  ax-12 2220  ax-ext 2742  ax-sep 5262  ax-nul 5274  ax-pr 5408  ax-un 7736

This theorem depends on definitions:  df-bi 210  df-an 401  df-or 861  df-3or 1102  df-3an 1103  df-tru 1571  df-fal 1581  df-ex 1808  df-nf 1812  df-sb 2099  df-mo 2574  df-eu 2604  df-clab 2749  df-cleq 2762  df-clel 2845  df-nfc 2919  df-ne 2966  df-ral 3087  df-rex 3097  df-reu 3377  df-rab 3424  df-v 3464  df-sbc 3753  df-dif 3916  df-un 3918  df-in 3920  df-ss 3930  df-pss 3933  df-nul 4295  df-if 4493  df-pw 4569  df-sn 4595  df-pr 4597  df-op 4601  df-uni 4878  df-br 5115  df-opab 5179  df-tr 5224  df-id 5560  df-eprel 5565  df-po 5573  df-so 5574  df-fr 5618  df-we 5620  df-xp 5671  df-rel 5672  df-cnv 5673  df-co 5674  df-dm 5675  df-rn 5676  df-res 5677  df-ima 5678  df-ord 6367  df-on 6368  df-lim 6369  df-suc 6370  df-iota 6496  df-fun 6542  df-fn 6543  df-f 6544  df-f1 6545  df-fo 6546  df-f1o 6547  df-fv 6548  df-om 7866  df-1o 8456  df-en 8947  df-dom 8948  df-fin 8950

This theorem is referenced by:  ssdomfi  9183