Theorem dfac2 8579

Description: Axiom of Choice (first form) of [Enderton] p. 49 implies of our Axiom of Choice (in the form of ac3 8910). The proof does not make use of AC. Note that the Axiom of Regularity is used by the proof. Specifically, elirrv 8130 and preleq 8140 that are referenced in the proof each make use of Regularity for their derivations. (The reverse implication can be derived without using Regularity; see dfac2a 8578.) TODO: Fix label in comment, and put label changes into list at top of set.mm. (Contributed by NM, 5-Apr-2004.) (Revised by Mario Carneiro, 26-Jun-2015.)

Assertion

Ref	Expression
dfac2	|- (CHOICE <-> A. x E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) )

Distinct variable group:   x, y, z, w, v

Proof of Theorem dfac2

Dummy variables u f g are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		dfac3 8570	. . 3 |- (CHOICE <-> A. x E. f A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) )
2		nfra1 2785	. . . . . . 7 |- F/ z A. z e. x ( z =/= (/) -> ( f ` z ) e. z )
3		rsp 2773	. . . . . . . . . . . . 13 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( z e. x -> ( z =/= (/) -> ( f ` z ) e. z ) ) )
4		equid 1863	. . . . . . . . . . . . . . . . . . 19 |- z = z
5		neeq1 2705	. . . . . . . . . . . . . . . . . . . . 21 |- ( u = z -> ( u =/= (/) <-> z =/= (/) ) )
6		eqeq1 2475	. . . . . . . . . . . . . . . . . . . . 21 |- ( u = z -> ( u = z <-> z = z ) )
7	5, 6	anbi12d 725	. . . . . . . . . . . . . . . . . . . 20 |- ( u = z -> ( ( u =/= (/) /\ u = z ) <-> ( z =/= (/) /\ z = z ) ) )
8	7	rspcev 3136	. . . . . . . . . . . . . . . . . . 19 |- ( ( z e. x /\ ( z =/= (/) /\ z = z ) ) -> E. u e. x ( u =/= (/) /\ u = z ) )
9	4, 8	mpanr2 698	. . . . . . . . . . . . . . . . . 18 |- ( ( z e. x /\ z =/= (/) ) -> E. u e. x ( u =/= (/) /\ u = z ) )
10		fveq2 5879	. . . . . . . . . . . . . . . . . . . . . 22 |- ( u = z -> ( f ` u ) = ( f ` z ) )
11	10	preq1d 4048	. . . . . . . . . . . . . . . . . . . . 21 |- ( u = z -> { ( f ` u ) , u } = { ( f ` z ) , u } )
12		preq2 4043	. . . . . . . . . . . . . . . . . . . . 21 |- ( u = z -> { ( f ` z ) , u } = { ( f ` z ) , z } )
13	11, 12	eqtr2d 2506	. . . . . . . . . . . . . . . . . . . 20 |- ( u = z -> { ( f ` z ) , z } = { ( f ` u ) , u } )
14	13	anim2i 579	. . . . . . . . . . . . . . . . . . 19 |- ( ( u =/= (/) /\ u = z ) -> ( u =/= (/) /\ { ( f ` z ) , z } = { ( f ` u ) , u } ) )
15	14	reximi 2852	. . . . . . . . . . . . . . . . . 18 |- ( E. u e. x ( u =/= (/) /\ u = z ) -> E. u e. x ( u =/= (/) /\ { ( f ` z ) , z } = { ( f ` u ) , u } ) )
16	9, 15	syl 17	. . . . . . . . . . . . . . . . 17 |- ( ( z e. x /\ z =/= (/) ) -> E. u e. x ( u =/= (/) /\ { ( f ` z ) , z } = { ( f ` u ) , u } ) )
17		prex 4642	. . . . . . . . . . . . . . . . . 18 |- { ( f ` z ) , z } e. _V
18		eqeq1 2475	. . . . . . . . . . . . . . . . . . . 20 |- ( g = { ( f ` z ) , z } -> ( g = { ( f ` u ) , u } <-> { ( f ` z ) , z } = { ( f ` u ) , u } ) )
19	18	anbi2d 718	. . . . . . . . . . . . . . . . . . 19 |- ( g = { ( f ` z ) , z } -> ( ( u =/= (/) /\ g = { ( f ` u ) , u } ) <-> ( u =/= (/) /\ { ( f ` z ) , z } = { ( f ` u ) , u } ) ) )
20	19	rexbidv 2892	. . . . . . . . . . . . . . . . . 18 |- ( g = { ( f ` z ) , z } -> ( E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) <-> E. u e. x ( u =/= (/) /\ { ( f ` z ) , z } = { ( f ` u ) , u } ) ) )
21	17, 20	elab 3173	. . . . . . . . . . . . . . . . 17 |- ( { ( f ` z ) , z } e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } <-> E. u e. x ( u =/= (/) /\ { ( f ` z ) , z } = { ( f ` u ) , u } ) )
22	16, 21	sylibr 217	. . . . . . . . . . . . . . . 16 |- ( ( z e. x /\ z =/= (/) ) -> { ( f ` z ) , z } e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } )
23		vex 3034	. . . . . . . . . . . . . . . . . 18 |- z e. _V
24	23	prid2 4072	. . . . . . . . . . . . . . . . 17 |- z e. { ( f ` z ) , z }
25		fvex 5889	. . . . . . . . . . . . . . . . . 18 |- ( f ` z ) e. _V
26	25	prid1 4071	. . . . . . . . . . . . . . . . 17 |- ( f ` z ) e. { ( f ` z ) , z }
27	24, 26	pm3.2i 462	. . . . . . . . . . . . . . . 16 |- ( z e. { ( f ` z ) , z } /\ ( f ` z ) e. { ( f ` z ) , z } )
28		eleq2 2538	. . . . . . . . . . . . . . . . . 18 |- ( v = { ( f ` z ) , z } -> ( z e. v <-> z e. { ( f ` z ) , z } ) )
29		eleq2 2538	. . . . . . . . . . . . . . . . . 18 |- ( v = { ( f ` z ) , z } -> ( ( f ` z ) e. v <-> ( f ` z ) e. { ( f ` z ) , z } ) )
30	28, 29	anbi12d 725	. . . . . . . . . . . . . . . . 17 |- ( v = { ( f ` z ) , z } -> ( ( z e. v /\ ( f ` z ) e. v ) <-> ( z e. { ( f ` z ) , z } /\ ( f ` z ) e. { ( f ` z ) , z } ) ) )
31	30	rspcev 3136	. . . . . . . . . . . . . . . 16 |- ( ( { ( f ` z ) , z } e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } /\ ( z e. { ( f ` z ) , z } /\ ( f ` z ) e. { ( f ` z ) , z } ) ) -> E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ ( f ` z ) e. v ) )
32	22, 27, 31	sylancl 675	. . . . . . . . . . . . . . 15 |- ( ( z e. x /\ z =/= (/) ) -> E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ ( f ` z ) e. v ) )
33		eleq1 2537	. . . . . . . . . . . . . . . . 17 |- ( w = ( f ` z ) -> ( w e. z <-> ( f ` z ) e. z ) )
34		eleq1 2537	. . . . . . . . . . . . . . . . . . 19 |- ( w = ( f ` z ) -> ( w e. v <-> ( f ` z ) e. v ) )
35	34	anbi2d 718	. . . . . . . . . . . . . . . . . 18 |- ( w = ( f ` z ) -> ( ( z e. v /\ w e. v ) <-> ( z e. v /\ ( f ` z ) e. v ) ) )
36	35	rexbidv 2892	. . . . . . . . . . . . . . . . 17 |- ( w = ( f ` z ) -> ( E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) <-> E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ ( f ` z ) e. v ) ) )
37	33, 36	anbi12d 725	. . . . . . . . . . . . . . . 16 |- ( w = ( f ` z ) -> ( ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) <-> ( ( f ` z ) e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ ( f ` z ) e. v ) ) ) )
38	25, 37	spcev 3127	. . . . . . . . . . . . . . 15 |- ( ( ( f ` z ) e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ ( f ` z ) e. v ) ) -> E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
39	32, 38	sylan2 482	. . . . . . . . . . . . . 14 |- ( ( ( f ` z ) e. z /\ ( z e. x /\ z =/= (/) ) ) -> E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
40	39	ex 441	. . . . . . . . . . . . 13 |- ( ( f ` z ) e. z -> ( ( z e. x /\ z =/= (/) ) -> E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) )
41	3, 40	syl8 71	. . . . . . . . . . . 12 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( z e. x -> ( z =/= (/) -> ( ( z e. x /\ z =/= (/) ) -> E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) ) ) )
42	41	impd 438	. . . . . . . . . . 11 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( ( z e. x /\ z =/= (/) ) -> ( ( z e. x /\ z =/= (/) ) -> E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) ) )
43	42	pm2.43d 49	. . . . . . . . . 10 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( ( z e. x /\ z =/= (/) ) -> E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) )
44		df-rex 2762	. . . . . . . . . . . . . 14 |- ( E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) <-> E. v ( v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } /\ ( z e. v /\ w e. v ) ) )
45		vex 3034	. . . . . . . . . . . . . . . . . . . 20 |- v e. _V
46		eqeq1 2475	. . . . . . . . . . . . . . . . . . . . . 22 |- ( g = v -> ( g = { ( f ` u ) , u } <-> v = { ( f ` u ) , u } ) )
47	46	anbi2d 718	. . . . . . . . . . . . . . . . . . . . 21 |- ( g = v -> ( ( u =/= (/) /\ g = { ( f ` u ) , u } ) <-> ( u =/= (/) /\ v = { ( f ` u ) , u } ) ) )
48	47	rexbidv 2892	. . . . . . . . . . . . . . . . . . . 20 |- ( g = v -> ( E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) <-> E. u e. x ( u =/= (/) /\ v = { ( f ` u ) , u } ) ) )
49	45, 48	elab 3173	. . . . . . . . . . . . . . . . . . 19 |- ( v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } <-> E. u e. x ( u =/= (/) /\ v = { ( f ` u ) , u } ) )
50		neeq1 2705	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 |- ( z = u -> ( z =/= (/) <-> u =/= (/) ) )
51		fveq2 5879	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 |- ( z = u -> ( f ` z ) = ( f ` u ) )
52	51	eleq1d 2533	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 |- ( z = u -> ( ( f ` z ) e. z <-> ( f ` u ) e. z ) )
53		eleq2 2538	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 |- ( z = u -> ( ( f ` u ) e. z <-> ( f ` u ) e. u ) )
54	52, 53	bitrd 261	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 |- ( z = u -> ( ( f ` z ) e. z <-> ( f ` u ) e. u ) )
55	50, 54	imbi12d 327	. . . . . . . . . . . . . . . . . . . . . . . . . 26 |- ( z = u -> ( ( z =/= (/) -> ( f ` z ) e. z ) <-> ( u =/= (/) -> ( f ` u ) e. u ) ) )
56	55	rspccv 3133	. . . . . . . . . . . . . . . . . . . . . . . . 25 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( u e. x -> ( u =/= (/) -> ( f ` u ) e. u ) ) )
57		elirrv 8130	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 |- -. w e. w
58		eleq2 2538	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 |- ( w = z -> ( w e. w <-> w e. z ) )
59	57, 58	mtbii 309	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 |- ( w = z -> -. w e. z )
60	59	con2i 124	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 |- ( w e. z -> -. w = z )
61		vex 3034	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 |- w e. _V
62		fvex 5889	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 |- ( f ` u ) e. _V
63		vex 3034	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 |- u e. _V
64	61, 23, 62, 63	prel12 4143	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 |- ( -. w = z -> ( { w , z } = { ( f ` u ) , u } <-> ( w e. { ( f ` u ) , u } /\ z e. { ( f ` u ) , u } ) ) )
65		ancom 457	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 |- ( ( w e. v /\ z e. v ) <-> ( z e. v /\ w e. v ) )
66		eleq2 2538	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 |- ( v = { ( f ` u ) , u } -> ( w e. v <-> w e. { ( f ` u ) , u } ) )
67		eleq2 2538	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 |- ( v = { ( f ` u ) , u } -> ( z e. v <-> z e. { ( f ` u ) , u } ) )
68	66, 67	anbi12d 725	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 |- ( v = { ( f ` u ) , u } -> ( ( w e. v /\ z e. v ) <-> ( w e. { ( f ` u ) , u } /\ z e. { ( f ` u ) , u } ) ) )
69	65, 68	syl5rbbr 268	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 |- ( v = { ( f ` u ) , u } -> ( ( w e. { ( f ` u ) , u } /\ z e. { ( f ` u ) , u } ) <-> ( z e. v /\ w e. v ) ) )
70	64, 69	sylan9bbr 715	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 |- ( ( v = { ( f ` u ) , u } /\ -. w = z ) -> ( { w , z } = { ( f ` u ) , u } <-> ( z e. v /\ w e. v ) ) )
71	60, 70	sylan2 482	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 |- ( ( v = { ( f ` u ) , u } /\ w e. z ) -> ( { w , z } = { ( f ` u ) , u } <-> ( z e. v /\ w e. v ) ) )
72	71	adantrr 731	. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 |- ( ( v = { ( f ` u ) , u } /\ ( w e. z /\ ( f ` u ) e. u ) ) -> ( { w , z } = { ( f ` u ) , u } <-> ( z e. v /\ w e. v ) ) )
73	72	pm5.32da 653	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 |- ( v = { ( f ` u ) , u } -> ( ( ( w e. z /\ ( f ` u ) e. u ) /\ { w , z } = { ( f ` u ) , u } ) <-> ( ( w e. z /\ ( f ` u ) e. u ) /\ ( z e. v /\ w e. v ) ) ) )
74	61, 23, 62, 63	preleq 8140	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 |- ( ( ( w e. z /\ ( f ` u ) e. u ) /\ { w , z } = { ( f ` u ) , u } ) -> ( w = ( f ` u ) /\ z = u ) )
75	73, 74	syl6bir 237	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 |- ( v = { ( f ` u ) , u } -> ( ( ( w e. z /\ ( f ` u ) e. u ) /\ ( z e. v /\ w e. v ) ) -> ( w = ( f ` u ) /\ z = u ) ) )
76	51	eqeq2d 2481	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 |- ( z = u -> ( w = ( f ` z ) <-> w = ( f ` u ) ) )
77	76	biimparc 495	. . . . . . . . . . . . . . . . . . . . . . . . . . . 28 |- ( ( w = ( f ` u ) /\ z = u ) -> w = ( f ` z ) )
78	75, 77	syl6 33	. . . . . . . . . . . . . . . . . . . . . . . . . . 27 |- ( v = { ( f ` u ) , u } -> ( ( ( w e. z /\ ( f ` u ) e. u ) /\ ( z e. v /\ w e. v ) ) -> w = ( f ` z ) ) )
79	78	exp4c 619	. . . . . . . . . . . . . . . . . . . . . . . . . 26 |- ( v = { ( f ` u ) , u } -> ( w e. z -> ( ( f ` u ) e. u -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) )
80	79	com13 82	. . . . . . . . . . . . . . . . . . . . . . . . 25 |- ( ( f ` u ) e. u -> ( w e. z -> ( v = { ( f ` u ) , u } -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) )
81	56, 80	syl8 71	. . . . . . . . . . . . . . . . . . . . . . . 24 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( u e. x -> ( u =/= (/) -> ( w e. z -> ( v = { ( f ` u ) , u } -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) ) ) )
82	81	com4r 88	. . . . . . . . . . . . . . . . . . . . . . 23 |- ( w e. z -> ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( u e. x -> ( u =/= (/) -> ( v = { ( f ` u ) , u } -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) ) ) )
83	82	imp 436	. . . . . . . . . . . . . . . . . . . . . 22 |- ( ( w e. z /\ A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) ) -> ( u e. x -> ( u =/= (/) -> ( v = { ( f ` u ) , u } -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) ) )
84	83	imp4a 600	. . . . . . . . . . . . . . . . . . . . 21 |- ( ( w e. z /\ A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) ) -> ( u e. x -> ( ( u =/= (/) /\ v = { ( f ` u ) , u } ) -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) )
85	84	com3l 83	. . . . . . . . . . . . . . . . . . . 20 |- ( u e. x -> ( ( u =/= (/) /\ v = { ( f ` u ) , u } ) -> ( ( w e. z /\ A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) ) -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) )
86	85	rexlimiv 2867	. . . . . . . . . . . . . . . . . . 19 |- ( E. u e. x ( u =/= (/) /\ v = { ( f ` u ) , u } ) -> ( ( w e. z /\ A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) ) -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) )
87	49, 86	sylbi 200	. . . . . . . . . . . . . . . . . 18 |- ( v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } -> ( ( w e. z /\ A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) ) -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) )
88	87	expd 443	. . . . . . . . . . . . . . . . 17 |- ( v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } -> ( w e. z -> ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) )
89	88	com13 82	. . . . . . . . . . . . . . . 16 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( w e. z -> ( v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } -> ( ( z e. v /\ w e. v ) -> w = ( f ` z ) ) ) ) )
90	89	imp4b 601	. . . . . . . . . . . . . . 15 |- ( ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) /\ w e. z ) -> ( ( v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } /\ ( z e. v /\ w e. v ) ) -> w = ( f ` z ) ) )
91	90	exlimdv 1787	. . . . . . . . . . . . . 14 |- ( ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) /\ w e. z ) -> ( E. v ( v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } /\ ( z e. v /\ w e. v ) ) -> w = ( f ` z ) ) )
92	44, 91	syl5bi 225	. . . . . . . . . . . . 13 |- ( ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) /\ w e. z ) -> ( E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) -> w = ( f ` z ) ) )
93	92	expimpd 614	. . . . . . . . . . . 12 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) -> w = ( f ` z ) ) )
94	93	alrimiv 1781	. . . . . . . . . . 11 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> A. w ( ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) -> w = ( f ` z ) ) )
95		mo2icl 3205	. . . . . . . . . . 11 |- ( A. w ( ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) -> w = ( f ` z ) ) -> E* w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
96	94, 95	syl 17	. . . . . . . . . 10 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> E* w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
97	43, 96	jctird 553	. . . . . . . . 9 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( ( z e. x /\ z =/= (/) ) -> ( E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) /\ E* w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) ) )
98		df-reu 2763	. . . . . . . . . 10 |- ( E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) <-> E! w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
99		eu5 2345	. . . . . . . . . 10 |- ( E! w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) <-> ( E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) /\ E* w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) )
100	98, 99	bitri 257	. . . . . . . . 9 |- ( E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) <-> ( E. w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) /\ E* w ( w e. z /\ E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) )
101	97, 100	syl6ibr 235	. . . . . . . 8 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( ( z e. x /\ z =/= (/) ) -> E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
102	101	expd 443	. . . . . . 7 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> ( z e. x -> ( z =/= (/) -> E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) )
103	2, 102	ralrimi 2800	. . . . . 6 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> A. z e. x ( z =/= (/) -> E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
104		vex 3034	. . . . . . . . . . . 12 |- f e. _V
105	104	rnex 6746	. . . . . . . . . . 11 |- ran f e. _V
106		p0ex 4588	. . . . . . . . . . 11 |- { (/) } e. _V
107	105, 106	unex 6608	. . . . . . . . . 10 |- ( ran f u. { (/) } ) e. _V
108		vex 3034	. . . . . . . . . 10 |- x e. _V
109	107, 108	unex 6608	. . . . . . . . 9 |- ( ( ran f u. { (/) } ) u. x ) e. _V
110	109	pwex 4584	. . . . . . . 8 |- ~P ( ( ran f u. { (/) } ) u. x ) e. _V
111		ssun1 3588	. . . . . . . . . . . . . . 15 |- ( ran f u. { (/) } ) C_ ( ( ran f u. { (/) } ) u. x )
112		fvrn0 5901	. . . . . . . . . . . . . . 15 |- ( f ` u ) e. ( ran f u. { (/) } )
113	111, 112	sselii 3415	. . . . . . . . . . . . . 14 |- ( f ` u ) e. ( ( ran f u. { (/) } ) u. x )
114		elun2 3593	. . . . . . . . . . . . . 14 |- ( u e. x -> u e. ( ( ran f u. { (/) } ) u. x ) )
115		prssi 4119	. . . . . . . . . . . . . 14 |- ( ( ( f ` u ) e. ( ( ran f u. { (/) } ) u. x ) /\ u e. ( ( ran f u. { (/) } ) u. x ) ) -> { ( f ` u ) , u } C_ ( ( ran f u. { (/) } ) u. x ) )
116	113, 114, 115	sylancr 676	. . . . . . . . . . . . 13 |- ( u e. x -> { ( f ` u ) , u } C_ ( ( ran f u. { (/) } ) u. x ) )
117		prex 4642	. . . . . . . . . . . . . 14 |- { ( f ` u ) , u } e. _V
118	117	elpw 3948	. . . . . . . . . . . . 13 |- ( { ( f ` u ) , u } e. ~P ( ( ran f u. { (/) } ) u. x ) <-> { ( f ` u ) , u } C_ ( ( ran f u. { (/) } ) u. x ) )
119	116, 118	sylibr 217	. . . . . . . . . . . 12 |- ( u e. x -> { ( f ` u ) , u } e. ~P ( ( ran f u. { (/) } ) u. x ) )
120		eleq1 2537	. . . . . . . . . . . 12 |- ( g = { ( f ` u ) , u } -> ( g e. ~P ( ( ran f u. { (/) } ) u. x ) <-> { ( f ` u ) , u } e. ~P ( ( ran f u. { (/) } ) u. x ) ) )
121	119, 120	syl5ibrcom 230	. . . . . . . . . . 11 |- ( u e. x -> ( g = { ( f ` u ) , u } -> g e. ~P ( ( ran f u. { (/) } ) u. x ) ) )
122	121	adantld 474	. . . . . . . . . 10 |- ( u e. x -> ( ( u =/= (/) /\ g = { ( f ` u ) , u } ) -> g e. ~P ( ( ran f u. { (/) } ) u. x ) ) )
123	122	rexlimiv 2867	. . . . . . . . 9 |- ( E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) -> g e. ~P ( ( ran f u. { (/) } ) u. x ) )
124	123	abssi 3490	. . . . . . . 8 |- { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } C_ ~P ( ( ran f u. { (/) } ) u. x )
125	110, 124	ssexi 4541	. . . . . . 7 |- { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } e. _V
126		rexeq 2974	. . . . . . . . . 10 |- ( y = { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } -> ( E. v e. y ( z e. v /\ w e. v ) <-> E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
127	126	reubidv 2961	. . . . . . . . 9 |- ( y = { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } -> ( E! w e. z E. v e. y ( z e. v /\ w e. v ) <-> E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) )
128	127	imbi2d 323	. . . . . . . 8 |- ( y = { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } -> ( ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) <-> ( z =/= (/) -> E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) )
129	128	ralbidv 2829	. . . . . . 7 |- ( y = { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } -> ( A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) <-> A. z e. x ( z =/= (/) -> E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) ) )
130	125, 129	spcev 3127	. . . . . 6 |- ( A. z e. x ( z =/= (/) -> E! w e. z E. v e. { g | E. u e. x ( u =/= (/) /\ g = { ( f ` u ) , u } ) } ( z e. v /\ w e. v ) ) -> E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) )
131	103, 130	syl 17	. . . . 5 |- ( A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) )
132	131	exlimiv 1784	. . . 4 |- ( E. f A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) )
133	132	alimi 1692	. . 3 |- ( A. x E. f A. z e. x ( z =/= (/) -> ( f ` z ) e. z ) -> A. x E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) )
134	1, 133	sylbi 200	. 2 |- (CHOICE -> A. x E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) )
135		dfac2a 8578	. 2 |- ( A. x E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) -> CHOICE )
136	134, 135	impbii 192	1 |- (CHOICE <-> A. x E. y A. z e. x ( z =/= (/) -> E! w e. z E. v e. y ( z e. v /\ w e. v ) ) )

Syntax hints:   -. wn 3   -> wi 4   <-> wb 189   /\ wa 376   A.wal 1450   = wceq 1452   E.wex 1671   e. wcel 1904   E!weu 2319   E*wmo 2320   {cab 2457   =/= wne 2641   A.wral 2756   E.wrex 2757   E!wreu 2758   u. cun 3388   C_ wss 3390   (/)c0 3722   ~Pcpw 3942   {csn 3959   {cpr 3961   ran crn 4840   ` cfv 5589  CHOICEwac 8564

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1677  ax-4 1690  ax-5 1766  ax-6 1813  ax-7 1859  ax-8 1906  ax-9 1913  ax-10 1932  ax-11 1937  ax-12 1950  ax-13 2104  ax-ext 2451  ax-sep 4518  ax-nul 4527  ax-pow 4579  ax-pr 4639  ax-un 6602  ax-reg 8125

This theorem depends on definitions:  df-bi 190  df-or 377  df-an 378  df-3an 1009  df-tru 1455  df-ex 1672  df-nf 1676  df-sb 1806  df-eu 2323  df-mo 2324  df-clab 2458  df-cleq 2464  df-clel 2467  df-nfc 2601  df-ne 2643  df-ral 2761  df-rex 2762  df-reu 2763  df-rab 2765  df-v 3033  df-sbc 3256  df-dif 3393  df-un 3395  df-in 3397  df-ss 3404  df-nul 3723  df-if 3873  df-pw 3944  df-sn 3960  df-pr 3962  df-op 3966  df-uni 4191  df-br 4396  df-opab 4455  df-mpt 4456  df-eprel 4750  df-id 4754  df-fr 4798  df-xp 4845  df-rel 4846  df-cnv 4847  df-co 4848  df-dm 4849  df-rn 4850  df-res 4851  df-ima 4852  df-iota 5553  df-fun 5591  df-fn 5592  df-f 5593  df-fv 5597  df-riota 6270  df-ac 8565

This theorem is referenced by:  dfac7  8580