MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  dcomex Structured version   Visualization version   GIF version

Theorem dcomex 9550
Description: The Axiom of Dependent Choice implies Infinity, the way we have stated it. Thus, we have Inf+AC implies DC and DC implies Inf, but AC does not imply Inf. (Contributed by Mario Carneiro, 25-Jan-2013.)
Assertion
Ref Expression
dcomex ω ∈ V

Proof of Theorem dcomex
Dummy variables 𝑡 𝑠 𝑥 𝑓 𝑛 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 1n0 7808 . . . . . . 7 1𝑜 ≠ ∅
2 df-br 4845 . . . . . . . 8 ((𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛) ↔ ⟨(𝑓𝑛), (𝑓‘suc 𝑛)⟩ ∈ {⟨1𝑜, 1𝑜⟩})
3 elsni 4387 . . . . . . . . 9 (⟨(𝑓𝑛), (𝑓‘suc 𝑛)⟩ ∈ {⟨1𝑜, 1𝑜⟩} → ⟨(𝑓𝑛), (𝑓‘suc 𝑛)⟩ = ⟨1𝑜, 1𝑜⟩)
4 fvex 6417 . . . . . . . . . 10 (𝑓𝑛) ∈ V
5 fvex 6417 . . . . . . . . . 10 (𝑓‘suc 𝑛) ∈ V
64, 5opth1 5133 . . . . . . . . 9 (⟨(𝑓𝑛), (𝑓‘suc 𝑛)⟩ = ⟨1𝑜, 1𝑜⟩ → (𝑓𝑛) = 1𝑜)
73, 6syl 17 . . . . . . . 8 (⟨(𝑓𝑛), (𝑓‘suc 𝑛)⟩ ∈ {⟨1𝑜, 1𝑜⟩} → (𝑓𝑛) = 1𝑜)
82, 7sylbi 208 . . . . . . 7 ((𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛) → (𝑓𝑛) = 1𝑜)
9 tz6.12i 6430 . . . . . . 7 (1𝑜 ≠ ∅ → ((𝑓𝑛) = 1𝑜𝑛𝑓1𝑜))
101, 8, 9mpsyl 68 . . . . . 6 ((𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛) → 𝑛𝑓1𝑜)
11 vex 3394 . . . . . . 7 𝑛 ∈ V
12 1oex 7800 . . . . . . 7 1𝑜 ∈ V
1311, 12breldm 5530 . . . . . 6 (𝑛𝑓1𝑜𝑛 ∈ dom 𝑓)
1410, 13syl 17 . . . . 5 ((𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛) → 𝑛 ∈ dom 𝑓)
1514ralimi 3140 . . . 4 (∀𝑛 ∈ ω (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛) → ∀𝑛 ∈ ω 𝑛 ∈ dom 𝑓)
16 dfss3 3787 . . . 4 (ω ⊆ dom 𝑓 ↔ ∀𝑛 ∈ ω 𝑛 ∈ dom 𝑓)
1715, 16sylibr 225 . . 3 (∀𝑛 ∈ ω (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛) → ω ⊆ dom 𝑓)
18 vex 3394 . . . . 5 𝑓 ∈ V
1918dmex 7325 . . . 4 dom 𝑓 ∈ V
2019ssex 4997 . . 3 (ω ⊆ dom 𝑓 → ω ∈ V)
2117, 20syl 17 . 2 (∀𝑛 ∈ ω (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛) → ω ∈ V)
22 snex 5098 . . 3 {⟨1𝑜, 1𝑜⟩} ∈ V
2312, 12fvsn 6667 . . . . . . . 8 ({⟨1𝑜, 1𝑜⟩}‘1𝑜) = 1𝑜
2412, 12funsn 6149 . . . . . . . . 9 Fun {⟨1𝑜, 1𝑜⟩}
2512snid 4402 . . . . . . . . . 10 1𝑜 ∈ {1𝑜}
2612dmsnop 5821 . . . . . . . . . 10 dom {⟨1𝑜, 1𝑜⟩} = {1𝑜}
2725, 26eleqtrri 2884 . . . . . . . . 9 1𝑜 ∈ dom {⟨1𝑜, 1𝑜⟩}
28 funbrfvb 6454 . . . . . . . . 9 ((Fun {⟨1𝑜, 1𝑜⟩} ∧ 1𝑜 ∈ dom {⟨1𝑜, 1𝑜⟩}) → (({⟨1𝑜, 1𝑜⟩}‘1𝑜) = 1𝑜 ↔ 1𝑜{⟨1𝑜, 1𝑜⟩}1𝑜))
2924, 27, 28mp2an 675 . . . . . . . 8 (({⟨1𝑜, 1𝑜⟩}‘1𝑜) = 1𝑜 ↔ 1𝑜{⟨1𝑜, 1𝑜⟩}1𝑜)
3023, 29mpbi 221 . . . . . . 7 1𝑜{⟨1𝑜, 1𝑜⟩}1𝑜
31 breq12 4849 . . . . . . . 8 ((𝑠 = 1𝑜𝑡 = 1𝑜) → (𝑠{⟨1𝑜, 1𝑜⟩}𝑡 ↔ 1𝑜{⟨1𝑜, 1𝑜⟩}1𝑜))
3212, 12, 31spc2ev 3494 . . . . . . 7 (1𝑜{⟨1𝑜, 1𝑜⟩}1𝑜 → ∃𝑠𝑡 𝑠{⟨1𝑜, 1𝑜⟩}𝑡)
3330, 32ax-mp 5 . . . . . 6 𝑠𝑡 𝑠{⟨1𝑜, 1𝑜⟩}𝑡
34 breq 4846 . . . . . . 7 (𝑥 = {⟨1𝑜, 1𝑜⟩} → (𝑠𝑥𝑡𝑠{⟨1𝑜, 1𝑜⟩}𝑡))
35342exbidv 2015 . . . . . 6 (𝑥 = {⟨1𝑜, 1𝑜⟩} → (∃𝑠𝑡 𝑠𝑥𝑡 ↔ ∃𝑠𝑡 𝑠{⟨1𝑜, 1𝑜⟩}𝑡))
3633, 35mpbiri 249 . . . . 5 (𝑥 = {⟨1𝑜, 1𝑜⟩} → ∃𝑠𝑡 𝑠𝑥𝑡)
37 ssid 3820 . . . . . . 7 {1𝑜} ⊆ {1𝑜}
3812rnsnop 5829 . . . . . . 7 ran {⟨1𝑜, 1𝑜⟩} = {1𝑜}
3937, 38, 263sstr4i 3841 . . . . . 6 ran {⟨1𝑜, 1𝑜⟩} ⊆ dom {⟨1𝑜, 1𝑜⟩}
40 rneq 5552 . . . . . . 7 (𝑥 = {⟨1𝑜, 1𝑜⟩} → ran 𝑥 = ran {⟨1𝑜, 1𝑜⟩})
41 dmeq 5525 . . . . . . 7 (𝑥 = {⟨1𝑜, 1𝑜⟩} → dom 𝑥 = dom {⟨1𝑜, 1𝑜⟩})
4240, 41sseq12d 3831 . . . . . 6 (𝑥 = {⟨1𝑜, 1𝑜⟩} → (ran 𝑥 ⊆ dom 𝑥 ↔ ran {⟨1𝑜, 1𝑜⟩} ⊆ dom {⟨1𝑜, 1𝑜⟩}))
4339, 42mpbiri 249 . . . . 5 (𝑥 = {⟨1𝑜, 1𝑜⟩} → ran 𝑥 ⊆ dom 𝑥)
44 pm5.5 352 . . . . 5 ((∃𝑠𝑡 𝑠𝑥𝑡 ∧ ran 𝑥 ⊆ dom 𝑥) → (((∃𝑠𝑡 𝑠𝑥𝑡 ∧ ran 𝑥 ⊆ dom 𝑥) → ∃𝑓𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛)) ↔ ∃𝑓𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛)))
4536, 43, 44syl2anc 575 . . . 4 (𝑥 = {⟨1𝑜, 1𝑜⟩} → (((∃𝑠𝑡 𝑠𝑥𝑡 ∧ ran 𝑥 ⊆ dom 𝑥) → ∃𝑓𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛)) ↔ ∃𝑓𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛)))
46 breq 4846 . . . . . 6 (𝑥 = {⟨1𝑜, 1𝑜⟩} → ((𝑓𝑛)𝑥(𝑓‘suc 𝑛) ↔ (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛)))
4746ralbidv 3174 . . . . 5 (𝑥 = {⟨1𝑜, 1𝑜⟩} → (∀𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛) ↔ ∀𝑛 ∈ ω (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛)))
4847exbidv 2012 . . . 4 (𝑥 = {⟨1𝑜, 1𝑜⟩} → (∃𝑓𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛) ↔ ∃𝑓𝑛 ∈ ω (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛)))
4945, 48bitrd 270 . . 3 (𝑥 = {⟨1𝑜, 1𝑜⟩} → (((∃𝑠𝑡 𝑠𝑥𝑡 ∧ ran 𝑥 ⊆ dom 𝑥) → ∃𝑓𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛)) ↔ ∃𝑓𝑛 ∈ ω (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛)))
50 ax-dc 9549 . . 3 ((∃𝑠𝑡 𝑠𝑥𝑡 ∧ ran 𝑥 ⊆ dom 𝑥) → ∃𝑓𝑛 ∈ ω (𝑓𝑛)𝑥(𝑓‘suc 𝑛))
5122, 49, 50vtocl 3452 . 2 𝑓𝑛 ∈ ω (𝑓𝑛){⟨1𝑜, 1𝑜⟩} (𝑓‘suc 𝑛)
5221, 51exlimiiv 2022 1 ω ∈ V
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 197  wa 384   = wceq 1637  wex 1859  wcel 2156  wne 2978  wral 3096  Vcvv 3391  wss 3769  c0 4116  {csn 4370  cop 4376   class class class wbr 4844  dom cdm 5311  ran crn 5312  suc csuc 5938  Fun wfun 6091  cfv 6097  ωcom 7291  1𝑜c1o 7785
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2068  ax-7 2104  ax-8 2158  ax-9 2165  ax-10 2185  ax-11 2201  ax-12 2214  ax-13 2420  ax-ext 2784  ax-sep 4975  ax-nul 4983  ax-pr 5096  ax-un 7175  ax-dc 9549
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2061  df-eu 2634  df-mo 2635  df-clab 2793  df-cleq 2799  df-clel 2802  df-nfc 2937  df-ne 2979  df-ral 3101  df-rex 3102  df-rab 3105  df-v 3393  df-sbc 3634  df-dif 3772  df-un 3774  df-in 3776  df-ss 3783  df-pss 3785  df-nul 4117  df-if 4280  df-pw 4353  df-sn 4371  df-pr 4373  df-tp 4375  df-op 4377  df-uni 4631  df-br 4845  df-opab 4907  df-tr 4947  df-id 5219  df-eprel 5224  df-po 5232  df-so 5233  df-fr 5270  df-we 5272  df-xp 5317  df-rel 5318  df-cnv 5319  df-co 5320  df-dm 5321  df-rn 5322  df-ord 5939  df-on 5940  df-suc 5942  df-iota 6060  df-fun 6099  df-fn 6100  df-fv 6105  df-1o 7792
This theorem is referenced by:  axdc2lem  9551  axdc3lem  9553  axdc4lem  9558  axcclem  9560
  Copyright terms: Public domain W3C validator