Theorem brdom3 9350

Description: Equivalence to a dominance relation. (Contributed by NM, 27-Mar-2007.)

Hypothesis

Ref	Expression
brdom3.2	|- B e. _V

Assertion

Ref	Expression
brdom3	|- ( A ~<_ B <-> E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )

Distinct variable groups:   x, f, y, A   B, f, x, y

Proof of Theorem brdom3

Step	Hyp	Ref	Expression
1		reldom 7961	. . . . . . . . 9 |- Rel ~<_
2	1	brrelexi 5158	. . . . . . . 8 |- ( A ~<_ B -> A e. _V )
3		0sdomg 8089	. . . . . . . 8 |- ( A e. _V -> ( (/) ~< A <-> A =/= (/) ) )
4	2, 3	syl 17	. . . . . . 7 |- ( A ~<_ B -> ( (/) ~< A <-> A =/= (/) ) )
5		df-ne 2795	. . . . . . 7 |- ( A =/= (/) <-> -. A = (/) )
6	4, 5	syl6bb 276	. . . . . 6 |- ( A ~<_ B -> ( (/) ~< A <-> -. A = (/) ) )
7	6	biimpar 502	. . . . 5 |- ( ( A ~<_ B /\ -. A = (/) ) -> (/) ~< A )
8		fodomr 8111	. . . . . 6 |- ( ( (/) ~< A /\ A ~<_ B ) -> E. f f : B -onto-> A )
9	8	ancoms 469	. . . . 5 |- ( ( A ~<_ B /\ (/) ~< A ) -> E. f f : B -onto-> A )
10	7, 9	syldan 487	. . . 4 |- ( ( A ~<_ B /\ -. A = (/) ) -> E. f f : B -onto-> A )
11		pm5.6 951	. . . 4 |- ( ( ( A ~<_ B /\ -. A = (/) ) -> E. f f : B -onto-> A ) <-> ( A ~<_ B -> ( A = (/) \/ E. f f : B -onto-> A ) ) )
12	10, 11	mpbi 220	. . 3 |- ( A ~<_ B -> ( A = (/) \/ E. f f : B -onto-> A ) )
13		br0 4701	. . . . . . . 8 |- -. x (/) y
14	13	nex 1731	. . . . . . 7 |- -. E. y x (/) y
15		exmo 2495	. . . . . . 7 |- ( E. y x (/) y \/ E* y x (/) y )
16	14, 15	mtpor 1695	. . . . . 6 |- E* y x (/) y
17	16	ax-gen 1722	. . . . 5 |- A. x E* y x (/) y
18		rzal 4073	. . . . 5 |- ( A = (/) -> A. x e. A E. y e. B y (/) x )
19		0ex 4790	. . . . . 6 |- (/) e. _V
20		breq 4655	. . . . . . . . 9 |- ( f = (/) -> ( x f y <-> x (/) y ) )
21	20	mobidv 2491	. . . . . . . 8 |- ( f = (/) -> ( E* y x f y <-> E* y x (/) y ) )
22	21	albidv 1849	. . . . . . 7 |- ( f = (/) -> ( A. x E* y x f y <-> A. x E* y x (/) y ) )
23		breq 4655	. . . . . . . . 9 |- ( f = (/) -> ( y f x <-> y (/) x ) )
24	23	rexbidv 3052	. . . . . . . 8 |- ( f = (/) -> ( E. y e. B y f x <-> E. y e. B y (/) x ) )
25	24	ralbidv 2986	. . . . . . 7 |- ( f = (/) -> ( A. x e. A E. y e. B y f x <-> A. x e. A E. y e. B y (/) x ) )
26	22, 25	anbi12d 747	. . . . . 6 |- ( f = (/) -> ( ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) <-> ( A. x E* y x (/) y /\ A. x e. A E. y e. B y (/) x ) ) )
27	19, 26	spcev 3300	. . . . 5 |- ( ( A. x E* y x (/) y /\ A. x e. A E. y e. B y (/) x ) -> E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )
28	17, 18, 27	sylancr 695	. . . 4 |- ( A = (/) -> E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )
29		fofun 6116	. . . . . . 7 |- ( f : B -onto-> A -> Fun f )
30		dffun6 5903	. . . . . . . 8 |- ( Fun f <-> ( Rel f /\ A. x E* y x f y ) )
31	30	simprbi 480	. . . . . . 7 |- ( Fun f -> A. x E* y x f y )
32	29, 31	syl 17	. . . . . 6 |- ( f : B -onto-> A -> A. x E* y x f y )
33		dffo4 6375	. . . . . . 7 |- ( f : B -onto-> A <-> ( f : B --> A /\ A. x e. A E. y e. B y f x ) )
34	33	simprbi 480	. . . . . 6 |- ( f : B -onto-> A -> A. x e. A E. y e. B y f x )
35	32, 34	jca 554	. . . . 5 |- ( f : B -onto-> A -> ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )
36	35	eximi 1762	. . . 4 |- ( E. f f : B -onto-> A -> E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )
37	28, 36	jaoi 394	. . 3 |- ( ( A = (/) \/ E. f f : B -onto-> A ) -> E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )
38	12, 37	syl 17	. 2 |- ( A ~<_ B -> E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )
39		inss1 3833	. . . . . . . . . . 11 |- ( f i^i ( B X. A ) ) C_ f
40	39	ssbri 4697	. . . . . . . . . 10 |- ( x ( f i^i ( B X. A ) ) y -> x f y )
41	40	moimi 2520	. . . . . . . . 9 |- ( E* y x f y -> E* y x ( f i^i ( B X. A ) ) y )
42	41	alimi 1739	. . . . . . . 8 |- ( A. x E* y x f y -> A. x E* y x ( f i^i ( B X. A ) ) y )
43		relxp 5227	. . . . . . . . . 10 |- Rel ( B X. A )
44		relin2 5237	. . . . . . . . . 10 |- ( Rel ( B X. A ) -> Rel ( f i^i ( B X. A ) ) )
45	43, 44	ax-mp 5	. . . . . . . . 9 |- Rel ( f i^i ( B X. A ) )
46		dffun6 5903	. . . . . . . . 9 |- ( Fun ( f i^i ( B X. A ) ) <-> ( Rel ( f i^i ( B X. A ) ) /\ A. x E* y x ( f i^i ( B X. A ) ) y ) )
47	45, 46	mpbiran 953	. . . . . . . 8 |- ( Fun ( f i^i ( B X. A ) ) <-> A. x E* y x ( f i^i ( B X. A ) ) y )
48	42, 47	sylibr 224	. . . . . . 7 |- ( A. x E* y x f y -> Fun ( f i^i ( B X. A ) ) )
49		funfn 5918	. . . . . . 7 |- ( Fun ( f i^i ( B X. A ) ) <-> ( f i^i ( B X. A ) ) Fn dom ( f i^i ( B X. A ) ) )
50	48, 49	sylib 208	. . . . . 6 |- ( A. x E* y x f y -> ( f i^i ( B X. A ) ) Fn dom ( f i^i ( B X. A ) ) )
51		rninxp 5573	. . . . . . 7 |- ( ran ( f i^i ( B X. A ) ) = A <-> A. x e. A E. y e. B y f x )
52	51	biimpri 218	. . . . . 6 |- ( A. x e. A E. y e. B y f x -> ran ( f i^i ( B X. A ) ) = A )
53	50, 52	anim12i 590	. . . . 5 |- ( ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) -> ( ( f i^i ( B X. A ) ) Fn dom ( f i^i ( B X. A ) ) /\ ran ( f i^i ( B X. A ) ) = A ) )
54		df-fo 5894	. . . . 5 |- ( ( f i^i ( B X. A ) ) : dom ( f i^i ( B X. A ) ) -onto-> A <-> ( ( f i^i ( B X. A ) ) Fn dom ( f i^i ( B X. A ) ) /\ ran ( f i^i ( B X. A ) ) = A ) )
55	53, 54	sylibr 224	. . . 4 |- ( ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) -> ( f i^i ( B X. A ) ) : dom ( f i^i ( B X. A ) ) -onto-> A )
56		vex 3203	. . . . . . 7 |- f e. _V
57	56	inex1 4799	. . . . . 6 |- ( f i^i ( B X. A ) ) e. _V
58	57	dmex 7099	. . . . 5 |- dom ( f i^i ( B X. A ) ) e. _V
59	58	fodom 9344	. . . 4 |- ( ( f i^i ( B X. A ) ) : dom ( f i^i ( B X. A ) ) -onto-> A -> A ~<_ dom ( f i^i ( B X. A ) ) )
60		brdom3.2	. . . . . 6 |- B e. _V
61		inss2 3834	. . . . . . . 8 |- ( f i^i ( B X. A ) ) C_ ( B X. A )
62		dmss 5323	. . . . . . . 8 |- ( ( f i^i ( B X. A ) ) C_ ( B X. A ) -> dom ( f i^i ( B X. A ) ) C_ dom ( B X. A ) )
63	61, 62	ax-mp 5	. . . . . . 7 |- dom ( f i^i ( B X. A ) ) C_ dom ( B X. A )
64		dmxpss 5565	. . . . . . 7 |- dom ( B X. A ) C_ B
65	63, 64	sstri 3612	. . . . . 6 |- dom ( f i^i ( B X. A ) ) C_ B
66		ssdomg 8001	. . . . . 6 |- ( B e. _V -> ( dom ( f i^i ( B X. A ) ) C_ B -> dom ( f i^i ( B X. A ) ) ~<_ B ) )
67	60, 65, 66	mp2 9	. . . . 5 |- dom ( f i^i ( B X. A ) ) ~<_ B
68		domtr 8009	. . . . 5 |- ( ( A ~<_ dom ( f i^i ( B X. A ) ) /\ dom ( f i^i ( B X. A ) ) ~<_ B ) -> A ~<_ B )
69	67, 68	mpan2 707	. . . 4 |- ( A ~<_ dom ( f i^i ( B X. A ) ) -> A ~<_ B )
70	55, 59, 69	3syl 18	. . 3 |- ( ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) -> A ~<_ B )
71	70	exlimiv 1858	. 2 |- ( E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) -> A ~<_ B )
72	38, 71	impbii 199	1 |- ( A ~<_ B <-> E. f ( A. x E* y x f y /\ A. x e. A E. y e. B y f x ) )

Syntax hints:   -. wn 3   -> wi 4   <-> wb 196   \/ wo 383   /\ wa 384   A.wal 1481   = wceq 1483   E.wex 1704   e. wcel 1990   E*wmo 2471   =/= wne 2794   A.wral 2912   E.wrex 2913   _Vcvv 3200   i^i cin 3573   C_ wss 3574   (/)c0 3915   class class class wbr 4653   X. cxp 5112   dom cdm 5114   ran crn 5115   Rel wrel 5119   Fun wfun 5882   Fn wfn 5883   -->wf 5884   -onto->wfo 5886   ~<_ cdom 7953   ~< csdm 7954

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1722  ax-4 1737  ax-5 1839  ax-6 1888  ax-7 1935  ax-8 1992  ax-9 1999  ax-10 2019  ax-11 2034  ax-12 2047  ax-13 2246  ax-ext 2602  ax-rep 4771  ax-sep 4781  ax-nul 4789  ax-pow 4843  ax-pr 4906  ax-un 6949  ax-ac2 9285

This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1038  df-3an 1039  df-tru 1486  df-ex 1705  df-nf 1710  df-sb 1881  df-eu 2474  df-mo 2475  df-clab 2609  df-cleq 2615  df-clel 2618  df-nfc 2753  df-ne 2795  df-ral 2917  df-rex 2918  df-reu 2919  df-rmo 2920  df-rab 2921  df-v 3202  df-sbc 3436  df-csb 3534  df-dif 3577  df-un 3579  df-in 3581  df-ss 3588  df-pss 3590  df-nul 3916  df-if 4087  df-pw 4160  df-sn 4178  df-pr 4180  df-tp 4182  df-op 4184  df-uni 4437  df-int 4476  df-iun 4522  df-br 4654  df-opab 4713  df-mpt 4730  df-tr 4753  df-id 5024  df-eprel 5029  df-po 5035  df-so 5036  df-fr 5073  df-se 5074  df-we 5075  df-xp 5120  df-rel 5121  df-cnv 5122  df-co 5123  df-dm 5124  df-rn 5125  df-res 5126  df-ima 5127  df-pred 5680  df-ord 5726  df-on 5727  df-suc 5729  df-iota 5851  df-fun 5890  df-fn 5891  df-f 5892  df-f1 5893  df-fo 5894  df-f1o 5895  df-fv 5896  df-isom 5897  df-riota 6611  df-ov 6653  df-oprab 6654  df-mpt2 6655  df-1st 7168  df-2nd 7169  df-wrecs 7407  df-recs 7468  df-er 7742  df-map 7859  df-en 7956  df-dom 7957  df-sdom 7958  df-card 8765  df-acn 8768  df-ac 8939

This theorem is referenced by:  brdom5  9351  brdom4  9352