Understanding Asymptotic Notation (Big Oh & Little Oh)

[Rasalhague]

Have I got the following definitions right. That's to say, do they express the idea behind "big oh" and "little oh" notation, using essentially the same symbols as are traditionally used. Is the syntax unambiguous? Are there any more assumptions I need to state?

Let f,g:S \subseteq \mathbb{R} \mapsto \mathbb{R}. Let x, x_0 \in \mathbb{R}.

O(g,x_0) := \left \{ f \; | \; \pmb{\exists} \varepsilon > 0 \exists \delta > 0 \forall x(|x-x_0| < \delta \Rightarrow \right |f(x)| \leq \varepsilon \cdot |g(x)| )\}

o(g,x_0) := \left \{ f \; | \; \pmb{\forall} \varepsilon > 0 \exists \delta > 0 \forall x(|x-x_0| < \delta \Rightarrow \right |f(x)| \leq \varepsilon \cdot |g(x)| )\}

These first two expressions differ from each other only in the first quantifier.

O(g,\infty) := \left \{ f \; | \; \pmb{\exists} \varepsilon > 0 \exists \delta > 0 \forall x(\pmb{x >} \delta \Rightarrow \right |f(x)| \leq \varepsilon \cdot |g(x)| )\}

o(g,\infty) := \left \{ f \; | \; \pmb{\forall} \varepsilon > 0 \exists \delta > 0 \forall x(\pmb{x >} \delta \Rightarrow \right |f(x)| \leq \varepsilon \cdot |g(x)| )\}

This second pair of expressions differ from first pair in that |x-x_0| < \delta has become x > \delta.

Let O(g,-\infty) and o(g,-\infty) be defined by modifying the second pair in the obvious way, that is, by reversing the inequalities:

O(g,-\infty) := \left \{ f \; | \; \pmb{\exists} \varepsilon < 0 \exists \delta < 0 \forall x(x < \delta \Rightarrow \right |f(x)| \geq \varepsilon \cdot |g(x)| )\}

o(g,-\infty) := \left \{ f \; | \; \pmb{\forall} \varepsilon < 0 \exists \delta < 0 \forall x(x < \delta \Rightarrow \right |f(x)| \geq \varepsilon \cdot |g(x)| )\}

Regarding syntax, I've assumed that every existential quantifier, \exists, falls within the scope of all preceding universal quantifiers, \forall, and vice-versa, when they belong to the same string of quantifiers. For this reason, I've simply written \delta where some authors write \delta(\epsilon). Is this assumption correct? Can anyone recommend a thorough introduction to mathematical logic (first order logic) that gives the rules for constructing symbolic expressions.

 

[Rasalhague]

I think I need to change the final epsilon in each of the final pair of expressions, the one which multiplies |g(x)|, to the absolute value of epsilon. And I think that should be "by reversing all but the final inequality in each", rather than "by reversing the inequalities", shouldn't it? So the final two inequalities of the final pair of expressions should be less-than-or-equals.

 

[Rasalhague]

Regarding syntax, I've assumed that every existential quantifier falls within the scope of all preceding universal quantifiers and vice-versa, when they belong to the same string of quantifiers. For this reason, I've simply written delta where some authors write delta(epsilon). Is this assumption correct? Can anyone recommend a thorough introduction to mathematical logic (first order logic) that gives the rules for constructing symbolic expressions.

Correct. The rules for quantifiers are given in Loomis & Sternberg, Advanced Calculus, at the beginning of Chapter 1, online here at Sternberg's website:

http://www.math.harvard.edu/people/SternbergShlomo.html