let f, g be eventually-nonnegative Real_Sequence; :: thesis: ( Big_Oh f = Big_Oh g iff f in Big_Theta g )

hereby :: thesis: ( f in Big_Theta g implies Big_Oh f = Big_Oh g )

assume A1: Big_Oh f = Big_Oh g ; :: thesis: f in Big_Theta g
then A2: f in Big_Oh g by ASYMPT_0:10;
g in Big_Oh f by A1, ASYMPT_0:10;
then f in Big_Omega g by ASYMPT_0:19;
hence f in Big_Theta g by A2, XBOOLE_0:def 4; :: thesis: verum

end;

assume A3: f in Big_Theta g ; :: thesis: Big_Oh f = Big_Oh g

now

let x be set ; :: thesis: ( ( x in Big_Oh f implies x in Big_Oh g ) & ( x in Big_Oh g implies x in Big_Oh f ) )

hereby :: thesis: ( x in Big_Oh g implies x in Big_Oh f )

assume x in Big_Oh f ; :: thesis: x in Big_Oh g
then consider t being Element of Funcs NAT ,REAL such that
A4: x = t and
A5: ex c being Real ex N being Element of NAT st
( c > 0 & ( for n being Element of NAT st n >= N holds
( t . n <= c * (f . n) & t . n >= 0 ) ) ) ;
consider c being Real, N being Element of NAT such that
c > 0 and
A6: for n being Element of NAT st n >= N holds
( t . n <= c * (f . n) & t . n >= 0 ) by A5;

now

take N = N; :: thesis: for n being Element of NAT st n >= N holds
t . n >= 0
let n be Element of NAT ; :: thesis: ( n >= N implies t . n >= 0 )
assume n >= N ; :: thesis: t . n >= 0
hence t . n >= 0 by A6; :: thesis: verum

end;

then A7: t is eventually-nonnegative by ASYMPT_0:def 4;
A8: t in Big_Oh f by A5;
f in Big_Oh g by A3, XBOOLE_0:def 4;
hence x in Big_Oh g by A4, A7, A8, ASYMPT_0:12; :: thesis: verum

end;

assume x in Big_Oh g ; :: thesis: x in Big_Oh f
then consider t being Element of Funcs NAT ,REAL such that
A9: x = t and
A10: ex c being Real ex N being Element of NAT st
( c > 0 & ( for n being Element of NAT st n >= N holds
( t . n <= c * (g . n) & t . n >= 0 ) ) ) ;
consider c being Real, N being Element of NAT such that
c > 0 and
A11: for n being Element of NAT st n >= N holds
( t . n <= c * (g . n) & t . n >= 0 ) by A10;

now

take N = N; :: thesis: for n being Element of NAT st n >= N holds
t . n >= 0
let n be Element of NAT ; :: thesis: ( n >= N implies t . n >= 0 )
assume n >= N ; :: thesis: t . n >= 0
hence t . n >= 0 by A11; :: thesis: verum

end;

then A12: t is eventually-nonnegative by ASYMPT_0:def 4;
A13: t in Big_Oh g by A10;
f in Big_Omega g by A3, XBOOLE_0:def 4;
then g in Big_Oh f by ASYMPT_0:19;
hence x in Big_Oh f by A9, A12, A13, ASYMPT_0:12; :: thesis: verum

end;

hence Big_Oh f = Big_Oh g by TARSKI:2; :: thesis: verum