Volume 2, 1990

University of Bialystok

Copyright (c) 1990 Association of Mizar Users

### The abstract of the Mizar article:

### Cardinal Arithmetics

**by****Grzegorz Bancerek**- Received March 6, 1990
- MML identifier: CARD_2

- [ Mizar article, MML identifier index ]

environ vocabulary ORDINAL1, CARD_1, FUNCT_1, RELAT_1, BOOLE, TARSKI, FUNCT_2, MCART_1, ORDINAL2, ORDINAL3, FUNCOP_1, FINSET_1, FINSEQ_1, ARYTM_1, CARD_2; notation TARSKI, XBOOLE_0, ENUMSET1, ZFMISC_1, XREAL_0, RELAT_1, FUNCT_1, FUNCT_2, ORDINAL1, MCART_1, ORDINAL2, ORDINAL3, WELLORD2, REAL_1, NAT_1, FINSEQ_1, CARD_1, FINSET_1, FUNCOP_1; constructors DOMAIN_1, ORDINAL3, WELLORD2, REAL_1, NAT_1, FINSEQ_1, FUNCOP_1, XREAL_0, XBOOLE_0; clusters SUBSET_1, ORDINAL1, CARD_1, FINSEQ_1, FINSET_1, ZFMISC_1, XBOOLE_0; requirements NUMERALS, SUBSET, BOOLE, ARITHM; begin reserve A,B for Ordinal, K,M,N for Cardinal, x,x1,x2,y,y1,y2,z,u,X,Y,Z,X1,X2,Y1,Y2 for set, f,g for Function; canceled; theorem :: CARD_2:2 Card X <=` Card Y iff ex f st X c= f.:Y; theorem :: CARD_2:3 Card (f.:X) <=` Card X; theorem :: CARD_2:4 Card X <` Card Y implies Y \ X <> {}; theorem :: CARD_2:5 x in X & X,Y are_equipotent implies Y <> {} & ex x st x in Y; theorem :: CARD_2:6 bool X,bool Card X are_equipotent & Card bool X = Card bool Card X; theorem :: CARD_2:7 Z in Funcs(X,Y) implies Z,X are_equipotent & Card Z = Card X; definition let M,N; func M +` N -> Cardinal equals :: CARD_2:def 1 Card( M +^ N); commutativity; func M *` N -> Cardinal equals :: CARD_2:def 2 Card [:M,N:]; commutativity; func exp(M,N) -> Cardinal equals :: CARD_2:def 3 Card Funcs(N,M); end; canceled 3; theorem :: CARD_2:11 [:X,Y:],[:Y,X:] are_equipotent & Card [:X,Y:] = Card [:Y,X:]; theorem :: CARD_2:12 [:[:X,Y:],Z:],[:X,[:Y,Z:]:] are_equipotent & Card [:[:X,Y:],Z:] = Card [:X,[:Y,Z:]:]; theorem :: CARD_2:13 X,[:X,{x}:] are_equipotent & Card X = Card [:X,{x}:]; theorem :: CARD_2:14 [:X,Y:],[:Card X,Y:] are_equipotent & [:X,Y:],[:X,Card Y:] are_equipotent & [:X,Y:],[:Card X,Card Y:] are_equipotent & Card [:X,Y:] = Card [:Card X,Y:] & Card [:X,Y:] = Card [:X,Card Y:] & Card [:X,Y:] = Card [:Card X,Card Y:]; theorem :: CARD_2:15 X1,Y1 are_equipotent & X2,Y2 are_equipotent implies [:X1,X2:],[:Y1,Y2:] are_equipotent & Card [:X1,X2:] = Card [:Y1,Y2:]; theorem :: CARD_2:16 x1 <> x2 implies A+^B,[:A,{x1}:] \/ [:B,{x2}:] are_equipotent & Card(A+^B) = Card([:A,{x1}:] \/ [:B,{x2}:]); theorem :: CARD_2:17 x1 <> x2 implies K+`M,[:K,{x1}:] \/ [:M,{x2}:] are_equipotent & K+`M = Card([:K,{x1}:] \/ [:M,{x2}:]); theorem :: CARD_2:18 A*^B,[:A,B:] are_equipotent & Card(A*^B) = Card [:A,B:]; theorem :: CARD_2:19 0 = Card {} & 1 = Card one & 2 = Card succ one; theorem :: CARD_2:20 1 = one; canceled; theorem :: CARD_2:22 2 = {{},one} & 2 = succ one; theorem :: CARD_2:23 X1,Y1 are_equipotent & X2,Y2 are_equipotent & x1 <> x2 & y1 <> y2 implies [:X1,{x1}:] \/ [:X2,{x2}:],[:Y1,{y1}:] \/ [:Y2,{y2}:] are_equipotent & Card ([:X1,{x1}:] \/ [:X2,{x2}:]) = Card ([:Y1,{y1}:] \/ [:Y2,{y2}:]); theorem :: CARD_2:24 Card(A+^B) = Card A +` Card B; theorem :: CARD_2:25 Card(A*^B) = Card A *` Card B; theorem :: CARD_2:26 [:X,{0}:] \/ [:Y,{1}:],[:Y,{0}:] \/ [:X,{1}:] are_equipotent & Card([:X,{0}:] \/ [:Y,{1}:]) = Card([:Y,{0}:] \/ [:X,{1}:]); theorem :: CARD_2:27 [:X1,X2:] \/ [:Y1,Y2:],[:X2,X1:] \/ [:Y2,Y1:] are_equipotent & Card ([:X1,X2:] \/ [:Y1,Y2:]) = Card ([:X2,X1:] \/ [:Y2,Y1:]); theorem :: CARD_2:28 x <> y implies Card X +` Card Y = Card([:X,{x}:] \/ [:Y,{y}:]); theorem :: CARD_2:29 M+`0 = M; canceled; theorem :: CARD_2:31 (K+`M)+`N = K+`(M+`N); theorem :: CARD_2:32 K*`0 = 0; theorem :: CARD_2:33 K*`1 = K; canceled; theorem :: CARD_2:35 (K*`M)*`N = K*`(M*`N); theorem :: CARD_2:36 2*`K = K+`K; theorem :: CARD_2:37 K*`(M+`N) = K*`M +` K*`N; theorem :: CARD_2:38 exp(K,0) = 1; theorem :: CARD_2:39 K <> 0 implies exp(0,K) = 0; theorem :: CARD_2:40 exp(K,1) = K & exp(1,K) = 1; theorem :: CARD_2:41 exp(K,M+`N) = exp(K,M)*`exp(K,N); theorem :: CARD_2:42 exp(K*`M,N) = exp(K,N)*`exp(M,N); theorem :: CARD_2:43 exp(K,M*`N) = exp(exp(K,M),N); theorem :: CARD_2:44 exp(2,Card X) = Card bool X; theorem :: CARD_2:45 exp(K,2) = K*`K; theorem :: CARD_2:46 exp(K+`M,2) = K*`K +` 2*`K*`M +` M*`M; theorem :: CARD_2:47 Card(X \/ Y) <=` Card X +` Card Y; theorem :: CARD_2:48 X misses Y implies Card (X \/ Y) = Card X +` Card Y; reserve m,n for Nat; theorem :: CARD_2:49 n+m = n +^ m; theorem :: CARD_2:50 n*m = n *^ m; theorem :: CARD_2:51 Card(n+m) = Card n +` Card m; theorem :: CARD_2:52 Card(n*m) = Card n *` Card m; theorem :: CARD_2:53 for X,Y being finite set st X misses Y holds card (X \/ Y) = card X + card Y; theorem :: CARD_2:54 for X being finite set st not x in X holds card (X \/ {x}) = card X + 1; canceled 2; theorem :: CARD_2:57 for X,Y being finite set holds (Card X <=` Card Y iff card X <= card Y); theorem :: CARD_2:58 for X,Y being finite set holds Card X <` Card Y iff card X < card Y; theorem :: CARD_2:59 for X being set st Card X = 0 holds X = {}; theorem :: CARD_2:60 for X being set holds Card X = 1 iff ex x st X = {x}; theorem :: CARD_2:61 for X being finite set holds X,card X are_equipotent & X,Card card X are_equipotent & X,Seg card X are_equipotent; theorem :: CARD_2:62 for X,Y being finite set holds card(X \/ Y) <= card X + card Y; theorem :: CARD_2:63 for X,Y being finite set st Y c= X holds card (X \ Y) = card X - card Y; theorem :: CARD_2:64 for X,Y being finite set holds card (X \/ Y) = card X + card Y - card (X /\ Y); theorem :: CARD_2:65 for X,Y being finite set holds card [:X,Y:] = card X * card Y; canceled; theorem :: CARD_2:67 for X,Y being finite set st X c< Y holds card X < card Y & Card X <` Card Y; theorem :: CARD_2:68 (Card X <=` Card Y or Card X <` Card Y) & Y is finite implies X is finite; reserve x1,x2,x3,x4,x5,x6,x7,x8 for set; theorem :: CARD_2:69 card {x1,x2} <= 2; theorem :: CARD_2:70 card {x1,x2,x3} <= 3; theorem :: CARD_2:71 card {x1,x2,x3,x4} <= 4; theorem :: CARD_2:72 card {x1,x2,x3,x4,x5} <= 5; theorem :: CARD_2:73 card {x1,x2,x3,x4,x5,x6} <= 6; theorem :: CARD_2:74 card {x1,x2,x3,x4,x5,x6,x7} <= 7; theorem :: CARD_2:75 card {x1,x2,x3,x4,x5,x6,x7,x8} <= 8; theorem :: CARD_2:76 x1 <> x2 implies card {x1,x2} = 2; theorem :: CARD_2:77 x1 <> x2 & x1 <> x3 & x2 <> x3 implies card {x1,x2,x3} = 3; theorem :: CARD_2:78 x1 <> x2 & x1 <> x3 & x1 <> x4 & x2 <> x3 & x2 <> x4 & x3 <> x4 implies card {x1,x2,x3,x4} = 4;

Back to top