:: Preliminaries to Structures
:: by Library Committee
::
:: Received January 6, 1995
:: Copyright (c) 1995 Association of Mizar Users

begin

definition

attr c₁ is strict ;
struct 1-sorted -> ;
aggr 1-sorted(# carrier #) -> 1-sorted ;
sel carrier c₁ -> set ;

end;

definition

let S be 1-sorted ;
attr S is empty means :Def1: :: STRUCT_0:def 1
the carrier of S is empty ;

end;

:: deftheorem Def1 defines empty STRUCT_0:def 1 :
for S being 1-sorted holds
( S is empty iff the carrier of S is empty );

registration

cluster strict empty 1-sorted ;
existence
ex b₁ being 1-sorted st
( b₁ is strict & b₁ is empty )

proof end;

end;

registration

cluster strict non empty 1-sorted ;
existence
ex b₁ being 1-sorted st
( b₁ is strict & not b₁ is empty )

proof end;

end;

registration

let S be empty 1-sorted ;
cluster the carrier of S -> empty ;
coherence
the carrier of S is empty by Def1;

end;

registration

let S be non empty 1-sorted ;
cluster the carrier of S -> non empty ;
coherence
not the carrier of S is empty by Def1;

end;

definition

let S be 1-sorted ;
mode Element of S is Element of the carrier of S;
mode Subset of S is Subset of the carrier of S;
mode Subset-Family of S is Subset-Family of the carrier of S;

end;

definition

let S be 1-sorted ;
let X be set ;
mode Function of S,X is Function of the carrier of S,X;
mode Function of X,S is Function of X, the carrier of S;

end;

definition

let S, T be 1-sorted ;
mode Function of S,T is Function of the carrier of S, the carrier of T;

end;

definition

let T be 1-sorted ;
func {} T -> Subset of T equals :: STRUCT_0:def 2
{} ;
coherence
{} is Subset of T

proof end;

func [#] T -> Subset of T equals :: STRUCT_0:def 3
the carrier of T;
coherence
the carrier of T is Subset of T

proof end;

end;

:: deftheorem defines {} STRUCT_0:def 2 :
for T being 1-sorted holds {} T = {} ;

:: deftheorem defines [#] STRUCT_0:def 3 :
for T being 1-sorted holds [#] T = the carrier of T;

registration

let T be 1-sorted ;
cluster {} T -> empty ;
coherence
{} T is empty ;

end;

registration

let T be empty 1-sorted ;
cluster [#] T -> empty ;
coherence
[#] T is empty ;

end;

registration

let T be non empty 1-sorted ;
cluster [#] T -> non empty ;
coherence
not [#] T is empty ;

end;

registration

let S be non empty 1-sorted ;
cluster non empty Element of K21( the carrier of S);
existence
not for b₁ being Subset of S holds b₁ is empty

proof end;

end;

definition

let S be 1-sorted ;
mode FinSequence of S is FinSequence of the carrier of S;

end;

definition

let S be 1-sorted ;
mode ManySortedSet of S is ManySortedSet of the carrier of S;

end;

definition

let S be 1-sorted ;
func id S -> Function of S,S equals :: STRUCT_0:def 4
id the carrier of S;
coherence
id the carrier of S is Function of S,S ;

end;

:: deftheorem defines id STRUCT_0:def 4 :
for S being 1-sorted holds id S = id the carrier of S;

definition

let S be 1-sorted ;
mode sequence of S is sequence of the carrier of S;

end;

definition

let S be 1-sorted ;
let X be set ;
mode PartFunc of S,X is PartFunc of the carrier of S,X;
mode PartFunc of X,S is PartFunc of X, the carrier of S;

end;

definition

let S, T be 1-sorted ;
mode PartFunc of S,T is PartFunc of the carrier of S, the carrier of T;

end;

definition

let S be 1-sorted ;
let x be set ;
pred x in S means :: STRUCT_0:def 5
x in the carrier of S;

end;

:: deftheorem defines in STRUCT_0:def 5 :
for S being 1-sorted
for x being set holds
( x in S iff x in the carrier of S );

definition

attr c₁ is strict ;
struct ZeroStr -> 1-sorted ;
aggr ZeroStr(# carrier, ZeroF #) -> ZeroStr ;
sel ZeroF c₁ -> Element of the carrier of c₁;

end;

registration

cluster non empty strict ZeroStr ;
existence
ex b₁ being ZeroStr st
( b₁ is strict & not b₁ is empty )

proof end;

end;

definition

attr c₁ is strict ;
struct OneStr -> 1-sorted ;
aggr OneStr(# carrier, OneF #) -> OneStr ;
sel OneF c₁ -> Element of the carrier of c₁;

end;

definition

attr c₁ is strict ;
struct ZeroOneStr -> ZeroStr , OneStr ;
aggr ZeroOneStr(# carrier, ZeroF, OneF #) -> ZeroOneStr ;

end;

definition

let S be ZeroStr ;
func 0. S -> Element of S equals :: STRUCT_0:def 6
the ZeroF of S;
coherence
the ZeroF of S is Element of S ;

end;

:: deftheorem defines 0. STRUCT_0:def 6 :
for S being ZeroStr holds 0. S = the ZeroF of S;

definition

let S be OneStr ;
func 1. S -> Element of S equals :: STRUCT_0:def 7
the OneF of S;
coherence
the OneF of S is Element of S ;

end;

:: deftheorem defines 1. STRUCT_0:def 7 :
for S being OneStr holds 1. S = the OneF of S;

definition

let S be ZeroOneStr ;
attr S is degenerated means :Def8: :: STRUCT_0:def 8
0. S = 1. S;

end;

:: deftheorem Def8 defines degenerated STRUCT_0:def 8 :
for S being ZeroOneStr holds
( S is degenerated iff 0. S = 1. S );

definition

let IT be 1-sorted ;
attr IT is trivial means :Def9: :: STRUCT_0:def 9
the carrier of IT is trivial ;

end;

:: deftheorem Def9 defines trivial STRUCT_0:def 9 :
for IT being 1-sorted holds
( IT is trivial iff the carrier of IT is trivial );

registration

cluster empty -> trivial 1-sorted ;
coherence
for b₁ being 1-sorted st b₁ is empty holds
b₁ is trivial

proof end;

cluster non trivial -> non empty 1-sorted ;
coherence
for b₁ being 1-sorted st not b₁ is trivial holds
not b₁ is empty ;

end;

definition

let S be 1-sorted ;
redefine attr S is trivial means :Def10: :: STRUCT_0:def 10
for x, y being Element of S holds x = y;
compatibility
( S is trivial iff for x, y being Element of S holds x = y )

proof end;

end;

:: deftheorem Def10 defines trivial STRUCT_0:def 10 :
for S being 1-sorted holds
( S is trivial iff for x, y being Element of S holds x = y );

registration

cluster non degenerated -> non trivial ZeroOneStr ;
coherence
for b₁ being ZeroOneStr st not b₁ is degenerated holds
not b₁ is trivial

proof end;

end;

registration

cluster non empty trivial 1-sorted ;
existence
ex b₁ being 1-sorted st
( b₁ is trivial & not b₁ is empty )

proof end;

cluster non empty non trivial 1-sorted ;
existence
ex b₁ being 1-sorted st
( not b₁ is trivial & not b₁ is empty )

proof end;

end;

registration

let S be non trivial 1-sorted ;
cluster the carrier of S -> non trivial ;
coherence
not the carrier of S is trivial by Def9;

end;

registration

let S be trivial 1-sorted ;
cluster the carrier of S -> trivial ;
coherence
the carrier of S is trivial by Def9;

end;

begin

definition

let S be 1-sorted ;
attr S is finite means :Def11: :: STRUCT_0:def 11
the carrier of S is finite ;

end;

:: deftheorem Def11 defines finite STRUCT_0:def 11 :
for S being 1-sorted holds
( S is finite iff the carrier of S is finite );

registration

cluster strict non empty finite 1-sorted ;
existence
ex b₁ being 1-sorted st
( b₁ is strict & b₁ is finite & not b₁ is empty )

proof end;

end;

registration

let S be finite 1-sorted ;
cluster the carrier of S -> finite ;
coherence
the carrier of S is finite by Def11;

end;

registration

cluster empty -> empty finite 1-sorted ;
coherence
for b₁ being empty 1-sorted holds b₁ is finite

proof end;

end;

notation

let S be 1-sorted ;
antonym infinite S for finite ;

end;

registration

cluster strict infinite 1-sorted ;
existence
ex b₁ being 1-sorted st
( b₁ is strict & not b₁ is finite )

proof end;

end;

registration

let S be infinite 1-sorted ;
cluster the carrier of S -> infinite ;
coherence
not the carrier of S is finite by Def11;

end;

registration

cluster infinite -> non empty infinite 1-sorted ;
coherence
for b₁ being infinite 1-sorted holds not b₁ is empty ;

end;

registration

cluster trivial -> finite 1-sorted ;
coherence
for b₁ being 1-sorted st b₁ is trivial holds
b₁ is finite

proof end;

end;

registration

cluster infinite -> non trivial 1-sorted ;
coherence
for b₁ being 1-sorted st not b₁ is finite holds
not b₁ is trivial ;

end;

definition

let S be ZeroStr ;
let x be Element of S;
attr x is zero means :Def12: :: STRUCT_0:def 12
x = 0. S;

end;

:: deftheorem Def12 defines zero STRUCT_0:def 12 :
for S being ZeroStr
for x being Element of S holds
( x is zero iff x = 0. S );

registration

let S be ZeroStr ;
cluster 0. S -> zero ;
coherence
0. S is zero by Def12;

end;

registration

cluster strict non degenerated ZeroOneStr ;
existence
ex b₁ being ZeroOneStr st
( b₁ is strict & not b₁ is degenerated )

proof end;

end;

registration

let S be non degenerated ZeroOneStr ;
cluster 1. S -> non zero ;
coherence
not 1. S is zero

proof end;

end;

definition

let S be 1-sorted ;
mode Cover of S is Cover of the carrier of S;

end;

registration

let S be 1-sorted ;
cluster [#] S -> non proper ;
coherence
not [#] S is proper

proof end;

end;

begin

definition

attr c₁ is strict ;
struct 2-sorted -> 1-sorted ;
aggr 2-sorted(# carrier, carrier' #) -> 2-sorted ;
sel carrier' c₁ -> set ;

end;

definition

let S be 2-sorted ;
attr S is void means :Def13: :: STRUCT_0:def 13
the carrier' of S is empty ;

end;

:: deftheorem Def13 defines void STRUCT_0:def 13 :
for S being 2-sorted holds
( S is void iff the carrier' of S is empty );

registration

cluster empty strict void 2-sorted ;
existence
ex b₁ being 2-sorted st
( b₁ is strict & b₁ is empty & b₁ is void )

proof end;

end;

registration

let S be void 2-sorted ;
cluster the carrier' of S -> empty ;
coherence
the carrier' of S is empty by Def13;

end;

registration

cluster non empty strict non void 2-sorted ;
existence
ex b₁ being 2-sorted st
( b₁ is strict & not b₁ is empty & not b₁ is void )

proof end;

end;

registration

let S be non void 2-sorted ;
cluster the carrier' of S -> non empty ;
coherence
not the carrier' of S is empty by Def13;

end;

definition

let X be 1-sorted ;
let Y be non empty 1-sorted ;
let y be Element of Y;
func X --> y -> Function of X,Y equals :: STRUCT_0:def 14
the carrier of X --> y;
coherence
the carrier of X --> y is Function of X,Y ;

end;

:: deftheorem defines --> STRUCT_0:def 14 :
for X being 1-sorted
for Y being non empty 1-sorted
for y being Element of Y holds X --> y = the carrier of X --> y;

registration

let S be ZeroStr ;
cluster zero Element of the carrier of S;
existence
ex b₁ being Element of S st b₁ is zero

proof end;

end;

registration

cluster strict non trivial ZeroStr ;
existence
ex b₁ being ZeroStr st
( b₁ is strict & not b₁ is trivial )

proof end;

end;

registration

let S be non trivial ZeroStr ;
cluster non zero Element of the carrier of S;
existence
not for b₁ being Element of S holds b₁ is zero

proof end;

end;

definition

canceled;
let X be set ;
let S be ZeroStr ;
let R be Relation of X, the carrier of S;
attr R is non-zero means :: STRUCT_0:def 16
not 0. S in rng R;

end;

:: deftheorem STRUCT_0:def 15 :
canceled;

:: deftheorem defines non-zero STRUCT_0:def 16 :
for X being set
for S being ZeroStr
for R being Relation of X, the carrier of S holds
( R is non-zero iff not 0. S in rng R );

definition

let S be 1-sorted ;
func card S -> Cardinal equals :: STRUCT_0:def 17
card the carrier of S;
coherence
card the carrier of S is Cardinal ;

end;

:: deftheorem defines card STRUCT_0:def 17 :
for S being 1-sorted holds card S = card the carrier of S;

definition

let S be 1-sorted ;
mode UnOp of S is UnOp of the carrier of S;
mode BinOp of S is BinOp of the carrier of S;

end;

definition

let S be ZeroStr ;
func NonZero S -> Subset of S equals :: STRUCT_0:def 18
([#] S) \ {(0. S)};
coherence
([#] S) \ {(0. S)} is Subset of S ;

end;

:: deftheorem defines NonZero STRUCT_0:def 18 :
for S being ZeroStr holds NonZero S = ([#] S) \ {(0. S)};

theorem :: STRUCT_0:1

for S being non empty ZeroStr
for u being Element of S holds
( u in NonZero S iff not u is zero )

proof end;

definition

let V be non empty ZeroStr ;
redefine attr V is trivial means :Def19: :: STRUCT_0:def 19
for u being Element of V holds u = 0. V;
compatibility
( V is trivial iff for u being Element of V holds u = 0. V )

proof end;

end;

:: deftheorem Def19 defines trivial STRUCT_0:def 19 :
for V being non empty ZeroStr holds
( V is trivial iff for u being Element of V holds u = 0. V );

registration

let V be non trivial ZeroStr ;
cluster NonZero V -> non empty ;
coherence
not NonZero V is empty

proof end;

end;

registration

let S be non empty 1-sorted ;
cluster non empty trivial Element of K21( the carrier of S);
existence
ex b₁ being Subset of S st
( not b₁ is empty & b₁ is trivial )

proof end;

end;

theorem :: STRUCT_0:2

for F being non degenerated ZeroOneStr holds 1. F in NonZero F

proof end;