Theorem dfac2a 10043

Description: Our Axiom of Choice (in the form of ac3 10375) implies the Axiom of Choice (first form) of [Enderton] p. 49. The proof uses neither AC nor the Axiom of Regularity. See dfac2b 10044 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 2840	. . . . . . . 8 ⊢ (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧)
4		elequ2 2134	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (𝑤 ∈ 𝑢 ↔ 𝑤 ∈ 𝑧))
5		elequ1 2126	. . . . . . . . . . . . . . 15 ⊢ (𝑢 = 𝑧 → (𝑢 ∈ 𝑣 ↔ 𝑧 ∈ 𝑣))
6	5	anbi1d 637	. . . . . . . . . . . . . 14 ⊢ (𝑢 = 𝑧 → ((𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
7	6	rexbidv 3163	. . . . . . . . . . . . 13 ⊢ (𝑢 = 𝑧 → (∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) ↔ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)))
8	4, 7	anbi12d 638	. . . . . . . . . . . 12 ⊢ (𝑢 = 𝑧 → ((𝑤 ∈ 𝑢 ∧ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) ↔ (𝑤 ∈ 𝑧 ∧ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣))))
9	8	rabbidva2 3393	. . . . . . . . . . 11 ⊢ (𝑢 = 𝑧 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
10	9	unieqd 4851	. . . . . . . . . 10 ⊢ (𝑢 = 𝑧 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
11		eqid 2739	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
12		vex 3435	. . . . . . . . . . . 12 ⊢ 𝑧 ∈ V
13	12	rabex 5267	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
14	13	uniex 7684	. . . . . . . . . 10 ⊢ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ V
15	10, 11, 14	fvmpt 6935	. . . . . . . . 9 ⊢ (𝑧 ∈ 𝑥 → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) = ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})
16	15	eleq1d 2824	. . . . . . . 8 ⊢ (𝑧 ∈ 𝑥 → (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧 ↔ ∪ {𝑤 ∈ 𝑧 ∣ ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝑧))
17	3, 16	imbitrrid 247	. . . . . . 7 ⊢ (𝑧 ∈ 𝑥 → (∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣) → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
18	17	imim2d 57	. . . . . 6 ⊢ (𝑧 ∈ 𝑥 → ((𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
19	18	ralimia 3073	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
20		ssrab2 4011	. . . . . . . . . . 11 ⊢ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ 𝑢
21		elssuni 4869	. . . . . . . . . . 11 ⊢ (𝑢 ∈ 𝑥 → 𝑢 ⊆ ∪ 𝑥)
22	20, 21	sstrid 3926	. . . . . . . . . 10 ⊢ (𝑢 ∈ 𝑥 → {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ 𝑥)
23	22	unissd 4848	. . . . . . . . 9 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
24		vex 3435	. . . . . . . . . . . 12 ⊢ 𝑥 ∈ V
25	24	uniex 7684	. . . . . . . . . . 11 ⊢ ∪ 𝑥 ∈ V
26	25	uniex 7684	. . . . . . . . . 10 ⊢ ∪ ∪ 𝑥 ∈ V
27	26	elpw2 5262	. . . . . . . . 9 ⊢ (∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥 ↔ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ⊆ ∪ ∪ 𝑥)
28	23, 27	sylibr 235	. . . . . . . 8 ⊢ (𝑢 ∈ 𝑥 → ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)} ∈ 𝒫 ∪ ∪ 𝑥)
29	11, 28	fmpti 7053	. . . . . . 7 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥
30	26	pwex 5309	. . . . . . 7 ⊢ 𝒫 ∪ ∪ 𝑥 ∈ V
31		fex2 7876	. . . . . . 7 ⊢ (((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}):𝑥⟶𝒫 ∪ ∪ 𝑥 ∧ 𝑥 ∈ V ∧ 𝒫 ∪ ∪ 𝑥 ∈ V) → (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V)
32	29, 24, 30, 31	mp3an 1469	. . . . . 6 ⊢ (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) ∈ V
33		fveq1 6826	. . . . . . . . 9 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (𝑓‘𝑧) = ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧))
34	33	eleq1d 2824	. . . . . . . 8 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑓‘𝑧) ∈ 𝑧 ↔ ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧))
35	34	imbi2d 341	. . . . . . 7 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → ((𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
36	35	ralbidv 3162	. . . . . 6 ⊢ (𝑓 = (𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)}) → (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧) ↔ ∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧)))
37	32, 36	spcev 3544	. . . . 5 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ((𝑢 ∈ 𝑥 ↦ ∪ {𝑤 ∈ 𝑢 ∣ ∃𝑣 ∈ 𝑦 (𝑢 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)})‘𝑧) ∈ 𝑧) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
38	19, 37	syl 17	. . . 4 ⊢ (∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
39	38	exlimiv 1937	. . 3 ⊢ (∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
40	39	alimi 1818	. 2 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
41		dfac3 10034	. 2 ⊢ (CHOICE ↔ ∀𝑥∃𝑓∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → (𝑓‘𝑧) ∈ 𝑧))
42	40, 41	sylibr 235	1 ⊢ (∀𝑥∃𝑦∀𝑧 ∈ 𝑥 (𝑧 ≠ ∅ → ∃!𝑤 ∈ 𝑧 ∃𝑣 ∈ 𝑦 (𝑧 ∈ 𝑣 ∧ 𝑤 ∈ 𝑣)) → CHOICE)

Syntax hints:   → wi 4   ∧ wa 396  ∀wal 1545   = wceq 1547  ∃wex 1786   ∈ wcel 2119   ≠ wne 2934  ∀wral 3053  ∃wrex 3063  ∃!wreu 3342  {crab 3391  Vcvv 3431   ⊆ wss 3883  ∅c0 4261  𝒫 cpw 4529  ∪ cuni 4838   ↦ cmpt 5153  ⟶wf 6481  ‘cfv 6485  ℩crio 7312  CHOICEwac 10028

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1802  ax-4 1816  ax-5 1917  ax-6 1974  ax-7 2015  ax-8 2121  ax-9 2129  ax-10 2152  ax-11 2168  ax-12 2189  ax-ext 2711  ax-sep 5218  ax-nul 5228  ax-pow 5294  ax-pr 5362  ax-un 7678

This theorem depends on definitions:  df-bi 208  df-an 397  df-or 854  df-3an 1094  df-tru 1550  df-fal 1560  df-ex 1787  df-nf 1791  df-sb 2074  df-mo 2543  df-eu 2573  df-clab 2718  df-cleq 2731  df-clel 2814  df-nfc 2888  df-ne 2935  df-ral 3054  df-rex 3064  df-reu 3345  df-rab 3392  df-v 3433  df-sbc 3724  df-dif 3886  df-un 3888  df-in 3890  df-ss 3900  df-nul 4262  df-if 4455  df-pw 4531  df-sn 4556  df-pr 4558  df-op 4562  df-uni 4839  df-br 5073  df-opab 5135  df-mpt 5154  df-id 5513  df-xp 5624  df-rel 5625  df-cnv 5626  df-co 5627  df-dm 5628  df-rn 5629  df-res 5630  df-ima 5631  df-iota 6441  df-fun 6487  df-fn 6488  df-f 6489  df-fv 6493  df-riota 7313  df-ac 10029

This theorem is referenced by:  dfac2  10045  axac2  10379