Theorem mapen 7099

Description: Two set exponentiations are equinumerous when their bases and exponents are equinumerous. Theorem 6H(c) of [Enderton] p. 139. (Contributed by NM, 16-Dec-2003.) (Proof shortened by Mario Carneiro, 26-Apr-2015.)

Assertion

Ref	Expression
mapen	|- ( ( A ~~ B /\ C ~~ D ) -> ( A ^m C ) ~~ ( B ^m D ) )

Proof of Theorem mapen

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

Step	Hyp	Ref	Expression
1		bren 6983	. 2 |- ( A ~~ B <-> E. f f : A -1-1-onto-> B )
2		bren 6983	. 2 |- ( C ~~ D <-> E. g g : C -1-1-onto-> D )
3		eeanv 1986	. . 3 |- ( E. f E. g ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) <-> ( E. f f : A -1-1-onto-> B /\ E. g g : C -1-1-onto-> D ) )
4		fnmap 6889	. . . . . 6 |- ^m Fn ( _V X. _V )
5		f1odm 5618	. . . . . . . 8 |- ( f : A -1-1-onto-> B -> dom f = A )
6	5	adantr 276	. . . . . . 7 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> dom f = A )
7		vex 2816	. . . . . . . 8 |- f e. _V
8	7	dmex 5024	. . . . . . 7 |- dom f e. _V
9	6, 8	eqeltrrdi 2324	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> A e. _V )
10		f1odm 5618	. . . . . . . 8 |- ( g : C -1-1-onto-> D -> dom g = C )
11	10	adantl 277	. . . . . . 7 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> dom g = C )
12		vex 2816	. . . . . . . 8 |- g e. _V
13	12	dmex 5024	. . . . . . 7 |- dom g e. _V
14	11, 13	eqeltrrdi 2324	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> C e. _V )
15		fnovex 6083	. . . . . 6 |- ( ( ^m Fn ( _V X. _V ) /\ A e. _V /\ C e. _V ) -> ( A ^m C ) e. _V )
16	4, 9, 14, 15	mp3an2i 1379	. . . . 5 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( A ^m C ) e. _V )
17		f1ofo 5621	. . . . . . . . 9 |- ( f : A -1-1-onto-> B -> f : A -onto-> B )
18	17	adantr 276	. . . . . . . 8 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> f : A -onto-> B )
19		forn 5593	. . . . . . . 8 |- ( f : A -onto-> B -> ran f = B )
20	18, 19	syl 14	. . . . . . 7 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ran f = B )
21	7	rnex 5025	. . . . . . 7 |- ran f e. _V
22	20, 21	eqeltrrdi 2324	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> B e. _V )
23		f1ofo 5621	. . . . . . . . 9 |- ( g : C -1-1-onto-> D -> g : C -onto-> D )
24	23	adantl 277	. . . . . . . 8 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> g : C -onto-> D )
25		forn 5593	. . . . . . . 8 |- ( g : C -onto-> D -> ran g = D )
26	24, 25	syl 14	. . . . . . 7 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ran g = D )
27	12	rnex 5025	. . . . . . 7 |- ran g e. _V
28	26, 27	eqeltrrdi 2324	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> D e. _V )
29		fnovex 6083	. . . . . 6 |- ( ( ^m Fn ( _V X. _V ) /\ B e. _V /\ D e. _V ) -> ( B ^m D ) e. _V )
30	4, 22, 28, 29	mp3an2i 1379	. . . . 5 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( B ^m D ) e. _V )
31		elmapi 6904	. . . . . . 7 |- ( x e. ( A ^m C ) -> x : C --> A )
32		f1of 5614	. . . . . . . . . . 11 |- ( f : A -1-1-onto-> B -> f : A --> B )
33	32	adantr 276	. . . . . . . . . 10 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> f : A --> B )
34		fco 5527	. . . . . . . . . 10 |- ( ( f : A --> B /\ x : C --> A ) -> ( f o. x ) : C --> B )
35	33, 34	sylan 283	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ x : C --> A ) -> ( f o. x ) : C --> B )
36		f1ocnv 5627	. . . . . . . . . . . 12 |- ( g : C -1-1-onto-> D -> `' g : D -1-1-onto-> C )
37	36	adantl 277	. . . . . . . . . . 11 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> `' g : D -1-1-onto-> C )
38		f1of 5614	. . . . . . . . . . 11 |- ( `' g : D -1-1-onto-> C -> `' g : D --> C )
39	37, 38	syl 14	. . . . . . . . . 10 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> `' g : D --> C )
40	39	adantr 276	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ x : C --> A ) -> `' g : D --> C )
41	35, 40	fcod 5528	. . . . . . . 8 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ x : C --> A ) -> ( ( f o. x ) o. `' g ) : D --> B )
42	41	ex 115	. . . . . . 7 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( x : C --> A -> ( ( f o. x ) o. `' g ) : D --> B ) )
43	31, 42	syl5 32	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( x e. ( A ^m C ) -> ( ( f o. x ) o. `' g ) : D --> B ) )
44	22, 28	elmapd 6896	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( ( ( f o. x ) o. `' g ) e. ( B ^m D ) <-> ( ( f o. x ) o. `' g ) : D --> B ) )
45	43, 44	sylibrd 169	. . . . 5 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( x e. ( A ^m C ) -> ( ( f o. x ) o. `' g ) e. ( B ^m D ) ) )
46		elmapi 6904	. . . . . . 7 |- ( y e. ( B ^m D ) -> y : D --> B )
47		f1ocnv 5627	. . . . . . . . . . 11 |- ( f : A -1-1-onto-> B -> `' f : B -1-1-onto-> A )
48	47	adantr 276	. . . . . . . . . 10 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> `' f : B -1-1-onto-> A )
49		f1of 5614	. . . . . . . . . 10 |- ( `' f : B -1-1-onto-> A -> `' f : B --> A )
50	48, 49	syl 14	. . . . . . . . 9 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> `' f : B --> A )
51		id 19	. . . . . . . . . 10 |- ( y : D --> B -> y : D --> B )
52		f1of 5614	. . . . . . . . . . 11 |- ( g : C -1-1-onto-> D -> g : C --> D )
53	52	adantl 277	. . . . . . . . . 10 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> g : C --> D )
54		fco 5527	. . . . . . . . . 10 |- ( ( y : D --> B /\ g : C --> D ) -> ( y o. g ) : C --> B )
55	51, 53, 54	syl2anr 290	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ y : D --> B ) -> ( y o. g ) : C --> B )
56		fco 5527	. . . . . . . . 9 |- ( ( `' f : B --> A /\ ( y o. g ) : C --> B ) -> ( `' f o. ( y o. g ) ) : C --> A )
57	50, 55, 56	syl2an2r 599	. . . . . . . 8 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ y : D --> B ) -> ( `' f o. ( y o. g ) ) : C --> A )
58	57	ex 115	. . . . . . 7 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( y : D --> B -> ( `' f o. ( y o. g ) ) : C --> A ) )
59	46, 58	syl5 32	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( y e. ( B ^m D ) -> ( `' f o. ( y o. g ) ) : C --> A ) )
60	9, 14	elmapd 6896	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( ( `' f o. ( y o. g ) ) e. ( A ^m C ) <-> ( `' f o. ( y o. g ) ) : C --> A ) )
61	59, 60	sylibrd 169	. . . . 5 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( y e. ( B ^m D ) -> ( `' f o. ( y o. g ) ) e. ( A ^m C ) ) )
62		coass 5281	. . . . . . . . . . 11 |- ( ( f o. `' f ) o. ( y o. g ) ) = ( f o. ( `' f o. ( y o. g ) ) )
63		f1ococnv2 5641	. . . . . . . . . . . . . 14 |- ( f : A -1-1-onto-> B -> ( f o. `' f ) = ( _I |` B ) )
64	63	ad2antrr 488	. . . . . . . . . . . . 13 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( f o. `' f ) = ( _I |` B ) )
65	64	coeq1d 4916	. . . . . . . . . . . 12 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. `' f ) o. ( y o. g ) ) = ( ( _I |` B ) o. ( y o. g ) ) )
66	55	adantrl 478	. . . . . . . . . . . . 13 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( y o. g ) : C --> B )
67		fcoi2 5548	. . . . . . . . . . . . 13 |- ( ( y o. g ) : C --> B -> ( ( _I |` B ) o. ( y o. g ) ) = ( y o. g ) )
68	66, 67	syl 14	. . . . . . . . . . . 12 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( _I |` B ) o. ( y o. g ) ) = ( y o. g ) )
69	65, 68	eqtrd 2265	. . . . . . . . . . 11 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. `' f ) o. ( y o. g ) ) = ( y o. g ) )
70	62, 69	eqtr3id 2279	. . . . . . . . . 10 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( f o. ( `' f o. ( y o. g ) ) ) = ( y o. g ) )
71	70	eqeq2d 2244	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) = ( f o. ( `' f o. ( y o. g ) ) ) <-> ( f o. x ) = ( y o. g ) ) )
72		coass 5281	. . . . . . . . . . . 12 |- ( ( ( f o. x ) o. `' g ) o. g ) = ( ( f o. x ) o. ( `' g o. g ) )
73		f1ococnv1 5643	. . . . . . . . . . . . . . 15 |- ( g : C -1-1-onto-> D -> ( `' g o. g ) = ( _I |` C ) )
74	73	ad2antlr 489	. . . . . . . . . . . . . 14 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( `' g o. g ) = ( _I |` C ) )
75	74	coeq2d 4917	. . . . . . . . . . . . 13 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) o. ( `' g o. g ) ) = ( ( f o. x ) o. ( _I |` C ) ) )
76	35	adantrr 479	. . . . . . . . . . . . . 14 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( f o. x ) : C --> B )
77		fcoi1 5547	. . . . . . . . . . . . . 14 |- ( ( f o. x ) : C --> B -> ( ( f o. x ) o. ( _I |` C ) ) = ( f o. x ) )
78	76, 77	syl 14	. . . . . . . . . . . . 13 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) o. ( _I |` C ) ) = ( f o. x ) )
79	75, 78	eqtrd 2265	. . . . . . . . . . . 12 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) o. ( `' g o. g ) ) = ( f o. x ) )
80	72, 79	eqtrid 2277	. . . . . . . . . . 11 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( ( f o. x ) o. `' g ) o. g ) = ( f o. x ) )
81	80	eqeq2d 2244	. . . . . . . . . 10 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( y o. g ) = ( ( ( f o. x ) o. `' g ) o. g ) <-> ( y o. g ) = ( f o. x ) ) )
82		eqcom 2234	. . . . . . . . . 10 |- ( ( y o. g ) = ( f o. x ) <-> ( f o. x ) = ( y o. g ) )
83	81, 82	bitrdi 196	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( y o. g ) = ( ( ( f o. x ) o. `' g ) o. g ) <-> ( f o. x ) = ( y o. g ) ) )
84	71, 83	bitr4d 191	. . . . . . . 8 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) = ( f o. ( `' f o. ( y o. g ) ) ) <-> ( y o. g ) = ( ( ( f o. x ) o. `' g ) o. g ) ) )
85		f1of1 5613	. . . . . . . . . 10 |- ( f : A -1-1-onto-> B -> f : A -1-1-> B )
86	85	ad2antrr 488	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> f : A -1-1-> B )
87		simprl 531	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> x : C --> A )
88	57	adantrl 478	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( `' f o. ( y o. g ) ) : C --> A )
89		cocan1 5960	. . . . . . . . 9 |- ( ( f : A -1-1-> B /\ x : C --> A /\ ( `' f o. ( y o. g ) ) : C --> A ) -> ( ( f o. x ) = ( f o. ( `' f o. ( y o. g ) ) ) <-> x = ( `' f o. ( y o. g ) ) ) )
90	86, 87, 88, 89	syl3anc 1274	. . . . . . . 8 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) = ( f o. ( `' f o. ( y o. g ) ) ) <-> x = ( `' f o. ( y o. g ) ) ) )
91	24	adantr 276	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> g : C -onto-> D )
92		ffn 5508	. . . . . . . . . 10 |- ( y : D --> B -> y Fn D )
93	92	ad2antll 491	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> y Fn D )
94	41	adantrr 479	. . . . . . . . . 10 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) o. `' g ) : D --> B )
95	94	ffnd 5509	. . . . . . . . 9 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( f o. x ) o. `' g ) Fn D )
96		cocan2 5961	. . . . . . . . 9 |- ( ( g : C -onto-> D /\ y Fn D /\ ( ( f o. x ) o. `' g ) Fn D ) -> ( ( y o. g ) = ( ( ( f o. x ) o. `' g ) o. g ) <-> y = ( ( f o. x ) o. `' g ) ) )
97	91, 93, 95, 96	syl3anc 1274	. . . . . . . 8 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( ( y o. g ) = ( ( ( f o. x ) o. `' g ) o. g ) <-> y = ( ( f o. x ) o. `' g ) ) )
98	84, 90, 97	3bitr3d 218	. . . . . . 7 |- ( ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) /\ ( x : C --> A /\ y : D --> B ) ) -> ( x = ( `' f o. ( y o. g ) ) <-> y = ( ( f o. x ) o. `' g ) ) )
99	98	ex 115	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( ( x : C --> A /\ y : D --> B ) -> ( x = ( `' f o. ( y o. g ) ) <-> y = ( ( f o. x ) o. `' g ) ) ) )
100	31, 46, 99	syl2ani 408	. . . . 5 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( ( x e. ( A ^m C ) /\ y e. ( B ^m D ) ) -> ( x = ( `' f o. ( y o. g ) ) <-> y = ( ( f o. x ) o. `' g ) ) ) )
101	16, 30, 45, 61, 100	en3d 7008	. . . 4 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( A ^m C ) ~~ ( B ^m D ) )
102	101	exlimivv 1946	. . 3 |- ( E. f E. g ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( A ^m C ) ~~ ( B ^m D ) )
103	3, 102	sylbir 135	. 2 |- ( ( E. f f : A -1-1-onto-> B /\ E. g g : C -1-1-onto-> D ) -> ( A ^m C ) ~~ ( B ^m D ) )
104	1, 2, 103	syl2anb 291	1 |- ( ( A ~~ B /\ C ~~ D ) -> ( A ^m C ) ~~ ( B ^m D ) )

Syntax hints:   -> wi 4   /\ wa 104   <-> wb 105   = wceq 1398   E.wex 1541   e. wcel 2203   _Vcvv 2813   class class class wbr 4109   _I cid 4409   X. cxp 4747   `'ccnv 4748   dom cdm 4749   ran crn 4750   |` cres 4751   o. ccom 4753   Fn wfn 5347   -->wf 5348   -1-1->wf1 5349   -onto->wfo 5350   -1-1-onto->wf1o 5351  (class class class)co 6050   ^m cmap 6882   ~~ cen 6973

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 619  ax-in2 620  ax-io 717  ax-5 1496  ax-7 1497  ax-gen 1498  ax-ie1 1542  ax-ie2 1543  ax-8 1553  ax-10 1554  ax-11 1555  ax-i12 1556  ax-bndl 1558  ax-4 1559  ax-17 1575  ax-i9 1579  ax-ial 1583  ax-i5r 1584  ax-13 2205  ax-14 2206  ax-ext 2214  ax-sep 4228  ax-pow 4287  ax-pr 4322  ax-un 4554  ax-setind 4659

This theorem depends on definitions:  df-bi 117  df-3an 1007  df-tru 1401  df-fal 1404  df-nf 1510  df-sb 1812  df-eu 2083  df-mo 2084  df-clab 2219  df-cleq 2225  df-clel 2228  df-nfc 2373  df-ne 2413  df-ral 2525  df-rex 2526  df-rab 2529  df-v 2815  df-sbc 3043  df-csb 3139  df-dif 3213  df-un 3215  df-in 3217  df-ss 3224  df-pw 3671  df-sn 3695  df-pr 3696  df-op 3698  df-uni 3915  df-iun 3993  df-br 4110  df-opab 4172  df-mpt 4173  df-id 4414  df-xp 4755  df-rel 4756  df-cnv 4757  df-co 4758  df-dm 4759  df-rn 4760  df-res 4761  df-ima 4762  df-iota 5312  df-fun 5354  df-fn 5355  df-f 5356  df-f1 5357  df-fo 5358  df-f1o 5359  df-fv 5360  df-ov 6053  df-oprab 6054  df-mpo 6055  df-1st 6334  df-2nd 6335  df-map 6884  df-en 6976

This theorem is referenced by:  mapdom1g  7100