ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  enumct GIF version

Theorem enumct 6873
Description: A finitely enumerable set is countable. Lemma 8.1.14 of [AczelRathjen], p. 73 (except that our definition of countable does not require the set to be inhabited). "Finitely enumerable" is defined as 𝑛 ∈ ω∃𝑓𝑓:𝑛onto𝐴 per Definition 8.1.4 of [AczelRathjen], p. 71 and "countable" is defined as 𝑔𝑔:ω–onto→(𝐴 ⊔ 1o) per [BauerSwan], p. 14:3. (Contributed by Jim Kingdon, 13-Mar-2023.)
Assertion
Ref Expression
enumct (∃𝑛 ∈ ω ∃𝑓 𝑓:𝑛onto𝐴 → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o))
Distinct variable group:   𝐴,𝑓,𝑔,𝑛

Proof of Theorem enumct
Dummy variables 𝑥 𝑘 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 simpll 497 . . . . . . . . 9 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ 𝑛 = ∅) → 𝑓:𝑛onto𝐴)
2 foeq2 5265 . . . . . . . . . 10 (𝑛 = ∅ → (𝑓:𝑛onto𝐴𝑓:∅–onto𝐴))
32adantl 272 . . . . . . . . 9 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ 𝑛 = ∅) → (𝑓:𝑛onto𝐴𝑓:∅–onto𝐴))
41, 3mpbid 146 . . . . . . . 8 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ 𝑛 = ∅) → 𝑓:∅–onto𝐴)
5 fo00 5324 . . . . . . . 8 (𝑓:∅–onto𝐴 ↔ (𝑓 = ∅ ∧ 𝐴 = ∅))
64, 5sylib 121 . . . . . . 7 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ 𝑛 = ∅) → (𝑓 = ∅ ∧ 𝐴 = ∅))
7 0ct 6869 . . . . . . . 8 𝑔 𝑔:ω–onto→(∅ ⊔ 1o)
8 djueq1 6813 . . . . . . . . . 10 (𝐴 = ∅ → (𝐴 ⊔ 1o) = (∅ ⊔ 1o))
9 foeq3 5266 . . . . . . . . . 10 ((𝐴 ⊔ 1o) = (∅ ⊔ 1o) → (𝑔:ω–onto→(𝐴 ⊔ 1o) ↔ 𝑔:ω–onto→(∅ ⊔ 1o)))
108, 9syl 14 . . . . . . . . 9 (𝐴 = ∅ → (𝑔:ω–onto→(𝐴 ⊔ 1o) ↔ 𝑔:ω–onto→(∅ ⊔ 1o)))
1110exbidv 1760 . . . . . . . 8 (𝐴 = ∅ → (∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o) ↔ ∃𝑔 𝑔:ω–onto→(∅ ⊔ 1o)))
127, 11mpbiri 167 . . . . . . 7 (𝐴 = ∅ → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o))
136, 12simpl2im 379 . . . . . 6 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ 𝑛 = ∅) → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o))
14 omex 4436 . . . . . . . . 9 ω ∈ V
1514mptex 5562 . . . . . . . 8 (𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅))) ∈ V
16 simpll 497 . . . . . . . . 9 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → 𝑓:𝑛onto𝐴)
17 simplr 498 . . . . . . . . 9 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → 𝑛 ∈ ω)
18 simpr 109 . . . . . . . . 9 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → ∅ ∈ 𝑛)
19 eqid 2095 . . . . . . . . 9 (𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅))) = (𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅)))
2016, 17, 18, 19enumctlemm 6872 . . . . . . . 8 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → (𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅))):ω–onto𝐴)
21 foeq1 5264 . . . . . . . . 9 (𝑔 = (𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅))) → (𝑔:ω–onto𝐴 ↔ (𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅))):ω–onto𝐴))
2221spcegv 2721 . . . . . . . 8 ((𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅))) ∈ V → ((𝑘 ∈ ω ↦ if(𝑘𝑛, (𝑓𝑘), (𝑓‘∅))):ω–onto𝐴 → ∃𝑔 𝑔:ω–onto𝐴))
2315, 20, 22mpsyl 65 . . . . . . 7 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → ∃𝑔 𝑔:ω–onto𝐴)
24 fof 5268 . . . . . . . . . . 11 (𝑓:𝑛onto𝐴𝑓:𝑛𝐴)
2524ad2antrr 473 . . . . . . . . . 10 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → 𝑓:𝑛𝐴)
2625, 18ffvelrnd 5474 . . . . . . . . 9 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → (𝑓‘∅) ∈ 𝐴)
27 eleq1 2157 . . . . . . . . . 10 (𝑥 = (𝑓‘∅) → (𝑥𝐴 ↔ (𝑓‘∅) ∈ 𝐴))
2827spcegv 2721 . . . . . . . . 9 ((𝑓‘∅) ∈ 𝐴 → ((𝑓‘∅) ∈ 𝐴 → ∃𝑥 𝑥𝐴))
2926, 26, 28sylc 62 . . . . . . . 8 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → ∃𝑥 𝑥𝐴)
30 ctm 6871 . . . . . . . 8 (∃𝑥 𝑥𝐴 → (∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o) ↔ ∃𝑔 𝑔:ω–onto𝐴))
3129, 30syl 14 . . . . . . 7 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → (∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o) ↔ ∃𝑔 𝑔:ω–onto𝐴))
3223, 31mpbird 166 . . . . . 6 (((𝑓:𝑛onto𝐴𝑛 ∈ ω) ∧ ∅ ∈ 𝑛) → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o))
33 0elnn 4460 . . . . . . 7 (𝑛 ∈ ω → (𝑛 = ∅ ∨ ∅ ∈ 𝑛))
3433adantl 272 . . . . . 6 ((𝑓:𝑛onto𝐴𝑛 ∈ ω) → (𝑛 = ∅ ∨ ∅ ∈ 𝑛))
3513, 32, 34mpjaodan 750 . . . . 5 ((𝑓:𝑛onto𝐴𝑛 ∈ ω) → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o))
3635ex 114 . . . 4 (𝑓:𝑛onto𝐴 → (𝑛 ∈ ω → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o)))
3736exlimiv 1541 . . 3 (∃𝑓 𝑓:𝑛onto𝐴 → (𝑛 ∈ ω → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o)))
3837impcom 124 . 2 ((𝑛 ∈ ω ∧ ∃𝑓 𝑓:𝑛onto𝐴) → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o))
3938rexlimiva 2497 1 (∃𝑛 ∈ ω ∃𝑓 𝑓:𝑛onto𝐴 → ∃𝑔 𝑔:ω–onto→(𝐴 ⊔ 1o))
Colors of variables: wff set class
Syntax hints:  wi 4  wa 103  wb 104  wo 667   = wceq 1296  wex 1433  wcel 1445  wrex 2371  Vcvv 2633  c0 3302  ifcif 3413  cmpt 3921  ωcom 4433  wf 5045  ontowfo 5047  cfv 5049  1oc1o 6212  cdju 6810
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 582  ax-in2 583  ax-io 668  ax-5 1388  ax-7 1389  ax-gen 1390  ax-ie1 1434  ax-ie2 1435  ax-8 1447  ax-10 1448  ax-11 1449  ax-i12 1450  ax-bndl 1451  ax-4 1452  ax-13 1456  ax-14 1457  ax-17 1471  ax-i9 1475  ax-ial 1479  ax-i5r 1480  ax-ext 2077  ax-coll 3975  ax-sep 3978  ax-nul 3986  ax-pow 4030  ax-pr 4060  ax-un 4284  ax-setind 4381  ax-iinf 4431
This theorem depends on definitions:  df-bi 116  df-dc 784  df-3or 928  df-3an 929  df-tru 1299  df-fal 1302  df-nf 1402  df-sb 1700  df-eu 1958  df-mo 1959  df-clab 2082  df-cleq 2088  df-clel 2091  df-nfc 2224  df-ne 2263  df-ral 2375  df-rex 2376  df-reu 2377  df-rab 2379  df-v 2635  df-sbc 2855  df-csb 2948  df-dif 3015  df-un 3017  df-in 3019  df-ss 3026  df-nul 3303  df-if 3414  df-pw 3451  df-sn 3472  df-pr 3473  df-op 3475  df-uni 3676  df-int 3711  df-iun 3754  df-br 3868  df-opab 3922  df-mpt 3923  df-tr 3959  df-id 4144  df-iord 4217  df-on 4219  df-suc 4222  df-iom 4434  df-xp 4473  df-rel 4474  df-cnv 4475  df-co 4476  df-dm 4477  df-rn 4478  df-res 4479  df-ima 4480  df-iota 5014  df-fun 5051  df-fn 5052  df-f 5053  df-f1 5054  df-fo 5055  df-f1o 5056  df-fv 5057  df-1st 5949  df-2nd 5950  df-1o 6219  df-dju 6811  df-inl 6819  df-inr 6820  df-case 6855
This theorem is referenced by:  finct  6874
  Copyright terms: Public domain W3C validator