Theorem dfac2a 9541

Description: Our Axiom of Choice (in the form of ac3 9870) implies the Axiom of Choice (first form) of [Enderton] p. 49. The proof uses neither AC nor the Axiom of Regularity. See dfac2b 9542 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 7106	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
2		riotacl 7117	. . . . . . . . 9 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → (℩𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ∈ 𝑧)
3	1, 2	eqeltrrd 2914	. . . . . . . 8 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧)
4		elequ2 2129	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (𝑤 ∈ 𝑢 ↔ 𝑤 ∈ 𝑧))
5		elequ1 2121	. . . . . . . . . . . . . . 15 ⊢ (𝑢 = 𝑧 → (𝑢 ∈ 𝑣 ↔ 𝑧 ∈ 𝑣))
6	5	anbi1d 631	. . . . . . . . . . . . . 14 ⊢ (𝑢 = 𝑧 → ((𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
7	6	rexbidv 3297	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
8	4, 7	anbi12d 632	. . . . . . . . . . . 12 ⊢ (𝑢 = 𝑧 → ((𝑤 ∈ 𝑢 ∧ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ↔ (𝑤 ∈ 𝑧 ∧ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))))
9	8	rabbidva2 3468	. . . . . . . . . . 11 ⊢ (𝑢 = 𝑧 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
10	9	unieqd 4838	. . . . . . . . . 10 ⊢ (𝑢 = 𝑧 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
11		eqid 2821	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
12		vex 3489	. . . . . . . . . . . 12 ⊢ 𝑧 ∈ V
13	12	rabex 5221	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
14	13	uniex 7453	. . . . . . . . . 10 ⊢ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
15	10, 11, 14	fvmpt 6754	. . . . . . . . 9 ⊢ (𝑧 ∈ 𝑥 → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
16	15	eleq1d 2897	. . . . . . . 8 ⊢ (𝑧 ∈ 𝑥 → (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧 ↔ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧))
17	3, 16	syl5ibr 248	. . . . . . 7 ⊢ (𝑧 ∈ 𝑥 → (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
18	17	imim2d 57	. . . . . 6 ⊢ (𝑧 ∈ 𝑥 → ((𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
19	18	ralimia 3158	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
20		ssrab2 4044	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ 𝑢
21		elssuni 4854	. . . . . . . . . . 11 ⊢ (𝑢 ∈ 𝑥 → 𝑢 ⊆ ∪ 𝑥)
22	20, 21	sstrid 3966	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ 𝑥)
23	22	unissd 4834	. . . . . . . . 9 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
24		vex 3489	. . . . . . . . . . . 12 ⊢ 𝑥 ∈ V
25	24	uniex 7453	. . . . . . . . . . 11 ⊢ ∪ 𝑥 ∈ V
26	25	uniex 7453	. . . . . . . . . 10 ⊢ ∪ ∪ 𝑥 ∈ V
27	26	elpw2 5234	. . . . . . . . 9 ⊢ (∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥 ↔ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
28	23, 27	sylibr 236	. . . . . . . 8 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥)
29	11, 28	fmpti 6862	. . . . . . 7 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥
30	26	pwex 5267	. . . . . . 7 ⊢ 𝒫 ∪ ∪ 𝑥 ∈ V
31		fex2 7624	. . . . . . 7 ⊢ (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥 ∧ 𝑥 ∈ V ∧ 𝒫 ∪ ∪ 𝑥 ∈ V) → (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V)
32	29, 24, 30, 31	mp3an 1457	. . . . . 6 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V
33		fveq1 6655	. . . . . . . . 9 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (𝑓‘𝑧) = ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧))
34	33	eleq1d 2897	. . . . . . . 8 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑓‘𝑧) ∈ 𝑧 ↔ ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
35	34	imbi2d 343	. . . . . . 7 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
36	35	ralbidv 3197	. . . . . 6 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
37	32, 36	spcev 3599	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
38	19, 37	syl 17	. . . 4 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
39	38	exlimiv 1931	. . 3 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
40	39	alimi 1812	. 2 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
41		dfac3 9533	. 2 ⊢ (CHOICE ↔ ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
42	40, 41	sylibr 236	1 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → CHOICE)

Syntax hints:   → wi 4   ∧ wa 398  ∀wal 1535   = wceq 1537  ∃wex 1780   ∈ wcel 2114   ≠ wne 3016  ∀wral 3138  ∃wrex 3139  ∃!wreu 3140  {crab 3142  Vcvv 3486   ⊆ wss 3924  ∅c0 4279  𝒫 cpw 4525  ∪ cuni 4824   ↦ cmpt 5132  ⟶wf 6337  ‘cfv 6341  ℩crio 7099  CHOICEwac 9527

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 1970  ax-7 2015  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2161  ax-12 2177  ax-ext 2793  ax-sep 5189  ax-nul 5196  ax-pow 5252  ax-pr 5316  ax-un 7447

This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3an 1085  df-tru 1540  df-ex 1781  df-nf 1785  df-sb 2070  df-mo 2622  df-eu 2654  df-clab 2800  df-cleq 2814  df-clel 2893  df-nfc 2963  df-ne 3017  df-ral 3143  df-rex 3144  df-reu 3145  df-rab 3147  df-v 3488  df-sbc 3764  df-dif 3927  df-un 3929  df-in 3931  df-ss 3940  df-nul 4280  df-if 4454  df-pw 4527  df-sn 4554  df-pr 4556  df-op 4560  df-uni 4825  df-br 5053  df-opab 5115  df-mpt 5133  df-id 5446  df-xp 5547  df-rel 5548  df-cnv 5549  df-co 5550  df-dm 5551  df-rn 5552  df-res 5553  df-ima 5554  df-iota 6300  df-fun 6343  df-fn 6344  df-f 6345  df-fv 6349  df-riota 7100  df-ac 9528

This theorem is referenced by:  dfac2  9543  axac2  9874