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

Theorem cfflb 9362
Description: If there is a cofinal map from 𝐵 to 𝐴, then 𝐵 is at least (cf‘𝐴). This theorem and cff1 9361 motivate the picture of (cf‘𝐴) as the greatest lower bound of the domain of cofinal maps into 𝐴. (Contributed by Mario Carneiro, 28-Feb-2013.)
Assertion
Ref Expression
cfflb ((𝐴 ∈ On ∧ 𝐵 ∈ On) → (∃𝑓(𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤)) → (cf‘𝐴) ⊆ 𝐵))
Distinct variable groups:   𝐴,𝑓,𝑤,𝑧   𝐵,𝑓,𝑤,𝑧

Proof of Theorem cfflb
Dummy variables 𝑠 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 frn 6258 . . . . . . 7 (𝑓:𝐵𝐴 → ran 𝑓𝐴)
21adantr 468 . . . . . 6 ((𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤)) → ran 𝑓𝐴)
3 ffn 6252 . . . . . . . . . . . 12 (𝑓:𝐵𝐴𝑓 Fn 𝐵)
4 fnfvelrn 6574 . . . . . . . . . . . 12 ((𝑓 Fn 𝐵𝑤𝐵) → (𝑓𝑤) ∈ ran 𝑓)
53, 4sylan 571 . . . . . . . . . . 11 ((𝑓:𝐵𝐴𝑤𝐵) → (𝑓𝑤) ∈ ran 𝑓)
6 sseq2 3824 . . . . . . . . . . . 12 (𝑠 = (𝑓𝑤) → (𝑧𝑠𝑧 ⊆ (𝑓𝑤)))
76rspcev 3502 . . . . . . . . . . 11 (((𝑓𝑤) ∈ ran 𝑓𝑧 ⊆ (𝑓𝑤)) → ∃𝑠 ∈ ran 𝑓 𝑧𝑠)
85, 7sylan 571 . . . . . . . . . 10 (((𝑓:𝐵𝐴𝑤𝐵) ∧ 𝑧 ⊆ (𝑓𝑤)) → ∃𝑠 ∈ ran 𝑓 𝑧𝑠)
98exp31 408 . . . . . . . . 9 (𝑓:𝐵𝐴 → (𝑤𝐵 → (𝑧 ⊆ (𝑓𝑤) → ∃𝑠 ∈ ran 𝑓 𝑧𝑠)))
109rexlimdv 3218 . . . . . . . 8 (𝑓:𝐵𝐴 → (∃𝑤𝐵 𝑧 ⊆ (𝑓𝑤) → ∃𝑠 ∈ ran 𝑓 𝑧𝑠))
1110ralimdv 3151 . . . . . . 7 (𝑓:𝐵𝐴 → (∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤) → ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠))
1211imp 395 . . . . . 6 ((𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤)) → ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)
132, 12jca 503 . . . . 5 ((𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤)) → (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠))
14 fvex 6417 . . . . . 6 (card‘ran 𝑓) ∈ V
15 cfval 9350 . . . . . . . . . . 11 (𝐴 ∈ On → (cf‘𝐴) = {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))})
1615adantr 468 . . . . . . . . . 10 ((𝐴 ∈ On ∧ 𝐵 ∈ On) → (cf‘𝐴) = {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))})
17163ad2ant2 1157 . . . . . . . . 9 ((𝑥 = (card‘ran 𝑓) ∧ (𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → (cf‘𝐴) = {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))})
18 vex 3394 . . . . . . . . . . . . . 14 𝑓 ∈ V
1918rnex 7326 . . . . . . . . . . . . 13 ran 𝑓 ∈ V
20 fveq2 6404 . . . . . . . . . . . . . . 15 (𝑦 = ran 𝑓 → (card‘𝑦) = (card‘ran 𝑓))
2120eqeq2d 2816 . . . . . . . . . . . . . 14 (𝑦 = ran 𝑓 → (𝑥 = (card‘𝑦) ↔ 𝑥 = (card‘ran 𝑓)))
22 sseq1 3823 . . . . . . . . . . . . . . 15 (𝑦 = ran 𝑓 → (𝑦𝐴 ↔ ran 𝑓𝐴))
23 rexeq 3328 . . . . . . . . . . . . . . . 16 (𝑦 = ran 𝑓 → (∃𝑠𝑦 𝑧𝑠 ↔ ∃𝑠 ∈ ran 𝑓 𝑧𝑠))
2423ralbidv 3174 . . . . . . . . . . . . . . 15 (𝑦 = ran 𝑓 → (∀𝑧𝐴𝑠𝑦 𝑧𝑠 ↔ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠))
2522, 24anbi12d 618 . . . . . . . . . . . . . 14 (𝑦 = ran 𝑓 → ((𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠) ↔ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)))
2621, 25anbi12d 618 . . . . . . . . . . . . 13 (𝑦 = ran 𝑓 → ((𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠)) ↔ (𝑥 = (card‘ran 𝑓) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠))))
2719, 26spcev 3493 . . . . . . . . . . . 12 ((𝑥 = (card‘ran 𝑓) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠)))
28 abid 2794 . . . . . . . . . . . 12 (𝑥 ∈ {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))} ↔ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠)))
2927, 28sylibr 225 . . . . . . . . . . 11 ((𝑥 = (card‘ran 𝑓) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → 𝑥 ∈ {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))})
30 intss1 4684 . . . . . . . . . . 11 (𝑥 ∈ {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))} → {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))} ⊆ 𝑥)
3129, 30syl 17 . . . . . . . . . 10 ((𝑥 = (card‘ran 𝑓) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))} ⊆ 𝑥)
32313adant2 1154 . . . . . . . . 9 ((𝑥 = (card‘ran 𝑓) ∧ (𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦𝐴 ∧ ∀𝑧𝐴𝑠𝑦 𝑧𝑠))} ⊆ 𝑥)
3317, 32eqsstrd 3836 . . . . . . . 8 ((𝑥 = (card‘ran 𝑓) ∧ (𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → (cf‘𝐴) ⊆ 𝑥)
34333expib 1145 . . . . . . 7 (𝑥 = (card‘ran 𝑓) → (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → (cf‘𝐴) ⊆ 𝑥))
35 sseq2 3824 . . . . . . 7 (𝑥 = (card‘ran 𝑓) → ((cf‘𝐴) ⊆ 𝑥 ↔ (cf‘𝐴) ⊆ (card‘ran 𝑓)))
3634, 35sylibd 230 . . . . . 6 (𝑥 = (card‘ran 𝑓) → (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → (cf‘𝐴) ⊆ (card‘ran 𝑓)))
3714, 36vtocle 3475 . . . . 5 (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (ran 𝑓𝐴 ∧ ∀𝑧𝐴𝑠 ∈ ran 𝑓 𝑧𝑠)) → (cf‘𝐴) ⊆ (card‘ran 𝑓))
3813, 37sylan2 582 . . . 4 (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤))) → (cf‘𝐴) ⊆ (card‘ran 𝑓))
39 cardidm 9064 . . . . . . 7 (card‘(card‘ran 𝑓)) = (card‘ran 𝑓)
40 onss 7216 . . . . . . . . . . . . . 14 (𝐴 ∈ On → 𝐴 ⊆ On)
411, 40sylan9ssr 3812 . . . . . . . . . . . . 13 ((𝐴 ∈ On ∧ 𝑓:𝐵𝐴) → ran 𝑓 ⊆ On)
42413adant2 1154 . . . . . . . . . . . 12 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → ran 𝑓 ⊆ On)
43 onssnum 9142 . . . . . . . . . . . 12 ((ran 𝑓 ∈ V ∧ ran 𝑓 ⊆ On) → ran 𝑓 ∈ dom card)
4419, 42, 43sylancr 577 . . . . . . . . . . 11 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → ran 𝑓 ∈ dom card)
45 cardid2 9058 . . . . . . . . . . 11 (ran 𝑓 ∈ dom card → (card‘ran 𝑓) ≈ ran 𝑓)
4644, 45syl 17 . . . . . . . . . 10 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → (card‘ran 𝑓) ≈ ran 𝑓)
47 onenon 9054 . . . . . . . . . . . . 13 (𝐵 ∈ On → 𝐵 ∈ dom card)
48 dffn4 6333 . . . . . . . . . . . . . 14 (𝑓 Fn 𝐵𝑓:𝐵onto→ran 𝑓)
493, 48sylib 209 . . . . . . . . . . . . 13 (𝑓:𝐵𝐴𝑓:𝐵onto→ran 𝑓)
50 fodomnum 9159 . . . . . . . . . . . . 13 (𝐵 ∈ dom card → (𝑓:𝐵onto→ran 𝑓 → ran 𝑓𝐵))
5147, 49, 50syl2im 40 . . . . . . . . . . . 12 (𝐵 ∈ On → (𝑓:𝐵𝐴 → ran 𝑓𝐵))
5251imp 395 . . . . . . . . . . 11 ((𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → ran 𝑓𝐵)
53523adant1 1153 . . . . . . . . . 10 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → ran 𝑓𝐵)
54 endomtr 8246 . . . . . . . . . 10 (((card‘ran 𝑓) ≈ ran 𝑓 ∧ ran 𝑓𝐵) → (card‘ran 𝑓) ≼ 𝐵)
5546, 53, 54syl2anc 575 . . . . . . . . 9 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → (card‘ran 𝑓) ≼ 𝐵)
56 cardon 9049 . . . . . . . . . . . 12 (card‘ran 𝑓) ∈ On
57 onenon 9054 . . . . . . . . . . . 12 ((card‘ran 𝑓) ∈ On → (card‘ran 𝑓) ∈ dom card)
5856, 57ax-mp 5 . . . . . . . . . . 11 (card‘ran 𝑓) ∈ dom card
59 carddom2 9082 . . . . . . . . . . 11 (((card‘ran 𝑓) ∈ dom card ∧ 𝐵 ∈ dom card) → ((card‘(card‘ran 𝑓)) ⊆ (card‘𝐵) ↔ (card‘ran 𝑓) ≼ 𝐵))
6058, 47, 59sylancr 577 . . . . . . . . . 10 (𝐵 ∈ On → ((card‘(card‘ran 𝑓)) ⊆ (card‘𝐵) ↔ (card‘ran 𝑓) ≼ 𝐵))
61603ad2ant2 1157 . . . . . . . . 9 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → ((card‘(card‘ran 𝑓)) ⊆ (card‘𝐵) ↔ (card‘ran 𝑓) ≼ 𝐵))
6255, 61mpbird 248 . . . . . . . 8 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → (card‘(card‘ran 𝑓)) ⊆ (card‘𝐵))
63 cardonle 9062 . . . . . . . . 9 (𝐵 ∈ On → (card‘𝐵) ⊆ 𝐵)
64633ad2ant2 1157 . . . . . . . 8 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → (card‘𝐵) ⊆ 𝐵)
6562, 64sstrd 3808 . . . . . . 7 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → (card‘(card‘ran 𝑓)) ⊆ 𝐵)
6639, 65syl5eqssr 3847 . . . . . 6 ((𝐴 ∈ On ∧ 𝐵 ∈ On ∧ 𝑓:𝐵𝐴) → (card‘ran 𝑓) ⊆ 𝐵)
67663expa 1140 . . . . 5 (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ 𝑓:𝐵𝐴) → (card‘ran 𝑓) ⊆ 𝐵)
6867adantrr 699 . . . 4 (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤))) → (card‘ran 𝑓) ⊆ 𝐵)
6938, 68sstrd 3808 . . 3 (((𝐴 ∈ On ∧ 𝐵 ∈ On) ∧ (𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤))) → (cf‘𝐴) ⊆ 𝐵)
7069ex 399 . 2 ((𝐴 ∈ On ∧ 𝐵 ∈ On) → ((𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤)) → (cf‘𝐴) ⊆ 𝐵))
7170exlimdv 2024 1 ((𝐴 ∈ On ∧ 𝐵 ∈ On) → (∃𝑓(𝑓:𝐵𝐴 ∧ ∀𝑧𝐴𝑤𝐵 𝑧 ⊆ (𝑓𝑤)) → (cf‘𝐴) ⊆ 𝐵))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 197  wa 384  w3a 1100   = wceq 1637  wex 1859  wcel 2156  {cab 2792  wral 3096  wrex 3097  Vcvv 3391  wss 3769   cint 4669   class class class wbr 4844  dom cdm 5311  ran crn 5312  Oncon0 5936   Fn wfn 6092  wf 6093  ontowfo 6095  cfv 6097  cen 8185  cdom 8186  cardccrd 9040  cfccf 9042
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-rep 4964  ax-sep 4975  ax-nul 4983  ax-pow 5035  ax-pr 5096  ax-un 7175
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-reu 3103  df-rmo 3104  df-rab 3105  df-v 3393  df-sbc 3634  df-csb 3729  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-int 4670  df-iun 4714  df-br 4845  df-opab 4907  df-mpt 4924  df-tr 4947  df-id 5219  df-eprel 5224  df-po 5232  df-so 5233  df-fr 5270  df-se 5271  df-we 5272  df-xp 5317  df-rel 5318  df-cnv 5319  df-co 5320  df-dm 5321  df-rn 5322  df-res 5323  df-ima 5324  df-pred 5893  df-ord 5939  df-on 5940  df-suc 5942  df-iota 6060  df-fun 6099  df-fn 6100  df-f 6101  df-f1 6102  df-fo 6103  df-f1o 6104  df-fv 6105  df-isom 6106  df-riota 6831  df-ov 6873  df-oprab 6874  df-mpt2 6875  df-1st 7394  df-2nd 7395  df-wrecs 7638  df-recs 7700  df-er 7975  df-map 8090  df-en 8189  df-dom 8190  df-sdom 8191  df-card 9044  df-cf 9046  df-acn 9047
This theorem is referenced by:  cfsmolem  9373  cfcoflem  9375  cfcof  9377  inar1  9878
  Copyright terms: Public domain W3C validator