![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > hashf1rn | Structured version Visualization version GIF version |
Description: The size of a finite set which is a one-to-one function is equal to the size of the function's range. (Contributed by Alexander van der Vekens, 12-Jan-2018.) (Revised by AV, 4-May-2021.) |
Ref | Expression |
---|---|
hashf1rn | ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → (♯‘𝐹) = (♯‘ran 𝐹)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | f1f 6240 | . . . . 5 ⊢ (𝐹:𝐴–1-1→𝐵 → 𝐹:𝐴⟶𝐵) | |
2 | 1 | anim2i 595 | . . . 4 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → (𝐴 ∈ 𝑉 ∧ 𝐹:𝐴⟶𝐵)) |
3 | 2 | ancomd 467 | . . 3 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → (𝐹:𝐴⟶𝐵 ∧ 𝐴 ∈ 𝑉)) |
4 | fex 6631 | . . 3 ⊢ ((𝐹:𝐴⟶𝐵 ∧ 𝐴 ∈ 𝑉) → 𝐹 ∈ V) | |
5 | 3, 4 | syl 17 | . 2 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → 𝐹 ∈ V) |
6 | f1o2ndf1 7434 | . . . 4 ⊢ (𝐹:𝐴–1-1→𝐵 → (2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹) | |
7 | df-2nd 7314 | . . . . . . . . 9 ⊢ 2nd = (𝑥 ∈ V ↦ ∪ ran {𝑥}) | |
8 | 7 | funmpt2 6069 | . . . . . . . 8 ⊢ Fun 2nd |
9 | resfunexg 6621 | . . . . . . . 8 ⊢ ((Fun 2nd ∧ 𝐹 ∈ V) → (2nd ↾ 𝐹) ∈ V) | |
10 | 8, 5, 9 | sylancr 695 | . . . . . . 7 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → (2nd ↾ 𝐹) ∈ V) |
11 | f1oeq1 6267 | . . . . . . . . . 10 ⊢ ((2nd ↾ 𝐹) = 𝑓 → ((2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹 ↔ 𝑓:𝐹–1-1-onto→ran 𝐹)) | |
12 | 11 | biimpd 219 | . . . . . . . . 9 ⊢ ((2nd ↾ 𝐹) = 𝑓 → ((2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹 → 𝑓:𝐹–1-1-onto→ran 𝐹)) |
13 | 12 | eqcoms 2777 | . . . . . . . 8 ⊢ (𝑓 = (2nd ↾ 𝐹) → ((2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹 → 𝑓:𝐹–1-1-onto→ran 𝐹)) |
14 | 13 | adantl 474 | . . . . . . 7 ⊢ (((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) ∧ 𝑓 = (2nd ↾ 𝐹)) → ((2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹 → 𝑓:𝐹–1-1-onto→ran 𝐹)) |
15 | 10, 14 | spcimedv 3440 | . . . . . 6 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → ((2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹 → ∃𝑓 𝑓:𝐹–1-1-onto→ran 𝐹)) |
16 | 15 | ex 448 | . . . . 5 ⊢ (𝐴 ∈ 𝑉 → (𝐹:𝐴–1-1→𝐵 → ((2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹 → ∃𝑓 𝑓:𝐹–1-1-onto→ran 𝐹))) |
17 | 16 | com13 88 | . . . 4 ⊢ ((2nd ↾ 𝐹):𝐹–1-1-onto→ran 𝐹 → (𝐹:𝐴–1-1→𝐵 → (𝐴 ∈ 𝑉 → ∃𝑓 𝑓:𝐹–1-1-onto→ran 𝐹))) |
18 | 6, 17 | mpcom 38 | . . 3 ⊢ (𝐹:𝐴–1-1→𝐵 → (𝐴 ∈ 𝑉 → ∃𝑓 𝑓:𝐹–1-1-onto→ran 𝐹)) |
19 | 18 | impcom 444 | . 2 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → ∃𝑓 𝑓:𝐹–1-1-onto→ran 𝐹) |
20 | hasheqf1oi 13347 | . 2 ⊢ (𝐹 ∈ V → (∃𝑓 𝑓:𝐹–1-1-onto→ran 𝐹 → (♯‘𝐹) = (♯‘ran 𝐹))) | |
21 | 5, 19, 20 | sylc 65 | 1 ⊢ ((𝐴 ∈ 𝑉 ∧ 𝐹:𝐴–1-1→𝐵) → (♯‘𝐹) = (♯‘ran 𝐹)) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ∧ wa 383 = wceq 1629 ∃wex 1850 ∈ wcel 2143 Vcvv 3348 {csn 4313 ∪ cuni 4571 ran crn 5249 ↾ cres 5250 Fun wfun 6024 ⟶wf 6026 –1-1→wf1 6027 –1-1-onto→wf1o 6029 ‘cfv 6030 2nd c2nd 7312 ♯chash 13324 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1868 ax-4 1883 ax-5 1989 ax-6 2055 ax-7 2091 ax-8 2145 ax-9 2152 ax-10 2172 ax-11 2188 ax-12 2201 ax-13 2406 ax-ext 2749 ax-rep 4901 ax-sep 4911 ax-nul 4919 ax-pow 4970 ax-pr 5033 ax-un 7094 ax-cnex 10192 ax-resscn 10193 ax-1cn 10194 ax-icn 10195 ax-addcl 10196 ax-addrcl 10197 ax-mulcl 10198 ax-mulrcl 10199 ax-mulcom 10200 ax-addass 10201 ax-mulass 10202 ax-distr 10203 ax-i2m1 10204 ax-1ne0 10205 ax-1rid 10206 ax-rnegex 10207 ax-rrecex 10208 ax-cnre 10209 ax-pre-lttri 10210 ax-pre-lttrn 10211 ax-pre-ltadd 10212 ax-pre-mulgt0 10213 |
This theorem depends on definitions: df-bi 197 df-or 384 df-an 385 df-3or 1070 df-3an 1071 df-tru 1632 df-ex 1851 df-nf 1856 df-sb 2048 df-eu 2620 df-mo 2621 df-clab 2756 df-cleq 2762 df-clel 2765 df-nfc 2900 df-ne 2942 df-nel 3045 df-ral 3064 df-rex 3065 df-reu 3066 df-rab 3068 df-v 3350 df-sbc 3585 df-csb 3680 df-dif 3723 df-un 3725 df-in 3727 df-ss 3734 df-pss 3736 df-nul 4061 df-if 4223 df-pw 4296 df-sn 4314 df-pr 4316 df-tp 4318 df-op 4320 df-uni 4572 df-int 4609 df-iun 4653 df-br 4784 df-opab 4844 df-mpt 4861 df-tr 4884 df-id 5156 df-eprel 5161 df-po 5169 df-so 5170 df-fr 5207 df-we 5209 df-xp 5254 df-rel 5255 df-cnv 5256 df-co 5257 df-dm 5258 df-rn 5259 df-res 5260 df-ima 5261 df-pred 5822 df-ord 5868 df-on 5869 df-lim 5870 df-suc 5871 df-iota 5993 df-fun 6032 df-fn 6033 df-f 6034 df-f1 6035 df-fo 6036 df-f1o 6037 df-fv 6038 df-riota 6752 df-ov 6794 df-oprab 6795 df-mpt2 6796 df-om 7211 df-2nd 7314 df-wrecs 7557 df-recs 7619 df-rdg 7657 df-1o 7711 df-er 7894 df-en 8108 df-dom 8109 df-sdom 8110 df-fin 8111 df-card 8963 df-pnf 10276 df-mnf 10277 df-xr 10278 df-ltxr 10279 df-le 10280 df-sub 10468 df-neg 10469 df-nn 11221 df-n0 11493 df-z 11578 df-uz 11888 df-hash 13325 |
This theorem is referenced by: hashimarn 13432 usgrsizedg 26335 |
Copyright terms: Public domain | W3C validator |