:: Ordinal Arithmetics
:: by Grzegorz Bancerek
::
:: Received March 1, 1990
:: Copyright (c) 1990-2016 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 ORDINAL2, ORDINAL1, TARSKI, XBOOLE_0, SETFAM_1, RELAT_1, FUNCT_1,
SUBSET_1, ORDINAL3, CARD_1;
notations TARSKI, XBOOLE_0, SUBSET_1, RELAT_1, FUNCT_1, ORDINAL1, SETFAM_1,
ORDINAL2;
constructors SETFAM_1, ORDINAL2, XTUPLE_0;
registrations XBOOLE_0, ORDINAL1, ORDINAL2;
requirements SUBSET, BOOLE, NUMERALS;
begin
reserve fi,psi for Ordinal-Sequence,
A,B,C,D for Ordinal,
X,Y for set,
x,y for object;
theorem :: ORDINAL3:1
X c= succ X;
theorem :: ORDINAL3:2
succ X c= Y implies X c= Y;
theorem :: ORDINAL3:3
A in B iff succ A in succ B;
theorem :: ORDINAL3:4
X c= A implies union X is epsilon-transitive epsilon-connected set;
theorem :: ORDINAL3:5
union On X is epsilon-transitive epsilon-connected set;
theorem :: ORDINAL3:6
X c= A implies On X = X;
theorem :: ORDINAL3:7
On {A} = {A};
theorem :: ORDINAL3:8
A <> {} implies {} in A;
theorem :: ORDINAL3:9
inf A = {};
theorem :: ORDINAL3:10
inf {A} = A;
theorem :: ORDINAL3:11
X c= A implies meet X is Ordinal;
registration
let A,B;
cluster A \/ B -> ordinal;
cluster A /\ B -> ordinal;
end;
theorem :: ORDINAL3:12
A \/ B = A or A \/ B = B;
theorem :: ORDINAL3:13
A /\ B = A or A /\ B = B;
theorem :: ORDINAL3:14
A in 1 implies A = {};
theorem :: ORDINAL3:15
1 = {{}};
theorem :: ORDINAL3:16
A c= 1 implies A = {} or A = 1;
theorem :: ORDINAL3:17
(A c= B or A in B) & C in D implies A+^C in B+^D;
theorem :: ORDINAL3:18
A c= B & C c= D implies A+^C c= B+^D;
theorem :: ORDINAL3:19
A in B & (C c= D & D <> {} or C in D) implies A*^C in B*^D;
theorem :: ORDINAL3:20
A c= B & C c= D implies A*^C c= B*^D;
theorem :: ORDINAL3:21
B+^C = B+^D implies C = D;
theorem :: ORDINAL3:22
B+^C in B+^D implies C in D;
theorem :: ORDINAL3:23
B+^C c= B+^D implies C c= D;
theorem :: ORDINAL3:24
A c= A+^B & B c= A+^B;
theorem :: ORDINAL3:25
A in B implies A in B+^C & A in C+^B;
theorem :: ORDINAL3:26
A+^B = {} implies A = {} & B = {};
theorem :: ORDINAL3:27
A c= B implies ex C st B = A+^C;
theorem :: ORDINAL3:28
A in B implies ex C st B = A+^C & C <> {};
theorem :: ORDINAL3:29
A <> {} & A is limit_ordinal implies B+^A is limit_ordinal;
theorem :: ORDINAL3:30
A+^B+^C = A+^(B+^C);
theorem :: ORDINAL3:31
A*^B = {} implies A = {} or B = {};
theorem :: ORDINAL3:32
A in B & C <> {} implies A in B*^C & A in C*^B;
theorem :: ORDINAL3:33
B*^A = C*^A & A <> {} implies B = C;
theorem :: ORDINAL3:34
B*^A in C*^A implies B in C;
theorem :: ORDINAL3:35
B*^A c= C*^A & A <> {} implies B c= C;
theorem :: ORDINAL3:36
B <> {} implies A c= A*^B & A c= B*^A;
theorem :: ORDINAL3:37
A*^B = 1 implies A = 1 & B = 1;
theorem :: ORDINAL3:38
A in B+^C implies A in B or ex D st D in C & A = B+^D;
definition
let C,fi;
func C+^fi -> Ordinal-Sequence means
:: ORDINAL3:def 1
dom it = dom fi & for A st A in dom fi holds it.A = C+^(fi.A);
func fi+^C -> Ordinal-Sequence means
:: ORDINAL3:def 2
dom it = dom fi & for A st A in dom fi holds it.A = (fi.A)+^C;
func C*^fi -> Ordinal-Sequence means
:: ORDINAL3:def 3
dom it = dom fi & for A st A in dom fi holds it.A = C*^(fi.A);
func fi*^C -> Ordinal-Sequence means
:: ORDINAL3:def 4
dom it = dom fi & for A st A in dom fi holds it.A = (fi.A)*^C;
end;
theorem :: ORDINAL3:39
{} <> dom fi & dom fi = dom psi & (for A,B st A in dom fi & B =
fi.A holds psi.A = C+^B) implies sup psi = C+^sup fi;
theorem :: ORDINAL3:40
A is limit_ordinal implies A*^B is limit_ordinal;
theorem :: ORDINAL3:41
A in B*^C & B is limit_ordinal implies ex D st D in B & A in D*^ C;
theorem :: ORDINAL3:42
dom fi = dom psi & C <> {} & sup fi is limit_ordinal & (for A,B
st A in dom fi & B = fi.A holds psi.A = B*^C) implies sup psi = (sup fi)*^C;
theorem :: ORDINAL3:43
{} <> dom fi implies sup (C+^fi) = C+^sup fi;
theorem :: ORDINAL3:44
{} <> dom fi & C <> {} & sup fi is limit_ordinal implies sup (fi
*^C) = (sup fi)*^C;
theorem :: ORDINAL3:45
B <> {} implies union(A+^B) = A+^union B;
theorem :: ORDINAL3:46
(A+^B)*^C = A*^C +^ B*^C;
theorem :: ORDINAL3:47
A <> {} implies ex C,D st B = C*^A+^D & D in A;
theorem :: ORDINAL3:48
for C1,D1,C2,D2 being Ordinal st C1*^A+^D1 = C2*^A+^D2 & D1 in A
& D2 in A holds C1 = C2 & D1 = D2;
theorem :: ORDINAL3:49
1 in B & A <> {} & A is limit_ordinal implies for fi st dom fi =
A & for C st C in A holds fi.C = C*^B holds A*^B = sup fi;
theorem :: ORDINAL3:50
(A*^B)*^C = A*^(B*^C);
definition
let A,B;
func A -^ B -> Ordinal means
:: ORDINAL3:def 5
A = B+^it if B c= A otherwise it = {};
func A div^ B -> Ordinal means
:: ORDINAL3:def 6
ex C st A = it*^B+^C & C in B if B <> {} otherwise it = {};
end;
definition
let A,B;
func A mod^ B -> Ordinal equals
:: ORDINAL3:def 7
A-^(A div^ B)*^B;
end;
theorem :: ORDINAL3:51
A in B implies B = A+^(B-^A);
theorem :: ORDINAL3:52
A+^B-^A = B;
theorem :: ORDINAL3:53
A in B & (C c= A or C in A) implies A-^C in B-^C;
theorem :: ORDINAL3:54
A-^A = {};
theorem :: ORDINAL3:55
A in B implies B-^A <> {} & {} in B-^A;
theorem :: ORDINAL3:56
A-^{} = A & {}-^A = {};
theorem :: ORDINAL3:57
A-^(B+^C) = (A-^B)-^C;
theorem :: ORDINAL3:58
A c= B implies C-^B c= C-^A;
theorem :: ORDINAL3:59
A c= B implies A-^C c= B-^C;
theorem :: ORDINAL3:60
C <> {} & A in B+^C implies A-^B in C;
theorem :: ORDINAL3:61
A+^B in C implies B in C-^A;
theorem :: ORDINAL3:62
A c= B+^(A-^B);
theorem :: ORDINAL3:63
A*^C -^ B*^C = (A-^B)*^C;
theorem :: ORDINAL3:64
(A div^ B)*^B c= A;
theorem :: ORDINAL3:65
A = (A div^ B)*^B+^(A mod^ B);
theorem :: ORDINAL3:66
A = B*^C+^D & D in C implies B = A div^ C & D = A mod^ C;
theorem :: ORDINAL3:67
A in B*^C implies A div^ C in B & A mod^ C in C;
theorem :: ORDINAL3:68
B <> {} implies A*^B div^ B = A;
theorem :: ORDINAL3:69
A*^B mod^ B = {};
theorem :: ORDINAL3:70
{} div^ A = {} & {} mod^ A = {} & A mod^ {} = A;
theorem :: ORDINAL3:71
A div^ 1 = A & A mod^ 1 = {};
begin :: Addenda
:: from ZF_REFLE, 2007.03.13, A.T.
theorem :: ORDINAL3:72
sup X c= succ union On X;
:: from ZFREFLE1, 2007.03.14, A.T.
reserve e,u for set;
theorem :: ORDINAL3:73
succ A is_cofinal_with 1;
:: from ARYTM_3, 2007.10.23, A.T.
theorem :: ORDINAL3:74
for a,b being Ordinal st a+^b is natural holds a in omega & b in omega;
registration
let a, b be natural Ordinal;
cluster a -^ b -> natural;
cluster a *^ b -> natural;
end;
theorem :: ORDINAL3:75
for a,b being Ordinal st a*^b is natural non empty holds a in omega &
b in omega;
definition
let a,b be natural Ordinal;
redefine func a+^b;
commutativity;
end;
definition
let a,b be natural Ordinal;
redefine func a*^b;
commutativity;
end;