27
$\begingroup$

I'll state my questions upfront and attempt to motivate/explain them afterwards.

Q1: Is there a direct way of expressing the relation "$y$ is a function of $x$" inside set theory? More precisely: Can you provide a formula of first order logic + $\in$, containing only two free variables $y$ and $x$, which directly captures the idea that "$y$ is a function of $x$"?

In case the answer to Q1 is negative, here's

Q2: Do any other foundations of mathematics (like univalent) allow one to directly formalize the relation "$y$ is a function of $x$"? Or have there been any attempts to formalize (parts of) mathematics with a language where the relation is taken as primitive/undefined?

From discussing Q1 with colleagues I've learned that it's hard to convey what my problem is, causing frustration on both sides. I suspect this is to a certain extent because we all only learned the modern definition of function (which is not the answer to Q1) and because neither the people I talk to nor myself are experts in logic/type theory/category theory. So please bear with me in (or forgive me for) this lengthy attempt at an

Explanation/Motivation:

The relation "$y$ is a function of $x$" between two things $y$ and $x$, was the original (and apparently only) way of using the word function in mathematics until roughly 1925. The things $y$ and $x$ were traditionally called variable quantities, and the same relation was sometimes worded differently as "$y$ depends on $x$", "$y$ is determined by $x$" or "$y$ changes with $x$". This was used as a genuine mathematical proposition: something that could be proved, refuted or assumed. People would say "let $y$ be a function of $x$" just like today we might say "let $U$ be subgroup of $G$".

I could cite more than 40 well known mathematicians from Bernoulli to Courant who gave definitions of this relation, but I'll limit myself to quote eight at the end of my question. As far as I can tell, these definitions cannot be directly translated into first order logic + $\in$.

Although the word function assumed a different meaning with the rise of set theory an formal logic, the original relation is still used a lot among physicist, engineers or even mathematicians. Think of statements like "The pressure is a function of the volume", "The area of the circle is a function of its radius", "The number of computations is a function of the size of the matrix", "The fiber depends on the base point" etc. This even crops up in scientific communities where I wouldn't expect it. One finds it for instance in Pierce's Types and Programming Languages or Harper's Practical foundations of programming languages.

So it seems that something being a function of something else (or something depending on something else) is a very natural notion for many people. In fact, I have the impression that for physicists, engineers and most scientist who apply mathematics, this relation is closer to the ideas they want to express, than the modern notion of function.

Yet, I don’t see a direct way of formalizing the idea inside set theory. (The modern notion of a map $f\colon X \to Y$ is not what I'm looking for, since by itself it's not a predicate on two variables.)

I know how to capture the idea at the meta-level, by saying that a formula of first order logic is a function of $x$, iff its set of free variables contains at most $x$. But this is not a definition inside FOL. When a physicist says “The kinetic energy is a function of the velocity” he’s certainly making a physical claim and not a claim about the linguistic objects he uses to talk about physics. So this syntactic interpretation of “$y$ is a function of $x$” is not what I’m looking for.

I also know a way to encode the idea inside set theory. But I’m not completely happy with it.

First, here’s a naive and obviously wrong approach: Let $x\in X$ and $y\in Y$, call $y$ a function of $x$, iff there exists a map $f:X\to Y$, such that $y=f(x)$. Since every such $y\in Y$ is a function of every $x$ (use a constant map $f=(u\mapsto y))$, this is not the right definition.

Here’s a better approach: Let $x$ and $y$ be maps with equal domain, say $x:A\to X$ and $y: A \to Y$. Before giving the definition let me switch terminology: Instead of calling $x$ a "map from $A$ to $X$" I'll call it a "variable quantity of type $X$ in context $A$". (This change of terminology is borrowed from categorical logic/type theory. In categorical logic people say “$x$ is a generalized element of $X$ with stage of definition $A$”. But don’t assume from this, that I have a thorough understanding of categorical logic or type theory.)

Definition: Let $x$ and $y$ be variable quantities of type $X$ and $Y$ in the same context $A$. We call $y$ a function of $x$, iff there exists a map $f: X\to Y$ such that $y=f\circ x$.

(It would be suggestive to switch notation from $f{\circ} x$ to $f(x)$, so we could write $y=f(x)$ when $y$ is a function of $x$. I'll refrain from doing this, since $f(x)$ has an established meaning in set theory.)

Since my post is getting long, I won’t explain why this definition captures the original idea quite well. Let me only say why I don't consider it a direct way of capturing it: It seems backwards from a historical perspective. Mathematicians first had the notion of something being a function of something else, and only from there did they arrive at maps and sets. With this approach we first need to make sense of maps and sets, in order to arrive at the original idea. This might not be a strong counter argument, but if I wanted to use the original idea when teaching calculus, I would need a lot of preparation and overhead with this approach. What I’d like to have instead, is a formalization of mathematics where the relation can be used "out of the box".

The other thing I don’t like about this (maybe due to my lack of knowledge of categorical logic) has to do with the context $A$ and what Anders Kock calls an “important abuse of notation”. To illustrate: suppose I have two variables quantities $x,y$ of type $\mathbb{R}$ in some context $A$. If I now assume something additional about these variables, like the equation $y=x^2$, this assumption should change the context from $A$ to a new context $B$. This $B$ is the domain of the equalizer $e:B\to A$ of the two maps $x^2,y\colon A\to \mathbb{R}$. The abuse of notation consist in denoting the "new" variable quantities $x\circ e, y\circ e$ in context $B$, with the same letters $x,y$. I suspect this abuse is considered important, since in everyday mathematics it's natural to keep the names of mathematical objects, even when additional assumptions are added to the context. In fact, if I’m not mistaken, in a type theory with identity types there is no abuse of notation involved when changing the context from $A\vdash (x,y) \colon \mathbb{R}^2$ to $A, e\colon y=x^2 \vdash (x,y) \colon \mathbb{R}^2$. So maybe type theorist also already know a language where one can talk of "functions of something" in a way that's closer to how way mathematicians did until the 1920's?

Some historical definitions of "$y$ is a function of $x$":

Johann Bernoulli 1718, in Remarques sur ce qu’on a donné jusqu’ici de solutions des Problêmes sur les isoprimetres, p. 241:

Definition. We call a function of a variable quantity, a quantity composed in any way whatsoever of the variable quantity and constants.

(I'd call this the first definition. Leibniz, who initiated the use of the word function in mathematics around 1673, gave a definition even earlier. But his is not directly compatible with Bernoulli's, even though he later approved of Bernoulli's definition.)

Euler, 1755 in Institutiones calculi differentialis, Preface p.VI:

Thus when some quantities so depend on other quantities, that if the latter are changed the former undergo change, then the former quantities are called functions of the latter ; this definition applies rather widely, and all ways, in which one quantity could be determined by others, are contained in it. If therefore $x$ denotes a variable quantity, then all quantities, which depend upon $x$ in any way, or are determined by it, are called functions of it.

Cauchy, 1821 in Cours d'analyse, p. 19:

When variable quantities are related to each other such that the values of some of them being given one can find all of the others, we consider these various quantities to be expressed by means of several among them, which therefore take the name independent variables. The other quantities expressed by means of the independent variables are called functions of those same variables.

Bolzano, ca. 1830 in Erste Begriffe der allgemeinen Grössenlehre,

The variable quantity $W$ is a function of one or more variable quantities $X,Y,Z$, if there exist certain propositions of the form: "the quantity $W$ has the properties $w,w_{1},w_{2}$,", which can be deduced from certain propositions of the form "the quantity $X$ has the properties $\xi,\xi',\xi''$, -- the quantity $Y$ has the properties $\eta,\eta',\eta''$; the quantity $Z$ has the properties $\zeta,\zeta',\zeta''$, etc.

Dirichlet, 1837 in Über die Darstellung ganz willkürlicher Functionen durch Sinus- und Cosinusreihen:

Imagine $a$ and $b$ two fixed values and $x$ a variable quantity, which continuously assumes all values between $a$ and $b$. If now a unique finite $y$ corresponds to each $x$, in such a way that when $x$ ranges continuously over the interval from $a$ to $b$, ${y=f(x)}$ also varies continuously, then $y$ is called a continuous function of $x$ for this interval.

(Many historians call this the first modern definition of function. I disagree, since Dirichlet calls $y$ the function, not $f$.)

Riemann, 1851 in Grundlagen für eine allgemeine Theorie der Functionen einer veränderlichen complexen Grösse

If one thinks of $z$ as a variable quantity, which may gradually assume all possible real values, then, if to any of its values corresponds a unique value of the indeterminate quantity $w$, we call $w$ a function of $z$.

Peano, 1884 in Calcolo differenziale e principii di calcolo integrale p.3:

Among the variables there are those to which we can assign arbitrarily and successively different values, called independent variables, and others whose values depend on the values given to the first ones. These are called dependent variables or functions of the first ones.

Courant, 1934 in Differential and Integral Calculus Vol. 1, p.14:

In order to give a general definition of the mathematical concept of function, we fix upon a definite interval of our number scale, say the interval between the numbers $a$ and $b$, and consider the totality of numbers $x$ which belong to this interval, that is, which, satisfy the relation $$ a\leq x \leq b. $$ If we consider the symbol $x$ as denoting at will any of the numbers in this interval, we call it a (continuous) variable in the interval.

If now to each value of $x$ in this interval there corresponds a single definite value $y$, where $x$ and $y$ are connected by any law whatsoever, we say that $y$ is a function of $x$

(It's funny how at after Cauchy many mathematicians talk of values of variables, which is not something we're allowed to do in set theory. (What's the value of a set or of the element of a set?). Yet, if one looks at modern type theory literature, it's full of talk of "values" again.)

$\endgroup$
33
  • 3
    $\begingroup$ I'm not a logician, and I don't understand exactly what you want. But on an intuitive level, why isn't the modern notion of function a good way to formalize the idea that something depends on something else? If you want to use set theory at all, the "something" and the "something else" must live inside some sets, and at that point you might as well call those sets the domain and range and use the modern definition of a function, no? $\endgroup$
    – user101142
    Aug 9, 2018 at 20:57
  • 6
    $\begingroup$ I disagree with your dissatisfactions re: your bolded definition. Re: the first dissatisfaction, I don't think it is artificial in the way you claim. First of all, note that we can make it less abstract by simply saying "... whenever $x(a)=x(b)$, we have $y(a)=y(b)$," which I think is much easier to explain. Second, I think that viewing quantities like kinetic energy as functions - namely, as functions from the set of possible "states" - is a useful new idea: sometimes the way we approached things historically is fundamentally non-optimal. (cont'd) $\endgroup$ Aug 9, 2018 at 21:12
  • 2
    $\begingroup$ I also think that this view of observed-quantities-as-functions is a conceptual development which students can and should learn; I think it would be a bit tricky at first, but ultimately would actually help them understand the basic properties of functions (in particular, by not being confused by the very question you ask here). Re: your second satisfaction, I disagree that we have an obligation to change the codomain when we gain new information ("... this assumption should change the context ..."). Can you explain why you think this is something we need to do? $\endgroup$ Aug 9, 2018 at 21:17
  • 5
    $\begingroup$ In the "measurable category", given two measurable functions $f,g$ on a measurable space, one can ask whether $f$ is measurable with respect to the $\sigma$-algebra generated by $g$, and this turns out to be equivalent to asking whether $f$ is of the form $f = \phi \circ g$, i.e. $f$ is a function of $g$. Now if you are doing probability theory, you can ask the same question about random variables $X,Y$ defined on a sample space. And probabilists try really hard to forget that random variables are "really" functions. This is probably not really what you want, but it's in that direction? $\endgroup$ Aug 9, 2018 at 22:43
  • 3
    $\begingroup$ @NoahSchweber I agree with almost everything you say, and have thought about teaching calculus this way (with state spaces) to engineers. But there is another problem I see, which relates to what I just wrote to Nate Eldredge: In physical applications you almost never know beforehand what the state space is, i.e. how to describe it directly as a set. Instead, what happens in practice, is that the state space is described by the variable quantities you assume given and the relations you assume to exist between them. The set theoretical encoding doesn't tell me how to do that. $\endgroup$ Aug 10, 2018 at 7:25

5 Answers 5

29
$\begingroup$

First of all, it seems to me as though the real question here is "what is a variable quantity?" Most of the definitions you quote from pre-20th century mathematicians assume that the notion of "variable quantity" is already understood. But this is already not a standard part of modern formalizations of mathematics; so it's unsurprising that definitions of a subsidiary notion, like when one variable quantity is a function of another one, are hard to make sense of.

So what is a variable quantity? If we want to define the notion of variable quantity "analytically" inside some standard foundational system, then I think we cannot do better than your second suggestion: given a fixed "state space" $A$, an $R$-valued quantity varying over $A$ is a map $A \to R$. Far from worrying that this is historically backward, I think we should be proud that modern mathematics supplies a precise way to make sense of a previously vague concept, and we should not be surprised that in stumbling towards precision people took historically a more roundabout route than the eventual geodesic route that we now know. I think if you pressed any modern mathematician using the phrase "is a function of" to say what they mean by it, this is what they would say (for some suitable $A$, e.g. in "the area of a circle is the function of its radius" the space $A$ is the space of circles, while in "the number of computations is a function of the size of the matrix" the space $A$ is the space of matrices).

However, you seem to be looking for something somewhat different, such as a formalism which the notion of "variable quantity" is basic rather than defined in terms of other things — a "synthetic theory of variable quantities" if you will. Here I think topos theory as well as type theory does indeed help. Given a fixed state space $A$, consider the category ${\rm Sh}(A)$ of sheaves on $A$; this is a topos and hence has an internal logic that is a type theory in which we can do arbitrary (constructive) mathematics. If inside this "universe of $A$-varying mathematics" we construct the (Dedekind) real numbers $R_A$, what we obtain externally is the sheaf of continuous real-valued functions on $A$. Thus, internally "a real number", i.e. a section of this sheaf, is externally a continuous map $A\to \mathbb{R}$, i.e. a real-valued quantity varying over $A$ in the analytic sense. So here we have a formalism in which all quantities are variable. (This point of view, that objects of an arbitrary topos should be regarded as "variable sets" has been promulgated particularly by Lawvere.)

This isn't sufficient to define "function of", however, because as you point out, internally in this type theory, for any "variable quantities" $x,y:R$ there exists a map $f:R\to R$ such that $f(x)=y$, namely the constant map at $y$. If we rephrase this externally, it says that given $x:A\to \mathbb R$ and $y:A\to \mathbb R$, there always exists $f:A\times \mathbb R\to \mathbb R$ such that $f(a,x(a)) = y(a)$ for all $a$, namely $f(a,r) \equiv y(a)$. So the problem is that although $x$ and $y$ are variable quantities, we don't want the function $f$ to be a "variable function"!

Thus we need a formalism in which not only are "variable quantities" basic, there is also a contrasting basic notion of "constant quantity". Categorically, a natural way to talk about this is to think about not just the category ${\rm Sh}(A)$, but the geometric morphism $\Gamma:{\rm Sh}(A)\leftrightarrows \rm Set: \Delta$, which compares the "variable world" ${\rm Sh}(A)$ with the "constant world" $\rm Set$. Just as a single topos has an internal logic that is a type theory, a geometric morphism has an internal logic that is a modal type theory, in which there are two "modes" of types (here the "variable" and "constant" ones) and operators that shift back and forth between them (here the "global sections" $\Gamma$ and the "constant/discrete" $\Delta$).

Now inside this modal type theory, we can construct the object $R^v$ of "variable real numbers" and also the object $R^c$ of "constant real numbers", by copying the usual Dedekind construction in the variable and constant word, and there is a map $\Delta R^c \to R^v$ saying that every constant real number can be regarded as a "trivially" variable one. This gives us a way to say in modal type theory that $y:R^v$ is a function of $x:R^v$, namely that there exists a non-variable function $f:R^c\to R^c$ such that $\Delta f : \Delta R^c \to \Delta R^c$ extends to a function $\bar{f}:R^v\to R^v$ such that $\bar{f}(x)=y$. Or, equivalently, that there is a function $g:R^v\to R^v$ such that $g(x)=y$ and $g$ "preserves constant real numbers", i.e. restricts to a map $\Delta R^c \to \Delta R^c$.

I'm not sure exactly what you hope to achieve with the issue involving assumptions like $y=x^2$ (maybe you can elaborate), but it seems to me that this setup also handles that problem just fine, in roughly the way you sketch: if variable quantities are just elements of $R^v$, then assuming some property of them, like $y= x^2$, doesn't change those elements themselves, internally.

$\endgroup$
10
  • 1
    $\begingroup$ This is great! Indeed, if you look at the old calculus, people always made the distinction between variables and constants inside their language. Calculus textbooks and physicists still do this, but it makes no sense inside set theory. Do you know if there is a place where I could read more about such a modal type theory? $\endgroup$ Aug 13, 2018 at 6:07
  • 6
    $\begingroup$ @MichaelBächtold Type theories with "higher modalities" like this are a recent innovation. If $A$ is connected, so $\Delta$ is fully faithful, the type theory is the one called "spatial" in arxiv.org/abs/1509.07584 and "crisp" in arxiv.org/abs/1801.07664 (with different applications in mind). A type theory for a not necessarily connected geometric morphism has not as far as I know been studied explicitly, but should be a special case of my work in progress with Licata and Riley which I talked about at HoTTEST: uwo.ca/math/faculty/kapulkin/seminars/hottest.html $\endgroup$ Aug 13, 2018 at 7:49
  • 1
    $\begingroup$ Hi @MikeShulman, I was wondering if your definition of "$y$ is a function of $x$" in such a modal type theory could also be reformulated along the lines of: "whenever $x$ is constant, it follows that also $y$ is constant." Or is this only expressible at the meta-level? I'm trying to mimic the old definitions which talked of values and didn't mention $f$. $\endgroup$ Apr 12, 2019 at 12:06
  • $\begingroup$ @MichaelBächtold I don't immediately see any way to do that. If $x$ is a fixed variable quantity, i.e. externally a map $A\to R$, then I believe the internal truth-value of "$x$ is constant" is the largest open subspace of $A$ on which $x$ is locally constant. So "whenever $x$ is constant, $y$ is also constant" would mean externally that on every open subspace where $x$ is locally constant, $y$ is also locally constant. In particular, it would say nothing about what happens where $x$ is not constant. $\endgroup$ Apr 12, 2019 at 16:35
  • 1
    $\begingroup$ @MichaelBächtold The largest open subspace on which $x$ is locally constant is the union of all open subspaces on which $x$ is locally constant. $\endgroup$ Apr 12, 2019 at 20:44
12
$\begingroup$

The situation here seems very analogous to that in probability, where there is also a state space $\Omega$ (which is the underlying set of a probability space $(\Omega, {\mathcal B}, {\bf P})$) which is required in the foundations of the subject in order to define everything properly, but is then downplayed as strongly as possible once one starts doing probability. Thus, technically, every random variable $X$ is a function on this state space (e.g., a real random variable would be a (measurable) function from $\Omega$ to ${\bf R}$), but one tries to avoid explicit mention of this space as much as possible, and in fact every so often one actually exercises the freedom to change the state space or probability space, for instance by adding some new sources of randomness, conditioning to an event (somewhat analogous to your equaliser example), and so forth. One can then view probability theory as the study of objects and concepts that remain invariant under a certain type of change of state space, namely that of extending that space; see these lecture notes of mine for more on this (see also these later notes).

One can adapt this viewpoint to non-probabilistic settings. This brings us back to your proposal to view all mathematical objects as depending on a state space $A$, which is not specified precisely and is in fact downplayed as much as possible. One could view this state space as being somewhat dynamic in nature, for instance it could become larger as one makes more measurements in a physical system or introduces some new variables, or it could shrink as one makes some assumptions or fixes some values of certain observables. If one sets things up properly, these evolutions of the state space should not destroy any mathematical facts and relationships one has already gathered about the existing observables: for instance, if two observables $X,Y$ are known to always obey the relation $Y=X^2$, this fact should be unaffected by any changes to the state space caused by performing a measurement of a new observable $Z$, or by making some hypothesis constraining the known observables. (This suggests also to consider some "quantum" version of this setup where making new measurements can destroy the truth of previously established facts... but I digress.)

Incidentally, information theory, which builds upon probability theory, has a well-developed and quite quantitative theory of dependence: for instance, given two discrete (and finite entropy) random variables $X$ and $Y$, $Y$ is a function of $X$ (almost surely) if and only if the conditional entropy ${\bf H}(Y|X)$ vanishes.

$\endgroup$
0
5
$\begingroup$

When you say "$a$ is a function of $b$", it seems to me that what you're really saying is that "$a$ is independent of $c$" where $c$ is some implicit other part of the context which is somehow "orthogonal" to $b$. It goes without saying that there will typically be other "even more deeply implicit" parts of the context on which $a$ still does depend.

So in type theory, here's how I would formalize it. Let $\Gamma$ be a context, and suppose that

$$\Gamma, b: B, c: C \vdash a: A$$

That is, $a$ is a term (of type $A$) in the bigger context $\Gamma, b: B, c: C$. Then I would say that

$a$ is a function of $b$ (relative to $\Gamma$)

or equivalently

$a$ is independent of $c$ (relative to $\Gamma$)

if the following hold:

  1. We already have $\Gamma, b: B \vdash A$. That is, the type $A$ is independent of $c$.

  2. We already have $\Gamma, b: B \vdash a: A$. That is, the term $a$ is independent of $c$.

This isn't actually a definition internal to type theory, though. So it exists at the same level as the usual "function" definition in set theory (which I would also regard as a perfectly adequate formalization).

In order to get an "internal" definition, you would need to formalize internally what a context is, which seems like overkill to me. I think this is the correct level to define this concept at.

In answer to part of Question 2, I would regard all of type theory, with this formalism of contexts, as a formalism where the notion of "being a function of" is primitive.

$\endgroup$
4
  • $\begingroup$ Thanks. Could you explain why you say that the usual definition of "function" in set theory is external? (Do you mean the definition of a map, i.e. a subset of the cartesian product $A\times B$, or the meta-definition of "function of" I gave in my question?). $\endgroup$ Aug 10, 2018 at 7:43
  • $\begingroup$ "...which seems like overkill" ... maybe. When I teach, I would like to say: "assume that y is a function of x". Wouldn't this then be a statement at the meta-meta level? $\endgroup$ Aug 10, 2018 at 8:04
  • $\begingroup$ "Assume that $y$ is a function of $x$" is actually a simpler statement, because $y$ is not already floating around somewhere before you stipulate this -- rather, $y$ is introduced as something that depends only on $x$. It would be formalized as follows. Assume we have a context $\Gamma$, and $\Gamma \vdash X$. Then "Assume that $y$ is a function of $x$ (relative to $\Gamma$)" means that $\Gamma, x:X \vdash Y$ and you're expanding the context to $\Gamma, x:X,y:Y$. In that sense, it's a completely ordinary statement. $\endgroup$
    – Tim Campion
    Aug 10, 2018 at 17:01
  • 2
    $\begingroup$ Interesting. I'll need to think about that. A first spontaneous question: wouldn't every new variable introduced after $x$ then automatically be a function of $x$? Or how could you introduce a variable $z$ after $x$, and assume that it is not a function of $x$? $\endgroup$ Aug 10, 2018 at 17:09
4
$\begingroup$

I'm not an expert on this and hence I'm not writing a very detailed answer. However, it looks to me like Dependence logic captures what you're after, by directly adding to FOL atoms expressing things such as "x is a function of y".

$\endgroup$
1
  • $\begingroup$ Thanks, this seems very relevant. If someone knows an introductory article on this for non logicians that would be nice. $\endgroup$ Aug 13, 2018 at 18:19
4
$\begingroup$

There is some philosophical literature on this topic. My book 'Reasoning with Arbitrary Objects' (1985, Blackwell: Oxford) advocates the traditional view of variables. A new edition will soon come out in OUP with a new introduction in which I attempt to axiomatize the traditional view of variables. Leon Horsten has a recent book 'The Metaphysics and Mathematics of Arbitrary Objects' (2019, Cambridge University Press) in which he develops the theory using the idea of there being an underlying set (relative to which the variables vary).

$\endgroup$
1
  • $\begingroup$ Thank you for this answer. I'm looking forward to the axiomatization in the new edition of your book. $\endgroup$ Jan 13, 2020 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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