:: The Ordinal Numbers. Transfinite Induction and Defining by
:: Transfinite Induction
:: by Grzegorz Bancerek
::
:: Received March 20, 1989
:: 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 TARSKI, XBOOLE_0, SUBSET_1, FUNCT_1, RELAT_1, ZFMISC_1, ORDINAL1,
CARD_1, XCMPLX_0, NAT_1, VALUED_0, QUANTAL1, FREEALG, SETFAM_1;
notations TARSKI, XBOOLE_0, ZFMISC_1, ENUMSET1, XTUPLE_0, SUBSET_1, SETFAM_1,
RELAT_1, FUNCT_1;
constructors TARSKI, ENUMSET1, SUBSET_1, FUNCT_1, XTUPLE_0, SETFAM_1;
registrations XBOOLE_0, SUBSET_1, RELAT_1, FUNCT_1, ZFMISC_1;
requirements SUBSET, BOOLE;
begin
reserve X,Y,Z,X1,X2,X3,X4,X5,X6 for set, x,y for object;
::$CT 4
theorem :: ORDINAL1:5
Y in X implies not X c= Y;
definition
let X;
func succ X -> set equals
:: ORDINAL1:def 1
X \/ { X };
end;
registration
let X;
cluster succ X -> non empty;
end;
theorem :: ORDINAL1:6
X in succ X;
theorem :: ORDINAL1:7
succ X = succ Y implies X = Y;
theorem :: ORDINAL1:8
x in succ X iff x in X or x = X;
theorem :: ORDINAL1:9
X <> succ X;
::
:: 3. epsilon-transitivity & epsilon-connectedness
::
reserve a,b,c for object, X,Y,Z,x,y,z for set;
definition
let X;
attr X is epsilon-transitive means
:: ORDINAL1:def 2
for x st x in X holds x c= X;
attr X is epsilon-connected means
:: ORDINAL1:def 3
for x,y st x in X & y in X holds x in y or x = y or y in x;
end;
::
:: 4. Definition of ordinal numbers - Ordinal
::
registration
cluster epsilon-transitive epsilon-connected for set;
end;
definition
let IT be object;
attr IT is ordinal means
:: ORDINAL1:def 4
IT is epsilon-transitive epsilon-connected set;
end;
registration
cluster ordinal -> epsilon-transitive epsilon-connected for set;
cluster epsilon-transitive epsilon-connected -> ordinal for set;
end;
notation
synonym Number for object;
synonym number for set;
end;
registration
cluster ordinal for number;
end;
registration
cluster ordinal for Number;
end;
definition
mode Ordinal is ordinal number;
end;
reserve A,B,C,D for Ordinal;
theorem :: ORDINAL1:10
for A,B being set, C being epsilon-transitive set st A in B & B in C
holds A in C;
theorem :: ORDINAL1:11
for x being epsilon-transitive set, A being Ordinal st x c< A holds x in A;
theorem :: ORDINAL1:12
for A being epsilon-transitive set, B, C being Ordinal st A c= B & B
in C holds A in C;
theorem :: ORDINAL1:13
a in A implies a is Ordinal;
theorem :: ORDINAL1:14
A in B or A = B or B in A;
definition
let A,B;
redefine pred A c= B means
:: ORDINAL1:def 5
for C st C in A holds C in B;
connectedness;
end;
theorem :: ORDINAL1:15
A,B are_c=-comparable;
theorem :: ORDINAL1:16
A c= B or B in A;
registration
cluster empty -> ordinal for number;
end;
theorem :: ORDINAL1:17
x is Ordinal implies succ x is Ordinal;
theorem :: ORDINAL1:18
x is ordinal implies union x is epsilon-transitive epsilon-connected;
registration
cluster non empty for Ordinal;
end;
registration
let A;
cluster succ A -> non empty ordinal;
cluster union A -> ordinal;
end;
theorem :: ORDINAL1:19
(for x st x in X holds x is Ordinal & x c= X) implies
X is epsilon-transitive epsilon-connected;
theorem :: ORDINAL1:20
X c= A & X <> {} implies ex C st C in X & for B st B in X holds C c= B;
theorem :: ORDINAL1:21
A in B iff succ A c= B;
theorem :: ORDINAL1:22
A in succ C iff A c= C;
::
:: 6. Transfinite induction and principle of minimum of ordinals
::
scheme :: ORDINAL1:sch 1
OrdinalMin { P[Ordinal] } : ex A st P[A] & for B st P[B] holds A c= B
provided
ex A st P[A];
::$N Transfinite induction
scheme :: ORDINAL1:sch 2
TransfiniteInd { P[Ordinal] } : for A holds P[A]
provided
for A st for C st C in A holds P[C] holds P[A];
::
:: 7. Properties of sets of ordinals
::
theorem :: ORDINAL1:23
for X st for a st a in X holds a is Ordinal
holds union X is epsilon-transitive epsilon-connected;
theorem :: ORDINAL1:24
for X st for a st a in X holds a is Ordinal ex A st X c= A;
theorem :: ORDINAL1:25
not ex X st for x holds x in X iff x is Ordinal;
theorem :: ORDINAL1:26
not ex X st for A holds A in X;
theorem :: ORDINAL1:27
for X ex A st not A in X & for B st not B in X holds A c= B;
::
:: 8. Limit ordinals
::
definition
let A be set;
attr A is limit_ordinal means
:: ORDINAL1:def 6
A = union A;
end;
theorem :: ORDINAL1:28
for A holds A is limit_ordinal iff for C st C in A holds succ C in A;
theorem :: ORDINAL1:29
not A is limit_ordinal iff ex B st A = succ B;
reserve F,G for Function;
::
:: 9. Transfinite sequences
::
definition
let IT be set;
attr IT is Sequence-like means
:: ORDINAL1:def 7
proj1 IT is epsilon-transitive epsilon-connected;
end;
registration
cluster empty -> Sequence-like for set;
end;
definition
mode Sequence is Sequence-like Function;
end;
registration
let Z;
cluster Z-valued for Sequence;
end;
definition
let Z;
mode Sequence of Z is Z-valued Sequence;
end;
theorem :: ORDINAL1:30
{} is Sequence of Z;
reserve L,L1 for Sequence;
theorem :: ORDINAL1:31
dom F is Ordinal implies F is Sequence of rng F;
registration
let L;
cluster dom L -> ordinal;
end;
theorem :: ORDINAL1:32
X c= Y implies for L being Sequence of X holds L is Sequence of Y;
registration
let L,A;
cluster L|A -> rng L-valued Sequence-like;
end;
theorem :: ORDINAL1:33
for L being Sequence of X for A holds L|A is Sequence of X;
definition
let IT be set;
attr IT is c=-linear means
:: ORDINAL1:def 8
for x,y being set st x in IT & y in IT holds x,y are_c=-comparable;
end;
theorem :: ORDINAL1:34
(for a st a in X holds a is Sequence) & X is c=-linear implies
union X is Sequence;
::
:: 10. Schemes of definability by transfinite induction
::
scheme :: ORDINAL1:sch 3
TSUniq { A()->Ordinal, H(Sequence)->set, L1, L2() -> Sequence } : L1() =
L2()
provided
dom L1() = A() & for B,L st B in A() & L = L1()|B holds L1().B = H(L ) and
dom L2() = A() & for B,L st B in A() & L = L2()|B holds L2().B = H(L );
scheme :: ORDINAL1:sch 4
TSExist { A()->Ordinal,H(Sequence)->set } : ex L st dom L = A() & for B,L1
st B in A() & L1 = L|B holds L.B = H(L1);
scheme :: ORDINAL1:sch 5
FuncTS { L() -> Sequence, F(Ordinal)->set, H(Sequence)->set } :
for B st B in dom L() holds L().B = H(L()|B)
provided
for A,a holds a = F(A) iff ex L st a = H(L) & dom L = A & for B st B
in A holds L.B = H(L|B) and
for A st A in dom L() holds L().A = F(A);
theorem :: ORDINAL1:35
A c< B or A = B or B c< A;
begin :: Addenda
:: moved from ORDINAL2, 2006.06.22, A.T.
definition
let X;
func On X -> set means
:: ORDINAL1:def 9
for x being object holds x in it iff x in X & x is Ordinal;
func Lim X -> set means
:: ORDINAL1:def 10
for x being object holds x in it iff
x in X & ex A st x = A & A is limit_ordinal;
end;
::$N Generalized Axiom of Infinity
theorem :: ORDINAL1:36
for D ex A st D in A & A is limit_ordinal;
definition
func omega -> set means
:: ORDINAL1:def 11
{} in it & it is limit_ordinal & it is
ordinal & for A st {} in A & A is limit_ordinal holds it c= A;
end;
registration
cluster omega -> non empty ordinal;
end;
definition
let A be object;
attr A is natural means
:: ORDINAL1:def 12
A in omega;
end;
registration
cluster natural for Number;
cluster natural for set;
end;
definition
mode Nat is natural set;
end;
registration
sethood of Nat;
end;
:: from ARYTM_3, 2006.05.26
registration
let A be Ordinal;
cluster -> ordinal for Element of A;
end;
:: missing, 2006.06.25, A.T.
registration
cluster natural -> ordinal for number;
end;
:: from ZF_REFLE, 2007,03.13, A.T.
scheme :: ORDINAL1:sch 6
ALFA { D() -> non empty set, P[object,object] }:
ex F st dom F = D() & for d being
Element of D() ex A st A = F.d & P[d,A] & for B st P[d,B] holds A c= B
provided
for d being Element of D() ex A st P[d,A];
:: from CARD_4, 2007.08.06, A.T.
theorem :: ORDINAL1:37
succ X \ {X} = X;
:: from ARYTM_3, 2007.09.16, A.T.
registration
cluster empty -> natural for number;
cluster -> natural for Element of omega;
end;
registration
cluster non empty natural for number;
end;
:: from ARYTM_3, 2007.10.23, A.T.
registration
let a be natural Ordinal;
cluster succ a -> natural;
end;
:: from DILWORTH, 2011.07.31,A.T.
registration
cluster empty -> c=-linear for set;
end;
registration let X be c=-linear set;
cluster -> c=-linear for Subset of X;
end;
::$CT
definition
func 0 -> set equals
:: ORDINAL1:def 13
{};
end;
registration
cluster 0 -> natural;
end;
definition
let x be Number;
attr x is zero means
:: ORDINAL1:def 14
x = 0;
end;
registration
cluster 0 -> zero;
cluster zero for Number;
cluster zero for set;
end;
registration
cluster zero -> natural for Number;
end;
registration
cluster non zero for Number;
end;
registration
cluster zero -> trivial for set;
cluster non trivial -> non zero for set;
end;
definition let R be Relation;
attr R is non-zero means
:: ORDINAL1:def 15
not 0 in rng R;
end;
definition let X be set;
attr X is with_zero means
:: ORDINAL1:def 16
0 in X;
end;
notation let X be set;
antonym X is without_zero for X is with_zero;
end;
registration
cluster empty -> without_zero for set;
end;
registration
cluster empty -> non-zero for Relation;
end;
registration
cluster without_zero non empty for set;
end;
registration let X be without_zero non empty set;
cluster -> non zero for Element of X;
end;
registration
cluster non-zero for Relation;
cluster non non-zero for Relation;
end;
registration let R be non-zero Relation;
cluster rng R -> without_zero;
end;
registration let R be non non-zero Relation;
cluster rng R -> with_zero;
end;
registration let R be non-zero Relation, S be Relation;
cluster S*R -> non-zero;
end;
:: to be removed
registration
cluster without_zero -> with_non-empty_elements for set;
cluster with_zero -> non with_non-empty_elements for set;
cluster with_non-empty_elements -> without_zero for set;
cluster non with_non-empty_elements -> with_zero for set;
end;
definition let o be object;
func Segm o -> set equals
:: ORDINAL1:def 17
o;
end;
registration let n be Ordinal;
cluster Segm n -> ordinal;
end;
registration let n be zero Ordinal;
cluster Segm n -> empty;
end;