Thread: Prove/disprove these two claims

I'm having trouble understanding this pair of claims:

So g is some function whose result is greater or equal to 0... but I don't really get what the rest of the claim means.
Could someone please explain them to me?
Thanks in advance.

: For any two functions and from the set ,

: the fact that the function is in the set

: implies that

: is in the set

: and

: is in the set

Thanks for the explanation.
So the first claim would be true right? If neither f nor g could be positive, then one of f or g must be smaller than f + g; and if f + g is smaller than c*h(n), then f/g is also smaller than c*h(n)?
And the second would be false? Since either f or g could be greater than f + g if one of them is smaller than 1, then one of them could be greater than c*h(n)?

I agree that the answers are true for (1) and false for (2). However, your explanation makes no sense to me. First thing:

If neither f nor g could be positive

Why could they not be positive?

Oops typo, I meant neither could be negative. ~

So the first claim would be true right? If neither f nor g could be negative, then one of f or g must be smaller than f + g; and if f + g is smaller than c*h(n), then f/g is also smaller than c*h(n)?

Ah, now I see. Another reason I was confused is f/g. This problem defines f + g as a function, so, by analogy, I thought that f/g is a function defined by (f/g)(x) = f(x) / g(x). I could not see how division fits the first problem.

Finally, it would help to be consistent about the distinction between a function as a whole and its value at a particular point. Namely, in the phrase "f + g is smaller than c*h(n)", f + g is a function and c*h(n) is a number (and what is n)? At the risk of being pedantic, one could write, "if, for all n >= B, (f + g)(n) is smaller than c*h(n), then so are f(n) and g(n)".

And the second would be false? Since either f or g could be greater than f + g if one of them is smaller than 1, then one of them could be greater than c*h(n)?

Do you mean f * g rather than f + g? Then yes, that makes sense.

Originally Posted by emakarov

Ah, now I see. Another reason I was confused is f/g. This problem defines f + g as a function, so, by analogy, I thought that f/g is a function defined by (f/g)(x) = f(x) / g(x). I could not see how division fits the first problem.

Finally, it would help to be consistent about the distinction between a function as a whole and its value at a particular point. Namely, in the phrase "f + g is smaller than c*h(n)", f + g is a function and c*h(n) is a number (and what is n)? At the risk of being pedantic, one could write, "if, for all n >= B, (f + g)(n) is smaller than c*h(n), then so are f(n) and g(n)".

Oh yes I meant "f or g" by the f/g. So basically for the proof all I need to write is something along the lines of "since (f+g)(n) <= c*h(n), and individually f(n) and g(n) <= (f+g)(n) since both could only be positive, then f(n) <= c*h(n) and g(n) <= c*h(n)?

Originally Posted by emakarov

Do you mean f * g rather than f + g? Then yes, that makes sense.

Oh yes I meant f*g. Lol I think I was falling asleep when I wrote that.

So basically for the proof all I need to write is something along the lines of "since (f+g)(n) <= c*h(n), and individually f(n) and g(n) <= (f+g)(n) since both could only be nonnegative, then f(n) <= c*h(n) and g(n) <= c*h(n)?

Yes, provided it is obvious to you how to relate f(n) <= c*h(n) and -- it is this fact that you need ultimately to show. (This is indeed obvious.)