# Formal languages with non-unique interpretations of terms

In mathematical logic and model theory, one considers interpretations of syntactic expressions: terms without free variables are interpreted as elements of some structure, formulas without free variables have truth values, formulas with free variables can be interpreted as relations.

Multiple expressions may have identical interpretations. For example, $\ulcorner 1 + 1\urcorner$ and $\ulcorner 2\urcorner$ are both interpreted as $2$.

Question: does anyone ever consider formal languages where terms can have multiple interpretations? Is there some standard approach or framework?

I am thinking about this because i am trying to understand the $\omicron$ and $O$ notation in analysis, like in $$\ln(x) =\omicron(x),\quad x\to +\infty.$$ Also, when calculating an indefinite integral, on often writes $$\int 2x\,dx = x^2 + C.$$

Update. I understand that when the equality sign is used with $\omicron$/$O$ notation, it does not represent an equivalence relation. I also know that $\omicron(g(x))$ can be viewed as a set of functions. However, this interpretation does not fit my intuition well. When i write $\sin x = x + \omicron(x^2)$, $x→0$, i do not think about sets of functions, i think that i am replacing an anonymous implicitly understood function with a placeholder. In other words, the designated object does not change (it is still a function or a number, not a set of functions or set of numbers), only the notation is abbreviated and made less explicit, a bit like when i write "$1 + 2 + 3$" instead of "$((1 + 2) + 3)$".

• With respect to asymptotic notation, I don’t think that terms with multiple denotations would solve the problem, as the main issue is that the “=” behaves as a nonsymmetric relation. An adequate semantics here is that terms denote sets of functions rather than functions (but one term still denotes a unique set), operations such as composition and $O$ do the expected thing, and $t=s$ is interpreted as “every function in the denotation of the LHS equals some function in the denotation of the RHS”, and similarly for other relations like $t\le s$ (unless you consider this invalid notation). – Emil Jeřábek Dec 4 '14 at 22:35
• I think many of these can be somehow fit into the context of a rewriting system. In fact, the art of manipulating $\int$, $O$, $o$ often involves purely syntactic manipulations (e.g. $\int udv = uv - \int vdu$, $\sum_{x \leq y} x(1+o(1)) = O(y^2)$, etc). – François G. Dorais Dec 4 '14 at 23:20
• @EmilJeřábek, i understand well that the equality relation is not symmetric with the $\omicron/O$ notation, this is one of the first things i tell my students. However, my impression was that it is a secondary concern, and can be addressed after the ambiguity of the notation is addressed. I felt that multi-valued interpretations are better than interpretations by sets because they would generalize the usual interpretation instead of replacing it with a new one (no need to interpret $\ln(2x)=\ln2 +\ln x =O(\ln x),\ x\to\infty$ as two relations between sets of functions). – Alexey Muranov Dec 4 '14 at 23:50

As Emil says in his comment, we are never forced to use terms with many interpretations, because we can pass from "terms-as-elements" to "terms-as-sets" (I don't know if there is a name for this, but it's a common idea; the same idea is present in the easy proof that you can simulate a non-deterministic machine with a deterministic machine (I'm leaving "machine" vague here, since it holds for most interesting kinds)).

However, one could ask if there are times that it is more natural in practice to use many-valued terms than to switch to sets. I know of at least one: Multi- and hyper-rings and fields. See http://www.math.us.edu.pl/~pgladki/inedita/hypsurvey.pdf. I suspect there are others, from within logic, but I don't know of any offhand.

• Thanks for the link. I haven't thought of multivalued functions, but one of the things that motivated my question was my impression (i am not sure and have no reference) that in the first half of the nineteenth century, in model theory or mathematical logics texts, the equality was not always interpreted as the identity, but only as an equivalence relation. Sometimes (as mentioned by François Dorais) the equivalence relation could be the one of a rewriting system. – Alexey Muranov Dec 5 '14 at 0:05
• Yes, equality was not always assumed to be a logical notion - for instance, if I recall correctly Robinson's book "Complete Theories" is about first-order logic without equality. – Noah Schweber Dec 5 '14 at 1:36

It is possible to have multiple meanings for a given piece of syntax, this goes under the general name of polymorphism. For example, projections from a pair $\pi_1 : A \times B \to A$ and $\pi_2 : A \times B \to B$ are polymorphic because $\pi_1$ can mean the first projection for any sets $A$ and $B$, whereas a monomorphic notation (the opposite of polymorphic) would require us to always write $\pi_1^{A,B}$ (note that $\pi_A$ is broken as well as $\pi^{A,B}_A$ – think of the case $A = B$).

Logicians and mathematicians are the wrong people to ask about these issues. You should talk to computer scientists because they are constrained by two factors: they want usable syntax, or else people will not use it, and the syntax has to be sensible, or else computers will not understand it. There are many solutions to giving multiple meaning to a single piece of notation, for example operator overloading in C++ (bad example), notation scopes in proof assistants such as Coq, and type classes in Haskell. General mechanisms for resolving ambiguous notations can be quite involved. For instance, type classes in Haskell and Coq are really like little prolog programs which direct the machine in finding out what the user meant when he or she wrote down an expression.

Unfortnately, the examples you give about intervals and the little $o$ notation are not of the kind that can be repaired without at least some changes.

Let me state explicitly that I sympathize with the idea that notation should not hinder expression of ideas, and I use sloppy notation all the time as well – but a prerequisite for using sloppy notation is to be able to use non-sloppy notation as well. Non-sloppy notation is especially important in teaching and when things get tricky.