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

Theorem dfac2a 10124
Description: Our Axiom of Choice (in the form of ac3 10457) implies the Axiom of Choice (first form) of [Enderton] p. 49. The proof uses neither AC nor the Axiom of Regularity. See dfac2b 10125 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 7371 . . . . . . . . 9 (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ (℩𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) = βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
2 riotacl 7383 . . . . . . . . 9 (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ (℩𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) ∈ 𝑧)
31, 2eqeltrrd 2835 . . . . . . . 8 (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝑧)
4 elequ2 2122 . . . . . . . . . . . . 13 (𝑒 = 𝑧 β†’ (𝑀 ∈ 𝑒 ↔ 𝑀 ∈ 𝑧))
5 elequ1 2114 . . . . . . . . . . . . . . 15 (𝑒 = 𝑧 β†’ (𝑒 ∈ 𝑣 ↔ 𝑧 ∈ 𝑣))
65anbi1d 631 . . . . . . . . . . . . . 14 (𝑒 = 𝑧 β†’ ((𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) ↔ (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)))
76rexbidv 3179 . . . . . . . . . . . . 13 (𝑒 = 𝑧 β†’ (βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) ↔ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)))
84, 7anbi12d 632 . . . . . . . . . . . 12 (𝑒 = 𝑧 β†’ ((𝑀 ∈ 𝑒 ∧ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) ↔ (𝑀 ∈ 𝑧 ∧ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣))))
98rabbidva2 3435 . . . . . . . . . . 11 (𝑒 = 𝑧 β†’ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} = {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
109unieqd 4923 . . . . . . . . . 10 (𝑒 = 𝑧 β†’ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} = βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
11 eqid 2733 . . . . . . . . . 10 (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
12 vex 3479 . . . . . . . . . . . 12 𝑧 ∈ V
1312rabex 5333 . . . . . . . . . . 11 {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ V
1413uniex 7731 . . . . . . . . . 10 βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ V
1510, 11, 14fvmpt 6999 . . . . . . . . 9 (𝑧 ∈ π‘₯ β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) = βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})
1615eleq1d 2819 . . . . . . . 8 (𝑧 ∈ π‘₯ β†’ (((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧 ↔ βˆͺ {𝑀 ∈ 𝑧 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝑧))
173, 16imbitrrid 245 . . . . . . 7 (𝑧 ∈ π‘₯ β†’ (βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣) β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧))
1817imim2d 57 . . . . . 6 (𝑧 ∈ π‘₯ β†’ ((𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧)))
1918ralimia 3081 . . . . 5 (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧))
20 ssrab2 4078 . . . . . . . . . . 11 {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† 𝑒
21 elssuni 4942 . . . . . . . . . . 11 (𝑒 ∈ π‘₯ β†’ 𝑒 βŠ† βˆͺ π‘₯)
2220, 21sstrid 3994 . . . . . . . . . 10 (𝑒 ∈ π‘₯ β†’ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† βˆͺ π‘₯)
2322unissd 4919 . . . . . . . . 9 (𝑒 ∈ π‘₯ β†’ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† βˆͺ βˆͺ π‘₯)
24 vex 3479 . . . . . . . . . . . 12 π‘₯ ∈ V
2524uniex 7731 . . . . . . . . . . 11 βˆͺ π‘₯ ∈ V
2625uniex 7731 . . . . . . . . . 10 βˆͺ βˆͺ π‘₯ ∈ V
2726elpw2 5346 . . . . . . . . 9 (βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝒫 βˆͺ βˆͺ π‘₯ ↔ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} βŠ† βˆͺ βˆͺ π‘₯)
2823, 27sylibr 233 . . . . . . . 8 (𝑒 ∈ π‘₯ β†’ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)} ∈ 𝒫 βˆͺ βˆͺ π‘₯)
2911, 28fmpti 7112 . . . . . . 7 (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}):π‘₯βŸΆπ’« βˆͺ βˆͺ π‘₯
3026pwex 5379 . . . . . . 7 𝒫 βˆͺ βˆͺ π‘₯ ∈ V
31 fex2 7924 . . . . . . 7 (((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}):π‘₯βŸΆπ’« βˆͺ βˆͺ π‘₯ ∧ π‘₯ ∈ V ∧ 𝒫 βˆͺ βˆͺ π‘₯ ∈ V) β†’ (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) ∈ V)
3229, 24, 30, 31mp3an 1462 . . . . . 6 (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) ∈ V
33 fveq1 6891 . . . . . . . . 9 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ (π‘“β€˜π‘§) = ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§))
3433eleq1d 2819 . . . . . . . 8 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ ((π‘“β€˜π‘§) ∈ 𝑧 ↔ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧))
3534imbi2d 341 . . . . . . 7 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ ((𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧) ↔ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧)))
3635ralbidv 3178 . . . . . 6 (𝑓 = (𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)}) β†’ (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧) ↔ βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧)))
3732, 36spcev 3597 . . . . 5 (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ ((𝑒 ∈ π‘₯ ↦ βˆͺ {𝑀 ∈ 𝑒 ∣ βˆƒπ‘£ ∈ 𝑦 (𝑒 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)})β€˜π‘§) ∈ 𝑧) β†’ βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
3819, 37syl 17 . . . 4 (βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
3938exlimiv 1934 . . 3 (βˆƒπ‘¦βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
4039alimi 1814 . 2 (βˆ€π‘₯βˆƒπ‘¦βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ βˆƒ!𝑀 ∈ 𝑧 βˆƒπ‘£ ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑀 ∈ 𝑣)) β†’ βˆ€π‘₯βˆƒπ‘“βˆ€π‘§ ∈ π‘₯ (𝑧 β‰  βˆ… β†’ (π‘“β€˜π‘§) ∈ 𝑧))
41 dfac3 10116 . 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 2941  βˆ€wral 3062  βˆƒwrex 3071  βˆƒ!wreu 3375  {crab 3433  Vcvv 3475   βŠ† wss 3949  βˆ…c0 4323  π’« cpw 4603  βˆͺ cuni 4909   ↦ cmpt 5232  βŸΆwf 6540  β€˜cfv 6544  β„©crio 7364  CHOICEwac 10110
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 2704  ax-sep 5300  ax-nul 5307  ax-pow 5364  ax-pr 5428  ax-un 7725
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 2535  df-eu 2564  df-clab 2711  df-cleq 2725  df-clel 2811  df-nfc 2886  df-ne 2942  df-ral 3063  df-rex 3072  df-reu 3378  df-rab 3434  df-v 3477  df-sbc 3779  df-dif 3952  df-un 3954  df-in 3956  df-ss 3966  df-nul 4324  df-if 4530  df-pw 4605  df-sn 4630  df-pr 4632  df-op 4636  df-uni 4910  df-br 5150  df-opab 5212  df-mpt 5233  df-id 5575  df-xp 5683  df-rel 5684  df-cnv 5685  df-co 5686  df-dm 5687  df-rn 5688  df-res 5689  df-ima 5690  df-iota 6496  df-fun 6546  df-fn 6547  df-f 6548  df-fv 6552  df-riota 7365  df-ac 10111
This theorem is referenced by:  dfac2  10126  axac2  10461
  Copyright terms: Public domain W3C validator