# Is it possible to define functions with infinitely many variables, using relations?

In mathematical logic, we can define an n-ary function $$f$$ of variables $$\overline{x}=x_{0},x_{1},...x_{n}$$, using a relation $$R(y,\overline{x})$$, such that: $$\forall\overline{x}\exists!yR(y,\overline{x})$$. Then, $$y=f(\overline{x})\Leftrightarrow R(y,\overline{x})$$.

However, some times, in mathematics, we encounter functions with infinite number of variables. For example, in quantum mechanics, the state of a system concerning a continuous physical property, is represented by a vector in an infinite dimensional Hilbert space. Thus, any operator acting on the vector, is a function of (uncountably) infinitely many variables. If we are using relations to define functions, and without using sets, how can we deal with this situation?

I'm looking for an approach that doesn't require infinitely large expressions and/or quantification over infinite sequences of inputs.

• @MauroALLEGRANZA Infinitary logic still only allows finitary functions and relations. – Noah Schweber Oct 21 '19 at 14:58
• Isn' t there any indirect way to deal with it in ordinary logic, at least for some cases? For example, if we use a ternary relation P, representing a function p, such that $P(y,y_{0},x_{0})\wedge\forall nP(y_{n},y_{n+1},x_{n+1})$. That is, $y=f(\overline{x})=p(y_{0},x_{0})$ where $y_{0}=p(y_{1},x_{1})$, ... , $y_{n}=p(y_{n+1},x_{n+1})$,... – Aris Makrides Oct 21 '19 at 15:07
• @ArisMakrides Not really, no. That approach doesn't do anything useful I can see; in particular, try expressing "$f$ is injective" for an infinitary function $f$. – Noah Schweber Oct 21 '19 at 15:11
• $f$ is injective, if, $\forall n\left(\left[P(y_{n},y_{n+1},\alpha)\wedge P(y_{n},y_{n+1},\beta)\right]\rightarrow\alpha=\beta\right)$ – Aris Makrides Oct 21 '19 at 15:53
• That doesn't work (or parse, really) - you need to quantify over infinite sequences of inputs, and you can't do that. (Remember also that in first-order logic you can't directly quantify over naturals, you can only quantify over the domain of your structure.) – Noah Schweber Oct 22 '19 at 21:07

Related: discussion at this Mathoverflow question.

The answer is largely that we can't really, although of course it's hard to rigorously prove a negative like that.

Let me say a bit about the situation:

There is actually very little work on classical-style model theory of infinite-arity structures; essentially the only paper in this direction I know of is this old paper by Slapal, which is from $$1988$$ and doesn't seem to have been followed up on.

• Note that infinitary logic doesn't qualify - "infinitary" there refers to the nature of the logical operators $$\wedge$$ and $$\vee$$, but the structures of infinitary logic are the same as the structures of first-order logic.

So why the dearth?

One obvious issue with "infinite-arity first-order logic" (IFOL for short) is that loses the basic good behavior of (finite-arity) first-order logic. In particular, there is no notion of IFOL that I'm aware of that has either the compactness or downward Lowenheim-Skolem properties, which are pretty fundamental to model theory. Similarly, the natural approach to IFOL allows quantification over infinite tuples of variables at once, which is set-theoretically problematic (turning back to a more studied context for analogy, the infinitary logic $$\mathcal{L}_{\omega_1,\omega_1}$$ is much worse behaved than the infinitary logic $$\mathcal{L}_{\infty,\omega}$$). Even if we only allow quantification over finitely many variables at once, we still hit the issue that even when we have a single infinite-arity function we wind up with uncountably many terms, which is annoying in several technical contexts.

In particular, these issues are quite fundamental; the function-to-relation shift, while often useful, simply won't address them here.

So what's the fix?

It seems to be that we need to go beyond the classical flavor here. For example, abstract elementary classes were proposed - and have had great success - as a generalization of many different types of logic at once, and recently ones allowing operations of infinite arity have been studied (see e.g. the Baldwin/Boney paper this collection or this paper of Boney/Grossberg/Lieberman/Rosicky/Vasey. There is also (and this is mentioned at the MO question above) some work on infinite-arity structures from the category-theoretic side, which I think so far has been more substantially useful (although I'm not qualified to talk about it really), and I've heard (but can't find a citation for at the moment) that continuous logic handles the topic as well.

• More speculatively, it's hard not to guess that descriptive set theory can also be deployed in the case of countable-arity operations; sadly, I don't think that this has been investigated much (it's a topic of my own research though, and I've asked some Mathoverflow questions about it).