ukmuiik

Question

This question already has an answer here:

Confusion about the definition of function

2 answers

This remark appears in Terence Tao's Analysis I

Remark 3.3.6. Strictly speaking, functions are not sets, and sets are not functions; it does not make sense to ask whether an object $x$ is an element of a function $f$, and it does not make sense to apply a set $A$ to an input $x$ to create an output $A(x)$. On the other hand, it is possible to start with a function $f : X Ã¢Â†Â’ Y$ and construct its graph $ (x, f(x)) : x in X $ , which describes the function completely: see Section 3.5.

In a lot of books I checked (almost all of them about Set Theory) do consider $f$ to be a set defined as $f = (x, f(x)) : x in X $ which is included in $X times Y$ (i.e The Cartesian product of $X$ and $Y$) and I don't see why Tao sees it as nonsensical?

One other thing, lets consider this two definitions:

(1) For each element $x in A$, there exist at most an element $y$ in $B$ such that $(x,y) in f$, $y = f(x)$, or $x f y$ depends on the notation used.

(2) For each element $x$ in $A$, there exist a unique element $y in B$ such that $(x,y) in f$, $y = f(x)$, or $x f y$ depends on the notation used.

In almost all French books I checked (1) is a definition of a they call "fonction" (i.e Function in English apparently), and (2) is for what they call "application" (I don't know what it should be translated to in English, I think 'map' would do), but in English books I checked they don't make this distinction, they define function, map...etc as in (2) and consider (1) to a not be a function.

My question is which one I should consider as a the definition for a function? even though (2) would make the most sense for me, because why would you include elements that not have an image in the domain of $f$?

French people, as far as I know, don't really make a difference between "fonction" and "application". To me and my class comrades, this has always been the same pretty much. Also, both refer to the second definition, we never use the first one. However, I have some friends in the computer science department who use the first definition, and call this a "fonction partielle": a partial function (?). — Jul 25 at 23:30
This is not an answer to your question, but if you find some of this discussion unnatural as I did, there are alternatives that take sets and functions as there atomic elements. — Jul 25 at 23:33
A function $f: A longrightarrow B$ can't be defined (just) by its graph $(x, f(x)) in A times B hskip8pt $, at least not if you want to distinguish between functions that have the same graph but different codomain $B$. If you do want to make such distinctions, then I think it's better to define a function as a triple $(A, B, (x, f(x)) in A times B hskip8pt )$, ie. as the domain of the function $f: A longrightarrow B$ together with the codomain of the function and the graph of the function. — Jul 26 at 1:40
@Ã©tale-cohomology Good point, and I think that is the reason why gimusi uses exactly this triple in his answer. — Jul 26 at 5:41
@Ã©tale-cohomology I've edited the answer using your terminology for the triple, it seems more clear in that way. Thanks — Jul 26 at 6:38

Rob 761 · Accepted Answer · 2018-07-26 00:45:49Z

Tao defines a function from $X$ to $Y$ to be a property $P(x,y)$ of elements $x in X$ and $y in Y$ such that for each $x$ there is exactly one $y$ making the property true.

Of course, this definition of a function as being a "property" without further clarification does not meet the standards of precision and rigour one would find in a construction of mathematics on the basis of set theory. Tao presumably feels that such a construction is inappropriate at the level of his book. Obviously, since a "property" is not a set, Tao is correct in saying that, according to his definition of a function, it is not a set.

With respect to the question of whether the domain of definition is all of $X$ or not, I will make the following observations.

The distinction between a function (fonction) and a mapping (application) that you refer to does indeed exist in France (or once existed), but only at school level, not in higher mathematics in general. The reason is that one wants to be able to refer to a function such as $f(x) = 1/(x-1)$ as being a function from $mathbfR$ to $mathbfR$, even though it is a mapping from $mathbfR - 1$ to $mathbfR$. This distinction does not exist in English-speaking countries, as far as I am aware, and I don't know about other languages.

Even in France, other than in specific contexts, this distinction is not usually made by mathematicians. If one speaks of a function from $X$ to $Y$, one is saying that the domain of definition is all of $X$. One exception, to which Suzet alludes in a comment, is the theory of recursive functions, where one wants to be able to speak of a "partial function" from $mathbfN$ to $mathbfN$.

When the concept of a function is formalized set-theoretically, the most common approach is to define a mapping $f$ from $X$ to $Y$ as being synonymous with its graph, which is the set you define in (2).

This definition has much to be said for it, but it also has what some consider a serious deficiency. A graph $Gamma$ could represent a function $f$ from a set $X$ to a set $Y$, but the same graph could also represent a function from $X$ to any other set $Y'$ containing $f(X)$. There are areas of mathematics, particularly those where category theory is often used, where this is inconvenient, and one would like to consider two mappings $f colon X to Y$ and $f' colon X to Y'$ with the same graph $Gamma$ to be distinct objects. Consequently, Bourbaki defines the mappings $f$ and $f'$ to be the distinct triples $(Gamma, X, Y)$ and $(Gamma, X, Y')$, respectively. In this convention it has been followed by many authors, particularly in France where its influence has been greatest.

I think Tao's point is, on the contrary, that the reader should not confuse the abstract concept of a function with the particular representation of that concept that is used in set theory. Identifying them are typical of what he calls the "rigorous" stage of mathematical development, but he has higher goals than that. — Jul 26 at 0:52
@HenningMakholm Perhaps there are other formalizations of mathematics he has in mind, or perhaps he is arguing that it is not useful to formalize mathematics entirely. But you cannot have an uncountable Banach space consisting of "properties" which are descriptions given in words or symbols. They need to be formal objects of your theory. — Jul 26 at 0:58

Daniel Schepler 6,6681513 · Answer 2 · 2018-07-26 00:50:45Z

I think an answer to this question would have to go into philosophical questions on mathematical foundations. Currently, as far as I know, most mathematics education would present foundations based on ZFC. The basic idea here is that every object of consideration is considered to be a set, and then for any two objects $x$ and $y$ it is valid to ask whether $x in y$, and to ask whether $x = y$. This has the advantage of reducing things to a very small number of primitives, while still being powerful enough to eventually be able to represent almost all the useful mathematical concepts such as real or complex numbers, and yes, functions. (Though category theory does start to run into some theoretical issues when trying to express that in terms of ZFC...)

The disadvantage, though, is that this representation is "artificial" and doesn't really reflect the way that most mathematicians actually think about things on a daily basis. For instance, the most common "representation" of natural numbers in ZFC is: $0 = $, $1 = 0 = $, $2 = 0, 1 = , $, and so on. This is hardly a natural representation: we tend to think of natural numbers not as sets that you can compare by $in$ but rather as "atomic" objects that we can compare for example using $<$. Likewise, suppose for example that in an abstract algebra course you start off by saying "let $G$ and $H$ be two groups". Then you do think of $G$ and $H$ as being sets of elements; however, you usually don't think of elements $g in G$ or $h in H$ as sets themselves, nor do you usually think it would make sense to ask whether $g = h$ for $g in G$ and $h in H$ (or even if it is theoretically valid, it would almost always be considered an irrelevant thing to ask).

Going on to the subject of functions: at a primitive level, we tend to think of functions $f : X to Y$ not as an abstract set of pairs, but as some notion of a way of taking an element $x in X$ as input and producing some corresponding element $y in Y$ as output. Then, from that, we can indeed consider the graph of $f$ as a subset of $X times Y$; but we tend to think of this as being both more complex than the base "algorithm to transform input into output", and as being less useful in most cases.

So, some work has been done under the heading of "type theory" to try to come up with foundations for mathematics that are more natural and more closely reflect the mode of thinking of day-to-day mathematics, as compared to ZFC. The general idea of this philosophy for coming up with a foundational system is: we work with types that are considered to be incomparable; e.g. if $X$ and $Y$ are two different types, then in general it doesn't make sense to try to ask about $X cap Y$ or about $X cup Y$ (though many type theories do allow forming a disjoint union $X sqcup Y$). Moreover, the elements of a general type are considered to be "atomic" objects which are not considered to have any further internal structure. Also, functions are generally required to just be one of the irreducible notions which cannot be defined (just as the notion of "set" and the relation $in$ cannot be defined in ZFC). All we can do is to provide ways to take existing functions and build up more complex functions from them.

As an illustrative example of what such a type theory might look like, "simply typed lambda calculus" might be a good place to start. Here, the fundamental notion is of a "typing judgment" and of relations between them. For example, one valid "typing derivation" might be:

$$ X ~ type, Y ~ type, Z ~ type, f : X to Y, g : Y to Z vdash (lambda (x : X) . g(f(x))) : X to Z. $$

This says that if $X,Y,Z$ are variables representing types, and $f$ is a function from $X$ to $Y$ and $g$ is a function from $Y$ to $Z$, then the term $lambda (x : X) . g(f(x))$ forms a function from $X$ to $Z$, representing the composition $g circ f$. This would be proved formally from rules such as:

beginalign* Gamma & vdash phi : X to Y \
Gamma & vdash psi : X \ hline
Gamma & vdash phi(psi) : Y. endalign*

This says that if you have a context $Gamma$ (a list of things like $X~type$ or $term : X$), along with two terms $phi$ and $psi$, and in the context $Gamma$ you can prove that $phi$ is of type $X to Y$ and $psi$ is of type $Y$, then you can form a function application term and in the context $Gamma$ you have that $phi(psi)$ is of type $Y$.

Then, there are also type theories that extend this with assertions such as $tau~proposition$, $tau~true$, and add a formal proof system to work with these. Note that in keeping with the philosophy, it is much more common to use a natural deduction style of formal proof system in such an extended type theory as opposed to a Hilbert-style system. (Though a common alternative is to invoke the Curry-Howard correspondence which essentially says that type derivations, along with constructions such as product types and disjoint union types, are already enough to express the relevant first-order logic. If this is used, then in these formal systems, a proposition just becomes a special case of a type.)

So, these type theories do tend to map mathematical arguments more naturally into formal language. However, they do have some disadvantages as compared to ZFC. For one thing, they have significantly more primitive notions that have to be described in the metatheory, making a metamathematical study of the properties of a type theory possibly more difficult. Also, we do tend to think of relations such as $mathbbN subseteq mathbbZ subseteq mathbbQ subseteq mathbbR subseteq mathbbC$, whereas type theory tends to have difficulties in expressing such "canonical inclusion" relations.

To return to the original question, I'm not that familiar with Tao's Analysis text. But from the quote, it does appear that the author is subscribing more to the point of view of type theory that functions should be considered a primitive notion, and graphs of functions should be considered something you derive from the primitive - as opposed to the view of ZFC that a function is precisely a set satisfying certain properties.

I think of this situation as being like the distinction between low-level and high-level programming languages in computer programming - i.e. assembly languages vs. Java. — Jul 26 at 4:50
In assembly language, at least in a suitably simple processor, there are (mostly) no types, or, there's only one: "mash of bits" - a register just holds a mash of bits, memory holds mashes of bits, and you can do whatever you want to any two mashes of bits: what it represents does not constrain what you can do. You can have a mash of bits that's "supposed" to be the word "hi!", or another mash that's "supposed" to be the number 600, and you can multiply those two things together even though multiplying a word by a number makes no sense. — Jul 26 at 4:50
ZFC is the assembly language of maths. There's only one "type": a set, and everything is a set, and the only "operations" you can do are the set operations. Moreover, you can do them to anything, regardless of what it's "supposed" to represent, like take the union of a natural number and a linear functional, since those concepts only exist insofar as we use the data and don't break the rules we've set up while "programming" it down here. Those rules are not enforced by the system. — Jul 26 at 4:52
Type theories, on the other hand, are more like high-level languages like Java, for maths. They help to build more of our intuition and structure for things into the language, including type enforcement - e.g. now you cannot just add a text string and a number - but the cost is added complexity in the language specification. That is only sensible: if you want more structure, the information describing that structure has to go somewhere and so it goes into the language specification. — Jul 26 at 4:53
That said, I'm not necessarily so sure "losing" things like $mathbbN subseteq mathbbZ subseteq mathbbQ subseteq mathbbR subseteq mathbbC$ is really a huge loss. In particular - if the natural numbers, integers, rationals, reals and complexes are indeed different types of numbers, then it doesn't make sense to simplistically say one is a mere subset of the other. In a high level language, a variable of type integer is a different kind of thing from, say, a digit string, even if we might imagine a natural correspondence between the two. — Jul 26 at 4:55

score 6 · Answer 3 · 2018-07-26 06:37:01Z

up vote
6
down vote

I like and suggest the following definition:

A function $f:Ato B$ is a triple

a first set $A$ (domain)

a second set $B$ (codomain)

a law (i.e. a rule, a relationship, etc.) such that at each element of $A$ is associated one and only one element of $B$ that is

$$forall xin A quad exists ! yin B:,y=f(x)$$

edited Jul 26 at 6:37

answered Jul 25 at 23:31

gimusi

65k73583

why was this downvoted?
â€“Â Andres Mejia
Jul 25 at 23:33

I donÃ¢Â€Â™t know, it is an useful definition from my point of view which emphasizes the importance to declare the sets A and B and not only the law.
â€“Â gimusi
Jul 25 at 23:38

2

I didn't downvote, but I don't like the verb "is", as that sort of means you're saying that a function is, equivalently, 3 things, a first set A, ..., etc, which is nonsensical. Maybe the word "require" would be more precise.
â€“Â Jalapeno Nachos
Jul 26 at 1:57

1

But what exactly are the mathematical definitions of "a law" and of "associated with"?
â€“Â DanielWainfleet
Jul 26 at 4:18

4

What exactly is the mathematical definition of "a" and "the" and "and"? At some point you must express formal definition using either natural language or intuitive definition. As far as vagueness goes,this is certainly far from the line where more clarity would help rather than hinder. @DanielWainfleet
â€“Â Nij
Jul 26 at 4:56

Â |Â
show 5 more comments

Rob 761 · Accepted Answer · 2018-07-26 00:45:49Z

Tao defines a function from $X$ to $Y$ to be a property $P(x,y)$ of elements $x in X$ and $y in Y$ such that for each $x$ there is exactly one $y$ making the property true.

Of course, this definition of a function as being a "property" without further clarification does not meet the standards of precision and rigour one would find in a construction of mathematics on the basis of set theory. Tao presumably feels that such a construction is inappropriate at the level of his book. Obviously, since a "property" is not a set, Tao is correct in saying that, according to his definition of a function, it is not a set.

With respect to the question of whether the domain of definition is all of $X$ or not, I will make the following observations.

The distinction between a function (fonction) and a mapping (application) that you refer to does indeed exist in France (or once existed), but only at school level, not in higher mathematics in general. The reason is that one wants to be able to refer to a function such as $f(x) = 1/(x-1)$ as being a function from $mathbfR$ to $mathbfR$, even though it is a mapping from $mathbfR - 1$ to $mathbfR$. This distinction does not exist in English-speaking countries, as far as I am aware, and I don't know about other languages.

Even in France, other than in specific contexts, this distinction is not usually made by mathematicians. If one speaks of a function from $X$ to $Y$, one is saying that the domain of definition is all of $X$. One exception, to which Suzet alludes in a comment, is the theory of recursive functions, where one wants to be able to speak of a "partial function" from $mathbfN$ to $mathbfN$.

When the concept of a function is formalized set-theoretically, the most common approach is to define a mapping $f$ from $X$ to $Y$ as being synonymous with its graph, which is the set you define in (2).

This definition has much to be said for it, but it also has what some consider a serious deficiency. A graph $Gamma$ could represent a function $f$ from a set $X$ to a set $Y$, but the same graph could also represent a function from $X$ to any other set $Y'$ containing $f(X)$. There are areas of mathematics, particularly those where category theory is often used, where this is inconvenient, and one would like to consider two mappings $f colon X to Y$ and $f' colon X to Y'$ with the same graph $Gamma$ to be distinct objects. Consequently, Bourbaki defines the mappings $f$ and $f'$ to be the distinct triples $(Gamma, X, Y)$ and $(Gamma, X, Y')$, respectively. In this convention it has been followed by many authors, particularly in France where its influence has been greatest.

I think Tao's point is, on the contrary, that the reader should not confuse the abstract concept of a function with the particular representation of that concept that is used in set theory. Identifying them are typical of what he calls the "rigorous" stage of mathematical development, but he has higher goals than that. — Jul 26 at 0:52
@HenningMakholm Perhaps there are other formalizations of mathematics he has in mind, or perhaps he is arguing that it is not useful to formalize mathematics entirely. But you cannot have an uncountable Banach space consisting of "properties" which are descriptions given in words or symbols. They need to be formal objects of your theory. — Jul 26 at 0:58

Daniel Schepler 6,6681513 · Answer 5 · 2018-07-26 00:50:45Z