# Is the theory of asymptotic bounds finitely axiomatizable?

Let $$F$$ be the set of functions over real numbers. Consider the structure $$M = \langle F, <, \leq, =, \geq, > \rangle$$ where the $$<, \leq, =, \geq, >$$ are defined as asymptotic notions $$o$$, $$O$$, $$\Theta$$, $$\Omega$$, $$\omega$$. For example, for $$f,g\in F$$, $$f\leq g$$ iff $$f \in O(g)$$.

Consider the first-order theory of this structure $$T = Th(M)$$.

Questions:

Is $$T$$ finitely axiomatizable?

Does $$T$$ have quantifier elimination property?

Is $$T$$ a decidable theory?

Is there a references discussing logical and model theoretic properties of this theory (statements similar to those above)?

• An optimistic guess: might this just be the theory of distributive lattices with zero? – Colin McQuillan Oct 22 '12 at 13:40
• @Colin, as a theory of a structure the theory needs to be complete, I don't think the theory of distributed lattices with zero is a complete theory. – Kaveh Oct 22 '12 at 13:58
• Nice question! Could you give examples of interesting theorems that could be expressed in this theory? Do you know if there are any open questions? – Vijay D Oct 22 '12 at 17:40
• @Vijay, I was looking at the standard properties of asymptotic notations like $f \leq g \land g \leq h \rightarrow f \leq h$, $\exists f,g,h \ (f \leq g \land f \neq g \land f \not < g)$, $\forall f,g \ \exists h \ [f,g \leq h \land \forall h' \ (f,g \leq h' \rightarrow h \leq h')]$. – Kaveh Oct 22 '12 at 23:52
• It would be much more interesting if we would through in some other constants and operations like $0:x \mapsto 0$, $1:x \mapsto 1$, $id: x \mapsto x$, $+$, $\cdot$, $o$ (composition), etc. so that we can express more interesting statements but the theory becomes too strong as soon as we have addition and multiplication. – Kaveh Oct 22 '12 at 23:59