Theorem dfac2a 10112

Description: Our Axiom of Choice (in the form of ac3 10445) implies the Axiom of Choice (first form) of [Enderton] p. 49. The proof uses neither AC nor the Axiom of Regularity. See dfac2b 10113 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.

Step	Hyp	Ref	Expression
1		riotauni 7374	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
2		riotacl 7385	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ∈ 𝑧)
3	1, 2	eqeltrrd 2870	. . . . . . . 8 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧)
4		elequ2 2164	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (𝑤 ∈ 𝑢 ↔ 𝑤 ∈ 𝑧))
5		elequ1 2156	. . . . . . . . . . . . . . 15 ⊢ (𝑢 = 𝑧 → (𝑢 ∈ 𝑣 ↔ 𝑧 ∈ 𝑣))
6	5	anbi1d 642	. . . . . . . . . . . . . 14 ⊢ (𝑢 = 𝑧 → ((𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
7	6	rexbidv 3195	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
8	4, 7	anbi12d 643	. . . . . . . . . . . 12 ⊢ (𝑢 = 𝑧 → ((𝑤 ∈ 𝑢 ∧ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ↔ (𝑤 ∈ 𝑧 ∧ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))))
9	8	rabbidva2 3425	. . . . . . . . . . 11 ⊢ (𝑢 = 𝑧 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
10	9	unieqd 4889	. . . . . . . . . 10 ⊢ (𝑢 = 𝑧 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
11		eqid 2769	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
12		vex 3467	. . . . . . . . . . . 12 ⊢ 𝑧 ∈ V
13	12	rabex 5310	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
14	13	uniex 7739	. . . . . . . . . 10 ⊢ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
15	10, 11, 14	fvmpt 6990	. . . . . . . . 9 ⊢ (𝑧 ∈ 𝑥 → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
16	15	eleq1d 2854	. . . . . . . 8 ⊢ (𝑧 ∈ 𝑥 → (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧 ↔ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧))
17	3, 16	imbitrrid 249	. . . . . . 7 ⊢ (𝑧 ∈ 𝑥 → (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
18	17	imim2d 58	. . . . . 6 ⊢ (𝑧 ∈ 𝑥 → ((𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
19	18	ralimia 3105	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
20		ssrab2 4042	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ 𝑢
21		elssuni 4908	. . . . . . . . . . 11 ⊢ (𝑢 ∈ 𝑥 → 𝑢 ⊆ ∪ 𝑥)
22	20, 21	sstrid 3956	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ 𝑥)
23	22	unissd 4886	. . . . . . . . 9 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
24		vex 3467	. . . . . . . . . . . 12 ⊢ 𝑥 ∈ V
25	24	uniex 7739	. . . . . . . . . . 11 ⊢ ∪ 𝑥 ∈ V
26	25	uniex 7739	. . . . . . . . . 10 ⊢ ∪ ∪ 𝑥 ∈ V
27	26	elpw2 5305	. . . . . . . . 9 ⊢ (∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥 ↔ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
28	23, 27	sylibr 237	. . . . . . . 8 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥)
29	11, 28	fmpti 7108	. . . . . . 7 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥
30	26	pwex 5352	. . . . . . 7 ⊢ 𝒫 ∪ ∪ 𝑥 ∈ V
31		fex2 7932	. . . . . . 7 ⊢ (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥 ∧ 𝑥 ∈ V ∧ 𝒫 ∪ ∪ 𝑥 ∈ V) → (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V)
32	29, 24, 30, 31	mp3an 1487	. . . . . 6 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V
33		fveq1 6881	. . . . . . . . 9 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (𝑓‘𝑧) = ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧))
34	33	eleq1d 2854	. . . . . . . 8 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑓‘𝑧) ∈ 𝑧 ↔ ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
35	34	imbi2d 343	. . . . . . 7 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
36	35	ralbidv 3194	. . . . . 6 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
37	32, 36	spcev 3574	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
38	19, 37	syl 18	. . . 4 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
39	38	exlimiv 1957	. . 3 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
40	39	alimi 1838	. 2 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
41		dfac3 10104	. 2 ⊢ (CHOICE ↔ ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
42	40, 41	sylibr 237	1 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → CHOICE)

Syntax hints:   → wi 4   ∧ wa 400  ∀wal 1565   = wceq 1567  ∃wex 1806   ∈ wcel 2149   ≠ wne 2964  ∀wral 3085  ∃wrex 3095  ∃!wreu 3374  {crab 3423  Vcvv 3463   ⊆ wss 3913  ∅c0 4294  𝒫 cpw 4567  ∪ cuni 4876   ↦ cmpt 5196  ⟶wf 6533  ‘cfv 6537  ℩crio 7367  CHOICEwac 10098

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1822  ax-4 1836  ax-5 1937  ax-6 1994  ax-7 2035  ax-8 2151  ax-9 2159  ax-10 2182  ax-11 2198  ax-12 2219  ax-ext 2741  ax-sep 5261  ax-nul 5271  ax-pow 5337  ax-pr 5405  ax-un 7733

This theorem depends on definitions:  df-bi 210  df-an 401  df-or 861  df-3an 1103  df-tru 1570  df-fal 1580  df-ex 1807  df-nf 1811  df-sb 2098  df-mo 2573  df-eu 2603  df-clab 2748  df-cleq 2761  df-clel 2844  df-nfc 2918  df-ne 2965  df-ral 3086  df-rex 3096  df-reu 3377  df-rab 3424  df-v 3465  df-sbc 3754  df-dif 3916  df-un 3918  df-in 3920  df-ss 3930  df-nul 4295  df-if 4493  df-pw 4569  df-sn 4595  df-pr 4597  df-op 4601  df-uni 4877  df-br 5114  df-opab 5178  df-mpt 5197  df-id 5557  df-xp 5668  df-rel 5669  df-cnv 5670  df-co 5671  df-dm 5672  df-rn 5673  df-res 5674  df-ima 5675  df-iota 6493  df-fun 6539  df-fn 6540  df-f 6541  df-fv 6545  df-riota 7368  df-ac 10099

This theorem is referenced by:  dfac2  10114  axac2  10449