Theorem dfac2a 10247

Description: Our Axiom of Choice (in the form of ac3 10579) implies the Axiom of Choice (first form) of [Enderton] p. 49. The proof uses neither AC nor the Axiom of Regularity. See dfac2b 10248 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 7414	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
2		riotacl 7425	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ∈ 𝑧)
3	1, 2	eqeltrrd 2865	. . . . . . . 8 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧)
4		elequ2 2162	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (𝑤 ∈ 𝑢 ↔ 𝑤 ∈ 𝑧))
5		elequ1 2154	. . . . . . . . . . . . . . 15 ⊢ (𝑢 = 𝑧 → (𝑢 ∈ 𝑣 ↔ 𝑧 ∈ 𝑣))
6	5	anbi1d 643	. . . . . . . . . . . . . 14 ⊢ (𝑢 = 𝑧 → ((𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
7	6	rexbidv 3190	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
8	4, 7	anbi12d 644	. . . . . . . . . . . 12 ⊢ (𝑢 = 𝑧 → ((𝑤 ∈ 𝑢 ∧ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ↔ (𝑤 ∈ 𝑧 ∧ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))))
9	8	rabbidva2 3418	. . . . . . . . . . 11 ⊢ (𝑢 = 𝑧 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
10	9	unieqd 4885	. . . . . . . . . 10 ⊢ (𝑢 = 𝑧 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
11		eqid 2763	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
12		vex 3458	. . . . . . . . . . . 12 ⊢ 𝑧 ∈ V
13	12	rabex 5307	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
14	13	uniex 7790	. . . . . . . . . 10 ⊢ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
15	10, 11, 14	fvmpt 7024	. . . . . . . . 9 ⊢ (𝑧 ∈ 𝑥 → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
16	15	eleq1d 2849	. . . . . . . 8 ⊢ (𝑧 ∈ 𝑥 → (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧 ↔ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧))
17	3, 16	imbitrrid 249	. . . . . . 7 ⊢ (𝑧 ∈ 𝑥 → (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
18	17	imim2d 58	. . . . . 6 ⊢ (𝑧 ∈ 𝑥 → ((𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
19	18	ralimia 3100	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
20		ssrab2 4008	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ 𝑢
21		elssuni 4904	. . . . . . . . . . 11 ⊢ (𝑢 ∈ 𝑥 → 𝑢 ⊆ ∪ 𝑥)
22	20, 21	sstrid 3924	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ 𝑥)
23	22	unissd 4882	. . . . . . . . 9 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
24		vex 3458	. . . . . . . . . . . 12 ⊢ 𝑥 ∈ V
25	24	uniex 7790	. . . . . . . . . . 11 ⊢ ∪ 𝑥 ∈ V
26	25	uniex 7790	. . . . . . . . . 10 ⊢ ∪ ∪ 𝑥 ∈ V
27	26	elpw2 5303	. . . . . . . . 9 ⊢ (∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥 ↔ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
28	23, 27	sylibr 237	. . . . . . . 8 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥)
29	11, 28	fmpti 7144	. . . . . . 7 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥
30	26	pwex 5349	. . . . . . 7 ⊢ 𝒫 ∪ ∪ 𝑥 ∈ V
31		fex2 7982	. . . . . . 7 ⊢ (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥 ∧ 𝑥 ∈ V ∧ 𝒫 ∪ ∪ 𝑥 ∈ V) → (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V)
32	29, 24, 30, 31	mp3an 1491	. . . . . 6 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V
33		fveq1 6915	. . . . . . . . 9 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (𝑓‘𝑧) = ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧))
34	33	eleq1d 2849	. . . . . . . 8 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑓‘𝑧) ∈ 𝑧 ↔ ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
35	34	imbi2d 343	. . . . . . 7 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
36	35	ralbidv 3189	. . . . . 6 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
37	32, 36	spcev 3564	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
38	19, 37	syl 18	. . . 4 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
39	38	exlimiv 1965	. . 3 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
40	39	alimi 1844	. 2 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
41		dfac3 10239	. 2 ⊢ (CHOICE ↔ ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
42	40, 41	sylibr 237	1 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → CHOICE)

This proof depends on syntax axioms:   → wi 4   ∧ wa 401  ∀wal 1568   = wceq 1570  ∃wex 1812   ∈ wcel 2147   ≠ wne 2959  ∀wral 3080  ∃wrex 3090  ∃!wreu 3367  {crab 3416  Vcvv 3454   ⊆ wss 3900  ∅c0 4281  𝒫 cpw 4560  ∪ cuni 4872   ↦ cmpt 5192  ⟶wf 6562  ‘cfv 6566  ℩crio 7407  CHOICEwac 10233

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-10 2180  ax-11 2197  ax-12 2216  ax-ext 2735  ax-sep 5255  ax-nul 5266  ax-pow 5334  ax-pr 5398  ax-un 7783

This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2102  df-mo 2567  df-eu 2597  df-clab 2742  df-cleq 2755  df-clel 2839  df-nfc 2913  df-ne 2960  df-ral 3081  df-rex 3091  df-reu 3370  df-rab 3417  df-v 3456  df-sbc 3743  df-ss 3901  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-pw 4562  df-sn 4589  df-pr 4591  df-op 4841  df-uni 4873  df-br 5109  df-opab 5174  df-mpt 5193  df-id 5553  df-xp 5664  df-rel 5665  df-cnv 5666  df-co 5667  df-dm 5668  df-rn 5669  df-res 5670  df-ima 5671  df-iota 6520  df-fun 6568  df-fn 6569  df-f 6570  df-fv 6574  df-riota 7408  df-ac 10234

This theorem is used by:  dfac2  10249  axac2  10583