Theorem cfcof 8547

Description: If there is a cofinal map from A to B, then they have the same cofinality. This was used as Definition 11.1 of [TakeutiZaring] p. 100, who defines an equivalence relation cof ( A , B ) and defines our cf ( B ) as the minimum B such that cof ( A , B ). (Contributed by Mario Carneiro, 20-Mar-2013.)

Assertion

Ref	Expression
cfcof	|- ( ( A e. On /\ B e. On ) -> ( E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) -> ( cf ` A ) = ( cf ` B ) ) )

Distinct variable groups:   w, f, z, A   B, f, w, z

Proof of Theorem cfcof

Dummy variables c g h k r s t x y v are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		cfcoflem 8545	. . . 4 |- ( ( A e. On /\ B e. On ) -> ( E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) -> ( cf ` A ) C_ ( cf ` B ) ) )
2	1	imp 429	. . 3 |- ( ( ( A e. On /\ B e. On ) /\ E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) ) -> ( cf ` A ) C_ ( cf ` B ) )
3		cff1 8531	. . . . . . 7 |- ( A e. On -> E. g ( g : ( cf ` A ) -1-1-> A /\ A. s e. A E. t e. ( cf ` A ) s C_ ( g ` t ) ) )
4		f1f 5707	. . . . . . . . 9 |- ( g : ( cf ` A ) -1-1-> A -> g : ( cf ` A ) --> A )
5	4	anim1i 568	. . . . . . . 8 |- ( ( g : ( cf ` A ) -1-1-> A /\ A. s e. A E. t e. ( cf ` A ) s C_ ( g ` t ) ) -> ( g : ( cf ` A ) --> A /\ A. s e. A E. t e. ( cf ` A ) s C_ ( g ` t ) ) )
6	5	eximi 1626	. . . . . . 7 |- ( E. g ( g : ( cf ` A ) -1-1-> A /\ A. s e. A E. t e. ( cf ` A ) s C_ ( g ` t ) ) -> E. g ( g : ( cf ` A ) --> A /\ A. s e. A E. t e. ( cf ` A ) s C_ ( g ` t ) ) )
7	3, 6	syl 16	. . . . . 6 |- ( A e. On -> E. g ( g : ( cf ` A ) --> A /\ A. s e. A E. t e. ( cf ` A ) s C_ ( g ` t ) ) )
8		eqid 2451	. . . . . . 7 |- ( y e. ( cf ` A ) |-> |^| { v e. B | ( g ` y ) C_ ( f ` v ) } ) = ( y e. ( cf ` A ) |-> |^| { v e. B | ( g ` y ) C_ ( f ` v ) } )
9	8	coftr 8546	. . . . . 6 |- ( E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) -> ( E. g ( g : ( cf ` A ) --> A /\ A. s e. A E. t e. ( cf ` A ) s C_ ( g ` t ) ) -> E. h ( h : ( cf ` A ) --> B /\ A. r e. B E. t e. ( cf ` A ) r C_ ( h ` t ) ) ) )
10	7, 9	syl5com 30	. . . . 5 |- ( A e. On -> ( E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) -> E. h ( h : ( cf ` A ) --> B /\ A. r e. B E. t e. ( cf ` A ) r C_ ( h ` t ) ) ) )
11		eloni 4830	. . . . . . 7 |- ( B e. On -> Ord B )
12		cfon 8528	. . . . . . 7 |- ( cf ` A ) e. On
13		eqid 2451	. . . . . . . 8 |- { x e. ( cf ` A ) | A. t e. x ( h ` t ) e. ( h ` x ) } = { x e. ( cf ` A ) | A. t e. x ( h ` t ) e. ( h ` x ) }
14		eqid 2451	. . . . . . . 8 |- |^| { c e. ( cf ` A ) | r C_ ( h ` c ) } = |^| { c e. ( cf ` A ) | r C_ ( h ` c ) }
15		eqid 2451	. . . . . . . 8 |- OrdIso ( _E , { x e. ( cf ` A ) | A. t e. x ( h ` t ) e. ( h ` x ) } ) = OrdIso ( _E , { x e. ( cf ` A ) | A. t e. x ( h ` t ) e. ( h ` x ) } )
16	13, 14, 15	cofsmo 8542	. . . . . . 7 |- ( ( Ord B /\ ( cf ` A ) e. On ) -> ( E. h ( h : ( cf ` A ) --> B /\ A. r e. B E. t e. ( cf ` A ) r C_ ( h ` t ) ) -> E. c e. suc ( cf ` A ) E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) ) )
17	11, 12, 16	sylancl 662	. . . . . 6 |- ( B e. On -> ( E. h ( h : ( cf ` A ) --> B /\ A. r e. B E. t e. ( cf ` A ) r C_ ( h ` t ) ) -> E. c e. suc ( cf ` A ) E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) ) )
18		3simpb 986	. . . . . . . . . . . 12 |- ( ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) -> ( k : c --> B /\ A. r e. B E. s e. c r C_ ( k ` s ) ) )
19	18	eximi 1626	. . . . . . . . . . 11 |- ( E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) -> E. k ( k : c --> B /\ A. r e. B E. s e. c r C_ ( k ` s ) ) )
20	12	onsuci 6552	. . . . . . . . . . . . 13 |- suc ( cf ` A ) e. On
21	20	oneli 4927	. . . . . . . . . . . 12 |- ( c e. suc ( cf ` A ) -> c e. On )
22		cfflb 8532	. . . . . . . . . . . 12 |- ( ( B e. On /\ c e. On ) -> ( E. k ( k : c --> B /\ A. r e. B E. s e. c r C_ ( k ` s ) ) -> ( cf ` B ) C_ c ) )
23	21, 22	sylan2 474	. . . . . . . . . . 11 |- ( ( B e. On /\ c e. suc ( cf ` A ) ) -> ( E. k ( k : c --> B /\ A. r e. B E. s e. c r C_ ( k ` s ) ) -> ( cf ` B ) C_ c ) )
24	19, 23	syl5 32	. . . . . . . . . 10 |- ( ( B e. On /\ c e. suc ( cf ` A ) ) -> ( E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) -> ( cf ` B ) C_ c ) )
25	24	imp 429	. . . . . . . . 9 |- ( ( ( B e. On /\ c e. suc ( cf ` A ) ) /\ E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) ) -> ( cf ` B ) C_ c )
26		onsssuc 4907	. . . . . . . . . . . 12 |- ( ( c e. On /\ ( cf ` A ) e. On ) -> ( c C_ ( cf ` A ) <-> c e. suc ( cf ` A ) ) )
27	21, 12, 26	sylancl 662	. . . . . . . . . . 11 |- ( c e. suc ( cf ` A ) -> ( c C_ ( cf ` A ) <-> c e. suc ( cf ` A ) ) )
28	27	ibir 242	. . . . . . . . . 10 |- ( c e. suc ( cf ` A ) -> c C_ ( cf ` A ) )
29	28	ad2antlr 726	. . . . . . . . 9 |- ( ( ( B e. On /\ c e. suc ( cf ` A ) ) /\ E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) ) -> c C_ ( cf ` A ) )
30	25, 29	sstrd 3467	. . . . . . . 8 |- ( ( ( B e. On /\ c e. suc ( cf ` A ) ) /\ E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) ) -> ( cf ` B ) C_ ( cf ` A ) )
31	30	exp31 604	. . . . . . 7 |- ( B e. On -> ( c e. suc ( cf ` A ) -> ( E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) -> ( cf ` B ) C_ ( cf ` A ) ) ) )
32	31	rexlimdv 2939	. . . . . 6 |- ( B e. On -> ( E. c e. suc ( cf ` A ) E. k ( k : c --> B /\ Smo k /\ A. r e. B E. s e. c r C_ ( k ` s ) ) -> ( cf ` B ) C_ ( cf ` A ) ) )
33	17, 32	syld 44	. . . . 5 |- ( B e. On -> ( E. h ( h : ( cf ` A ) --> B /\ A. r e. B E. t e. ( cf ` A ) r C_ ( h ` t ) ) -> ( cf ` B ) C_ ( cf ` A ) ) )
34	10, 33	sylan9 657	. . . 4 |- ( ( A e. On /\ B e. On ) -> ( E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) -> ( cf ` B ) C_ ( cf ` A ) ) )
35	34	imp 429	. . 3 |- ( ( ( A e. On /\ B e. On ) /\ E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) ) -> ( cf ` B ) C_ ( cf ` A ) )
36	2, 35	eqssd 3474	. 2 |- ( ( ( A e. On /\ B e. On ) /\ E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) ) -> ( cf ` A ) = ( cf ` B ) )
37	36	ex 434	1 |- ( ( A e. On /\ B e. On ) -> ( E. f ( f : B --> A /\ Smo f /\ A. z e. A E. w e. B z C_ ( f ` w ) ) -> ( cf ` A ) = ( cf ` B ) ) )

Syntax hints:   -> wi 4   <-> wb 184   /\ wa 369   /\ w3a 965   = wceq 1370   E.wex 1587   e. wcel 1758   A.wral 2795   E.wrex 2796   {crab 2799   C_ wss 3429   |^|cint 4229   |-> cmpt 4451   _E cep 4731   Ord word 4819   Oncon0 4820   suc csuc 4822   -->wf 5515   -1-1->wf1 5516   ` cfv 5519   Smo wsmo 6909  OrdIsocoi 7827   cfccf 8211

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1592  ax-4 1603  ax-5 1671  ax-6 1710  ax-7 1730  ax-8 1760  ax-9 1762  ax-10 1777  ax-11 1782  ax-12 1794  ax-13 1952  ax-ext 2430  ax-rep 4504  ax-sep 4514  ax-nul 4522  ax-pow 4571  ax-pr 4632  ax-un 6475

This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 966  df-3an 967  df-tru 1373  df-ex 1588  df-nf 1591  df-sb 1703  df-eu 2264  df-mo 2265  df-clab 2437  df-cleq 2443  df-clel 2446  df-nfc 2601  df-ne 2646  df-ral 2800  df-rex 2801  df-reu 2802  df-rmo 2803  df-rab 2804  df-v 3073  df-sbc 3288  df-csb 3390  df-dif 3432  df-un 3434  df-in 3436  df-ss 3443  df-pss 3445  df-nul 3739  df-if 3893  df-pw 3963  df-sn 3979  df-pr 3981  df-tp 3983  df-op 3985  df-uni 4193  df-int 4230  df-iun 4274  df-br 4394  df-opab 4452  df-mpt 4453  df-tr 4487  df-eprel 4733  df-id 4737  df-po 4742  df-so 4743  df-fr 4780  df-se 4781  df-we 4782  df-ord 4823  df-on 4824  df-lim 4825  df-suc 4826  df-xp 4947  df-rel 4948  df-cnv 4949  df-co 4950  df-dm 4951  df-rn 4952  df-res 4953  df-ima 4954  df-iota 5482  df-fun 5521  df-fn 5522  df-f 5523  df-f1 5524  df-fo 5525  df-f1o 5526  df-fv 5527  df-isom 5528  df-riota 6154  df-ov 6196  df-oprab 6197  df-mpt2 6198  df-1st 6680  df-2nd 6681  df-smo 6910  df-recs 6935  df-er 7204  df-map 7319  df-en 7414  df-dom 7415  df-sdom 7416  df-oi 7828  df-card 8213  df-cf 8215  df-acn 8216

This theorem is referenced by:  alephsing  8549