Theorem dfac2a 10038

Description: Our Axiom of Choice (in the form of ac3 10370) implies the Axiom of Choice (first form) of [Enderton] p. 49. The proof uses neither AC nor the Axiom of Regularity. See dfac2b 10039 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 7319	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
2		riotacl 7330	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ∈ 𝑧)
3	1, 2	eqeltrrd 2835	. . . . . . . 8 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧)
4		elequ2 2128	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (𝑤 ∈ 𝑢 ↔ 𝑤 ∈ 𝑧))
5		elequ1 2120	. . . . . . . . . . . . . . 15 ⊢ (𝑢 = 𝑧 → (𝑢 ∈ 𝑣 ↔ 𝑧 ∈ 𝑣))
6	5	anbi1d 631	. . . . . . . . . . . . . 14 ⊢ (𝑢 = 𝑧 → ((𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
7	6	rexbidv 3158	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
8	4, 7	anbi12d 632	. . . . . . . . . . . 12 ⊢ (𝑢 = 𝑧 → ((𝑤 ∈ 𝑢 ∧ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ↔ (𝑤 ∈ 𝑧 ∧ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))))
9	8	rabbidva2 3399	. . . . . . . . . . 11 ⊢ (𝑢 = 𝑧 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
10	9	unieqd 4874	. . . . . . . . . 10 ⊢ (𝑢 = 𝑧 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
11		eqid 2734	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
12		vex 3442	. . . . . . . . . . . 12 ⊢ 𝑧 ∈ V
13	12	rabex 5282	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
14	13	uniex 7684	. . . . . . . . . 10 ⊢ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
15	10, 11, 14	fvmpt 6939	. . . . . . . . 9 ⊢ (𝑧 ∈ 𝑥 → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
16	15	eleq1d 2819	. . . . . . . 8 ⊢ (𝑧 ∈ 𝑥 → (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧 ↔ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧))
17	3, 16	imbitrrid 246	. . . . . . 7 ⊢ (𝑧 ∈ 𝑥 → (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
18	17	imim2d 57	. . . . . 6 ⊢ (𝑧 ∈ 𝑥 → ((𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
19	18	ralimia 3068	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
20		ssrab2 4030	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ 𝑢
21		elssuni 4892	. . . . . . . . . . 11 ⊢ (𝑢 ∈ 𝑥 → 𝑢 ⊆ ∪ 𝑥)
22	20, 21	sstrid 3943	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ 𝑥)
23	22	unissd 4871	. . . . . . . . 9 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
24		vex 3442	. . . . . . . . . . . 12 ⊢ 𝑥 ∈ V
25	24	uniex 7684	. . . . . . . . . . 11 ⊢ ∪ 𝑥 ∈ V
26	25	uniex 7684	. . . . . . . . . 10 ⊢ ∪ ∪ 𝑥 ∈ V
27	26	elpw2 5277	. . . . . . . . 9 ⊢ (∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥 ↔ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
28	23, 27	sylibr 234	. . . . . . . 8 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥)
29	11, 28	fmpti 7055	. . . . . . 7 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥
30	26	pwex 5323	. . . . . . 7 ⊢ 𝒫 ∪ ∪ 𝑥 ∈ V
31		fex2 7876	. . . . . . 7 ⊢ (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥 ∧ 𝑥 ∈ V ∧ 𝒫 ∪ ∪ 𝑥 ∈ V) → (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V)
32	29, 24, 30, 31	mp3an 1463	. . . . . 6 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V
33		fveq1 6831	. . . . . . . . 9 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (𝑓‘𝑧) = ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧))
34	33	eleq1d 2819	. . . . . . . 8 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑓‘𝑧) ∈ 𝑧 ↔ ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
35	34	imbi2d 340	. . . . . . 7 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
36	35	ralbidv 3157	. . . . . 6 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
37	32, 36	spcev 3558	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
38	19, 37	syl 17	. . . 4 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
39	38	exlimiv 1931	. . 3 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
40	39	alimi 1812	. 2 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
41		dfac3 10029	. 2 ⊢ (CHOICE ↔ ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
42	40, 41	sylibr 234	1 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → CHOICE)

Syntax hints:   → wi 4   ∧ wa 395  ∀wal 1539   = wceq 1541  ∃wex 1780   ∈ wcel 2113   ≠ wne 2930  ∀wral 3049  ∃wrex 3058  ∃!wreu 3346  {crab 3397  Vcvv 3438   ⊆ wss 3899  ∅c0 4283  𝒫 cpw 4552  ∪ cuni 4861   ↦ cmpt 5177  ⟶wf 6486  ‘cfv 6490  ℩crio 7312  CHOICEwac 10023

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1968  ax-7 2009  ax-8 2115  ax-9 2123  ax-10 2146  ax-11 2162  ax-12 2182  ax-ext 2706  ax-sep 5239  ax-nul 5249  ax-pow 5308  ax-pr 5375  ax-un 7678

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3an 1088  df-tru 1544  df-fal 1554  df-ex 1781  df-nf 1785  df-sb 2068  df-mo 2537  df-eu 2567  df-clab 2713  df-cleq 2726  df-clel 2809  df-nfc 2883  df-ne 2931  df-ral 3050  df-rex 3059  df-reu 3349  df-rab 3398  df-v 3440  df-sbc 3739  df-dif 3902  df-un 3904  df-in 3906  df-ss 3916  df-nul 4284  df-if 4478  df-pw 4554  df-sn 4579  df-pr 4581  df-op 4585  df-uni 4862  df-br 5097  df-opab 5159  df-mpt 5178  df-id 5517  df-xp 5628  df-rel 5629  df-cnv 5630  df-co 5631  df-dm 5632  df-rn 5633  df-res 5634  df-ima 5635  df-iota 6446  df-fun 6492  df-fn 6493  df-f 6494  df-fv 6498  df-riota 7313  df-ac 10024

This theorem is referenced by:  dfac2  10040  axac2  10374