Theorem ssenen 5598

Description: Equinumerosity of equinumerous subsets of a set.

Hypotheses

Ref	Expression
ssenen.1	|- A e. _V
ssenen.2	|- B e. _V

Assertion

Ref	Expression
ssenen	|- (A ~~ B -> {x | (x C_ A /\ x ~~ C)} ~~ {x | (x C_ B /\ x ~~ C)})

Distinct variable groups:   x,A   x,B   x,C

Proof of Theorem ssenen

Step	Hyp	Ref	Expression
1		ssenen.2	. . . 4 |- B e. _V
2	1	bren 5436	. . 3 |- (A ~~ B <-> E.f f:A-1-1-onto->B)
3		ssenen.1	. . . . . . . 8 |- A e. _V
4	3	pwex 3487	. . . . . . 7 |- ~PA e. _V
5	4	inex1 3452	. . . . . 6 |- (~PA i^i {x | x ~~ C}) e. _V
6	5	a1i 8	. . . . 5 |- (f:A-1-1-onto->B -> (~PA i^i {x | x ~~ C}) e. _V)
7		entr 5473	. . . . . . . . 9 |- (((f"y) ~~ y /\ y ~~ C) -> (f"y) ~~ C)
8		visset 2295	. . . . . . . . . . 11 |- y e. _V
9	8	f1imaen 5481	. . . . . . . . . 10 |- ((f:A-1-1->B /\ y C_ A) -> (f"y) ~~ y)
10		f1of1 4634	. . . . . . . . . 10 |- (f:A-1-1-onto->B -> f:A-1-1->B)
11	9, 10	sylan 497	. . . . . . . . 9 |- ((f:A-1-1-onto->B /\ y C_ A) -> (f"y) ~~ y)
12	7, 11	sylan 497	. . . . . . . 8 |- (((f:A-1-1-onto->B /\ y C_ A) /\ y ~~ C) -> (f"y) ~~ C)
13	12	expl 420	. . . . . . 7 |- (f:A-1-1-onto->B -> ((y C_ A /\ y ~~ C) -> (f"y) ~~ C))
14		f1ofo 4643	. . . . . . . 8 |- (f:A-1-1-onto->B -> f:A-onto->B)
15		imassrn 4278	. . . . . . . . 9 |- (f"y) C_ ran f
16		forn 4620	. . . . . . . . . 10 |- (f:A-onto->B -> ran f = B)
17	16	sseq2d 2645	. . . . . . . . 9 |- (f:A-onto->B -> ((f"y) C_ ran f <-> (f"y) C_ B))
18	15, 17	mpbii 210	. . . . . . . 8 |- (f:A-onto->B -> (f"y) C_ B)
19	14, 18	syl 12	. . . . . . 7 |- (f:A-1-1-onto->B -> (f"y) C_ B)
20	13, 19	jctild 662	. . . . . 6 |- (f:A-1-1-onto->B -> ((y C_ A /\ y ~~ C) -> ((f"y) C_ B /\ (f"y) ~~ C)))
21		elin 2786	. . . . . . 7 |- (y e. (~PA i^i {x | x ~~ C}) <-> (y e. ~PA /\ y e. {x | x ~~ C}))
22	8	elpw 3037	. . . . . . . 8 |- (y e. ~PA <-> y C_ A)
23		breq1 3341	. . . . . . . . 9 |- (x = y -> (x ~~ C <-> y ~~ C))
24	8, 23	elab 2403	. . . . . . . 8 |- (y e. {x | x ~~ C} <-> y ~~ C)
25	22, 24	anbi12i 540	. . . . . . 7 |- ((y e. ~PA /\ y e. {x | x ~~ C}) <-> (y C_ A /\ y ~~ C))
26	21, 25	bitri 190	. . . . . 6 |- (y e. (~PA i^i {x | x ~~ C}) <-> (y C_ A /\ y ~~ C))
27		elin 2786	. . . . . . 7 |- ((f"y) e. (~PB i^i {x | x ~~ C}) <-> ((f"y) e. ~PB /\ (f"y) e. {x | x ~~ C}))
28		visset 2295	. . . . . . . . . 10 |- f e. _V
29		imaexg 4279	. . . . . . . . . 10 |- (f e. _V -> (f"y) e. _V)
30	28, 29	ax-mp 7	. . . . . . . . 9 |- (f"y) e. _V
31	30	elpw 3037	. . . . . . . 8 |- ((f"y) e. ~PB <-> (f"y) C_ B)
32		breq1 3341	. . . . . . . . 9 |- (x = (f"y) -> (x ~~ C <-> (f"y) ~~ C))
33	30, 32	elab 2403	. . . . . . . 8 |- ((f"y) e. {x | x ~~ C} <-> (f"y) ~~ C)
34	31, 33	anbi12i 540	. . . . . . 7 |- (((f"y) e. ~PB /\ (f"y) e. {x | x ~~ C}) <-> ((f"y) C_ B /\ (f"y) ~~ C))
35	27, 34	bitri 190	. . . . . 6 |- ((f"y) e. (~PB i^i {x | x ~~ C}) <-> ((f"y) C_ B /\ (f"y) ~~ C))
36	20, 26, 35	3imtr4g 612	. . . . 5 |- (f:A-1-1-onto->B -> (y e. (~PA i^i {x | x ~~ C}) -> (f"y) e. (~PB i^i {x | x ~~ C})))
37		f1ocnv 4651	. . . . . . 7 |- (f:A-1-1-onto->B -> `'f:B-1-1-onto->A)
38		entr 5473	. . . . . . . . . 10 |- (((`'f"z) ~~ z /\ z ~~ C) -> (`'f"z) ~~ C)
39		visset 2295	. . . . . . . . . . . 12 |- z e. _V
40	39	f1imaen 5481	. . . . . . . . . . 11 |- ((`'f:B-1-1->A /\ z C_ B) -> (`'f"z) ~~ z)
41		f1of1 4634	. . . . . . . . . . 11 |- (`'f:B-1-1-onto->A -> `'f:B-1-1->A)
42	40, 41	sylan 497	. . . . . . . . . 10 |- ((`'f:B-1-1-onto->A /\ z C_ B) -> (`'f"z) ~~ z)
43	38, 42	sylan 497	. . . . . . . . 9 |- (((`'f:B-1-1-onto->A /\ z C_ B) /\ z ~~ C) -> (`'f"z) ~~ C)
44	43	expl 420	. . . . . . . 8 |- (`'f:B-1-1-onto->A -> ((z C_ B /\ z ~~ C) -> (`'f"z) ~~ C))
45		f1ofo 4643	. . . . . . . . 9 |- (`'f:B-1-1-onto->A -> `'f:B-onto->A)
46		imassrn 4278	. . . . . . . . . 10 |- (`'f"z) C_ ran `' f
47		forn 4620	. . . . . . . . . . 11 |- (`'f:B-onto->A -> ran `' f = A)
48	47	sseq2d 2645	. . . . . . . . . 10 |- (`'f:B-onto->A -> ((`'f"z) C_ ran `' f <-> (`'f"z) C_ A))
49	46, 48	mpbii 210	. . . . . . . . 9 |- (`'f:B-onto->A -> (`'f"z) C_ A)
50	45, 49	syl 12	. . . . . . . 8 |- (`'f:B-1-1-onto->A -> (`'f"z) C_ A)
51	44, 50	jctild 662	. . . . . . 7 |- (`'f:B-1-1-onto->A -> ((z C_ B /\ z ~~ C) -> ((`'f"z) C_ A /\ (`'f"z) ~~ C)))
52	37, 51	syl 12	. . . . . 6 |- (f:A-1-1-onto->B -> ((z C_ B /\ z ~~ C) -> ((`'f"z) C_ A /\ (`'f"z) ~~ C)))
53		elin 2786	. . . . . . 7 |- (z e. (~PB i^i {x | x ~~ C}) <-> (z e. ~PB /\ z e. {x | x ~~ C}))
54	39	elpw 3037	. . . . . . . 8 |- (z e. ~PB <-> z C_ B)
55		breq1 3341	. . . . . . . . 9 |- (x = z -> (x ~~ C <-> z ~~ C))
56	39, 55	elab 2403	. . . . . . . 8 |- (z e. {x | x ~~ C} <-> z ~~ C)
57	54, 56	anbi12i 540	. . . . . . 7 |- ((z e. ~PB /\ z e. {x | x ~~ C}) <-> (z C_ B /\ z ~~ C))
58	53, 57	bitri 190	. . . . . 6 |- (z e. (~PB i^i {x | x ~~ C}) <-> (z C_ B /\ z ~~ C))
59		elin 2786	. . . . . . 7 |- ((`'f"z) e. (~PA i^i {x | x ~~ C}) <-> ((`'f"z) e. ~PA /\ (`'f"z) e. {x | x ~~ C}))
60	28	cnvex 4425	. . . . . . . . . 10 |- `'f e. _V
61		imaexg 4279	. . . . . . . . . 10 |- (`'f e. _V -> (`'f"z) e. _V)
62	60, 61	ax-mp 7	. . . . . . . . 9 |- (`'f"z) e. _V
63	62	elpw 3037	. . . . . . . 8 |- ((`'f"z) e. ~PA <-> (`'f"z) C_ A)
64		breq1 3341	. . . . . . . . 9 |- (x = (`'f"z) -> (x ~~ C <-> (`'f"z) ~~ C))
65	62, 64	elab 2403	. . . . . . . 8 |- ((`'f"z) e. {x | x ~~ C} <-> (`'f"z) ~~ C)
66	63, 65	anbi12i 540	. . . . . . 7 |- (((`'f"z) e. ~PA /\ (`'f"z) e. {x | x ~~ C}) <-> ((`'f"z) C_ A /\ (`'f"z) ~~ C))
67	59, 66	bitri 190	. . . . . 6 |- ((`'f"z) e. (~PA i^i {x | x ~~ C}) <-> ((`'f"z) C_ A /\ (`'f"z) ~~ C))
68	52, 58, 67	3imtr4g 612	. . . . 5 |- (f:A-1-1-onto->B -> (z e. (~PB i^i {x | x ~~ C}) -> (`'f"z) e. (~PA i^i {x | x ~~ C})))
69		imaeq2 4260	. . . . . . . . . . . 12 |- (y = (`'f"z) -> (f"y) = (f"(`'f"z)))
70		f1orel 4638	. . . . . . . . . . . . . . . 16 |- (f:A-1-1-onto->B -> Rel f)
71		dfrel2 4358	. . . . . . . . . . . . . . . 16 |- (Rel f <-> `'`'f = f)
72	70, 71	sylib 215	. . . . . . . . . . . . . . 15 |- (f:A-1-1-onto->B -> `'`'f = f)
73	72	imaeq1d 4263	. . . . . . . . . . . . . 14 |- (f:A-1-1-onto->B -> (`'`'f"(`'f"z)) = (f"(`'f"z)))
74	73	adantr 425	. . . . . . . . . . . . 13 |- ((f:A-1-1-onto->B /\ z C_ B) -> (`'`'f"(`'f"z)) = (f"(`'f"z)))
75		f1imacnv 4656	. . . . . . . . . . . . . 14 |- ((`'f:B-1-1->A /\ z C_ B) -> (`'`'f"(`'f"z)) = z)
76	37, 41	syl 12	. . . . . . . . . . . . . 14 |- (f:A-1-1-onto->B -> `'f:B-1-1->A)
77	75, 76	sylan 497	. . . . . . . . . . . . 13 |- ((f:A-1-1-onto->B /\ z C_ B) -> (`'`'f"(`'f"z)) = z)
78	74, 77	eqtr3d 1927	. . . . . . . . . . . 12 |- ((f:A-1-1-onto->B /\ z C_ B) -> (f"(`'f"z)) = z)
79	69, 78	sylan9eqr 1951	. . . . . . . . . . 11 |- (((f:A-1-1-onto->B /\ z C_ B) /\ y = (`'f"z)) -> (f"y) = z)
80	79	eqcomd 1889	. . . . . . . . . 10 |- (((f:A-1-1-onto->B /\ z C_ B) /\ y = (`'f"z)) -> z = (f"y))
81	80	ex 402	. . . . . . . . 9 |- ((f:A-1-1-onto->B /\ z C_ B) -> (y = (`'f"z) -> z = (f"y)))
82		simpl 346	. . . . . . . . . . 11 |- ((z e. ~PB /\ z e. {x | x ~~ C}) -> z e. ~PB)
83	82, 54	sylib 215	. . . . . . . . . 10 |- ((z e. ~PB /\ z e. {x | x ~~ C}) -> z C_ B)
84	53, 83	sylbi 216	. . . . . . . . 9 |- (z e. (~PB i^i {x | x ~~ C}) -> z C_ B)
85	81, 84	sylan2 500	. . . . . . . 8 |- ((f:A-1-1-onto->B /\ z e. (~PB i^i {x | x ~~ C})) -> (y = (`'f"z) -> z = (f"y)))
86	85	adantrl 430	. . . . . . 7 |- ((f:A-1-1-onto->B /\ (y e. (~PA i^i {x | x ~~ C}) /\ z e. (~PB i^i {x | x ~~ C}))) -> (y = (`'f"z) -> z = (f"y)))
87		imaeq2 4260	. . . . . . . . . . . 12 |- (z = (f"y) -> (`'f"z) = (`'f"(f"y)))
88		f1imacnv 4656	. . . . . . . . . . . . 13 |- ((f:A-1-1->B /\ y C_ A) -> (`'f"(f"y)) = y)
89	88, 10	sylan 497	. . . . . . . . . . . 12 |- ((f:A-1-1-onto->B /\ y C_ A) -> (`'f"(f"y)) = y)
90	87, 89	sylan9eqr 1951	. . . . . . . . . . 11 |- (((f:A-1-1-onto->B /\ y C_ A) /\ z = (f"y)) -> (`'f"z) = y)
91	90	eqcomd 1889	. . . . . . . . . 10 |- (((f:A-1-1-onto->B /\ y C_ A) /\ z = (f"y)) -> y = (`'f"z))
92	91	ex 402	. . . . . . . . 9 |- ((f:A-1-1-onto->B /\ y C_ A) -> (z = (f"y) -> y = (`'f"z)))
93		simpl 346	. . . . . . . . . . 11 |- ((y e. ~PA /\ y e. {x | x ~~ C}) -> y e. ~PA)
94	93, 22	sylib 215	. . . . . . . . . 10 |- ((y e. ~PA /\ y e. {x | x ~~ C}) -> y C_ A)
95	21, 94	sylbi 216	. . . . . . . . 9 |- (y e. (~PA i^i {x | x ~~ C}) -> y C_ A)
96	92, 95	sylan2 500	. . . . . . . 8 |- ((f:A-1-1-onto->B /\ y e. (~PA i^i {x | x ~~ C})) -> (z = (f"y) -> y = (`'f"z)))
97	96	adantrr 431	. . . . . . 7 |- ((f:A-1-1-onto->B /\ (y e. (~PA i^i {x | x ~~ C}) /\ z e. (~PB i^i {x | x ~~ C}))) -> (z = (f"y) -> y = (`'f"z)))
98	86, 97	impbid 574	. . . . . 6 |- ((f:A-1-1-onto->B /\ (y e. (~PA i^i {x | x ~~ C}) /\ z e. (~PB i^i {x | x ~~ C}))) -> (y = (`'f"z) <-> z = (f"y)))
99	98	ex 402	. . . . 5 |- (f:A-1-1-onto->B -> ((y e. (~PA i^i {x | x ~~ C}) /\ z e. (~PB i^i {x | x ~~ C})) -> (y = (`'f"z) <-> z = (f"y))))
100	6, 36, 68, 99	en3d 5460	. . . 4 |- (f:A-1-1-onto->B -> (~PA i^i {x | x ~~ C}) ~~ (~PB i^i {x | x ~~ C}))
101	100	19.23aiv 1674	. . 3 |- (E.f f:A-1-1-onto->B -> (~PA i^i {x | x ~~ C}) ~~ (~PB i^i {x | x ~~ C}))
102	2, 101	sylbi 216	. 2 |- (A ~~ B -> (~PA i^i {x | x ~~ C}) ~~ (~PB i^i {x | x ~~ C}))
103		df-pw 3035	. . . 4 |- ~PA = {x | x C_ A}
104	103	ineq1i 2792	. . 3 |- (~PA i^i {x | x ~~ C}) = ({x | x C_ A} i^i {x | x ~~ C})
105		inab 2861	. . 3 |- ({x | x C_ A} i^i {x | x ~~ C}) = {x | (x C_ A /\ x ~~ C)}
106	104, 105	eqtri 1908	. 2 |- (~PA i^i {x | x ~~ C}) = {x | (x C_ A /\ x ~~ C)}
107		df-pw 3035	. . . 4 |- ~PB = {x | x C_ B}
108	107	ineq1i 2792	. . 3 |- (~PB i^i {x | x ~~ C}) = ({x | x C_ B} i^i {x | x ~~ C})
109		inab 2861	. . 3 |- ({x | x C_ B} i^i {x | x ~~ C}) = {x | (x C_ B /\ x ~~ C)}
110	108, 109	eqtri 1908	. 2 |- (~PB i^i {x | x ~~ C}) = {x | (x C_ B /\ x ~~ C)}
111	102, 106, 110	3brtr3g 3368	1 |- (A ~~ B -> {x | (x C_ A /\ x ~~ C)} ~~ {x | (x C_ B /\ x ~~ C)})

Syntax hints:   -> wi 3   <-> wb 163   /\ wa 240   = wceq 1298   e. wcel 1300  E.wex 1326  {cab 1871  _Vcvv 2292   i^i cin 2592   C_ wss 2593  ~Pcpw 3032   class class class wbr 3338  `'ccnv 3985  ran crn 3987  "cima 3989  Rel wrel 3991  -1-1->wf1 3995  -onto->wfo 3996  -1-1-onto->wf1o 3997   ~~ cen 5423

This theorem is referenced by:  infmap2 8850

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 1304  ax-gen 1305  ax-8 1306  ax-9 1307  ax-10 1308  ax-11 1309  ax-12 1310  ax-13 1311  ax-14 1312  ax-17 1317  ax-4 1319  ax-5o 1321  ax-6o 1324  ax-9o 1481  ax-10o 1500  ax-16 1580  ax-11o 1588  ax-ext 1865  ax-rep 3428  ax-sep 3438  ax-nul 3445  ax-pow 3481  ax-pr 3524  ax-un 3790

This theorem depends on definitions:  df-bi 164  df-or 241  df-an 242  df-3an 860  df-ex 1327  df-sb 1536  df-eu 1775  df-mo 1776  df-clab 1872  df-cleq 1877  df-clel 1880  df-ne 2019  df-ral 2109  df-rex 2110  df-v 2294  df-dif 2597  df-un 2600  df-in 2603  df-ss 2605  df-nul 2876  df-pw 3035  df-sn 3049  df-pr 3050  df-op 3053  df-uni 3178  df-br 3339  df-opab 3396  df-id 3586  df-xp 4000  df-rel 4001  df-cnv 4002  df-co 4003  df-dm 4004  df-rn 4005  df-res 4006  df-ima 4007  df-fun 4008  df-fn 4009  df-f 4010  df-f1 4011  df-fo 4012  df-f1o 4013  df-er 5318  df-en 5427

Copyright terms: Public domain