<p>Let <span class="math-container">$F$</span> be the set of functions over real numbers.
Consider the structure <span class="math-container">$M = \langle F, &lt;, \leq, =, \geq, &gt; \rangle$</span> where the <span class="math-container">$&lt;, \leq, =, \geq, &gt;$</span> are defined as asymptotic notions <span class="math-container">$o$</span>, <span class="math-container">$O$</span>, <span class="math-container">$\Theta$</span>, <span class="math-container">$\Omega$</span>, <span class="math-container">$\omega$</span>. For example, for <span class="math-container">$f,g\in F$</span>, <span class="math-container">$f\leq g$</span> iff <span class="math-container">$f \in O(g)$</span>.</p>
<p>Consider the first-order theory of this structure <span class="math-container">$T = Th(M)$</span>.</p>
<p>Questions:</p>
<blockquote>
<p>Is <span class="math-container">$T$</span> finitely axiomatizable?</p>
<p>Does <span class="math-container">$T$</span> have quantifier elimination property?</p>
<p>Is <span class="math-container">$T$</span> a decidable theory?</p>
</blockquote>
<p>Is there a references discussing logical and model theoretic properties of this theory (statements similar to those above)?</p>

CC BY-SA 3.0
2012-10-22T17:40:46.150Z
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
CC BY-SA 3.0
2012-10-22T23:52:52.170Z
@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
CC BY-SA 3.0
2012-10-22T23:59:28.777Z
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
CC BY-SA 3.0
2012-10-23T20:41:52.183Z
Would it help to consider a countable model instead, something like finite tuples of natural numbers?
András Salamon
CC BY-SA 3.0
2012-10-24T05:51:06.167Z
@András, I don't know if that would be a model of this theory. Obviously there is a countable model, however I haven't thought about how a countable model would look like. That might be a good way to look at the question, if there is a simple countable model then we can consider the theory of that model in place of functions over reals.
Kaveh
CC BY-SA 3.0
2012-10-22T13:40:04.840Z
An optimistic guess: might this just be the theory of distributive lattices with zero?
Colin McQuillan
CC BY-SA 3.0
2012-10-22T13:58:37.033Z
@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
CC BY-SA 3.0
2017-08-03T22:27:39.787Z
@RickyDemer, F is all real function, so there is no function that is dominated by all functions, so the formula you have is equivalent to always false formula. But what if we restricted F to just the positive ones? I think in that case it would be fair to at least have constant functions and then the formula would be equivalent to $f \leq 0$.
Kaveh
<lo.logic><asymptotics>
Is the theory of asymptotic bounds finitely axiomatizable?
Kaveh
# Is the theory of asymptotic bounds finitely axiomatizable?

(Asked by: username_0 on 2012-10-22)

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

**Tags:** lo.logic, asymptotics

> **Comments:**
> **username_3**: An optimistic guess: might this just be the theory of distributive lattices with zero?  
> **username_0**: @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.  
> **username_1**: 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?  
> **username_0**: @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')]$.  
> **username_0**: 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.  
> **username_2**: Would it help to consider a countable model instead, something like finite tuples of natural numbers?  
> **username_0**: @András, I don't know if that would be a model of this theory. Obviously there is a countable model, however I haven't thought about how a countable model would look like. That might be a good way to look at the question, if there is a simple countable model then we can consider the theory of that model in place of functions over reals.  
> **username_0**: @RickyDemer, F is all real function, so there is no function that is dominated by all functions, so the formula you have is equivalent to always false formula. But what if we restricted F to just the positive ones? I think in that case it would be fair to at least have constant functions and then the formula would be equivalent to $f \leq 0$.  

---

## 0 answers

