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

Theorem dfac2a 10066
Description: Our Axiom of Choice (in the form of ac3 10399) implies the Axiom of Choice (first form) of [Enderton] p. 49. The proof uses neither AC nor the Axiom of Regularity. See dfac2b 10067 for the converse (which does use the Axiom of Regularity). (Contributed by NM, 5-Apr-2004.) (Revised by Mario Carneiro, 26-Jun-2015.)
Assertion
Ref Expression
dfac2a (βˆ€π‘₯βˆƒπ‘¦βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ CHOICE)
Distinct variable group:   π‘₯,𝑧,𝑦,𝑀,𝑣

Proof of Theorem dfac2a
Dummy variables 𝑓 𝑒 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 riotauni 7320 . . . . . . . . 9 (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ (℩𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) = βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
2 riotacl 7332 . . . . . . . . 9 (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ (℩𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) ∈ 𝑧)
31, 2eqeltrrd 2839 . . . . . . . 8 (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝑧)
4 elequ2 2122 . . . . . . . . . . . . 13 (𝑒 = 𝑧 β†’ (𝑀 ∈ 𝑒 ↔ 𝑀 ∈ 𝑧))
5 elequ1 2114 . . . . . . . . . . . . . . 15 (𝑒 = 𝑧 β†’ (𝑒 ∈ 𝑣 ↔ 𝑧 ∈ 𝑣))
65anbi1d 631 . . . . . . . . . . . . . 14 (𝑒 = 𝑧 β†’ ((𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) ↔ (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)))
76rexbidv 3176 . . . . . . . . . . . . 13 (𝑒 = 𝑧 β†’ (βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) ↔ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)))
84, 7anbi12d 632 . . . . . . . . . . . 12 (𝑒 = 𝑧 β†’ ((𝑀 ∈ 𝑒 ∧ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) ↔ (𝑀 ∈ 𝑧 ∧ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣))))
98rabbidva2 3410 . . . . . . . . . . 11 (𝑒 = 𝑧 β†’ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} = {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
109unieqd 4880 . . . . . . . . . 10 (𝑒 = 𝑧 β†’ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} = βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
11 eqid 2737 . . . . . . . . . 10 (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
12 vex 3450 . . . . . . . . . . . 12 𝑧 ∈ V
1312rabex 5290 . . . . . . . . . . 11 {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ V
1413uniex 7679 . . . . . . . . . 10 βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ V
1510, 11, 14fvmpt 6949 . . . . . . . . 9 (𝑧 ∈ π‘₯ β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) = βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
1615eleq1d 2823 . . . . . . . 8 (𝑧 ∈ π‘₯ β†’ (((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧 ↔ βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝑧))
173, 16syl5ibr 246 . . . . . . 7 (𝑧 ∈ π‘₯ β†’ (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧))
1817imim2d 57 . . . . . 6 (𝑧 ∈ π‘₯ β†’ ((𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧)))
1918ralimia 3084 . . . . 5 (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧))
20 ssrab2 4038 . . . . . . . . . . 11 {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† 𝑒
21 elssuni 4899 . . . . . . . . . . 11 (𝑒 ∈ π‘₯ β†’ 𝑒 βŠ† βˆͺ π‘₯)
2220, 21sstrid 3956 . . . . . . . . . 10 (𝑒 ∈ π‘₯ β†’ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† βˆͺ π‘₯)
2322unissd 4876 . . . . . . . . 9 (𝑒 ∈ π‘₯ β†’ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† βˆͺ βˆͺ π‘₯)
24 vex 3450 . . . . . . . . . . . 12 π‘₯ ∈ V
2524uniex 7679 . . . . . . . . . . 11 βˆͺ π‘₯ ∈ V
2625uniex 7679 . . . . . . . . . 10 βˆͺ βˆͺ π‘₯ ∈ V
2726elpw2 5303 . . . . . . . . 9 (βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝒫 βˆͺ βˆͺ π‘₯ ↔ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† βˆͺ βˆͺ π‘₯)
2823, 27sylibr 233 . . . . . . . 8 (𝑒 ∈ π‘₯ β†’ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝒫 βˆͺ βˆͺ π‘₯)
2911, 28fmpti 7061 . . . . . . 7 (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}):π‘₯βŸΆπ’« βˆͺ βˆͺ π‘₯
3026pwex 5336 . . . . . . 7 𝒫 βˆͺ βˆͺ π‘₯ ∈ V
31 fex2 7871 . . . . . . 7 (((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}):π‘₯βŸΆπ’« βˆͺ βˆͺ π‘₯ ∧ π‘₯ ∈ V ∧ 𝒫 βˆͺ βˆͺ π‘₯ ∈ V) β†’ (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) ∈ V)
3229, 24, 30, 31mp3an 1462 . . . . . 6 (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) ∈ V
33 fveq1 6842 . . . . . . . . 9 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ (π‘“β€˜π‘§) = ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§))
3433eleq1d 2823 . . . . . . . 8 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ ((π‘“β€˜π‘§) ∈ 𝑧 ↔ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧))
3534imbi2d 341 . . . . . . 7 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ ((𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧) ↔ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧)))
3635ralbidv 3175 . . . . . 6 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧) ↔ βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧)))
3732, 36spcev 3566 . . . . 5 (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧) β†’ βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
3819, 37syl 17 . . . 4 (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
3938exlimiv 1934 . . 3 (βˆƒπ‘¦βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
4039alimi 1814 . 2 (βˆ€π‘₯βˆƒπ‘¦βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆ€π‘₯βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
41 dfac3 10058 . 2 (CHOICE ↔ βˆ€π‘₯βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
4240, 41sylibr 233 1 (βˆ€π‘₯βˆƒπ‘¦βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ CHOICE)
Colors of variables: wff setvar class
Syntax hints:   β†’ wi 4   ∧ wa 397  βˆ€wal 1540   = wceq 1542  βˆƒwex 1782   ∈ wcel 2107   β‰  wne 2944  βˆ€wral 3065  βˆƒwrex 3074  βˆƒ!wreu 3352  {crab 3408  Vcvv 3446   βŠ† wss 3911  βˆ…c0 4283  π’« cpw 4561  βˆͺ cuni 4866   ↦ cmpt 5189  βŸΆwf 6493  β€˜cfv 6497  β„©crio 7313  CHOICEwac 10052
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  ax-5 1914  ax-6 1972  ax-7 2012  ax-8 2109  ax-9 2117  ax-10 2138  ax-11 2155  ax-12 2172  ax-ext 2708  ax-sep 5257  ax-nul 5264  ax-pow 5321  ax-pr 5385  ax-un 7673
This theorem depends on definitions:  df-bi 206  df-an 398  df-or 847  df-3an 1090  df-tru 1545  df-fal 1555  df-ex 1783  df-nf 1787  df-sb 2069  df-mo 2539  df-eu 2568  df-clab 2715  df-cleq 2729  df-clel 2815  df-nfc 2890  df-ne 2945  df-ral 3066  df-rex 3075  df-reu 3355  df-rab 3409  df-v 3448  df-sbc 3741  df-dif 3914  df-un 3916  df-in 3918  df-ss 3928  df-nul 4284  df-if 4488  df-pw 4563  df-sn 4588  df-pr 4590  df-op 4594  df-uni 4867  df-br 5107  df-opab 5169  df-mpt 5190  df-id 5532  df-xp 5640  df-rel 5641  df-cnv 5642  df-co 5643  df-dm 5644  df-rn 5645  df-res 5646  df-ima 5647  df-iota 6449  df-fun 6499  df-fn 6500  df-f 6501  df-fv 6505  df-riota 7314  df-ac 10053
This theorem is referenced by:  dfac2  10068  axac2  10403
  Copyright terms: Public domain W3C validator