:: Cardinal Numbers and Finite Sets :: by Karol P\c{a}k :: :: Received May 24, 2005 :: Copyright (c) 2005-2018 Association of Mizar Users :: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland). :: This code can be distributed under the GNU General Public Licence :: version 3.0 or later, or the Creative Commons Attribution-ShareAlike :: License version 3.0 or later, subject to the binding interpretation :: detailed in file COPYING.interpretation. :: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these :: licenses, or see http://www.gnu.org/licenses/gpl.html and :: http://creativecommons.org/licenses/by-sa/3.0/. environ vocabularies NUMBERS, SUBSET_1, FUNCT_1, NAT_1, TARSKI, FINSET_1, RELAT_1, AFINSQ_1, ARYTM_1, ARYTM_3, FINSEQ_1, XXREAL_0, CARD_1, XBOOLE_0, ORDINAL4, CARD_3, BINOP_1, FINSOP_1, FUNCOP_1, BINOP_2, FUNCT_2, INT_1, VALUED_1, NEWTON, REALSET1, ZFMISC_1, FUNCT_4, EQREL_1, SETFAM_1, STIRL2_1, CARD_FIN; notations TARSKI, XBOOLE_0, SUBSET_1, ORDINAL1, CARD_1, NUMBERS, RELAT_1, FUNCT_1, XCMPLX_0, NAT_1, FINSET_1, XXREAL_0, NAT_D, AFINSQ_1, VALUED_1, RELSET_1, PARTFUN1, DOMAIN_1, FUNCT_2, FUNCT_4, FUNCOP_1, INT_1, ENUMSET1, BINOP_1, BINOP_2, RECDEF_1, AFINSQ_2, ZFMISC_1, NEWTON, STIRL2_1, YELLOW20; constructors PARTFUN3, BINOM, WELLORD2, DOMAIN_1, SETWISEO, REAL_1, NAT_D, YELLOW20, RECDEF_1, BINOP_2, RELSET_1, ORDINAL4, AFINSQ_1, SEQ_4, AFINSQ_2, STIRL2_1, NUMBERS, NEWTON; registrations XBOOLE_0, SUBSET_1, RELAT_1, FUNCT_1, ORDINAL1, FUNCT_2, FUNCOP_1, FUNCT_4, FINSET_1, FRAENKEL, NUMBERS, XXREAL_0, XREAL_0, NAT_1, INT_1, BINOP_2, CARD_1, WSIERP_1, AFINSQ_1, RELSET_1, VALUED_1, VALUED_0, AFINSQ_2, XCMPLX_0, NEWTON; requirements REAL, NUMERALS, SUBSET, BOOLE, ARITHM; begin reserve x, x1, x2, y, z, X9 for set, X, Y for finite set, n, k, m for Nat, f for Function; ::\$CT theorem :: CARD_FIN:2 for X,Y,x,y st (Y={} implies X={}) & not x in X holds card Funcs( X,Y) = card{F where F is Function of X\/{x},Y\/{y}:rng (F|X) c=Y & F.x=y}; theorem :: CARD_FIN:3 for X,Y,x,y st not x in X & y in Y holds card Funcs(X,Y) = card{F where F is Function of X\/{x},Y:F.x=y}; :: card Funcs(X,Y) theorem :: CARD_FIN:4 (Y={} implies X={}) implies card Funcs(X,Y) = card Y |^ card X; theorem :: CARD_FIN:5 for X,Y,x,y st (Y is empty implies X is empty) & not x in X & not y in Y holds card{F where F is Function of X,Y:F is one-to-one}= card{F where F is Function of X\/{x},Y\/{y}:F is one-to-one & F.x=y}; theorem :: CARD_FIN:6 n!/((n-'k)!) is Element of NAT; :: one-to-one theorem :: CARD_FIN:7 card X <= card Y implies card {F where F is Function of X,Y:F is one-to-one} = card Y!/((card Y-'card X)!); :: Permutation of X theorem :: CARD_FIN:8 card{F where F is Function of X,X:F is Permutation of X}=card X!; definition let X,k; let x1,x2 be object; func Choose(X,k,x1,x2) -> Subset of Funcs(X,{x1,x2}) means :: CARD_FIN:def 1 x in it iff ex f be Function of X,{x1,x2} st f = x & card (f"{x1})=k; end; theorem :: CARD_FIN:9 card X<>k implies Choose(X,k,x1,x1) is empty; theorem :: CARD_FIN:10 for x1,x2 being object holds card X < k implies Choose(X,k,x1,x2) is empty; theorem :: CARD_FIN:11 for x1,x2 being object holds x1<>x2 implies card Choose(X,0,x1,x2)=1; theorem :: CARD_FIN:12 for x1,x2 being object holds card Choose(X,card X,x1,x2)=1; theorem :: CARD_FIN:13 for z,x,y being object holds not z in X implies card Choose(X,k,x,y)= card{f where f is Function of X\/{z},{x,y}:card (f"{x})=k+1 & f.z=x}; theorem :: CARD_FIN:14 for z,x,y being object holds not z in X & x<>y implies card Choose(X,k,x,y)= card{f where f is Function of X\/{z},{x,y}:card (f"{x})=k & f.z=y}; theorem :: CARD_FIN:15 for z,x,y being object holds x<>y & not z in X implies card Choose(X\/{z},k+1,x,y)= card Choose(X,k+1,x,y)+ card Choose(X,k,x,y); :: n choose k ::\$N Formula for the Number of Combinations theorem :: CARD_FIN:16 for x,y being object holds x<>y implies card Choose(X,k,x,y)=card X choose k; theorem :: CARD_FIN:17 for x,y being object holds x<>y implies (Y-->y)+*(X-->x) in Choose(X\/Y,card X,x,y); theorem :: CARD_FIN:18 x<>y & X misses Y implies (X-->x)+*(Y-->y) in Choose(X\/Y,card X ,x,y); definition let F,Ch be Function,y be object; func Intersection(F,Ch,y) -> Subset of union rng F means :: CARD_FIN:def 2 z in it iff z in union rng F & for x st x in dom Ch & Ch.x=y holds z in F.x; end; reserve F,Ch for Function; theorem :: CARD_FIN:19 for F,Ch st dom F/\Ch"{x} is non empty holds y in Intersection(F ,Ch,x) iff for z st z in dom Ch & Ch.z=x holds y in F.z; theorem :: CARD_FIN:20 Intersection(F,Ch,y) is non empty implies Ch"{y} c= dom F; theorem :: CARD_FIN:21 Intersection(F,Ch,y) is non empty implies for x1,x2 st x1 in Ch"{y} & x2 in Ch"{y} holds F.x1 meets F.x2; theorem :: CARD_FIN:22 z in Intersection(F,Ch,y) & y in rng Ch implies ex x st x in dom Ch & Ch.x=y & z in F.x; theorem :: CARD_FIN:23 F is empty or union rng F is empty implies Intersection(F,Ch,y)=union rng F; theorem :: CARD_FIN:24 for y being object holds F|Ch"{y}=(Ch"{y}-->union rng F) implies Intersection(F,Ch,y) = union rng F; theorem :: CARD_FIN:25 union rng F is non empty & Intersection(F,Ch,y)=union rng F implies F| Ch"{y}=(Ch"{y}-->union rng F); theorem :: CARD_FIN:26 for y being object holds Intersection(F,{},y)=union rng F; theorem :: CARD_FIN:27 for y being object holds Intersection(F,Ch,y) c= Intersection(F,Ch|X9,y); theorem :: CARD_FIN:28 Ch"{y}=(Ch|X9)"{y} implies Intersection(F,Ch,y)=Intersection(F, Ch|X9,y); theorem :: CARD_FIN:29 Intersection(F|X9,Ch,y) c= Intersection(F,Ch,y); theorem :: CARD_FIN:30 y in rng Ch & Ch"{y} c= X9 implies Intersection(F|X9,Ch,y) = Intersection(F,Ch,y); theorem :: CARD_FIN:31 for x,y being object holds x in Ch"{y} implies Intersection(F,Ch,y) c= F.x; theorem :: CARD_FIN:32 for x,y being object holds x in Ch"{y} implies Intersection(F,Ch|(dom Ch\{x}),y)/\F.x= Intersection(F,Ch,y); theorem :: CARD_FIN:33 for x1,x2 being object for Ch1,Ch2 be Function st Ch1"{x1}=Ch2"{x2} holds Intersection( F,Ch1,x1)=Intersection(F,Ch2,x2); theorem :: CARD_FIN:34 for y being object holds Ch"{y}={} implies Intersection(F,Ch,y)=union rng F; theorem :: CARD_FIN:35 for x,y being object holds {x}=Ch"{y} implies Intersection(F,Ch,y)=F.x; theorem :: CARD_FIN:36 {x1,x2}=Ch"{y} implies Intersection(F,Ch,y)=F.x1 /\ F.x2; theorem :: CARD_FIN:37 for F st F is non empty holds y in Intersection(F,(dom F-->x),x) iff for z st z in dom F holds y in F.z; registration let F be finite-yielding Function,X be set; cluster F|X -> finite-yielding; end; registration let F be finite-yielding Function,G be Function; cluster F*G -> finite-yielding; cluster Intersect(F,G) -> finite-yielding; end; reserve Fy for finite-yielding Function; theorem :: CARD_FIN:38 y in rng Ch implies Intersection(Fy,Ch,y) is finite; theorem :: CARD_FIN:39 dom Fy is finite implies union rng Fy is finite; theorem :: CARD_FIN:40 x in Choose(n,k,1,0) iff ex F be XFinSequence of NAT st F = x & dom F = n & rng F c= {0,1} & Sum F=k; definition ::\$CD let k; let F be finite-yielding Function; assume dom F is finite; func Card_Intersection(F,k) -> Element of NAT means :: CARD_FIN:def 4 for x,y be object,X be finite set, P be Function of card Choose(X,k,x,y),Choose(X,k,x,y) st dom F=X & P is one-to-one & x<>y ex XFS be XFinSequence of NAT st dom XFS=dom P & (for z,f st z in dom XFS & f=P.z holds XFS.z=card(Intersection(F,f,x))) & it=Sum XFS ; end; theorem :: CARD_FIN:41 for x,y be set,X be finite set, P be Function of card Choose(X,k,x,y), Choose(X,k,x,y) st dom Fy=X & P is one-to-one & x<>y for XFS be XFinSequence of NAT st dom XFS=dom P & (for z,f st z in dom XFS & f=P.z holds XFS.z=card( Intersection(Fy,f,x))) holds Card_Intersection(Fy,k)=Sum XFS; theorem :: CARD_FIN:42 dom Fy is finite & k=0 implies Card_Intersection(Fy,k)=card (union rng Fy); theorem :: CARD_FIN:43 dom Fy=X & k > card X implies Card_Intersection(Fy,k)=0; theorem :: CARD_FIN:44 for Fy,X st dom Fy=X for P be Function of card X,X st P is one-to-one holds ex XFS be XFinSequence of NAT st dom XFS=card X & (for z st z in dom XFS holds XFS.z=card ((Fy*P).z))& Card_Intersection(Fy,1)=Sum XFS; theorem :: CARD_FIN:45 for x being object holds dom Fy=X implies Card_Intersection(Fy,card X)=card Intersection( Fy,X-->x,x); theorem :: CARD_FIN:46 for x being object holds Fy=x.-->X implies Card_Intersection(Fy,1)=card X; theorem :: CARD_FIN:47 x<>y & Fy=(x,y)-->(X,Y) implies Card_Intersection(Fy,1)=card X + card Y & Card_Intersection(Fy,2)=card (X/\Y); theorem :: CARD_FIN:48 for Fy,x st dom Fy is finite & x in dom Fy holds Card_Intersection(Fy,1)=Card_Intersection(Fy|(dom Fy\{x}),1)+ card (Fy.x); theorem :: CARD_FIN:49 dom Intersect(F,dom F-->X9)=dom F & for x st x in dom F holds Intersect(F,dom F-->X9).x = F.x /\ X9; theorem :: CARD_FIN:50 (union rng F)/\X9=union rng Intersect(F,dom F-->X9); theorem :: CARD_FIN:51 Intersection(F,Ch,y)/\X9= Intersection(Intersect(F,dom F-->X9), Ch,y); theorem :: CARD_FIN:52 for F, G be XFinSequence st F is one-to-one & G is one-to-one & rng F misses rng G holds F^G is one-to-one; theorem :: CARD_FIN:53 for Fy,X,x,n st dom Fy = X & x in dom Fy & k>0 holds Card_Intersection(Fy,k+1)= Card_Intersection(Fy|(dom Fy\{x}),k+1)+ Card_Intersection(Intersect(Fy|(dom Fy\{x}),(dom Fy\{x})-->Fy.x),k); theorem :: CARD_FIN:54 x in dom F implies union rng F=union rng (F|(dom F\{x}))\/F.x; theorem :: CARD_FIN:55 for Fy be finite-yielding Function,X ex XFS be XFinSequence of INT st dom XFS = card X & for n st n in dom XFS holds XFS.n=((-1)|^n)* Card_Intersection(Fy,n+1); :: The principle of inclusions and the disconnections ::\$N Principle of Inclusion/Exclusion theorem :: CARD_FIN:56 for Fy be finite-yielding Function,X st dom Fy=X for XFS be XFinSequence of INT st dom XFS= card X & for n st n in dom XFS holds XFS.n=((-1 )|^n)*Card_Intersection(Fy,n+1) holds card union rng Fy=Sum XFS; theorem :: CARD_FIN:57 for Fy,X,n,k st dom Fy=X holds (ex x,y st x<>y & for f st f in Choose(X,k,x,y) holds card(Intersection(Fy,f,x))=n) implies Card_Intersection( Fy,k)=n*(card X choose k); theorem :: CARD_FIN:58 for Fy,X st dom Fy=X for XF be XFinSequence of NAT st dom XF= card X & for n st n in dom XF holds ex x,y st x<>y & for f st f in Choose(X,n+1 ,x,y) holds card(Intersection(Fy,f,x))=XF.n holds ex F be XFinSequence of INT st dom F=card X & card union rng Fy = Sum F & for n st n in dom F holds F.n=((- 1)|^n)*XF.n*(card X choose (n+1)); :: onto theorem :: CARD_FIN:59 for X,Y be finite set st X is non empty & Y is non empty ex F be XFinSequence of INT st dom F = card Y+1 & Sum F = card {f where f is Function of X,Y:f is onto} & for n st n in dom F holds F.n=((-1)|^n)*(card Y choose n)*( (card Y-n) |^ card X); :: n block k theorem :: CARD_FIN:60 for n,k st k <= n ex F be XFinSequence of INT st n block k = 1/(k!) * Sum F & dom F = k+1 & for m st m in dom F holds F.m=((-1)|^m)*(k choose m)*((k- m) |^ n); theorem :: CARD_FIN:61 for X1,Y1,X be finite set st (Y1 is empty implies X1 is empty) & X c= X1 for F be Function of X1,Y1 st F is one-to-one & card X1=card Y1 holds ( card X1-'card X)!= card{f where f is Function of X1,Y1: f is one-to-one & rng(f |(X1\X)) c= F.:(X1\X) & for x st x in X holds f.x=F.x}; theorem :: CARD_FIN:62 for F be Function st dom F=X & F is one-to-one ex XF be XFinSequence of INT st Sum XF=card {h where h is Function of X,rng F: h is one-to-one & for x st x in X holds h.x<>F.x}& dom XF = card X +1 & for n st n in dom XF holds XF.n=((-1)|^n)*(card X!)/(n!); :: disorders theorem :: CARD_FIN:63 ex XF be XFinSequence of INT st Sum XF=card {h where h is Function of X,X: h is one-to-one & for x st x in X holds h.x<>x}& dom XF = card X+1 & for n st n in dom XF holds XF.n=((-1)|^n)*(card X!)/(n!);