Theorem fodomfi 7797

Description: An onto function implies dominance of domain over range, for finite sets. Unlike fodom 8900 for arbitrary sets, this theorem does not require the Axiom of Choice for its proof. (Contributed by NM, 23-Mar-2006.) (Proof shortened by Mario Carneiro, 16-Nov-2014.)

Assertion

Ref	Expression
fodomfi	|- ( ( A e. Fin /\ F : A -onto-> B ) -> B ~<_ A )

Proof of Theorem fodomfi

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

Step	Hyp	Ref	Expression
1		foima 5786	. . 3 |- ( F : A -onto-> B -> ( F " A ) = B )
2	1	adantl 466	. 2 |- ( ( A e. Fin /\ F : A -onto-> B ) -> ( F " A ) = B )
3		fofn 5783	. . . 4 |- ( F : A -onto-> B -> F Fn A )
4		imaeq2 5319	. . . . . . . 8 |- ( x = (/) -> ( F " x ) = ( F " (/) ) )
5		ima0 5338	. . . . . . . 8 |- ( F " (/) ) = (/)
6	4, 5	syl6eq 2498	. . . . . . 7 |- ( x = (/) -> ( F " x ) = (/) )
7		id 22	. . . . . . 7 |- ( x = (/) -> x = (/) )
8	6, 7	breq12d 4446	. . . . . 6 |- ( x = (/) -> ( ( F " x ) ~<_ x <-> (/) ~<_ (/) ) )
9	8	imbi2d 316	. . . . 5 |- ( x = (/) -> ( ( F Fn A -> ( F " x ) ~<_ x ) <-> ( F Fn A -> (/) ~<_ (/) ) ) )
10		imaeq2 5319	. . . . . . 7 |- ( x = y -> ( F " x ) = ( F " y ) )
11		id 22	. . . . . . 7 |- ( x = y -> x = y )
12	10, 11	breq12d 4446	. . . . . 6 |- ( x = y -> ( ( F " x ) ~<_ x <-> ( F " y ) ~<_ y ) )
13	12	imbi2d 316	. . . . 5 |- ( x = y -> ( ( F Fn A -> ( F " x ) ~<_ x ) <-> ( F Fn A -> ( F " y ) ~<_ y ) ) )
14		imaeq2 5319	. . . . . . 7 |- ( x = ( y u. { z } ) -> ( F " x ) = ( F " ( y u. { z } ) ) )
15		id 22	. . . . . . 7 |- ( x = ( y u. { z } ) -> x = ( y u. { z } ) )
16	14, 15	breq12d 4446	. . . . . 6 |- ( x = ( y u. { z } ) -> ( ( F " x ) ~<_ x <-> ( F " ( y u. { z } ) ) ~<_ ( y u. { z } ) ) )
17	16	imbi2d 316	. . . . 5 |- ( x = ( y u. { z } ) -> ( ( F Fn A -> ( F " x ) ~<_ x ) <-> ( F Fn A -> ( F " ( y u. { z } ) ) ~<_ ( y u. { z } ) ) ) )
18		imaeq2 5319	. . . . . . 7 |- ( x = A -> ( F " x ) = ( F " A ) )
19		id 22	. . . . . . 7 |- ( x = A -> x = A )
20	18, 19	breq12d 4446	. . . . . 6 |- ( x = A -> ( ( F " x ) ~<_ x <-> ( F " A ) ~<_ A ) )
21	20	imbi2d 316	. . . . 5 |- ( x = A -> ( ( F Fn A -> ( F " x ) ~<_ x ) <-> ( F Fn A -> ( F " A ) ~<_ A ) ) )
22		0ex 4563	. . . . . . 7 |- (/) e. _V
23	22	0dom 7645	. . . . . 6 |- (/) ~<_ (/)
24	23	a1i 11	. . . . 5 |- ( F Fn A -> (/) ~<_ (/) )
25		fnfun 5664	. . . . . . . . . . . . . . 15 |- ( F Fn A -> Fun F )
26	25	ad2antrl 727	. . . . . . . . . . . . . 14 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> Fun F )
27		funressn 6065	. . . . . . . . . . . . . 14 |- ( Fun F -> ( F |` { z } ) C_ { <. z , ( F ` z ) >. } )
28		rnss 5217	. . . . . . . . . . . . . 14 |- ( ( F |` { z } ) C_ { <. z , ( F ` z ) >. } -> ran ( F |` { z } ) C_ ran { <. z , ( F ` z ) >. } )
29	26, 27, 28	3syl 20	. . . . . . . . . . . . 13 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ran ( F |` { z } ) C_ ran { <. z , ( F ` z ) >. } )
30		df-ima 4998	. . . . . . . . . . . . 13 |- ( F " { z } ) = ran ( F |` { z } )
31		vex 3096	. . . . . . . . . . . . . . 15 |- z e. _V
32	31	rnsnop 5475	. . . . . . . . . . . . . 14 |- ran { <. z , ( F ` z ) >. } = { ( F ` z ) }
33	32	eqcomi 2454	. . . . . . . . . . . . 13 |- { ( F ` z ) } = ran { <. z , ( F ` z ) >. }
34	29, 30, 33	3sstr4g 3527	. . . . . . . . . . . 12 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( F " { z } ) C_ { ( F ` z ) } )
35		snex 4674	. . . . . . . . . . . 12 |- { ( F ` z ) } e. _V
36		ssexg 4579	. . . . . . . . . . . 12 |- ( ( ( F " { z } ) C_ { ( F ` z ) } /\ { ( F ` z ) } e. _V ) -> ( F " { z } ) e. _V )
37	34, 35, 36	sylancl 662	. . . . . . . . . . 11 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( F " { z } ) e. _V )
38		fvi 5911	. . . . . . . . . . 11 |- ( ( F " { z } ) e. _V -> ( _I ` ( F " { z } ) ) = ( F " { z } ) )
39	37, 38	syl 16	. . . . . . . . . 10 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( _I ` ( F " { z } ) ) = ( F " { z } ) )
40	39	uneq2d 3640	. . . . . . . . 9 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( ( F " y ) u. ( _I ` ( F " { z } ) ) ) = ( ( F " y ) u. ( F " { z } ) ) )
41		imaundi 5404	. . . . . . . . 9 |- ( F " ( y u. { z } ) ) = ( ( F " y ) u. ( F " { z } ) )
42	40, 41	syl6eqr 2500	. . . . . . . 8 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( ( F " y ) u. ( _I ` ( F " { z } ) ) ) = ( F " ( y u. { z } ) ) )
43		simprr 756	. . . . . . . . 9 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( F " y ) ~<_ y )
44		ssdomg 7559	. . . . . . . . . . . 12 |- ( { ( F ` z ) } e. _V -> ( ( F " { z } ) C_ { ( F ` z ) } -> ( F " { z } ) ~<_ { ( F ` z ) } ) )
45	35, 34, 44	mpsyl 63	. . . . . . . . . . 11 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( F " { z } ) ~<_ { ( F ` z ) } )
46		fvex 5862	. . . . . . . . . . . . 13 |- ( F ` z ) e. _V
47	46	ensn1 7577	. . . . . . . . . . . 12 |- { ( F ` z ) } ~~ 1o
48	31	ensn1 7577	. . . . . . . . . . . 12 |- { z } ~~ 1o
49	47, 48	entr4i 7570	. . . . . . . . . . 11 |- { ( F ` z ) } ~~ { z }
50		domentr 7572	. . . . . . . . . . 11 |- ( ( ( F " { z } ) ~<_ { ( F ` z ) } /\ { ( F ` z ) } ~~ { z } ) -> ( F " { z } ) ~<_ { z } )
51	45, 49, 50	sylancl 662	. . . . . . . . . 10 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( F " { z } ) ~<_ { z } )
52	39, 51	eqbrtrd 4453	. . . . . . . . 9 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( _I ` ( F " { z } ) ) ~<_ { z } )
53		simplr 754	. . . . . . . . . 10 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> -. z e. y )
54		disjsn 4071	. . . . . . . . . 10 |- ( ( y i^i { z } ) = (/) <-> -. z e. y )
55	53, 54	sylibr 212	. . . . . . . . 9 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( y i^i { z } ) = (/) )
56		undom 7603	. . . . . . . . 9 |- ( ( ( ( F " y ) ~<_ y /\ ( _I ` ( F " { z } ) ) ~<_ { z } ) /\ ( y i^i { z } ) = (/) ) -> ( ( F " y ) u. ( _I ` ( F " { z } ) ) ) ~<_ ( y u. { z } ) )
57	43, 52, 55, 56	syl21anc 1226	. . . . . . . 8 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( ( F " y ) u. ( _I ` ( F " { z } ) ) ) ~<_ ( y u. { z } ) )
58	42, 57	eqbrtrrd 4455	. . . . . . 7 |- ( ( ( y e. Fin /\ -. z e. y ) /\ ( F Fn A /\ ( F " y ) ~<_ y ) ) -> ( F " ( y u. { z } ) ) ~<_ ( y u. { z } ) )
59	58	exp32 605	. . . . . 6 |- ( ( y e. Fin /\ -. z e. y ) -> ( F Fn A -> ( ( F " y ) ~<_ y -> ( F " ( y u. { z } ) ) ~<_ ( y u. { z } ) ) ) )
60	59	a2d 26	. . . . 5 |- ( ( y e. Fin /\ -. z e. y ) -> ( ( F Fn A -> ( F " y ) ~<_ y ) -> ( F Fn A -> ( F " ( y u. { z } ) ) ~<_ ( y u. { z } ) ) ) )
61	9, 13, 17, 21, 24, 60	findcard2s 7759	. . . 4 |- ( A e. Fin -> ( F Fn A -> ( F " A ) ~<_ A ) )
62	3, 61	syl5 32	. . 3 |- ( A e. Fin -> ( F : A -onto-> B -> ( F " A ) ~<_ A ) )
63	62	imp 429	. 2 |- ( ( A e. Fin /\ F : A -onto-> B ) -> ( F " A ) ~<_ A )
64	2, 63	eqbrtrrd 4455	1 |- ( ( A e. Fin /\ F : A -onto-> B ) -> B ~<_ A )

Syntax hints:   -. wn 3   -> wi 4   /\ wa 369   = wceq 1381   e. wcel 1802   _Vcvv 3093   u. cun 3456   i^i cin 3457   C_ wss 3458   (/)c0 3767   {csn 4010   <.cop 4016   class class class wbr 4433   _I cid 4776   ran crn 4986   |` cres 4987   "cima 4988   Fun wfun 5568   Fn wfn 5569   -onto->wfo 5572   ` cfv 5574   1oc1o 7121   ~~ cen 7511   ~<_ cdom 7512   Fincfn 7514

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1603  ax-4 1616  ax-5 1689  ax-6 1732  ax-7 1774  ax-8 1804  ax-9 1806  ax-10 1821  ax-11 1826  ax-12 1838  ax-13 1983  ax-ext 2419  ax-sep 4554  ax-nul 4562  ax-pow 4611  ax-pr 4672  ax-un 6573

This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 973  df-3an 974  df-tru 1384  df-ex 1598  df-nf 1602  df-sb 1725  df-eu 2270  df-mo 2271  df-clab 2427  df-cleq 2433  df-clel 2436  df-nfc 2591  df-ne 2638  df-ral 2796  df-rex 2797  df-reu 2798  df-rab 2800  df-v 3095  df-sbc 3312  df-dif 3461  df-un 3463  df-in 3465  df-ss 3472  df-pss 3474  df-nul 3768  df-if 3923  df-pw 3995  df-sn 4011  df-pr 4013  df-tp 4015  df-op 4017  df-uni 4231  df-br 4434  df-opab 4492  df-tr 4527  df-eprel 4777  df-id 4781  df-po 4786  df-so 4787  df-fr 4824  df-we 4826  df-ord 4867  df-on 4868  df-lim 4869  df-suc 4870  df-xp 4991  df-rel 4992  df-cnv 4993  df-co 4994  df-dm 4995  df-rn 4996  df-res 4997  df-ima 4998  df-iota 5537  df-fun 5576  df-fn 5577  df-f 5578  df-f1 5579  df-fo 5580  df-f1o 5581  df-fv 5582  df-om 6682  df-1o 7128  df-er 7309  df-en 7515  df-dom 7516  df-fin 7518

This theorem is referenced by:  fodomfib  7798  fofinf1o  7799  fidomdm  7800  fofi  7804  pwfilem  7812  cmpsub  19766  alexsubALT  20417