:: Sequences of Ordinal Numbers. Beginnings of Ordinal Arithmetics :: by Grzegorz Bancerek :: :: Received July 18, 1989 :: Copyright (c) 1990-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 ORDINAL1, FUNCT_1, XBOOLE_0, TARSKI, ZFMISC_1, RELAT_1, SETFAM_1, SUBSET_1, FUNCOP_1, ORDINAL2, NAT_1, CARD_1; notations TARSKI, XBOOLE_0, ZFMISC_1, SUBSET_1, RELAT_1, FUNCT_1, ORDINAL1, SETFAM_1, FUNCOP_1; constructors SETFAM_1, ORDINAL1, FUNCOP_1; registrations SUBSET_1, FUNCT_1, ORDINAL1, FUNCOP_1; requirements SUBSET, BOOLE, NUMERALS; begin reserve A,A1,A2,B,C,D for Ordinal, X,Y for set, x,y,a,b,c for object, L,L1,L2,L3 for Sequence, f for Function; scheme :: ORDINAL2:sch 1 OrdinalInd { P[Ordinal] } : for A holds P[A] provided P[0] and for A st P[A] holds P[succ A] and for A st A <> 0 & A is limit_ordinal & for B st B in A holds P[B] holds P[A]; theorem :: ORDINAL2:1 A c= B iff succ A c= succ B; theorem :: ORDINAL2:2 union succ A = A; theorem :: ORDINAL2:3 succ A c= bool A; theorem :: ORDINAL2:4 0 is limit_ordinal; theorem :: ORDINAL2:5 union A c= A; definition let L; func last L -> set equals :: ORDINAL2:def 1 L.(union dom L); end; theorem :: ORDINAL2:6 dom L = succ A implies last L = L.A; theorem :: ORDINAL2:7 On X c= X; theorem :: ORDINAL2:8 On A = A; theorem :: ORDINAL2:9 X c= Y implies On X c= On Y; theorem :: ORDINAL2:10 Lim X c= X; theorem :: ORDINAL2:11 X c= Y implies Lim X c= Lim Y; theorem :: ORDINAL2:12 Lim X c= On X; theorem :: ORDINAL2:13 (for x st x in X holds x is Ordinal) implies meet X is Ordinal; registration cluster limit_ordinal for Ordinal; end; definition let X; func inf X -> Ordinal equals :: ORDINAL2:def 2 meet On X; func sup X -> Ordinal means :: ORDINAL2:def 3 On X c= it & for A st On X c= A holds it c= A; end; theorem :: ORDINAL2:14 A in X implies inf X c= A; theorem :: ORDINAL2:15 On X <> 0 & (for A st A in X holds D c= A) implies D c= inf X; theorem :: ORDINAL2:16 A in X & X c= Y implies inf Y c= inf X; theorem :: ORDINAL2:17 A in X implies inf X in X; theorem :: ORDINAL2:18 sup A = A; theorem :: ORDINAL2:19 A in X implies A in sup X; theorem :: ORDINAL2:20 (for A st A in X holds A in D) implies sup X c= D; theorem :: ORDINAL2:21 A in sup X implies ex B st B in X & A c= B; theorem :: ORDINAL2:22 X c= Y implies sup X c= sup Y; theorem :: ORDINAL2:23 sup { A } = succ A; theorem :: ORDINAL2:24 inf X c= sup X; scheme :: ORDINAL2:sch 2 TSLambda { A()->Ordinal, F(Ordinal)->set } : ex L st dom L = A() & for A st A in A() holds L.A = F(A); definition let f; attr f is Ordinal-yielding means :: ORDINAL2:def 4 ex A st rng f c= A; end; registration cluster Ordinal-yielding for Sequence; end; definition mode Ordinal-Sequence is Ordinal-yielding Sequence; end; registration let A; cluster -> Ordinal-yielding for Sequence of A; end; registration let L be Ordinal-Sequence; let A; cluster L|A -> Ordinal-yielding; end; reserve fi,psi for Ordinal-Sequence; theorem :: ORDINAL2:25 A in dom fi implies fi.A is Ordinal; registration let f be Ordinal-Sequence, a be object; cluster f.a -> ordinal; end; scheme :: ORDINAL2:sch 3 OSLambda { A()->Ordinal, F(Ordinal)->Ordinal } : ex fi st dom fi = A() & for A st A in A() holds fi.A = F(A); scheme :: ORDINAL2:sch 4 TSUniq1 { A()->Ordinal, B()->object, C(Ordinal,set)->object, D(Ordinal,Sequence)->object, L1()->Sequence, L2()->Sequence } : L1() = L2() provided dom L1() = A() and 0 in A() implies L1().0 = B() and for A st succ A in A() holds L1().(succ A) = C(A,L1().A) and for A st A in A() & A <> 0 & A is limit_ordinal holds L1().A = D(A, L1()|A) and dom L2() = A() and 0 in A() implies L2().0 = B() and for A st succ A in A() holds L2().(succ A) = C(A,L2().A) and for A st A in A() & A <> 0 & A is limit_ordinal holds L2().A = D(A, L2()|A); scheme :: ORDINAL2:sch 5 TSExist1 { A()->Ordinal, B()->object, C(Ordinal,set)->object, D(Ordinal,Sequence)->object } : ex L st dom L = A() & (0 in A() implies L.0 = B() ) & (for A st succ A in A() holds L.(succ A) = C(A,L.A) ) & for A st A in A() & A <> 0 & A is limit_ordinal holds L.A = D(A,L|A); scheme :: ORDINAL2:sch 6 TSResult { L()->Sequence, F(Ordinal)->set, A()->Ordinal, B()->set, C( Ordinal,set)->set, D(Ordinal,Sequence)->set } : for A st A in dom L() holds L ().A = F(A) provided for A,x holds x = F(A) iff ex L st x = last L & dom L = succ A & L. 0 = B() & (for C st succ C in succ A holds L.succ C = C(C,L.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds L.C = D(C,L|C) and dom L() = A() and 0 in A() implies L().0 = B() and for A st succ A in A() holds L().(succ A) = C(A,L().A) and for A st A in A() & A <> 0 & A is limit_ordinal holds L().A = D(A,L ()|A); scheme :: ORDINAL2:sch 7 TSDef { A()->Ordinal, B()->set, C(Ordinal,set)->set, D(Ordinal,Sequence)-> set } : (ex x,L st x = last L & dom L = succ A() & L.0 = B() & (for C st succ C in succ A() holds L.succ C = C(C,L.C)) & for C st C in succ A() & C <> 0 & C is limit_ordinal holds L.C = D(C,L|C) ) & for x1,x2 being set st (ex L st x1 = last L & dom L = succ A() & L.0 = B() & (for C st succ C in succ A() holds L. succ C = C(C,L.C)) & for C st C in succ A() & C <> 0 & C is limit_ordinal holds L.C = D(C,L|C) ) & (ex L st x2 = last L & dom L = succ A() & L.0 = B() & (for C st succ C in succ A() holds L.succ C = C(C,L.C)) & for C st C in succ A( ) & C <> 0 & C is limit_ordinal holds L.C = D(C,L|C) ) holds x1 = x2; scheme :: ORDINAL2:sch 8 TSResult0 { F(Ordinal)->set, B()->set, C(Ordinal,set)->set, D(Ordinal, Sequence)->set } : F(0) = B() provided for A,x holds x = F(A) iff ex L st x = last L & dom L = succ A & L. 0 = B() & (for C st succ C in succ A holds L.succ C = C(C,L.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds L.C = D(C,L|C); scheme :: ORDINAL2:sch 9 TSResultS { B()->set, C(Ordinal,set)->set, D(Ordinal,Sequence)->set, F( Ordinal)->set } : for A holds F(succ A) = C(A,F(A)) provided for A,x holds x = F(A) iff ex L st x = last L & dom L = succ A & L. 0 = B() & (for C st succ C in succ A holds L.succ C = C(C,L.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds L.C = D(C,L|C); scheme :: ORDINAL2:sch 10 TSResultL { L()->Sequence, A()->Ordinal, F(Ordinal)->set, B()->set, C( Ordinal,set)->set, D(Ordinal,Sequence)->set } : F(A()) = D(A(),L()) provided for A,x holds x = F(A) iff ex L st x = last L & dom L = succ A & L. 0 = B() & (for C st succ C in succ A holds L.succ C = C(C,L.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds L.C = D(C,L|C) and A() <> 0 & A() is limit_ordinal and dom L() = A() and for A st A in A() holds L().A = F(A); scheme :: ORDINAL2:sch 11 OSExist { A()->Ordinal, B()->Ordinal, C(Ordinal,Ordinal)->Ordinal, D(Ordinal ,Sequence)->Ordinal } : ex fi st dom fi = A() & (0 in A() implies fi.0 = B( ) ) & (for A st succ A in A() holds fi.(succ A) = C(A,fi.A) ) & for A st A in A () & A <> 0 & A is limit_ordinal holds fi.A = D(A,fi|A); scheme :: ORDINAL2:sch 12 OSResult { fi()->Ordinal-Sequence, F(Ordinal)->Ordinal, A()->Ordinal, B()-> Ordinal, C(Ordinal,Ordinal)->Ordinal, D(Ordinal,Sequence)->Ordinal } : for A st A in dom fi() holds fi().A = F(A) provided for A,B holds B = F(A) iff ex fi st B = last fi & dom fi = succ A & fi.0 = B() & (for C st succ C in succ A holds fi.succ C = C(C,fi.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds fi.C = D(C,fi|C) and dom fi() = A() and 0 in A() implies fi().0 = B() and for A st succ A in A() holds fi().(succ A) = C(A,fi().A) and for A st A in A() & A <> 0 & A is limit_ordinal holds fi().A = D(A, fi()|A); scheme :: ORDINAL2:sch 13 OSDef { A()->Ordinal, B()->Ordinal, C(Ordinal,Ordinal)->Ordinal, D(Ordinal, Sequence)->Ordinal } : (ex A,fi st A = last fi & dom fi = succ A() & fi.0 = B() & (for C st succ C in succ A() holds fi.succ C = C(C,fi.C)) & for C st C in succ A() & C <> 0 & C is limit_ordinal holds fi.C = D(C,fi|C) ) & for A1,A2 st (ex fi st A1 = last fi & dom fi = succ A() & fi.0 = B() & (for C st succ C in succ A() holds fi.succ C = C(C,fi.C)) & for C st C in succ A() & C <> 0 & C is limit_ordinal holds fi.C = D(C,fi|C) ) & (ex fi st A2 = last fi & dom fi = succ A() & fi.0 = B() & (for C st succ C in succ A() holds fi.succ C = C(C,fi.C)) & for C st C in succ A() & C <> 0 & C is limit_ordinal holds fi.C = D(C,fi|C) ) holds A1 = A2; scheme :: ORDINAL2:sch 14 OSResult0 { F(Ordinal)->Ordinal, B()->Ordinal, C(Ordinal,Ordinal)->Ordinal, D(Ordinal,Sequence)->Ordinal } : F(0) = B() provided for A,B holds B = F(A) iff ex fi st B = last fi & dom fi = succ A & fi.0 = B() & (for C st succ C in succ A holds fi.succ C = C(C,fi.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds fi.C = D(C,fi|C); scheme :: ORDINAL2:sch 15 OSResultS { B()->Ordinal, C(Ordinal,Ordinal)->Ordinal, D(Ordinal,Sequence) ->Ordinal, F(Ordinal)->Ordinal } : for A holds F(succ A) = C(A,F(A)) provided for A,B holds B = F(A) iff ex fi st B = last fi & dom fi = succ A & fi.0 = B() & (for C st succ C in succ A holds fi.succ C = C(C,fi.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds fi.C = D(C,fi|C); scheme :: ORDINAL2:sch 16 OSResultL { fi()->Ordinal-Sequence, A()->Ordinal, F(Ordinal)->Ordinal, B()-> Ordinal, C(Ordinal,Ordinal)->Ordinal, D(Ordinal,Sequence)->Ordinal } : F(A()) = D(A(),fi()) provided for A,B holds B = F(A) iff ex fi st B = last fi & dom fi = succ A & fi.0 = B() & (for C st succ C in succ A holds fi.succ C = C(C,fi.C)) & for C st C in succ A & C <> 0 & C is limit_ordinal holds fi.C = D(C,fi|C) and A() <> 0 & A() is limit_ordinal and dom fi() = A() and for A st A in A() holds fi().A = F(A); definition let L; func sup L -> Ordinal equals :: ORDINAL2:def 5 sup rng L; func inf L -> Ordinal equals :: ORDINAL2:def 6 inf rng L; end; theorem :: ORDINAL2:26 sup L = sup rng L & inf L = inf rng L; definition let L; func lim_sup L -> Ordinal means :: ORDINAL2:def 7 ex fi st it = inf fi & dom fi = dom L & for A st A in dom L holds fi.A = sup rng (L|(dom L \ A)); func lim_inf L -> Ordinal means :: ORDINAL2:def 8 ex fi st it = sup fi & dom fi = dom L & for A st A in dom L holds fi.A = inf rng (L|(dom L \ A)); end; definition let A,fi; pred A is_limes_of fi means :: ORDINAL2:def 9 ex B st B in dom fi & for C st B c= C & C in dom fi holds fi.C = 0 if A = 0 otherwise for B,C st B in A & A in C ex D st D in dom fi & for E being Ordinal st D c= E & E in dom fi holds B in fi.E & fi.E in C; end; definition let fi; given A such that A is_limes_of fi; func lim fi -> Ordinal means :: ORDINAL2:def 10 it is_limes_of fi; end; definition let A,fi; func lim(A,fi) -> Ordinal equals :: ORDINAL2:def 11 lim(fi|A); end; definition let L be Ordinal-Sequence; attr L is increasing means :: ORDINAL2:def 12 for A,B st A in B & B in dom L holds L.A in L.B; attr L is continuous means :: ORDINAL2:def 13 for A,B st A in dom L & A <> 0 & A is limit_ordinal & B = L.A holds B is_limes_of L|A; end; definition let A,B be Ordinal; func A +^ B -> Ordinal means :: ORDINAL2:def 14 ex fi st it = last fi & dom fi = succ B & fi.0 = A & (for C st succ C in succ B holds fi.succ C = succ(fi.C)) & for C st C in succ B & C <> 0 & C is limit_ordinal holds fi.C = sup(fi|C); end; definition let A,B; func A *^ B -> Ordinal means :: ORDINAL2:def 15 ex fi st it = last fi & dom fi = succ A & fi.0 = 0 & (for C st succ C in succ A holds fi.succ C = (fi.C)+^B) & for C st C in succ A & C <> 0 & C is limit_ordinal holds fi.C = union sup(fi|C); end; registration let O be Ordinal; cluster -> ordinal for Element of O; end; definition let A,B; func exp(A,B) -> Ordinal means :: ORDINAL2:def 16 ex fi st it = last fi & dom fi = succ B & fi.0 = 1 & (for C st succ C in succ B holds fi.succ C = A*^(fi.C)) & for C st C in succ B & C <> 0 & C is limit_ordinal holds fi.C = lim(fi|C); end; theorem :: ORDINAL2:27 A+^0 = A; theorem :: ORDINAL2:28 A+^succ B = succ(A+^B); theorem :: ORDINAL2:29 B <> 0 & B is limit_ordinal implies for fi st dom fi = B & for C st C in B holds fi.C = A+^C holds A+^B = sup fi; theorem :: ORDINAL2:30 0+^A = A; theorem :: ORDINAL2:31 A+^1 = succ A; theorem :: ORDINAL2:32 A in B implies C +^ A in C +^ B; theorem :: ORDINAL2:33 A c= B implies C +^ A c= C +^ B; theorem :: ORDINAL2:34 A c= B implies A +^ C c= B +^ C; theorem :: ORDINAL2:35 0*^A = 0; theorem :: ORDINAL2:36 (succ B)*^A = B*^A +^ A; theorem :: ORDINAL2:37 B <> 0 & B is limit_ordinal implies for fi st dom fi = B & for C st C in B holds fi.C = C*^A holds B*^A = union sup fi; theorem :: ORDINAL2:38 A*^0 = 0; theorem :: ORDINAL2:39 1*^A = A & A*^1 = A; theorem :: ORDINAL2:40 C <> 0 & A in B implies A*^C in B*^C; theorem :: ORDINAL2:41 A c= B implies A*^C c= B*^C; theorem :: ORDINAL2:42 A c= B implies C*^A c= C*^B; theorem :: ORDINAL2:43 exp(A,0) = 1; theorem :: ORDINAL2:44 exp(A,succ B) = A*^exp(A,B); theorem :: ORDINAL2:45 B <> 0 & B is limit_ordinal implies for fi st dom fi = B & for C st C in B holds fi.C = exp(A,C) holds exp(A,B) = lim fi; theorem :: ORDINAL2:46 exp(A,1) = A & exp(1,A) = 1; theorem :: ORDINAL2:47 for A ex B,C st B is limit_ordinal & C is natural & A = B +^ C; :: 2005.05.04, A.T. registration let X be set, o be Ordinal; cluster X --> o -> Ordinal-yielding; end; registration let O be Ordinal, x be object; cluster O --> x -> Sequence-like; end; :: from ZFREFLE1, 2007.03.14, A.T. definition let A,B be Ordinal; pred A is_cofinal_with B means :: ORDINAL2:def 17 ex xi being Ordinal-Sequence st dom xi = B & rng xi c= A & xi is increasing & A = sup xi; reflexivity; end; reserve e,u for set; theorem :: ORDINAL2:48 e in rng psi implies e is Ordinal; theorem :: ORDINAL2:49 rng psi c= sup psi; theorem :: ORDINAL2:50 A is_cofinal_with 0 implies A = 0; :: from ARYTM_3, 2007.10.23, A.T. scheme :: ORDINAL2:sch 17 OmegaInd {a()-> Nat, P[object]}: P[a()] provided P[0] and for a being Nat st P[a] holds P[succ a]; registration let a, b be Nat; cluster a +^ b -> natural; end; :: from AMI_2, 2008.02.14, A.T. registration let x,y be set, a,b be Nat; cluster IFEQ(x,y,a,b) -> natural; end; :: 2010.03.16, A.T. scheme :: ORDINAL2:sch 18 LambdaRecEx{A() -> set,G(set,set) -> set}: ex f being Function st dom f = omega & f.0 = A() & for n being Nat holds f.succ n = G(n,f.n); reserve n for Nat; scheme :: ORDINAL2:sch 19 RecUn{A() -> set, F, G() -> Function, P[set,set,set]}: F() = G() provided dom F() = omega and F().0 = A() and for n holds P[n,F().n,F().(succ n)] and dom G() = omega and G().0 = A() and for n holds P[n,G().n,G().(succ n)] and for n for x,y1,y2 being set st P[n,x,y1] & P[n,x,y2] holds y1 = y2; scheme :: ORDINAL2:sch 20 LambdaRecUn{A() -> set, F(set,set) -> set, F, G() -> Function}: F() = G() provided dom F() = omega and F().0 = A() and for n holds F().(succ n) = F(n,F().n) and dom G() = omega and G().0 = A() and for n holds G().(succ n) = F(n,G().n);