Jump to content

Talk:Function (mathematics)/Archive 12

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Archive 5Archive 10Archive 11Archive 12Archive 13Archive 14Archive 15

Content of "In computer science"

I am surprised about this section not being about complexity, computability, and other concepts pertaining to "Function (mathematics)", but containing material better dealt with in "Function (programming)", which is a redirect to "Subroutine". Imho, from the math POV the latter concept is either about specifying a certain class of math functions (algorithms?), or about evaluating them for some argument. Of course, the relevant aspects of programming languages, like typing, parameter passing, ..., and of implementations (side effects?), ... are important, but are outside the usual mathematical topic, and definitely outside the scope of an introductory article.

I would agree to remove the current content again, but won't do so on my own. Purgy (talk) 09:04, 31 December 2018 (UTC)

I agree with you. I'll try to write something that is convenient for this article, that is, that explains how the mathematical concept is used in computer science in a fundamental way. D.Lazard (talk) 11:22, 31 December 2018 (UTC)
The formerly empty section only had those links to function (programming) and to lambda calculus. That means that the section was intended to connect and distinguish the content of the two articles. It is good information for readers of this article the fact that in computer science things are called functions which are not function in the mathematical sense. But if you 'remove the current content again', then I will put it back again. Add to it, if you are able to. That section has been empty for long enough.
About 'using the concept of function 'in a fundamental way'. That is what lambda calculus does. How deep into computability do you want to go? Grzegorczyk hierarchy? Cactus0192837465 (talk) 12:08, 31 December 2018 (UTC)
I have rewritten the section. My guideline for that was to provide answers to people who want to understand the relationship between the mathematical concept and what computer scientist call a function. I am not sure that it is exactly what Purgy asked for (complexity seems not really relevant here), but, IMO, this is what should be here.
Happy new year D.Lazard (talk) 16:45, 31 December 2018 (UTC)
Before you re-add your re-write make sure you fix the following false claims and imprecisions. In the first sentence you say that '[A function is] a computer program, which implements the abstract concept of function'. Functions in computer science are not and have never been implementations of the abstract concept of function. That part of the sentence is incorrect. Saying 'imitate' or 'similar' would be correct, but what is the point if the precise description of what they are can be given, and was already given. Another thing present in this sentence and repeated later is calling functions 'programs'. A function can be the entire content of a program, but this can also consist of many functions, no functions at all etc. Program is an umbrella term. Use proper language. If you are not familiar with it use references instead what you image that the content should be.
You replace the claim 'The system [lambda functions] is expressive enough to allow modelling any Turing machine.' with 'It is a part of Church–Turing thesis that the functions defined and computed in lambda calculus are exactly the recursive functions.'. The first is a theorem proven by Church and Turing, the second is only an ambiguous consequence of this theorem. 'It is part', what part? Ambiguous. It is the thesis. Also, what is the point of replacing a theorem, with a conjecture/axiom?
A few lines before 'These [recursive functions] are functions from integers to integers, but can model any computable function'. This sentence is just claiming Church-Turing thesis willy nilly, which misguides the reader. Did you find a proof of Turing's thesis? Again, if you don't have a good command of the content that you are writing, don't make it up out of what you image it to be. Use references.
'well founded theory, the lambda calculus'. Well founded has a technical meaning in mathematics. Either use proper language to prize the formal model, or don't just call it formal model. In which sense is it founded 'well'? Cactus0192837465 (talk) 20:10, 31 December 2018 (UTC)
I am happy with knowledge being connected and don't object to mentioning Church-Turing thesis here. But it is funny how you were so happy to threw it in here moments after saying that Kempe's universality theorem was 'too technical'. Cactus0192837465 (talk) 20:46, 31 December 2018 (UTC)

Scope ambiguity of quantifiers in natural language

When a sentence is formed as

  • A function is defined by associating one element of its codomain to every element of its domain.

or

  • A function associates to every element of its domain exactly one element of its codomain.

The scope of the universal quantifier is ambiguous because we don't have parentheses to indicate it or subscripts etc. to indicate whether the elements being associated depends or not on the arbitrary element of the domain. In both examples the sentence could be read as a single element from the codomain is associated to all elements of the domain. The first one is specially bad because the 'every' is near the end of the sentence, so it is more likely for its scope to be interpreted as what remains of the sentence. In the second example the same ambiguity occurs, in my opinion it feels less dangerous because this time the 'every' is earlier in the sentence. However, the 'exactly one' exacerbates the possibility of choosing the wrong interpretation in the ambiguous sentence. Note, I am talking about ambiguity. Of course, they can also be interpreted the right way. The way that we would like.

Now

  • A function is defined by associating to every element of its domain a corresponding element of its codomain.

is strictly the definition. The 'every' quantifies the element of the domain, but now we not only have the indication that the element of the codomain is unique from it being a[n] 'element', singular, we also have the adjective 'corresponding', which indicates the dependence on the element of the domain.

If the key words are interpreted technically, still the same meaning holds. So, the sentence is not only correct in plain language, but also in technical language. Namely, a function map is a correspondence, 'associating' a[n] 'element', singular. This is, a map. And since in this article we apparently we need to mix the two notions, a binary relation that associates a corresponding element to each and every element of the domain. This is, a function. Cactus0192837465 (talk) 08:21, 10 January 2019 (UTC)

The editor who introduced the ambiguously scoped quantifiers is also confusing the roles of 'associating' and 'corresponding' in the proposed fix. The first is a verb, that indicates what the functions does, the second is an adjective that qualifies the element of the codomain as being dependent (as opposed of necessarily constant, for example) on the element of the domain. Their meanings in the sentence are entirely different. In particular, the second removes the scope ambiguity. If you have difficulties with grammar, as you introduced the scope ambiguity without noticing it, using 'pleonastic' instead of 'redundant' will not turn nonsense into an argument. Cactus0192837465 (talk) 11:18, 10 January 2019 (UTC)
There are several problems with the above analysis that directly impinge on what we should do as editors. First of all, let me say that scope ambiguity exists (and probably more so in English than in other natural languages), but whether or not this is a problem is a debatable point. It is certainly a problem if your interest is in machine readability, or any related disciplines. It is a problem if you are studying linguistics. However, it is not a problem in everyday activities, nor in teaching, where it can be considered an opportunity to broach the subject of technical language. Technical language was developed to overcome the shortcomings of natural language. What you are proposing is to revise the rules of our natural language so that it becomes technically correct. This, in my opinion, is a waste of time. If we need that level of precision, we already have a language to turn to for it; we do not need a second one. To obtain your ends, which essentially is a rewriting of the rules of grammar to exclude possible ambiguity, you need to contort and rely on shades of meaning that can be expressed in, but are not essential parts of our natural language. If you were to succeed in your program, our language would no longer be natural. Wikipedia is not the place to push your POV as you attempt to restructure the language. --Bill Cherowitzo (talk) 19:08, 10 January 2019 (UTC)
There is no re-writing of any rules of grammar. You are not understanding. Sentences with scope ambiguity are valid grammatically. There is no re-writing of any rule to avoid them. They exist. The point is not to turn them invalid. The whole point is that when doing technical writing if there is an unambiguous alternative, then it is best to use that one because then the meaning of the sentence is clear is unique. Since in this case there is, we should use it. When technical writing is done competently this is written in a way that it is clear without space for interpretations that are incorrect. That is one of the reasons why mathematics had to develop its special language. Because it is not always easy to resolve those ambiguities. But in this case it is. There is no POV here. The first two options present scope ambiguity. Anyone can see why, and are well-known examples of it. Cactus0192837465 (talk) 20:03, 10 January 2019 (UTC)
I believe that I understand you perfectly well, but I do not agree with you. It is common sense to prefer, when given the alternatives, an unambiguous version of a sentence. You seem to be proffering the opinion that this is always to be striven for, whereas, I believe that there is a cost involved and one must decide if the gain is worth it. If, in order to obtain these unambiguous forms, every reader must become a grammarian, able to determine the true meaning of a statement from subtle hints of grammatical style, then I think the cost is too high. We have developed ways of handling this problem in the natural language, and it consists of providing context for our ambiguous statements. When this fails, we have a technical language to fall back on. I see no need for your approach. --Bill Cherowitzo (talk) 22:05, 11 January 2019 (UTC)
Okay. You choose, for some reason, to prefer typical examples of ambiguous sentences when trivial alternatives exist that are not ambiguous. I hope it is not because you still think that a singular 'a corresponding element' would allow multiple elements. As you said yourself, I prefer common sense, and use the many unambiguous alternative phrasings possible. On the other hand, you said that I 'always' would do that. Probably when speaking or writing quickly I wouldn't. But when writing a textbook, publishing my results, or in this case writing an encyclopedia, yes I would. That is what is normally done in mathematics. Reasoning strives for precision, such that your readers understand exactly what you intended to say. You also mentioned 'cost'. What cost? Is anything being lost with the replacement? None is being asked to detect every case and replace it. I found this one and replaced it. If anyone feels like it and sees another one they are free to clean it up, or leave it. This is a collaboration. What is pernicious is that strange impulse that some have to try to revert the state to one that is well known to be less adequate. Cactus0192837465 (talk) 14:54, 12 January 2019 (UTC)

Request for comments on the change of corresponding into single in a sentence

Presently this first sentence of § Specifying a function is

According to the definition, a function is defined by associating each element of its domain with a corresponding element of its codomain.

In this sentence, the word "corresponding" is problematic. It has been introduced by Cactus0192837465 against a clear WP:CONSENSUS against it. In fact, Cactus has added this word 6 times in the same day, and has been reverted 5 times by three different editors, including myself.

Reasons for which this word is problematic: In this sentence, the word "corresponding" is ambiguous and confusing, because it may have several interpretations. Either, it may viewed as a pleonasm for enforcing the meaning of "associating"; this is not useful here, as, if the word is removed, the sentence becomes much clearer. Or the word may refer to a "correspondence" that is not defined here, and this makes the sentence not understandable. Or the "correspondence" is the function itself; in this case, this makes the definition circular. Whichever interpretation is the right one, the word makes the sentence confusing for the intended audience of the article, which consists of beginners in mathematics, who are not customized with functions.

Moreover, with or without "corresponding", the sentence does not define a function, but a multivalued function, since it is not recalled that there is only one element of the codomain that is associated with an element of the domain. This is the reason for which I have replaced "corresponding" by "single" in my last reverts.

Because, of WP:3RR, I'll not change again the sentence. Thus, please, comment on this change, and do it, if there is a consensus. D.Lazard (talk) 12:28, 13 January 2019 (UTC)

I'm afraid I've been sort of busy and haven't been able to keep track of everything that's been going on. I really hadn't intended to wade into such a mess. Maybe we can just take a different tack and do something like:

According to the definition, every element of a function's domain has an element of the function's codomain associated with it.

This avoids "correspond", which I agree is a bit vague, and hopefully mitigates the issues with placement of quantifiers (which is going to be awkward no matter what). –Deacon Vorbis (carbon • videos) 14:55, 13 January 2019 (UTC)
1. 'a corresponding element' is singular. It doesn't allow for multiple elements to correspond. Multiple elements simply cannot be called 'a corresponding element'. The fact that I have to explain such a basic rule (the difference between singular and plural) to adults makes me really worried that they are simply not prepared to understand the next point. But well. It is the Internet, where a very diverse fauna exists.
2. 'associating' and 'corresponding' are both different grammatical entities and have different meanings in the sentence. The first is a verb, while the second is an adjective. The first refers to what the function does, the second to a quality of the element of the codomain. The use of both is not only proper English, but removing the second changes the sentence from an unambiguous sentence into an ambiguous one. That fact alone is a good rule of thumb that indicates that the two words are not redundant. This fact becomes even more clear if instead of having the elements of the domain quantified by an 'every' or 'each', we have them listed.
A function associates 1,2,3 to a,b,c, respectively.
Who hasn't seen this sentence? Here, the adverb 'respectively' is again not redundant. It indicates how the association works. Being an adverb it qualifies the verb instead of the noun, but the quality that is being applied is the same meaning. Namely, each choice of an element of the first list goes with the corresponding element of the second list: , , and . That is exactly why the sentence without 'corresponding' becomes ambiguous. In our case, instead of the adverb 'respectively' we are using its adjectival analogous, which is 'corresponding'.
A function associates 1,2,3, to their corresponding a,b,c.
Notice that the sentence with the universal quantifier can also be turned into the one using the adverb.
A function is defined by associating each element of its domain with an element of its codomain, respectively.
It just sounds more awkward to me. This form sounds better when the elements are a list. But it is also fine.
2.5 'if the word is removed, the sentence becomes much clearer'. If anyone follows the link I provided in the section above this one, or simply by googling articles about 'scope ambiguity' they can see that the sentence without 'corresponding' is the exact structure of the typical examples of a sentence with scope ambiguity. So, this claim that the sentence becomes clearer is proven to be false.
3. With all this being said, there are potentially many other ways in which the sentence can be written. For example, someone changed it already from the one that I originally wrote. I think they changed 'every' for 'each'. Before that, there was before an exchange between two editors about whether to mention the domain first or the codomain first. Any such change is fine with me. The only thing that I disagree is using an ambiguous sentence when unambiguous ones exist. Specially if it is due to a poor understanding of grammar. Cactus0192837465 (talk) 15:03, 13 January 2019 (UTC)
The version that Deacon Vorbis suggested looks good too. Cactus0192837465 (talk) 15:04, 13 January 2019 (UTC)
In my opinion, the sentence about which comments were requested has its drawbacks with and without "corresponding". I'd favor Deacon Vorbis' version, but would change "has an element" to "has exactly one element", to meet the objections about multivalued functions. - Jochen Burghardt (talk) 19:30, 13 January 2019 (UTC)
If you list the drawbacks that you see then your comment can turn from a mere opinion to something objective that can either be refuted or supported. I think that adding 'exactly one' is redundant. On the other hand, that's not a big deal. I would be fine with that version too. I wonder if mister pleonasm would recognize this as such. But maybe not, given that he doesn't recognize that 'an element' is singular. Cactus0192837465 (talk) 21:36, 13 January 2019 (UTC)
I agree with Jochen's suggestion. Leaving aside the correctness of the statement under discussion, I consider it an example of poor writing because it buries the essence of the concept in the proper interpretation of a grammatical rule. Proper understanding relies on the reader's ability to parse the sentence correctly. If we expect this ability from our readers, I think we are not giving them a fighting chance to understand the material. When we are criticized for being mathematicians writing for mathematicians, it is this type of issue that underlies the criticism and makes it hard to counter that argument. --Bill Cherowitzo (talk) 21:50, 13 January 2019 (UTC)
Jochen's variant of Deacon's suggestion is fine for me. I would have put "a single element" instead of "exactly one element": this is less jargon, and thus, if it is colloquial (I am not able to judge this point), it could be better. D.Lazard (talk) 10:52, 14 January 2019 (UTC)
I'd be fine with "a single element", too, but I'm not a native English speaker either. - Jochen Burghardt (talk) 11:59, 14 January 2019 (UTC)
Shouldering the burden of speaking for native English speakers, I would say that "a single element" is the right way to go here. The alternative does make one sound more like a mathematician, which, in this case, would send up red flags among the intended audience. The less jargony (oh, spellcheck will not like that word), "a single element", sounds more like it came from a real person. --Bill Cherowitzo (talk) 20:07, 14 January 2019 (UTC)

Section "Specifying a function"

Although this discussion may be winding down, there is still a big problem later in the same paragraph, where the current version states "When the domain and the codomain are sets of numbers, this association may take the form of a computation taking as input any element of the domain and producing an output in the codomain. This computation may be described by a formula." Or rather at least five problems packed into these two sentences: (1) the first sentence appears to be about algorithms, and falsely implies that all functions over numbers may be expressed as an algorithm, but this is not true; (2) only certain types of numbers are amenable to exact representation in algorithms, so we should be more careful about what kind of number is intended; (3) lots of things that are not numbers are also allowable as the input and output of an algorithm, so we should avoid the false implication that this kind of representation can only be used for numbers; (4) formulas do not generally describe algorithms; they describe the intended i/o behavior of the algorithm but not how it performs the computation; (5) the second sentence appears to imply that every algorithm can be represented by a formula, which is not true under most intuitive definitions of formulas, and it is also not true that every function can be represented by a formula or that every formula can be implemented by an algorithm. Making these distinctions accurately probably requires going far beyond the level of technicality we are aiming for, but it should be possible to rephrase things staying at the current level of technicality without being so completely incorrect. —David Eppstein (talk) 01:23, 15 January 2019 (UTC)

All your points are correct. They appear to say that due to the ambiguity of the meaning of 'may'.[[1]] The phrasing should be easy to fix by avoiding that word. Cactus0192837465 (talk) 02:22, 15 January 2019 (UTC)
I added one new possible version that avoids the 'may'. I also added another form of the use of formulas to specify a function. That should serve to distinguish formula from computation or algorithm. It is probably enough in this article to hint at the distinction through the use of examples like this. Distinguishing them doesn't have to be made into an explicit goal in the section. It can be left as a fact that is applied correctly in the exposition, and that is intentionally made apparent in the subtext only when read by those who know the entire story. Cactus0192837465 (talk) 04:15, 15 January 2019 (UTC)
I agree with David's remarks. I have reverted the last Cactus' edit because it does not solve these issues, and introduces an awkward second sentence that cannot be correctly understood by the intended audience. IMO, this section must not edited before a consensus will be reached.
My opinion is that this section must be restructured for clearly presenting the different ways of specifying a function, ordered by increasing technicality. Here are these methods of specification (some are presently lacking in the article):
  • If the domain if finite, a function may be specified by listing the elements of the codomain that are associated to the elements of the domain.
  • A function is often specified by a formula that may involve arithmetic operations, and other functions that have been previously defined
  • A function may be defined by a characterizing property; for example the natural logarithm is often defined as the unique function from the positive real numbers to the real numbers, which is differentiable, has 1/x as derivative, and takes the value 0 for the input 1.
  • A function may be defined by an algorithm for computing it. Such an algorithm may result from a formula that defines the function, but many algorithms for computing functions cannot be reduced to a formula.
  • A function may be defined recursively. This means that the function is defined by an algorithm which, for computing a value of the function, uses other values of the same function that have been previously computed (example of the Fibonacci sequence).
  • Many functions may not be explicitly defined (problem of cardinality), although their existence is fundamental in some areas of mathematics.
If there is a consensus for such a structure, I'll try to rewrite the section accordingly. D.Lazard (talk) 10:44, 15 January 2019 (UTC)
It is interesting how your explanation of what you think should be done is riddled by exactly the faulty language that this article contains all around.
  • The use of 'may' to indicate possibility, ignoring that it can also be read as plausibility. (46 occurrences in the article).
  • The abuse of words that indicate frequency like 'often', when there is no feasible test for such claim. (26 occurrences).
Your claim that my edit didn't fix the issue that must likely you introduced is just plain false. What was required was to expose properly the role of formulas and algorithms without mixing them up, and that was done in what I wrote. You were unable to mention a single incorrect claim, unlike what happens to the state to which you have reverted the article. I edited the section because no conflict existed about it but the first sentence.
But let's see what new problem you create. Try, if you are able, to re-write it without making again a disaster confusing formulas, algorithms, implicitly stating Church-Turing thesis as a fact without comment or naming it before a paragraph that named it, misrepresenting the definition of function in computer science, ignoring scope ambiguity, ignoring the ambiguity of the meaning of 'may', ignoring how to recognize the very notion that you proudly tried to apply, pleonasm. Yes, I can point at actual problems. But if you manage to write a clear text without so many conceptual mistakes, then I am fine with it. Cactus0192837465 (talk) 13:17, 15 January 2019 (UTC)

I’m very late to the party discussion. But I need to mention that there is a question of whether a function is an elementary function (and often the answer is not obvious). This is closely related whether there is some “closed form” (again an important term needed to be mentioned) for given a function. — Taku (talk) 15:20, 27 January 2019 (UTC)

Sure, that's fine. It could be mentioned. Probably it is better not to mention 'closed form'. That is an ambiguous concept, if not properly defined, and there are many options on how people define it. Settling for one wouldn't be correct. Listing some would be too much noise to mention 'closed form' in a way that is not ambiguous. But elementary function might be okay. Maybe just a link, as you already did, is enough. Cactus0192837465 (talk) 16:23, 27 January 2019 (UTC)
This fits well in the above proposed structure: the second item may be expanded as "A function is often specified by a closed-form formula, involving arithmetic operations and other functions that have been previously defined. In particular, the elementary functions are those that may be defined by a closed-form formula involving only constants, arithmetic operations, exponential functions, logarithms, and roots of polynomials.[1]" This mention "closed-form" and "elementary function" without "noise", and without ambiguity (every acceptable definition of a "closed-form formula" allows specifying functions). D.Lazard (talk) 17:02, 27 January 2019 (UTC)

References

  1. ^ Here "elementary" has not exactly its common sense: although most functions that are encountered in elementary courses of mathematics are elementary in this sense, some elementary functions are not elementary for the common sense, for example, those that involve roots of polynomials of high degree.
Closed-form formula is a badly defined concept. Therefore, the first sentence is not only ambiguous, but depending on the definition that one picks it can even be tautological. And using 'closed-form formula' to define 'elementary' is just ruining a definition that can be given without any ambiguity in the same space. There is absolutely no need to say 'closed-form formula' there, when one can say 'finite number of arithmetic operations and composition of ...' You really have incredible skills to write mathematics badly. Simply copying from Wikipedia's article would have allowed you to write a proper definition of elementary function. Cactus0192837465 (talk) 21:11, 27 January 2019 (UTC)
Well, it is tricky to define "pornography" but the term is still universally well understood (if not to aliens?); "closed-form expression" is a similar case. When people say a function is given by a formula, roughly this is what is meant and therefore has to be mentioned. We don't need to define "closed-form expression", but can still be described.
I'm basically in agreement with D. Lazard's proposed structure. But to add:
  • Currently, the section gives an impression that either a function can be defined by a formula or not at all. This is false or at best misleading. Just consider Riemann zeta function, which is given as a series, which is arguably a formula, when the real part of the complex variable is large enough (> 1) but not so in general. The general problem is that the section is written too vaguely ambiguously; "sets of numbers"? "This computation may be described by a formula."? I cannot completely tell whether zeta function fits into these descriptions. (Perhaps this is the point Cactus0192837465 is trying to make).
  • "Algorithms" defining a function is, while I can guess the intent, is problematic. Does Gaussian elimination determines a function? What about Euclidean algorithm? It's possible to fit these methods/operations/processes into a "function" terminology but is not quite typical; so should somehow be clarified. What about infinite iteration of a function? Is it still a function?
Basically speaking, the section lacks a sort of sharpness/clearness (due to the lack of specificities, I imagine). -- Taku (talk) 23:30, 27 January 2019 (UTC)
Your example about pornography has nothing to do with this. Some uses of 'closed-form' have meaning that are precise. The problems are that there are many options that are used depending on the context, and that one needs to explain them. Take into account that this is only the article about functions. There are more important things to say than name dropping an ill-defined concept. And definitely not using it to define elementary functions, specially since its definition is precise using only well known concepts. Everybody agrees with the structure and that currently it is ambiguous. The problem is whether the self-proclaimed responsible to write it can write it correctly, without deceiving the reader, letting in logical fallacies in the exposition, or ambiguous English.
The points that you add later have some confusions in them. Correcting them is going to be too much of a digression. Let me just mention the first two and you do your own research on the rest. An infinite series is a formula in a language in which you can write infinite series. The language of a grade schooler only needs the new symbol for that. The Riemann zeta function certainly can be given by a formula. Cactus0192837465 (talk) 01:37, 28 January 2019 (UTC)
Sorry I don't understand why you cannot understand me. "porn" is a perfectly good example of an ill-defined concept. Also, a Riemann zeta function is a very good example of a function that is given only partially by a formula and it is important to point this out (not every value of the zeta function is given by a series). I mentioned this example in part because it is not clear whether a formula here refers to an infinite series or not. This is a type of unclearness that I wanted to point out as problematic. Anyway, yes, some rewriting is needed, as everyone seems to agree; so I will try to give a shot, doing that. -- Taku (talk) 03:19, 28 January 2019 (UTC)
Since just doing it is easier than giving an explanation of doing (rewriting), I have started Draft:Specifying a function. It's not polished and I'm sure it has several problems, but I think it still shows a right direction. Other editors are very welcome to edit the draftpage too. Please note I have tried to eliminate ambiguous language (many confusing "may"), as much as I can. -- Taku (talk) 04:20, 28 January 2019 (UTC)
Just read the very article that you linked. There are plenty of formulas to define the Riemann zeta function at every single point of its domain. With the functional relation and the formula that you already know you should be able to write yourself such a formula. If not, read further down and you will find further options. Maybe take a look also in the article about formula? Although that article is rather vague. Maybe better Well-formed_formula. You will be in real trouble if you had to define a function that cannot be defined by a formula. But of course, the previous sentence makes no sense on its own if one doesn't specify in what language. Cactus0192837465 (talk) 12:22, 28 January 2019 (UTC)
Yes, "closed-form formula" is a concept that is not accurately defined ("ill-defined" is much too strong here). "Car" and "truck" are also non-accurately-defined concepts, but all three concepts are useful for communicating, as far one does not try reasoning with them. In the case of closed-form formula, you will hardly find two mathematicians agreeing on a definition, but, given a particular instance, they generally agree. Therefore, it is useful to use it. Moreover, as this is a widely used term, Wikipedia must refer to it, even if some editors (most?) think that it should not be used.
It is because of the lack of an unambiguous definition that I have included one: "involving arithmetic operations and other functions that have been previously defined". This is not a formal definition (which would be too WP:TECHNICAL here), but it is straightforward to formalize it as a formal language. So, as used in my formulation, "closed-form formula" is not really ambiguous, and if some ambiguity remains, this would be harmless, as the only consequence would be that more kinds of specifications would fit in several categories.
About zeta function: in my definition of "closed-form formula", I have implicitly excluded quantifiers and implicit function definition, such as "f(x) = y such that P(x, y)". I believe that, for most people using the term "closed-form formula", this is not a closed-form formula. This is the reason of including the specification by "characterizing property". It must be noted that "characterizing property" includes function specifications that do not provide any explicit association between values of the variable and values of the function. This is the case of zeta function, which is generally defined as the unique holomorphic function defined in the whole complex plane, except for z = 1, which equals some infinite product for Re(z) > 1 . There is no series or infinite product that converges to zeta function in its whole domain of convergence. So there is not "formula" expressing the function value in term of the variable value, in the whole domain of the function, even if one accepts series and infinite products as formulas. D.Lazard (talk) 15:07, 28 January 2019 (UTC)
Everything was fine until the last two sentences. You know that something like is a formula too. The 'So' (implication) of the last sentence is an incorrect conclusion. Formula, is a language-dependent concept. If you have something that you consider a formula for one region of the complex plane, and a functional relation that allows you to produce the definition on the remaining points, then you can write an explicit formula for all the points. That is just keeping the argument quite elementary. If not, just pick the formula with Jacobi's theta function, or Abel-PLana's formula. In any case, this is just too much digression. As I said, if thinking a little is not at hand, simply reading the relevant article is enough to know that that claim is false. It shouldn't appear anywhere here.
The other strange thing is, why mentioning that an implicit definition wouldn't be considered a closed-form formula, and then in the final conclusion say that there is no formula for the zeta function? The adjective 'closed-form' got dropped and with it all logic. Cactus0192837465 (talk) 16:07, 28 January 2019 (UTC)
Bring radical is a function that is defined as an implicit function. Not only nobody would consider it as defined by a closed-form formula, but it it has been introduced just because of the lack of a closed-form formula (Abel–Ruffini theorem). Also, in common sense, "formula" has a much wider meaning than "closed-form formula". Personally, I consider that an algorithm that compute a value is a formula, but many people would disagree. However, everybody would agree that an algorithm is not a closed-form formula. One may argue endless whether a case definition such as is a closed-form formula, a formula or something else. But, in any case, one cannot define Riemann zeta function this way, as infinitely many cases would be needed.
Again, all these considerations are much too technical for belonging to this article. D.Lazard (talk) 17:32, 28 January 2019 (UTC)
Ok, I simply cannot argue with so many mathematical mistakes. Did you even read what I said? What I said was wrong to was your last sentence, which said
> "So there is not "formula" expressing the function value in term of the variable value ..."
See the missing "closed-form" from there? The claim with the missing "closed-form" adjective is wrong.
The formula for the zeta function that I implied from using the definition that everyone knows and the functional equation only requires 2 cases and the named formulas that you can find in the article (which you clearly didn't read before replying) have only one case each. This is just ridiculous. Don't you get ashamed posting such things signed with your name? What the heck. You don't even need to think, only click the link and read.
The Bring radical is the value of an hypergeometric function, so yes, there are contexts in which that is considered a closed-form. Ask Doron Zeilberger and all the people who have worked in algorithms to reduce summations to finite sums of hypergeometric functions if in their works hypergeometric terms are considered or not closed-form. Or open their book titled "A=B". So, don't put words in everybody's mouth that are only based in your own ignorance of the topic. Cactus0192837465 (talk) 18:58, 28 January 2019 (UTC)
I think we are getting off on a tangent: this article nor the talkpage is a place to discuss what a closed-form formula is (so I will not comment on the zeta function debate above). But I think the example like that need to be mentioned in the section, so to avoid the impression the formula can describe a function on some part of the domain if not the entire domain (it is a common misconception to conflate power series and a function and that misconception need to be dispelled.) So, is there a general agreement that Draft:Specifying a function can replace the existing section? For me, it is the implementation of Lazard’s proposal and I think it’s a general improvement (though it needs polishing). —- Taku (talk)
There is a general question of: given a function, can you write a computer program implementing it? The answer is (of course) no in general but I don't think this section is the best place for that discussion, much better to discuss in a section with a name like "Computability / programability of a function". -- Taku (talk) 23:07, 28 January 2019 (UTC)
Looks good to me. I didn't find any errors. It can always be expanded and changed. The content of Wikipedia never has a final form. I made a note about a small point, though. Saying that "Sometimes, formulas can be given, that define functions." could suggest that sometimes formulas cannot be given, that define a function. As far as I know, that is not possible. Or, since I suspect that that impossibility claim is equivalent to Church–Turing–Deutsch_principle, then let me say: As far as I believe, that is not possible. Since the question of whether functions exist at all that cannot be given by a formula is well beyond the scope of this article, I thought that is it better staying safely away from that question. For example, saying something like "Formulas are often used to define a function" instead. Cactus0192837465 (talk) 23:43, 28 January 2019 (UTC)
Since there does not appear to be a strong objection to the draft of the new version of this section, I will be merging back Draft:Specifying a function in a day or two (after making some further minor edits).
On the "computation" issue, no, I think the article does need to discuss this aspect; at least, mention this above "obvious" question. Of course, the question can be unanswerable, etc and I'm not the person to add a discussion on this topic. But the article needs to discuss it. -- Taku (talk) 21:46, 30 January 2019 (UTC)
This is now done. -- Taku (talk) 23:32, 2 February 2019 (UTC)

Article bloat

The recent flurry of work here has reminded me that this article is really too bloated. I don't want to get into all the specifics right now, but my general feeling is that a lot of this stuff shouldn't be in here or should at least be pared down. For example, there's a section for § Function of several real or complex variables, which is even tagged for expansion. This is way too specific for such a general article. We can link to the main articles elsewhere if they aren't already, but there's already discussion of multivariable functions. –Deacon Vorbis (carbon • videos) 17:12, 31 December 2018 (UTC)

Those sections were just empty for a long time, with the tag for expansion also existing for a long time. I also think that those topic don't deserve as much as a section, when a mention in a sentence with a link is enough. But the existence of the sections with the tags suggested that people wanted them. So, I did what the tags were asking. Maybe they existed empty (together with a few false statements) only due to laziness and those who feel owners of the article only awaken when they see new hands touching it. I am for downgrading those little sections to just a mention of each term (with the links to the other articles) in a sentence or two. Cactus0192837465 (talk) 17:20, 31 December 2018 (UTC)
On the other hand, I also think that sectioning, with the different fonts that appear as a consequence, is useful to quick searching of the information for the reader. It is harder when the information is embedded in prose. Maybe it is just enough to remove the tags for expansion. Cactus0192837465 (talk) 17:26, 31 December 2018 (UTC)

I agree with this observation (too bloated) and therefore I have boldly deleted some of the sections I thought are too specialized. There are also some duplications (like a graphing a function); further consolidation should help shortening the article. -- Taku (talk) 23:44, 2 February 2019 (UTC)

On the characterization of the equality of functions

The article cannot contain logical errors. Given the whole mess that textbook writers have left us with whether the codomain is part of the function or not a clear correspondence between each definition and the corresponding form of the characterization of the equality of functions has to be made.

  • When functions are defined as relations (set of ordered pairs), the characterization of equality of functions cannot have the equality of codomains included in it. The codomain cannot be determined from the set of ordered pairs. Blame the logicians who popularized this definition.
  • When functions are defined as correspondences (triple of domain, codomain and relation) then the characterization of equality must have the equality of codomains included.

Since this article has had to present both variants, we have to deal with presenting both equivalences, but we must do it as they are. We cannot mix them as giving the definition of functions as relations, and then immediately saying that equality of functions requires equality of codomains, or of course the other wrong way of giving the definition of functions as correspondences and forgetting to include the equality of codomains in the characterization. Cactus0192837465 (talk) 13:24, 3 February 2019 (UTC)

The article is getting into a bit of a mess. Links for the Apostol and Kaplan cites no longer work. And functions now are equal even with different codomains. Are peoole now going back to old style functions when just the graph defined the function completely and one always has to sppecify the codomain as well otherwise things like surjective are meaningless? Are we really taking Apostol as the source for the definition of functions? Surely we went through this argument some yyears ago and it was determined the main definition of function required the codomain annd that not requiring the codomain was a secondary definition that needed to be handled in a subsection? Dmcq (talk) 13:25, 3 February 2019 (UTC)
No, don't confuse what I have said. I have given two implications, not definitions. I am not dictating that functions should be considered equal with different codomains. I am saying that **if** functions are defined as sets of ordered pairs, then their equality has nothing to do with equality of their codomains. Since the section with the change defines them that way, then the theorem must have that form to be correct. Cactus0192837465 (talk) 13:31, 3 February 2019 (UTC)
Some clarification on the equality of a function. I haven’t introduced anything new. This is simply the same statement that appeared in the previous version of the article (see for example [2]) If you want to drop codomain from the requirement, you need to establish the consensus at the talkpage to do so. (For the standard convention, see for example [3] and many other related threads). —- Taku (talk) 13:55, 3 February 2019 (UTC)
”Trust me I know I’m right” isn’t an argument, I know, I know. But the standard definition of a function includes “codomain” as a part of the definition of a function. Dropping codomain has an ugly consequence like asking whether a function is surjective or not doesn’t make sense. Some authors do use some non-standard convention but presenting such variant as normal is very confusing to the readers. We need to stick to the standard def (almost) everyone uses. —- Taku (talk) 14:17, 3 February 2019 (UTC)
Also, on relation vs correspondence. Again, this depends on authors. For example, when one considers the category of relations, a relation comes with domain and codomain; i.e., a relation is an ordered triple (not just a set of ordered pairs). Please follow the link. So, even a function is defined as a relation, depending on a def of relation, “codomain” can be considered as a part of def of a function. —- Taku (talk) 14:45, 3 February 2019 (UTC)

@Dmcq: The problem is that not everyone follows the past discussions; so the decision like "main definition of function required the codomain" needs to be codified in the article (not to the memories of the editors), which I will do in moment to save everyone's time. -- Taku (talk) 11:08, 5 February 2019 (UTC)

Well either the definition just from the graaph or the definition with the triple make sense, and I think the tripe is the main one. I have a great regard for Apostol but I haven't the foggiest why that definition has the domain and the graph but not the codomain, after all for a function one can get the domain from the graph. Unless one also includes partial functions of course. Or perhaps it is at the other end of the scale from my ythinking that the domain and codomain are best inclluded as just talking about the square function would the graph include integers or reals or complex numbers and the graph is different for each - perhaps a huge graph cut down by the domain is what is at the back of the Apostol definition. Dmcq (talk) 11:17, 5 February 2019 (UTC)
I agree the triple one (X, Y, f) is the most precise version; the issue I'm guessing is that it would look too technical to beginning readers. I have thus added a footnote to explicitly state domains and codomains are parts of a function. I feel like it is we the editors who care the most about this issue not the actual readers... Also, I don't think we need to follow Apostol; sometimes calculus textbooks have strange definitions for the pedagogical reasons and they don't make a good reference because of that. -- Taku (talk) 11:35, 5 February 2019 (UTC)
User:Dmcq, I think that you can still keep having high regard for Apostol (and Kaplan too), since his exposition is the least disingenuous among many introductory books. He does have a concept for which properties like onto make sense. He reserves the word map for this. The reason why he took the trouble to separate them is because since the arrival of the foundational work after Hilbert, functions were defined (and myriads of books still do) as the set of pairs. The problem has been the textbook writers, who have neglected to do their work properly. Many keep defining in their books functions as sets of pairs, and then magically the property of being onto is introduced, inconsistently of course. Cactus0192837465 (talk) 13:48, 5 February 2019 (UTC)
I've no problem with people considering the graph to be a function instead of the triple. My beef with Apostol was with him having a tuple of the graph and the domain but not the codomain. That just makes zero sense. The graph definition is common in set theory and the triple definition is common when talking about types of functions. Apostol's definition is just unpleasant. Dmcq (talk) 01:01, 8 February 2019 (UTC)
When you specify the domain as well as the codomain, you get a partial function. So if you want to talk about functions rather than partial functions, it makes sense to omit it. —David Eppstein (talk) 01:24, 8 February 2019 (UTC)
He omits the codomain, but keeps the domain. In the triple definition the domain makes sense as one is talking about functions from the domain to the codomain, for instance functions from the reals to the reals. You don't get a partial function because that's the definition. And partial functions are such because they follow a different definition - and the concept only applies if one does have a domain. Dmcq (talk) 14:18, 8 February 2019 (UTC)
All functions have a domain. It is the codomain that is being discussed here. I don't understand what you mean by a "partial function".Rick Norwood (talk) 16:21, 8 February 2019 (UTC)
If you specify just the set G of ordered pairs (x,f(x)) (the graph of the function) then you don't know from that information whether the function is surjective. So it makes sense to specify instead the pair (G,C) where C is the codomain and every f(x) belongs to C. You do already know the domain of the function, though: it is just the set of x's in the pairs in G. If you specify a function as a triple (D,G,C) where D is the domain then the specification is redundant because you're specifying the same set D in two ways: as D and as the set of x's in the pairs of G. So you either have to additionally require that these two sets are equal (in which case, why bother including one of them in the definition when it can be derived from other information) or allow D to be a proper superset of the x's in G (in which case what you have is a partial function: something that has a value only on some of the elements in its domain, not all of them). —David Eppstein (talk) 18:42, 8 February 2019 (UTC)

With all due respect to Apostol, in most textbooks I'm familiar with a function consists of a domain, a codomain, and a well-defined method of finding the output from a given input. That well-defined method need not be a "formula"; it can be, for example, analytic continuation. It need not even be computable. But it has to be a method. To define f(x) as a random number, for example, would not be well-defined. Then the set of ordered pairs is the graph of the function. As observed above, if we followed Apostol, we could have two equal functions, one of which was surjective and the other not. That makes no sense.

In the history section, we can mention earlier definitions, including "function" as "formula", and also Apostol's definition.Rick Norwood (talk) 12:46, 8 February 2019 (UTC)

All this discussion is rather surrealistic. It seems that everybody agrees that the domain is a part of the definition (specification?) of a specific function. Unfortunately, this is rarely the case in calculus and its applications, particularly in physics. In many cases, the domain is not given a priori, but results of a computation, which may be difficult (how to compute the domain of the square root of a polynomial of high degree?), and even outside the possibility of the current technology (the domain of where is the Riemann zeta function, depends on Riemann's hypothesis). I know that these examples are partial functions, but partial functions are functions, and I guess that most of our readers do not care of this distinction, which is not really important for them. So, we need a compromise between a formulation that is formally correct, but necessarily too technical for this article, and a formulation that is useful, and not confusing for most readers. I have not a clear opinion on the best compromise, but the preceding discussion is of no help for that. D.Lazard (talk) 18:39, 8 February 2019 (UTC)
For me, the current version is the best compromise we can get: surely, the ordered triple def is the most precise version and it is the version that will be too confusing to non-technically minded readers. We however still mention it at the footnote for few readers who care about this issue. We then mention a variation; e.g., a partial function is also sometimes simply called a function (i.e., the domain of definition might differ). -- Taku (talk) 00:36, 9 February 2019 (UTC)
Aside from the codomain issue (continuing the discussion in the above thread), the "well-defined" stuff need to be more clearly articulated (I don't believe the current content in sections like "Specifying a function" is enough, while correct). For example, in addition to the zeta function example (which, wow, depends on a conjecture!), how do we deal with a choice function? It is an example of a God-given function. -- Taku (talk) 00:36, 9 February 2019 (UTC)
I'm with having both options - functions defined just by the graph and functions defined by a triple. They are useful for different purposes. For practical purposes in applied mathematics the graph version is often best and it is usual in set theory whereas when people are taking about function spaces for instance the tuple version is best. And in Wikipedia we're supposed to cover the main options in proportion to their importance. It seems here either can be more important depending on the area of interest. Dmcq (talk) 01:16, 9 February 2019 (UTC)

The domain is always a part of the function, especially in calculus. Consider, for example, the calculus theorem that every differentiable function is continuous. The function f(x)=tan(x) is differentiable and therefore continuous, on its domain. It is not differentiable or continuous at pi/2, because pi/2 is not part of its domain. Admittedly, a lot of my students don't know this, until I point it out to them. Of course, not every domain can be computed. Not every function can be computed. For example, by the axiom of choice, we know that a well ordering of the real numbers exists. Let < be such a well ordering, and define a function from the natural numbers into the reals based on that well ordering, where f(1) is the least real, f(2) the least real other than f(1), and so on. By the axiom of choice, that function exists, but since no well ordering of the reals is known, that function cannot be computed. But, no matter how we define a function, it must by its very nature have a domain. If we define it by a formula, the domain does not contain any points that cause division by zero, or any other point where the formula leads to an expression that is not defined. If we define it by a set of ordered pairs, the set of all first elements is the domain. Rick Norwood (talk) 13:42, 9 February 2019 (UTC)

New version of section "Specifying a function"

I have just installed a new version of this section. The main changes are the following:

  • Restructuring by replacing bulleted-list items by subsections. This allows more details for each item and an easier synthetic view of the content.
  • Making easier for a non-specialist to get quick explanation on many terms and concepts that appear often in the context of functions
  • Referring to other articles for technical details. In particular, the "recursion theorem" has been moved to Recurrence relation (To editor TakuyaMurata: the incomplete reference to Jacobson's book has been moved too; so, it must be completed there)
  • Avoiding any technical reference to Closed-form expression and its ambiguous meaning, by simply defining informally the classes of formulas that are considered
  • Putting "inverse and implicit functions" outside calculus, as calculus is only implied for providing a choice criterion in the preimage of an element
  • More emphasis on differential equations than on power series, and clarification of the role played by power series.
  • Removing the reference to the axiom of choice, as too technical here
  • And so on

This increases significantly the size of the section; my opinion is that this may be useful for many reader. D.Lazard (talk) 18:36, 20 February 2019 (UTC)

Subsection "Calculus of variations"

Purgy Purgatorio has added this subsection to section "Specifying a function". IMO it is too technical for this place, and should be either removed (my opinion) or moved down toward the bottom of the article. In fact, the section has been written for people who know what everybody knowing a little of mathematics should know, or, at least, should have encountered and possibly forgotten. In other words, it has been written as a guide for articles where basic functions are defined and studied. Sure that the calculus of variations allows defining functions, but this is not its primary use (its primary use is some kind of optimization), it requires much more advanced knowledge, and I do not know any standard function that is defined by using it. Therefore, I'll remove this subsection, but I would agree to restore it if there is a consensus for that. --D.Lazard (talk) 18:07, 22 February 2019 (UTC)

Since I wrote this text, I feel obliged to defend it, be it with or without any support from the authorities that are. Taking up the above sequence of arguments, I think:
- Calculus of variations is not that much more technical than e.g. the Bring radical, but way more influential.
- In fact, I wrote that subsection for people, who know what everybody knowing a little of mathematics should know, or, at least, should have encountered and possibly forgotten, but who are bold to look beyond this horizon, and take the chance of a 5-liner to sort out a few buzz words that meanwhile may have entered their consciousness ("Principle of least action"!), enjoying the offer of links in every line, hopefully leading to enlightenment.
- I am incapable to classify the primary purpose of variational calculus (I never saw offered the chance to indulge in this topic at a formal level that suits my requests), but I consider deriving equations of motions in GTR, or functions relevant within the standard model of particle physics as appearing on the show box of calculus of variations.
- I do not dare to ask for any support of keeping my amendment, not even for improving it, but can't help thinking that a few lines on topic, with important consequences, and with links leading further, is just and reasonable for the expectable readership.
Certainly, I won't add the subsection again anywhere in this article, but I strongly support mentioning this principle at the disputed place, and not only way down. Purgy (talk) 07:48, 23 February 2019 (UTC)
(Please don't consider "everybody" to be a physicist.)
I suggest to have a more systematical structure, by speaking about (1) operators on functions, (2) building new functions from given ones by applying such operators, and (3) specifying functions by equations involving such operators. As an analogy, in an article about numbers, (1) would introduce "+", etc., (2) would introduce terms like "3+4", and (3) would introduce "x such that 3x+5=14". In the function article, (1) should explain composition, derivative, etc., (2) should give examples like "sin ∘ arcsin" and "d/dx sin(x)", and (3) should subsume differential equations and (I guess:) calculus of variations. From computer science, the use of operations on functions in denotational semantics could be another example (the "semantics" of some piece of code is defined as the least function satisfying a recursive equation obtained from the code). Issue (3) could possible be generalized to "specifying a function by an arbitrary logical formula to be satisfied"; however, I don't know if this is used anywhere in practice (for sets in general, specifications by recursive "⊆"-inequations are known as set contraints). Maybe the axiom of choice can be seen as an example. - Jochen Burghardt (talk) 18:14, 23 February 2019 (UTC)
(I have been busy with real life and I will probably not be contributing much to this article in the immediate future), but here are some comments from me. I agree the basic problem is structural. So, for example, turning the bullet list into subsections is an improvement and I also support Jochen Burghardt's proposal and variants. As for "calculus", I do actually think it doesn't hurt if the article has materials motivating the notion of a function. For example, historically, a function emerges as an attempt to give a rigorous underpinning to the notion of a variable. Implicit functions are reminiscent of this history: one variable can be viewed as a variable depending on another and vice versa, and doing so requires specifying "domains" of a function. While it is important (and we do) to give the set-theoretic treatment of a function, it is also important (and we don't quite much yet) to discuss this aspect a function as a variable. For me, the subsection looks an attempt for this. -- Taku (talk) 23:42, 23 February 2019 (UTC)

In computer science

Around December 31, 2018, there was an edit war about the content of this section. My opinion is that my version fits better what should be in this article. Thus, I have restored it, after having edited it for taking into account some concerns of the other editor. Please, discuss here if you disagree with my choices for the content. Feel free to edit the section, if you can propose a better formulation, or if there are things that I have omitted and should be there. D.Lazard (talk) 11:23, 21 February 2019 (UTC)

As you were told, the section that you wrote was plagued with errors. Errors which you didn't fix when you added it back.
1. A functions in computer science is not and has never been a model of functions in mathematics. Specially if the sentence is going to say "in general". The proper definition should be used, and then just say why they are not the same.
2. Computable functions are not the same as \mu-recusive functions. This assumes the Church-Turing thesis. Have you proven it? Computable functions is an informal notion. \mu-recursive functions are but one of the equivalent formal concepts attempting to model that informal notion. Anagramatic (talk) 22:43, 22 February 2019 (UTC)
I suspect that Anagramatic is a WP:sockpuppet of Cactus0192837465. If this is true, please provide valid reasons for editing this pages under different identities. Nevertheless, I will answer to the previous post.
1. You suggest that there is a uniform "proper definition" of a function in computer science, and you have edited the article for suggesting this to the reader. This is factually wrong. Moreover, you assert that, in computer science a function may have no output. This is true for some programming languages, but wrong for others. This is also wrong in almost all aspects of theoretical computer science. Also as you do usually, you do not discuss the content of the article but your wrong interpretation of the content. For example, the sentence "A functions in computer science is not and has never been a model of functions in mathematics" is totally irrelevant, as the term "model" is not used in the article, and it is your invention of considering that "implementing" and "modeling" are the same thing. So your edit of the first paragraph introduces factual errors, supported here by wrong arguments.
2. I agree that the sentence "The concept of computable functions has been formalized by recursive functions" would be better written "The intuitive concept of computable functions has been formalized by recursive functions (there are other equivalent formalizations, see below). This is not a reason for changing the end of the paragraph in a summary of the linked article, nor for repeating here something that is said later in the article.
Thus, I'll revert your edit, and modify my formulation as above.
I suggest that we better speak of "functions in computer programming". In computer science in general, also the mathematical definition of function is being used. The definitions of big-O notation used in complexity theory are the first examples that come to my mind. Secondly, I suggest to distinguish
  • a narrow sense (used in functional programming: a function implements a mathematical function from the set of possible inputs to the set of possible return values; no side effects, no reading of memory outside its scope, no i/o; cf. pure function), and
  • a wide sence (used in imperative languages, meant to be synonymous with "subroutine": except for i/o, they can be viewed as implementing mathematical functions from the set of all possible states of accessible memory, including the available stack frame, to itself - this motivates the naming).
For the wide sense, see e.g. Brian W. Kernighan and Dennis M. Ritchie (Apr 1988). The C Programming Language. Prentice Hall Software Series (2nd ed.). Englewood Cliffs/NJ: Prentice Hall. ISBN 0131103628. For the narrow sense, I haven't a source at hand. - Jochen Burghardt (talk) 17:35, 23 February 2019 (UTC)
I agree with this analysis. Note that the first sentence of my version starts with "In computer programming". As computer programming belongs to computer science, there is no problem to have this starting sentence in a section called "In computer science".
However, in my opinion, above details belong to function (computer programming). That we need here is a sketchy description of what the reader should find on functions in the linked articles. The fact that, depending on programming languages, and even on programming paradigms, there are different definitions of a function, must be said, and this is what I have tried to say in the first paragraph (maybe this could be better clarified). But, because the numerous aspects of the concept of function in computer science, it is not reasonable to give much details here. Maybe, such a clarification should be done in function (computer programming). Maybe also, we should create an article function (computer science) for giving more details on all items in this section. I am not sure of the best choice, and personally, I am not readyr for expanding significantly this section here or elsewhere. D.Lazard (talk) 20:36, 23 February 2019 (UTC)
Clearly, your very argument implies that the sentence that you keep adding to the section is false. Namely, that "in general, functions in computer science implement the concept of function". As you yourself said, not every computer language uses the term function as functions in mathematics. Now, absolutely all of them use it for callable pieces of code.
Adding "intuitive" once to computable didn't remove the tacit assumption of Church-Turing thesis. This is made when it is said that "but can model any computable function". That assertion is Church-Turing thesis. Claiming it without acknowledging it is lying to the reader. Anagramatic (talk) 15:10, 25 February 2019 (UTC)
Please answer my question about sock-pupettry.
Please wait for a consensus before edit-warring. For the moment it seems that there is a consensus against you, as it seems that the other editor who has posted here has an opinion that is similar to mine. D.Lazard (talk) 15:27, 25 February 2019 (UTC)
@D.Lazard: No objection to omitting the details about functions in computer science/programming in the article here. I also agree that the details could be added to function (computer programming) (I didn't check whether they are there already). I wouldn't see a need to have a separate article "function (computer science)", since the use of mathematical functions in theory is common to all engineering disciplines (there is no article e.g. "function (civil engineering)" either).
@Anagramatic and D.Lazard: As for the notion of a "computable function", I think there are two versions around; the article "computable function" uses both of them, but (as usual) isn't too clear about their distinction. The versions are: (1) "Computability of a function is an informal notion"[1][2], and (2) "Computable functions are the formalized analogue of the intuitive notion of algorithm".[3][4][5][6] The subject of theoretical computer science can only be class (2), as only this one has a precise definition. - In order to settle your debate, and since the Church-Turing thesis is mentioned anyway in Function (mathematics)#In computer science, I suggest to rephrase the text to mention that thesis earlier. - Jochen Burghardt (talk) 10:22, 26 February 2019 (UTC)
I agree with this suggestion. I'll edit the section in this way. D.Lazard (talk) 14:57, 26 February 2019 (UTC)
 Done I hope that my edit will be considered as an improvement. Feel free to improve it more. D.Lazard (talk) 15:47, 26 February 2019 (UTC)
@D.Lazard: Thanks! Your recent edits already implement what I still was trying to come up with. I subsequently made 3 minor changes, explained in the edit summary; I hope they are ok. - I'd suggest to delete the last sentence, about "typed lambda calculus": most versions are no longer Turing complete, since all evaluations are guaranteed to terminate; it seems that PCF is the only exception; see the last paragraph in typed lambda calculus#Kinds of typed lambda calculi. - Jochen Burghardt (talk) 09:25, 27 February 2019 (UTC)
To editor Jochen Burghardt: Thanks for your edit the improves my wording. About typed lambda calculus, I am not competent enough on this subject for objecting removal of the last sentence paragraph. This is the reason for which I used "roughly speaking". Nevertheless. I remains convinced that what I wrote is among original motivations, or, at least, that one reason for developing typed lambda calculus was similar to the motivation of emphasizing on domains and codomains in function definitions (see above discussions). In any case the removal of this paragraph would be harmless, as too technical for the normal reader of this page. D.Lazard (talk) 09:59, 27 February 2019 (UTC)
@D.Lazard: Yes, I meant the complete last paragraph - sorry. If it is kept, warning on typed lambda calculi should be added; I made a suggestion for it just now. If the whole paragraph is deleted, I wouldn't object; it might be too much detail here. - Jochen Burghardt (talk) 11:18, 1 March 2019 (UTC)

References

  1. ^ cited from computable function#Definition
  2. ^ Frank Stephan (2008). Recursion Theory. p.10
  3. ^ cited from computable function#lead
  4. ^ Michael Sipser (1997). Introduction to the Theory of Computation. Boston/MA: PWS Publishing Co. p.190
  5. ^ Dexter C. Kozen (1997). Automata and Computability. Undergraduate Texts in Computer Science. New York: Springer. p.347
  6. ^ A.M. Turing (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society, Series 2. 42 (1): 230–265. p.231,233; however, this dates before the Church-Turing thesis

Injective functions and axiom of choice

The section § Injective, surjective and bijective functions says that the axiom of choice is needed to prove that a function is injective if and only if it has a left inverse because "if f is injective, one defines g by if and by , if where is an arbitrarily chosen element of X." This contradicts Injective function § cite note-2, which says that "Unlike the corresponding statement that every surjective function has a right inverse, this does not require the axiom of choice, as the existence of a is implied by the non-emptiness of the domain." I think it is the first passage that is incorrect, but I'm not sure how to fix it. Gulumeemee (talk) 10:40, 14 August 2019 (UTC)

Good catch, I have fixed it.However, ZF is required, as it is wrong in constructive set theory. D.Lazard (talk) 11:03, 14 August 2019 (UTC)
A couple things: first, the wording should still just be "In Z-F set theory...", not "assuming...". Also, it's not currently reasonable because the rest of the paragraph still talks about how the AoC is needed, despite the change being made due to the claim that it's not (this is why I was confused about why the change was being made). Frankly, it seems plausible, but I certainly don't know with much certainty, so I wouldn't otherwise change the substance, which is why I added the unreferenced tag. –Deacon Vorbis (carbon • videos) 13:28, 14 August 2019 (UTC)
 fixed by D.Lazard who beat me by few munites. Certainly the cited piece is rubbish – good kill. Incnis Mrsi (talk) 11:06, 14 August 2019 (UTC)

@Deacon Vorbis: the domain is non-empty means x0X. No dependence of x0 on y. No axiom of choice, only direct application of non-emptiness. Incnis Mrsi (talk) 13:30, 14 August 2019 (UTC)

This isn't a reliable source, but it provides a good explanation: the only statement that requires the axiom of choice is that if f is surjective then f has a right inverse. Gulumeemee (talk) 04:04, 15 August 2019 (UTC)

Notation

Concerning the recent edits: It should not be too difficult to introduce as the real numbers.

More important, the notation "f:XY" is used in the sections before, without being explained. I suggest to introduce it in section "Definition", and to restrict section "Notation" to notational variants (and to rename it accordingly). - Jochen Burghardt (talk) 09:18, 15 April 2021 (UTC)

Thank you for your nice comments. I have no objection to introducing the meaning of in the "Definition" section. I have no objection to introducing either.
The main issue is whether we should use the standard statement "let be the function defined by the equation for all values of in " (or whether this textbook statement is too difficult for the general audience in Wikipedia, as suggested by the Administrator).
-- Laiwoonsiu (talk) 10:38, 15 April 2021 (UTC)
If the Administrator and other editors do not object, I propose the following simple solution to solve the problem:
(1) I will only replace "valid for all real values of " by "for all in " according to standard textbooks. In this way, readers who know mathematics will agree with the correction, whereas lay surfers will hardly notice any change. As a result, the latter do not even need to know that means the set of real numbers.
(2) I will leave the introduction of in the "Definition" section to other editors, as I do not have time for a new task.
-- Laiwoonsiu (talk) 04:07, 16 April 2021 (UTC)
I'll make a suggestion for section "Definition", and leave the issue of "" vs. "real" to you and David Eppstein. I don't have a clear preference about the latter, except that I feel that a valid/invalid distinction doesn't make sense for defining equations, and hence prefer to omit the "valid". - Jochen Burghardt (talk) 07:58, 16 April 2021 (UTC)
Thank you, Jochen.
Regarding the issue of "" vs. "real", consider the following examples:
(a) Let be the function defined by the equation for all non-negative values of .
(b) Let be the function defined by the equation for all non-zero values of .
(c) Let be the function defined by the equation for all in .
Only example (c) illustrates the standard meaning of (total) functions.
-- Laiwoonsiu (talk) 15:15, 16 April 2021 (UTC)
We received no contrary opinion about the proposal to write "for all in " in the "long-winded" statement as per standard textbooks. I will revise the Notation section accordingly. -- Laiwoonsiu (talk) 15:31, 17 April 2021 (UTC)

Relational Approach: Incomplete definition of well-defined?

In the section "Relational Approach", it says the following:

"The functional property is also commonly referred to as the function being well defined."

However, everywhere else I've learned it, a function is well-defined if and only if it is both functional (uniqueness of outputs) and serial (total).

108.20.210.156 (talk) 20:22, 22 April 2021 (UTC)

Different authors may use different notions of "well defined". (In a quick search, I couldn't find any reference at all using "well-defined function".) I requested a citation for the meaning claimed in the article; if you have a citation for your meaning, we can add it as an alternative. - Jochen Burghardt (talk) 08:13, 23 April 2021 (UTC)
See well-defined for context. —Kusma (t·c) 08:26, 23 April 2021 (UTC)
To editor Kusma: Thanks for the link. It well explains the meaning of "well defined" and the fact that it is a term that can be explained, but not formally defined. More, the explanation given there shows implicitely that the phrase is used for avoiding the use of the relational language. Thus the mention of "well defined" in the section on the relational approach is not useful, and I'll remove this remark. D.Lazard (talk) 08:53, 23 April 2021 (UTC)
It seems that reference [2] in "well-defined" (Rotman.1965) is a citation supporting the sentence under discussion. Since this naming is a possible source of confusion (as noticed by 108.20.210.156), it should be discussed somewhere in the article. One possible place would be the section Function (mathematics)#Multi-valued functions. However, since that section seems to (tacitly) presuppose a topology in the function domain, I'd prefer section Function (mathematics)#Definition, right after the paragraph about partial functions. That is, after haing talked about generalizations of functions that may associate zero y to a given x, we would briefly talk about generalizations that may associate two or more y. One or two sentence(s) should suffice. They could link to the "Multi-valued functions" section and to well-defined, cite Rotman.1965, and remark that "well-defined" implies less than "having an acceptable definition" (the latter also implying seriality). - Jochen Burghardt (talk) 11:43, 23 April 2021 (UTC)

Correcting shortcomings in the article

An article of this importance should aspire to become A-class!

Probably everyone will agree that the article should be free of logical conflicts and provide the clearest and simplest account. Reading the various discussions on this talk page reveals various gaps that may explain the current shortcomings.

The clearest and simplest definitions for the function concept have the common characteristic that function equality coincides with equality of their graphs or, equivalently, that a function is fully specified by its domain (say, ) and the value for every in that domain. Introducing a function as stipulates that the domain of is and the range of is a subset of . No codomain is involved here.

The discussion seems to be bogged down by attributing this view to Apostol only, but in reality it is the most widespread view on functions throughout the sciences, including calculus/analysis (Apostol, Bartle, Flett, Kolmogorov, Royden, Rudin, Thomas), set theory (Dasgupta, Halmos), algebra (Herstein), discrete mathematics (Scheinerman), programming language theory (Reynolds), mathematical physics (Szekeres), to mention only a few (a detailed annotated bibliography can be obtained by sending me an e-mail).

A legitimate concern in the discussion is the concept of onto-ness, but it is a misconception that this requires a codomain. In the aforementioned references, a function is called onto or surjective on iff (if and only if) its range is . Even some authors who introduce onto as an adjective (assuming a codomain) occasionally realize the need to be more specific and use onto properly as a preposition when saying that a certain function is onto but not onto . Similarly, a function is partial on iff its domain is a subset of and total on iff its domain is .

The most important operation on functions is composition. In the aforementioned references, is defined for any functions and . The domain of is defined as the set of all in the domain of such that is in the domain of . As usual, for every in that domain. Hence, given and , clearly is a partial function from to . It is a total function from to iff the range of is a subset of , the domain of . This is trivially satisfied if , but requiring this equality for to exist would evidently be a severe limitation.

This generality in the definition of composition is indispensable in calculus and explains why nearly all calculus texts (with very few exceptions) define functions in the manner described thus far, avoiding codomains. It is also significant that in his magnum opus Theories of programming languages, Reynolds exclusively used the above definitions although in some of his earlier work (pioneering the use of category theory in computer science) he used variants with codomains.

Incidentally, in a random sample of four introductory textbooks that introduced codomains, all of them did so with a logical inconsistency, and I had to search through six more introductory texts using codomains to find one with a consistent definition. In its current form (2022/01/11) the Wikipedia article only adds to this confusion.

Conclusion: for the sake of simplicity, generality, balance/objectivity (reflecting widespread usage) and logical safety, it would be a good idea to start the article with the above definition for a function . Subsequently introducing a triplet and calling its codomain (following Dasgupta and many others) is then a simple and safe step (a one-liner or a very short paragraph). Borrowing Mac Lane's terminology, such a triplet might be called a labeled function. Proceeding in the reverse order (starting with codomains) is evidently very tedious. Boute (talk) 15:50, 11 January 2022 (UTC)

Introducing a function as stipulates that the domain of is and the range of is a subset of No codomain is involved here. The last sentence is wrong, as is exactly what every one calls the codomain of the function. So, a codomain is involved here.
Probably everyone will agree that the article should be free of logical conflicts. The problem is that logical conflicts cannot be avoided, since the exact definition of a function may depend on the context and the area of mathematics. When several non-equivelent definitions are common, Wikipedia must not choose one or them, but it must present the various definitions, state their difference and explain in which contexts they are used.
Conclusion: [...] it would be a good idea to start the article with the above definition for a function [...] Maybe, it would be a good idea, but, before, you must write down the definition that you suggest. I did not find it in your long post.
In my opinion, the definition given in the first paragraph of the article is clear, sinple, logically correct, and conform of the definitions appearing in most textbooks. Maybe. it is possible to do better, but you long post does not help for that. D.Lazard (talk) 20:48, 11 January 2022 (UTC)
To avoid interfering with D.Lazard's text, assume that the preceding four comments are labeled (A) to (D).
Ad (A). Not really. By this definition can be any set that contains the range and may be replaced by any other such set without changing . Hence is not uniquely defined by the function and hence can be chosen in the most informative way (a valuable opportunity). By contrast, what almost "everyone" calls the codomain of is considered to be attached to the function to the extent that function equality requires codomain equality.
Ad (B). Having different definitions that are clearly identified as defining different concepts are not considered "logical conflicts", but self-contradicting definitions definitely are. By no means did I suggest that Wikipedia should choose only one definition; my last paragraph indicates the contrary. What I did suggest is an order of presentation that best clarifies the options.
Ad (C). Any of the definitions in the dozen or so references given will do. Their common essence is that a function is fully specified by its domain and the value for each domain element . Here "fully" means that iff (if and only if) and have the same domain and for each in that domain.

Ad (D). The definition given in the first paragraph of the article is flawed: saying that is the domain of the function and is the codomain of the function makes the definition either ambiguous or self-contradicting, depending on the interpretation. For instance, let be a function from to according to the current Wikipedia definition, let be a proper subset of and let be a proper superset of . Then assigns to each element of a unique element of and hence is a function from to by the same definition, which makes the domain and the codomain ill-defined. Fortunately this is not conform the definitions appearing in most textbooks. Moreover, an extensive bibliographic comparison of introductory math books indicates that most of them do not mention codomains at all, whereas those that try to introduce codomains nearly always make the definition of function self-contradicting (with less room for a mild interpretation than the current Wikipedia definition). Boute (talk) 22:53, 11 January 2022 (UTC)

Is there any standardized symbol for a set of all functions from set A to set B?

. — Preceding unsigned comment added by 80.49.58.196 (talk) 13:49, 3 February 2022 (UTC)

The notation is This was in the former section "As an element of a Cartesian product over the domain", which I have renamed § Set exponentiation and completely rewritten. D.Lazard (talk) 15:20, 3 February 2022 (UTC)

"Funktionen" listed at Redirects for discussion

An editor has identified a potential problem with the redirect Funktionen and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 February 16#Funktionen until a consensus is reached, and readers of this page are welcome to contribute to the discussion. ~~~~
User:1234qwer1234qwer4 (talk)
22:19, 16 February 2022 (UTC)

"Empty map" listed at Redirects for discussion

An editor has identified a potential problem with the redirect Empty map and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 March 30#Empty map until a consensus is reached, and readers of this page are welcome to contribute to the discussion. Steel1943 (talk) 05:50, 30 March 2022 (UTC)

"Function(mathematics)" listed at Redirects for discussion

An editor has identified a potential problem with the redirect Function(mathematics) and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 March 30#Function(mathematics) until a consensus is reached, and readers of this page are welcome to contribute to the discussion. Steel1943 (talk) 08:43, 30 March 2022 (UTC)

Prehistory of the concept

A sentence in the lead, about the prehistory of the concept, of function has been the subject of an edit war between two editors. I have removed the sentence for the following reasons.

The sentence was placed at the beginning of a paragraph that summarizes the history of the concept. This paragraph has his place in the lead, because it provides indications on the the context (in particular the importance of the subject, and the reason for which arguments of the functions are called variables). The disputed sentence adds nothing to the context. On the opposite, it is confusing as suggesting that the paragraph is only about the history and not about the context.

So, the disputed sentence does not belong to the lead. Before remarking the role of context of the paragraph, I intended to move the whole paragraph, with the disputed sentence, into a history section (presently not existing). Nevertheless, creating a section "History" could improve the article. The disputed sentence could have it place in such a section, after verification that it presents a neutral point of views (one of the source present earlier precursors, such as Archimedes). D.Lazard (talk) 10:17, 16 January 2023 (UTC)