0
$\begingroup$

This is related to my previous question on expressions. Consider a countably infinite set of variables, indexed by the positive integers. Suppose also we are considering the set of real numbers as our domain. How would we associate a function to an expression, as in how would we formally define it. For example, should $x_2$ be associated to the identity function on $\mathbb{R}$, or to the projection function on $\mathbb{R}^2$ that returns the second coordinate? Also, should something like $x_1+x_2-x_3+x_3$ be defined on $\mathbb{R}^3$, or $\mathbb{R}^2$? Is there some mathematical text where the mapping from expressions to functions is formally defined?

$\endgroup$
4
  • $\begingroup$ Are you asking about common usage across mathematics, or about how things can be done in a textbook on formal logic? $\endgroup$ – Mark S. Sep 1 '20 at 0:04
  • $\begingroup$ @MarkS. How things are done in a textbook on formal logic. $\endgroup$ – user107952 Sep 1 '20 at 0:08
  • $\begingroup$ With "expression" do you mean an $\mathscr L$-term for some first-order language $\mathscr L$? $\endgroup$ – Rick Sep 1 '20 at 12:42
  • $\begingroup$ @Rick Yeah, that is what I mean. I specifically chose the real numbers and addition and subtraction in my examples, but of course this can be generalized to any set S and a collection of n-ary functions on S. $\endgroup$ – user107952 Sep 1 '20 at 13:34
1
$\begingroup$

You're right that there's some flexibility here. The simplest approach is to just clear everything up by adding some "metadata." Say that an annotated term (in a given language, using $\mathbb{N}$-indexed variables) is a pair $(t,n)$ where $t$ is a term in the language and every variable occurring in $t$ has index $\le n$. Then we can construe each annotated term $(t,n)$ as a function from the $n$th Cartesian power of our structure to itself.

The default, then, is to use the smallest possible $n$. So for example (abusing parentheses for simplicity) "$x_1+x_2$" and "$x_1+x_2+x_3-x_3$" would refer to functions from $\mathbb{R}^2$ and from $\mathbb{R}^3$ respectively; their "equivalence" would amount to the fact that the former is the projection of the latter.

  • Note that in this approach we do lose some parsimony: e.g. taking the term "$x_5+x_2$" we have to have $n\ge 5$, and so we can't construe that as a function from $\mathbb{R}^2$ even though it only has two variables occurring in it. If you want to get around this you can modify the definition of "annotated term" above to refer to pairs $(t,X)$ where $t$ is a term and $X$ is a finite sequence of variables, such that each variable in $t$ occurs in $X$. For example, we then would interpret $(2\cdot x_5+x_2, \langle x_5,x_3,x_2\rangle)$ as the function $$\mathbb{R}^3\rightarrow\mathbb{R}: (a,b,c)\mapsto 2\cdot a+c$$ (because the sequence part tells us that $x_5$ is the first variable in our approach here). This also has the advantage that we can use any set of variables that we want, instead of just $\mathbb{N}$-indexed ones.

Unfortunately this is generally swept under the rug, but hopefully the above indicates that it's pretty straightforward to treat if you really want to. It's also worth noting that usually we go the other way: we first declare that we're going to consider functions $\mathbb{R}^n\rightarrow\mathbb{R}$, and then interpret terms with variables only from $\{x_1,...,x_n\}$ as maps $\mathbb{R}^n\rightarrow\mathbb{R}$ in the obvious way. So a lot of the time this doesn't come up at all: while it's true that we can interpret a given term as living on different domains, since we specify what domain we're interested in at the outset we don't care about this ambiguity.

$\endgroup$
1
$\begingroup$

I think that you question is slightly ambiguous as I'm not really sure what do you mean by "associate a function to an expression"; nevertheless let me give a couple of observations on this issue.

First and foremost, when talking about "expressions" one should fix a language over which these expressions are constructed; from your given example about the real numbers, I will take my expressions from now onwards to be formulated in the first-order language of fields $\mathscr L = \{+, \cdot, -, 0, 1\}$. As you've clarified in your comment, "expressions" here mean $\mathscr L$-terms; in particular, $\mathscr L$-terms in the language of fields are finite sequences of symbols from $\mathscr L$ of the form $$t_1(x):= x,$$ or $$t_1(x_1, x_2):= -3\cdot x_1^2 +2\cdot x_2,$$ or $$t_3(x_1,x_2,x_3) := x_1\cdot x_2 \cdot x_3,$$ for example. Note that $\mathscr L$-terms are nothing more than syntactical constructions which we can interpret (i.e. "give meaning") in an $\mathscr L$-structure. In your example, you work with the $\mathscr L$-structure $\mathscr M$ whose domain is the set of real numbers and where each of the functions $+, \cdot, -$ and constants $0,1$ are interpreted in the standard way, so that each $\mathscr L$-term is interpreted as a polynomial with coefficients in $\mathbb Z$, in one (e.g. $t_1(x)$) or multiple variables (e.g. $t_3(x_1, x_2, x_3)$).

Surely one can associate to each of these polynomials a polynomial map, but in general there is no canonical way of doing this, even after specifying the language and the $\mathscr L$-structure in which we interpret our terms. In our example, the term $t_1(x) := x$ can be seen as a term in one variable, and in such way we could associate to the interpretation of this term the identity map on $\mathbb R$. However, we could also associate to it the projection map onto, say, the third co-ordinate, sice $t_1$ is also a term in the free variables $w,v,x,z$; remember that the notation $t_1(x)$ means that $t_1$ has free variables amongst $\{x\}$, so in particular a term in the free variable $x$ is also a term in the free variables $x, v, x$ and $z$. By the same reasoning, the interpretation of the term $t_4: =x_1 + x_2 + x_3 -x_3$ in $\mathscr M$ could be associated to a polynomial map on $\mathbb R^3$ or on $\mathbb R^n$ for any $n \in \mathbb N^{\geq 3}$. We can also associate to it a polynomial map on $\mathbb R^2$ since the interpretation of $t_4$ and of $x_1 +x_2$ in $\mathscr M$ coincides; however, if we have another $\mathscr L$-structure $\mathscr M'$ in which we interpret $-$ in the same way we interpret $+$ (yes, we can do this!), then the interpretation of $t_4$ cannot be associated to a polynomial map on $\mathbb R^2$.

$\endgroup$
1
  • $\begingroup$ Thank you. This clarified some details. I still have a few questions, though. Just to be clear, I am using the variables x_1, x_2, ..., x_n, etc. not x, y, z, etc. In other words, the variables are indexed by the positive integers. I do not see how x_1 can possibly be interpreted as the projection on to the third coordinate. Surely, it would be the first coordinate. Also, what about something like x_2+x_5? Should it be the addition function on R^2, or the function on R^5 that adds the 2nd and 5th components? Is there a text where the mapping between terms to n-ary functions is defined? $\endgroup$ – user107952 Sep 1 '20 at 15:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.