Theorem mapen 7146

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 7030	. 2 |- ( A ~~ B <-> E. f f : A -1-1-onto-> B )
2		bren 7030	. 2 |- ( C ~~ D <-> E. g g : C -1-1-onto-> D )
3		eeanv 1992	. . 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 6929	. . . . . 6 |- ^m Fn ( _V X. _V )
5		f1odm 5643	. . . . . . . 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 2824	. . . . . . . 8 |- f e. _V
8	7	dmex 5049	. . . . . . 7 |- dom f e. _V
9	6, 8	eqeltrrdi 2330	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> A e. _V )
10		f1odm 5643	. . . . . . . 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 2824	. . . . . . . 8 |- g e. _V
13	12	dmex 5049	. . . . . . 7 |- dom g e. _V
14	11, 13	eqeltrrdi 2330	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> C e. _V )
15		fnovex 6118	. . . . . 6 |- ( ( ^m Fn ( _V X. _V ) /\ A e. _V /\ C e. _V ) -> ( A ^m C ) e. _V )
16	4, 9, 14, 15	mp3an2i 1383	. . . . 5 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( A ^m C ) e. _V )
17		f1ofo 5646	. . . . . . . . 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 5618	. . . . . . . 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 5050	. . . . . . 7 |- ran f e. _V
22	20, 21	eqeltrrdi 2330	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> B e. _V )
23		f1ofo 5646	. . . . . . . . 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 5618	. . . . . . . 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 5050	. . . . . . 7 |- ran g e. _V
28	26, 27	eqeltrrdi 2330	. . . . . 6 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> D e. _V )
29		fnovex 6118	. . . . . 6 |- ( ( ^m Fn ( _V X. _V ) /\ B e. _V /\ D e. _V ) -> ( B ^m D ) e. _V )
30	4, 22, 28, 29	mp3an2i 1383	. . . . 5 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( B ^m D ) e. _V )
31		elmapi 6944	. . . . . . 7 |- ( x e. ( A ^m C ) -> x : C --> A )
32		f1of 5639	. . . . . . . . . . 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 5552	. . . . . . . . . 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 5652	. . . . . . . . . . . 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 5639	. . . . . . . . . . 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 5553	. . . . . . . 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 6936	. . . . . 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 6944	. . . . . . 7 |- ( y e. ( B ^m D ) -> y : D --> B )
47		f1ocnv 5652	. . . . . . . . . . 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 5639	. . . . . . . . . 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 5639	. . . . . . . . . . 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 5552	. . . . . . . . . 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 5552	. . . . . . . . 9 |- ( ( `' f : B --> A /\ ( y o. g ) : C --> B ) -> ( `' f o. ( y o. g ) ) : C --> A )
57	50, 55, 56	syl2an2r 603	. . . . . . . 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 6936	. . . . . 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 5306	. . . . . . . . . . 11 |- ( ( f o. `' f ) o. ( y o. g ) ) = ( f o. ( `' f o. ( y o. g ) ) )
63		f1ococnv2 5666	. . . . . . . . . . . . . 14 |- ( f : A -1-1-onto-> B -> ( f o. `' f ) = ( _I |` B ) )
64	63	ad2antrr 492	. . . . . . . . . . . . 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 4941	. . . . . . . . . . . 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 482	. . . . . . . . . . . . 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 5573	. . . . . . . . . . . . 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 2271	. . . . . . . . . . 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 2285	. . . . . . . . . 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 2250	. . . . . . . . 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 5306	. . . . . . . . . . . 12 |- ( ( ( f o. x ) o. `' g ) o. g ) = ( ( f o. x ) o. ( `' g o. g ) )
73		f1ococnv1 5668	. . . . . . . . . . . . . . 15 |- ( g : C -1-1-onto-> D -> ( `' g o. g ) = ( _I |` C ) )
74	73	ad2antlr 493	. . . . . . . . . . . . . 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 4942	. . . . . . . . . . . . 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 483	. . . . . . . . . . . . . 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 5572	. . . . . . . . . . . . . 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 2271	. . . . . . . . . . . 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 2283	. . . . . . . . . . 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 2250	. . . . . . . . . 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 2240	. . . . . . . . . 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 5638	. . . . . . . . . 10 |- ( f : A -1-1-onto-> B -> f : A -1-1-> B )
86	85	ad2antrr 492	. . . . . . . . 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 535	. . . . . . . . 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 482	. . . . . . . . 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 5993	. . . . . . . . 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 1278	. . . . . . . 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 5533	. . . . . . . . . 10 |- ( y : D --> B -> y Fn D )
93	92	ad2antll 495	. . . . . . . . 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 483	. . . . . . . . . 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 5534	. . . . . . . . 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 5994	. . . . . . . . 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 1278	. . . . . . . 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 412	. . . . 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 7055	. . . 4 |- ( ( f : A -1-1-onto-> B /\ g : C -1-1-onto-> D ) -> ( A ^m C ) ~~ ( B ^m D ) )
102	101	exlimivv 1952	. . 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 ) )

This proof depends on syntax axioms:   -> wi 4   /\ wa 104   <-> wb 105   = wceq 1402   E.wex 1545   e. wcel 2209   _Vcvv 2821   class class class wbr 4130   _I cid 4433   X. cxp 4772   `'ccnv 4773   dom cdm 4774   ran crn 4775   |` cres 4776   o. ccom 4778   Fn wfn 5372   -->wf 5373   -1-1->wf1 5374   -onto->wfo 5375   -1-1-onto->wf1o 5376  (class class class)co 6085   ^m cmap 6922   ~~ cen 7020

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 623  ax-in2 624  ax-io 721  ax-5 1500  ax-7 1501  ax-gen 1502  ax-ie1 1546  ax-ie2 1547  ax-8 1557  ax-10 1558  ax-11 1559  ax-i12 1560  ax-bndl 1562  ax-4 1563  ax-17 1579  ax-i9 1583  ax-ial 1587  ax-i5r 1588  ax-14 2212  ax-ext 2220  ax-sep 4249  ax-pow 4311  ax-pr 4346  ax-un 4578  ax-setind 4684

This proof depends on definitions:  df-bi 117  df-3an 1011  df-tru 1405  df-fal 1408  df-nf 1514  df-sb 1816  df-eu 2089  df-mo 2090  df-clab 2225  df-cleq 2231  df-clel 2234  df-nfc 2381  df-ne 2421  df-ral 2533  df-rex 2534  df-rab 2537  df-v 2823  df-sbc 3052  df-csb 3148  df-dif 3222  df-un 3224  df-in 3226  df-ss 3233  df-pw 3690  df-sn 3715  df-pr 3716  df-op 3718  df-uni 3936  df-iun 4014  df-br 4131  df-opab 4193  df-mpt 4194  df-id 4438  df-xp 4780  df-rel 4781  df-cnv 4782  df-co 4783  df-dm 4784  df-rn 4785  df-res 4786  df-ima 4787  df-iota 5337  df-fun 5379  df-fn 5380  df-f 5381  df-f1 5382  df-fo 5383  df-f1o 5384  df-fv 5385  df-ov 6088  df-oprab 6089  df-mpo 6090  df-1st 6374  df-2nd 6375  df-map 6924  df-en 7023

This theorem is used by:  mapdom1g  7147