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)$.


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)?

  • $\begingroup$ An optimistic guess: might this just be the theory of distributive lattices with zero? $\endgroup$ – Colin McQuillan Oct 22 '12 at 13:40
  • 1
    $\begingroup$ @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. $\endgroup$ – Kaveh Oct 22 '12 at 13:58
  • 1
    $\begingroup$ 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? $\endgroup$ – Vijay D Oct 22 '12 at 17:40
  • $\begingroup$ @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')]$. $\endgroup$ – Kaveh Oct 22 '12 at 23:52
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 22 '12 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.