Jump to content

Talk:Function (mathematics)/Archive 3

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Archive 1Archive 2Archive 3Archive 4Archive 5Archive 10

Function notation

In my fairly short university career I have be taught that if you define a function as f(x)=x^2, for example, then you can also say f=x^2. Similarly if you say y=x^2 then you can also say y(x)=x^2. i.e. There is no difference between f(x) and f they mean the same thing but with slightly different stresses on what the function is used for.

What I am suggesting is that this should be be flagged as different notation "f(x)=y" saying that instead "f(x)=f" or "y=y(x)".

The classic notation is y = f(x). In the past twenty years, I see just f and also y(x) more and more frequently, and see no problem as long as these notations are used unambiguously. If they are mentioned in the article, it should be mentioned that these are modernisms. Rick Norwood 14:13, 27 May 2006 (UTC)
Study of foundations and use of computers has forced more careful use of notation, though convenient brief forms persist. Contrast
with
or
More provocatively, contrast with Standard ML's
fun f x = x * conj x
or the C programming language
float f(struct complex x) {return ctimes(x,cconj(x));}
or the Common Lisp
(lambda (x) (* x (conjugate x)))
In the SML case type polymorphism broadens the domain and range possibilities, while in the C case the result is restricted to a float rather than, say, a double. The Lisp case does not name the function, nor does it restrict the domain and range. --KSmrqT 18:45, 27 May 2006 (UTC)
I have never seen f=x². I have seen that f(x) is used instead of f when speaking of the function (although f(x) is the value at x), usually it is clear from the context that x is "unbound" i.e. not a particular value, but a "placeholder". But it is clear that the information f(x)=x² is incomplete insofar we cannot know on what set the function is defined (N, R, C ?) and even less if it is surjective or so (not surjective on N, although this is smaller than R+, surjective on C although this is larger than R).
Other notations not mentioned here are things like , which some mathematicians like. (We understood that WP is not for mathematicians; a pity since it could have been useful.)
Also, the C language example is quite mathematical (float as well as double are sets and ctimes is a function (with precise domain and codomain) both well-defined in the most strict mathematical sense), while the ML one is not, neither the Lisp: these clearly are not functions in the set-theoretical sense, (though maybe in the category theory sense, if it is understood that arguments are in the category that has the operations occuring in the function body, and results are in the category implied by the involved functions/operators).
Maple or MuPAD allow both, writing f:= x -> x*x ; or (with or without type specification), f:=proc(x :: float)::float x*x end; — MFH:Talk 15:10, 13 October 2006 (UTC)

Non-Numeric Functions

"A function need not involve numbers. An example of a function that does not use numbers is the function that assigns to each nation its capital. In this case Capital(France) = Paris."

I'm not a mathematician, but I question the validity of this. In the example given, the fucntion, Capital(x) = y does not yield exactly one output per input. Capital(France) = Vichy and Capital(France) = Aachen are arguably valid outputs for the input "France." Generally a nation has only one capital (at a time). However it's misleading to equate the mathematical certainty of a fuction (exactly one output per input) with a historical rule-of-thumb (unless a war has disrupted the normal political process, a nation, during modern times, shall usually have only one capital). Perhaps someone could come up with a better example of a Non-Numeric Function? Thanks! 66.17.118.207 15:11, 26 June 2006 (UTC)

Absolute non-ambiguity is impossible. Even f(x) = x + 5, which seems non-ambiguous, would admit a question whether the addition took place in the natural number system, in the real number system, or in the integers modulo 7. I suspect that any example of a non-numerical function would suffer from similar problems. One has to use common sense. Rick Norwood 15:37, 26 June 2006 (UTC)
Are you serious? First, this is a non-mathematical example. Second, France has only one capital now. Third, if some country happens to have simultaneous multiple capitals we can simply allow the function to return a set. Fourth, if we really need to accommodate different facts at different times we have tools such as modal logic. Finally, are you serious?! --KSmrqT 23:49, 26 June 2006 (UTC)
Well just as with mathmatical functions you could say that the complete function should include the domain (i.e. year = 2006)DougBrown 16:39, 2 November 2006 (UTC)

notation for functions.

See Talk:Fourier_transform#Where_to_put_it. The conventional notation for functions, where you write f(x) meaning f, is insufficient when it is not obvious what the independent variable is. Please comment on the suggestion for a solution. Bo Jacoby 11:44, 7 August 2006 (UTC)

I think what this article does, begin with the simple case and go on to more advanced cases, is the only way to go. Another advanced problem is free variables vs. bound variables. Probably worth discussing, but only near the end of the article.
A discussion of independent and dependent variables should be discussed in the context of implicit functions. Rick Norwood 13:27, 7 August 2006 (UTC)

Bo, a simple request: provide a mainstream citation showing that your proposed notation (e.g. f = (x^y←x) instead of f(x) = x^y) is an established notation in mathematics. When you were asked for citations for this notation in Talk:Fourier transform, the only thing you provided was a loosely similar syntax in the J programming language. (I've seen ← used to denote functions, and I've seen "=", but I don't recall seeing this kind of combination of "=" and ←; it seems obscure at best.)

Wikipedia should stick with the conventional notations for a given topic; more obscure/uncommon ones can be mentioned but should be presented as such. Notations not used in mainstream mathematics publications should not be included in Wikipedia at all, according to policy.

—Steven G. Johnson 05:36, 11 August 2006 (UTC)

Steven, I appreciate your entering a discussion rather than to delete my contribution. You are slowly growing civilized.

The use of the colon in the notation, fxy is unconventional and pointless and confusing. Equality should always be written with the equality sign: f=xy. Parentheses should be used to fix the order of operations: f=(xy).

The arrow points from the independent to the dependent variable. Usually an asymmetric symbol signifying an asymmetric connection is reversed to mean the reverse connection. For example, (a<b) is the same thing as (b>a). Both notations are free to be used. So (xy) has the same meaning as (yx), that x is mapped to y and that y is a function of x.

The lambda notation, λ x.y, uses the symmetrical symbol (.) to signify an asymmetrical connection between independent and dependent variable. This makes it hard to read. Using the arrow instead of the dot is an improvement: λ x→y . Now the lambda is no longer needed and we are left with x→y.

The convention that letter x implicitely signifies the independent variable, is useful for simple cases, but insufficient for complicated cases. An explicite indication of the independent variable is needed to distinguish the power function xy from the exponential function xy.

You know the equality sign, the arrow and the parentheses. The combination f=(yx) means what it is supposed to mean. Even if you don't recall seeing this combination of digits: 1329685, you will not request me to provide a mainstream citation showing that it is an established notation in mathematic.

Bo Jacoby 10:20, 11 August 2006 (UTC)

Standard mathematical notation has its share of confusions and inconsistencies. Innovative notations may claim to be far superior. That's all irrelevant here. We're documenting, not advocating.
Besides that, the claims above exhibit their own confusion. If the lambda notation shouldn't use a "symmetrical symbol" then we'd better replace the minus sign in xy as well. But only for those who cannot distinguish left from right.
The notation fxy is non-standard and incorrect, and not what the article should use. The standard is exhibited in a previous comment on this talk page.
On the first line, the colon–arrow notation gives the name, domain, and codomain of the function, using a simple arrow (""). On the second line, the function name is not mentioned; instead pure function notation is used, with a different arrow symbol (""). I'll fix this in the article. (I thought I already had; mea culpa.)
It is absolutely true that other notation shows up. In commutative diagrams the colon–arrow notation is altered by putting the function name above the arrow. Occasionally in mathematics, and in (reverse Polish notation) programming languages like Forth, function names are written after their arguments. Omission of parentheses is common, so long as there is no risk of confusion. And so on. What we need to do is collect some of the major mathematical variants in a section on notations, or even split out a separate article if the list gets long.
What we do not need is to clutter the main presentation.
All editors should take note that the topic of this article is familiar to almost anyone. That tends to cause problems, in two ways. First, such an article will be consulted by readers with an enormous range of sophistication, from pre-college to post-doctorate. Second, the editors will also have a diverse range, and will likely have seen more computer notation than pure mathematics. Even more than usual it will help to be kind and thoughtful in what we say to our readers. We also need to be extra aware of our fellow editors' possible limitations, and of our own. --KSmrqT 23:32, 11 August 2006 (UTC)

If we're documenting, not advocating, the confusions and inconsistencies of standard mathematical notation, then we must tell the embarrassing truth: "There is no useful standard notation for the solution f to the equation y=f(x). The power function f defined by the equation f(x)=xy is not the same thing as the exponential function f defined by the equation f(y)=xy. The arrow notation yx is useful but not standard. The lambda notation λ x.y is standard in a limited context but not generally useful. The concept of a mathematical expression is much older than the concept of a mathematical function". The minus sign is symmetric even if the minus operation is asymmetric. ab is not the same as ba, although a=b is the same as b=a. Touché. The minus sign is familiar to almost everyone, while the lambda calculus is familiar to almost noone. So it is easier to criticise the bad design of the lambda notation than to criticise the bad design of the minus sign. Bo Jacoby 06:36, 13 August 2006 (UTC)

And yet, somehow, mathematics muddles on.
A few thoughts:
  1. On this talk page I gave examples of how functions may be presented in programming languages; however, I would like to confine the article itself to purely mathematical examples, given its name.
  2. Having worked with symbolic computation systems and mathematical typesetting, I am very much aware that for computers we often use much more explicit notation.
  3. Having read a great deal of mathematics covering a broad range of topics, I would also like to point out that most mathematics notation is written for humans, not computers; so we abuse notation, rely on context, and generally trust that a motivated and intelligent reader will find the terse notation friendlier than something totally explicit.
I offer as an exhibit of the difference the following MathML presentation markup for xy.
<math xmlns="http://www.w3.org/1999/xhtml">
  <mrow><mi>x</mi><mo>-</mo><mi>y</mi><mrow>
</math>
The standard itself makes clear that this is not meant for human consumption. We can also use content markup, which is no better. (I'll even omit the <math> tags.)
<apply><minus/><ci>x</ci><ci>y</ci></apply>
I'm surprised at your choice of targets. As it happens, lambda calculus and its notation is extremely useful; aside from its applications in the pure mathematics of recursive functions, it formed the basis for John McCarthy's creation of the heavily used and influential programming language LISP, and its functional programming language successors.
Your example of xy is also puzzling. I cannot imagine this being used in an actual paper or text without enough context to clearly tell the reader the intent.
Besides, syntax always involves position. The matrix multiplication written AB is not the same as BA, and we can't blame the shape of the operator for any confusion.
This article, like mathematics in journals and textbooks, is written for humans. I believe our primary goal in discussing notation should be to tell readers about the most common notations they will see, and explain how to interpret them.
Often it helps to form a mental image of a typical reader. For an article like this, we can expect many readers will have little mathematics experience, else they would already be familiar with the term "function". In addition, we may attract a minority of readers with a great deal of mathematical experience hoping for some technical subtleties. If we write carefully, we can serve both groups. I commend to you the Wikipedia:Manual of Style (mathematics). --KSmrqT 11:27, 13 August 2006 (UTC)

What is your solution to KYN's problem in Talk:Fourier_transform#notation once again? How do you express the shift operator ((ck+1k)←(ckk)) ? Will you suggest lambda calculus or lisp or MathML ? Rather than to argue that there is no problem you should try to solve the problem.

The suggestion (yx) is primary for human consumption.

The problem of xy is discussed in relation to defining 00 . (0yy)(0)= 0 by continuity, while (x0x)(0)= 1 by continuity. A lot of confusion and seemingly endless discussion arises as a result of lack of appropriate notation for these functions. (See for example Talk:Empty_product#00_is_indeterminate.3F).

I am not an expert on lambda calculus, and I do not understand the supposed advantage of writing λ x.y rather than (xy) or (yx).

Bo Jacoby 13:09, 13 August 2006 (UTC)

Please carefully read WP:NOR. Three different editors at Fourier transform told you Wikipedia is not the place to introduce your personal pet notation. You've been told that on this page as well. Believe it. --KSmrqT 22:24, 13 August 2006 (UTC)

There is a difference between notation and research. There is no ban against notation. The ban is against what does any of the following:

  • It introduces a theory or method of solution; (yx) does not.
  • It introduces original ideas; (yx) does not.
  • It defines new terms; (yx) does not.
  • It provides or presumes new definitions of pre-existing terms; (yx) does not.
  • It introduces an argument, without citing a reputable source for that argument, that purports to refute or support another idea, theory, argument, or position; (yx) does not.
  • It introduces an analysis or synthesis of established facts, ideas, opinions, or arguments in a way that builds a particular case favored by the editor, without attributing that analysis or synthesis to a reputable source; (yx) does not.
  • It introduces or uses neologisms, without attributing the neologism to a reputable source. (yx) does not.

If you know a more established notation expressing the same thing as (yx), let's use it. I have no pet notation, but we need some notation. It's your problem as well as mine. Bo Jacoby 08:00, 14 August 2006 (UTC)

No, I have no problem with using common notation here; used wisely, it is clear. And I have searched both this talk page and the article history in vain for a citation of a reputable source to support the notation you propose. Since I have seen a wide assortment of mathematics yet have no recollection of having seen this notation, and since functions and their usual notation are very much standard mathematics, I can only conclude that your proposed new notation is original research. Feel free to use it as much as you like on talk pages, but expect it to be poorly received because no one will know what it means. It has no place in the article. --KSmrqT 08:49, 14 August 2006 (UTC)

What is your 'common notation' for (sin(x)/xx) ? Bo Jacoby 09:09, 14 August 2006 (UTC)

I also have lots of mathematics experience, including higher math, and have not seen that notation. Do you mean f(x)=sin(x)/x? Everything I've seen suggests that's the 'common notation'. The notation you proposed will not be understood by nearly as many people as the 'common notation'. -- Schapel 12:47, 14 August 2006 (UTC)

Hi Schapel. Yes, I mean that the equation, f(x)=sin(x)/x, for the function value, f(x), is true for all values of x for which the right hand side makes sense. Which function, f, solves that equation? What is the 'common notation' for f itself? f=??? Tell me. Bo Jacoby 08:32, 15 August 2006 (UTC)

I would say f=sin(x)/x. It usually isn't written that way so you can easily tell the constants from the variables, and also so that you can clearly tell a function of one variable from a function with two variables. For example, f(x)=sin(x)/x, g(x,y)=sin(x)/x, h(x)=k sin(x)/x. -- Schapel 12:59, 15 August 2006 (UTC)

The challenge is to have the function name alone on the left hand side of the equality sign, so that we get an expression for the function rather than for the function value. Do you suggest to strip away the parameters : f=sin(x)/x, g=sin(x)/x, h=k sin(x)/x ? Then you cannot tell the difference between f and g any longer. (My solution is f=(sin(x)/xx), g=(sin(x)/x←(x,y)), h=(k·sin(x)/xx).) Bo Jacoby 13:22, 15 August 2006 (UTC)

Sorry to jump in here, however as a student of mathmatics (university level), and therefore possibly a common type of reader, I would like to comment. I find issue with the words 'My solution' that you have used. From what I have read wikipedia is supposed to be representative of general use rather than personal preferance, therefore however useful and clear '[Your] Solution' is, Wikipedia is not the place to publish it. If you could publish in reputable source your solution to the issues you percieve to exist, and then experts accept the solution then maybe it will be worthy of addition. Sorry if I have spoken out of turn DougBrown 17:13, 2 November 2006 (UTC)
If you want the parameters in, why not put them where they belong in the first place? -- Schapel 18:15, 15 August 2006 (UTC)

In 'Talk:Fourier_transform#Where_to_put_it' some highly qualified people are seriously lacking an unambiguous notation. They have to settle with ambiguous expressions, sometimes complemented by explanations. It is unsatisfactory. Bo Jacoby 09:08, 16 August 2006 (UTC)

I just asked my wife, and she thought that f=(sin(x)/xx) was some sort of limit. I asked her how to indicate that f is a function of x, and she wrote f(x)=sin(x)/x and said that's the only notation she knows to write that. She has a masters degree in statistics. -- Schapel 22:49, 15 August 2006 (UTC)

You did not ask her how to indicate sin(x)/x as a function of x rather than as a value, showing that x is a variable rather than a constant? My complements to your skilled wife. Let us take her word for it: there exists no standard mathematical notation for a function alone, only for a function value, which is sufficient in some cases, but not in every case. We must document this sad and embarrassing state of affairs in the article. Hopefully some expert mathematician will show up and teach us that we are wrong and provide an acceptable solution. Bo Jacoby 09:08, 16 August 2006 (UTC)

I still don't see the problem. In the functions above, you do not give the domain and range. Are they the reals? The complex numbers? Usually you don't give the domain and range of functions in a mathematical notation; they are implied from the context. You can also write y=sin(x)/x when it's implied that y is a function of x from the context. You can argue that these are "ambiguous expressions," but mathematics is a human language, not a computer language. All human languages have ambiguities. -- Schapel 12:10, 16 August 2006 (UTC)

Standard notation

This is a response to a comment signed Bo Jacoby 09:08, 16 August 2006 (UTC) above. There are two standard ways of indicating the function that are explicit about the bound variable:

The first is commonly used in category theory, the second in logic. In most written mathematics, it is enough to just say (in prose) what the bound variable is when confusion could arise. Since the entire community of mathematicians seems to have agreed that this is precise enough, new notation is apparently not necessary. The notation is completely nonstandard. A common way of defining a shift map (in the context of Fourier analysis, dynamical systems, etc.) is by saying that the shift of a sequence is the unique sequence such that for all n. This could also be written with different function notation: . CMummert 12:00, 16 August 2006 (UTC)

Thank you very much

I suppose that this means that you can write

.

Can you omit the parentheses and write

 ?

Can you write the shift like this

,

or do you need parentheses:

or even

 ?

Is the function expression used like the function name?

.

Bo Jacoby 13:07, 16 August 2006 (UTC)

warning to editors

Other editors should be aware that the strong consensus policy against nonstandard personal notations has been explained to Bo many times, so you may be wasting your breath by arguing with him. On Root of unity, he tried to introduce the notation . On Discrete Fourier transform, he tried to introduce his own "involutary" definition of the DFT. On Ordinal fraction, he tried to introduce a new fraction notation. Each time, he gave no warning to other editors, until challenged, that the notation was not (to his knowledge) used by anyone else. The same thing has apparently happened here. He gives all indication of continuing this behavior in perpetuity, which is sad since he clearly has mathematical training and is capable of making positive contributions. —Steven G. Johnson 16:17, 14 August 2006 (UTC)

Steven agrees that z1/2 is a multivalued function of the complex variable z: "The expression z1/2 can signify any of the solutions, x, to the equation x2=z". This is true for every complex number z. Steven also agrees that every real number is also a complex number. 'Complex' does not mean 'non-real'. So, 1 is a complex number. It is a standard mathematical procedure to specialize a formula by substituting a constant for a variable name. Substituting the complex number 1 for the variable name z in the above statement gives the specialized statement: "The expression 11/2 can signify any of the solutions, x, to the equation x2=1". Nevertheless Steven claims that it is 'nonstandard personal notation', and he has consistently been deleting my contributions. That I am not fighting edit wars or wasting my breath by arguing does not imply that Steven is right. Steven is simply not right in this matter. Bo Jacoby 08:32, 15 August 2006 (UTC)
It's absurd to pretend that Steven alone disagreed when we can read the talk pages and the histories; multitudes correct you every time they see you trying to introduce your own notation. Wasting your own time is up to you, but forcing other editors to waste their time correcting you for the same behavior repeatedly is the kind of thing that can lead to disciplinary action. --KSmrqT 13:16, 15 August 2006 (UTC)
Which part of the above mathematics is nonstandard ? I do not pretend that Steven is alone, but he is the prime mover. Bo Jacoby 13:35, 15 August 2006 (UTC)

No, Steven is not alone. Wikipedia is not the place to introduce non-standard notation. There is no doubt that current matematical notation could be improved, but Wikipedia is not the place to do it. (My own personal bugbear is =o (little o notation), the only place in all mathematics where an equal sign is part of a notation that is not an equivalence relation.) But the place to introduce your ideas about mathematical notation is in an article for a refereed journal, not an encyclopedia. I suggest you try The American Mathematical Monthly but they are pretty conservative -- they wouldn't publish my article on little o. On the other hand, they did publish my article on why 2 + 2 = 2 * 2, so you never can tell. It's worth a try. But not in Wikipedia. Rick Norwood 14:05, 15 August 2006 (UTC)

Hi Rick. I am interested in your suggestion for an alternative to the little oh notation. Why not put an abstract on your user page? See also Degree_of_a_polynomial#The_degree_computed_from_the_function_values. And now please answer my question: "Which part of the above mathematics is nonstandard ?" Neither z1/2 nor 11/2 is nonstandard notation. See Exponentiation#Complex_powers_of_complex_numbers. It does not become nonstandard just because Steven or you do not use it. We agree that Wikipedia is not the place to introduce non-standard notation. Do we agree that Wikipedia is the place to use standard notation? Bo Jacoby 11:57, 16 August 2006 (UTC)
The notation 11/2 is not nonstandard. It indicates the square roots of 1, which are -1 and 1. The problem is that you used that standard notation in a different way from the standard meaning. Wikipedia is not the place to introduce nonstandard meanings to standard notations. -- Schapel 12:52, 16 August 2006 (UTC)
Did I ? Bo Jacoby 13:23, 16 August 2006 (UTC)
Yes, you used the notation 11/2 to mean -1 and not 1. That is not the standard meaning of that notation, and actually creates ambiguity where none existed before. -- Schapel 13:40, 16 August 2006 (UTC)
Who wrote 11/2 meaning +1 ? Bo Jacoby 14:08, 16 August 2006 (UTC)
I'm not sure what you're asking. 11/2 means one raised to the one-half power in standard notation. The values +1 and -1 are one raised to the one-half power. -- Schapel 15:23, 16 August 2006 (UTC)

I don't put my views on "little o" in Wikipedia because this is not the place for them. Nor is this the place to push for wider use of the multivalued 1/2 power. If you type 1 ^ (1/2) into a calculator, it returns 1, not {1, -1} In other words, the default for fractional powers is the principal value (if defined), not the set of values. When the author of a mathematics article wants to use fractional powers in some non-standard way -- as, for example, a function defined between two Riemann surfaces -- they mention that in the introduction to the article or book. Rick Norwood 14:23, 16 August 2006 (UTC)

Does Rick's calculator support complex numbers? If not, the argument is invalid. If you want to express the number 1, then write the symbol 1 rather than the expression 11/2. Actually 11/N is the systematic notation of an Nth root of unity, but it must be mentioned that it is ment to be a primitive Nth root of unity such as e2·π·i / N. Notations like ωN are ad hoc and should be banned. Some editors oppose the notation 11/N and so I do not pursue it, but that does not imply that their arguments are valid. Some people don't think that they can learn from me, and they are right. :-) Bo Jacoby 09:12, 17 August 2006 (UTC)
Bo writes, "11/N is the systematic notation of an Nth root of unity". Notice that he doesn't claim that it is a standard notation (although he carefully avoids saying that it isn't), and he has not been able to cite a single reference that uses this notation. This has all been covered on Talk:Root of unity where Bo tried to introduce the same notation, and is somewhat offtopic here. Conversations with him go round and round, because he keeps trying to convince you that his notation is better, and you keep explaining that this is irrelevant — Wikipedia policy is to use established mathematical notations, for better or for worse. —Steven G. Johnson 17:40, 17 August 2006 (UTC)
Conversation with Steven go round and round, because he keeps trying to convince you that his notation is standard, and you keep asking him for documentation for that claim. Seaching through the list of ISO standards showed me no standard for mathematical notation. But there is consensus that an is standard notation for the nth power of a, and that is all I need. I suggest that this ad hominem discussion be moved elsewhere. It does not belong on this talk page. Bo Jacoby 11:30, 18 August 2006 (UTC)
Mathematical notation is a de facto standard, not a de jure standard. If you use nonstandard spelling of words or use a word to mean something different from its standard meaning, your edits will be reverted. Similarly, if you use nonstandard notation or notation to mean something different from its standard meaning, your edits will also be reverted. There's nothing ad hominem about that. -- Schapel 12:45, 18 August 2006 (UTC)
That blows Stevens argument. The established de facto standard is that z1/2 is a multivalued function of the complex variable z. Bo Jacoby 17:11, 20 August 2006 (UTC)
It damages Steven's argument. It destroys yours, as 11/n, if given a single value, is always 1. That's why it's called the principal value. — Arthur Rubin | (talk) 17:59, 20 August 2006 (UTC)
Um, of course it's multivalued; no one disagrees with this. But, as I and others have explained repeatedly, when it is written in a context where a single number is implied (i.e., most contexts, unless otherwise indicated explicitly), then the default meaning is the principal value. The most familiar example, of course, is the square root, which is by convention taken to be positive, and this is where your suggestion will be most jarring to readers, but the same is true for other powers. Your implication above that should have a different meaning when talking about complex and real numbers is equally jarring. (That's why essentially every programming languange that supports complex numbers, from Maple to Mathematica to Matlab to the ISO C99 standard, defines the complex exponentiation operation/function to be the principal value in numeric calculation.) —Steven G. Johnson 18:18, 20 August 2006 (UTC)

Anyway, this is going offtopic; if Bo wants to try to argue for (again), the proper place is Talk:Root of unity. Or, more appropriately, since multiple editors have told him this is counter to policy, he can make an open policy-change proposal on the appropriate policy Talk pages (good luck). If he feels I have pursued an unjust vendetta against him, he is free to file a complaint on Wikipedia:Requests for arbitration, although I suspect that such a complaint would backfire. —Steven G. Johnson 18:18, 20 August 2006 (UTC)

While the principal Nth root of unity is always 1, a primitive Nth root of unity is never 1, except for N=1 . Steven emphasizes that "the standard choice is the principal value unless otherwise indicated explicitly". I agree, and I did indicate otherwise explicitely. Stevens position is that even if any Nth root of z may be called z1/N for any complex value of z except 1, a primitive Nth root of unity must not be called 11/N, but must be called e2·π·i / N, a transcendental expression, disguising the fact that this is an algebraic number.
This has been offtopic from the very beginning when Steven entered this "warning to editors". Even if Stevens argumentation is invalid, I did stop using the notation 11/N. Steven construed this as a victory, which it is, and as an indication that he is right, which it is not. We have had discussions, and his different arguments are refuted one by one, but that does not alter his opinion. The only one who is talking about "an unjust vendetta" is Steven's bad concience. I called it 'ad hominem', which it is, as it is a warning against a person in general, rather than against a specific opinion. Bo Jacoby 20:55, 20 August 2006 (UTC)
You're misstating my position and our discussions, but I'm not going to (re-)argue it here (for the nth time) as this is the wrong forum. Thanks for stopping your battle to introduce the notation, by the way, although you stopped only after re-inserting it into three separate articles at three separate times. I have no guilty conscience; "vendetta" was simply a paraphrase of your description of me as "prime mover" in "consistently deleting" your "contributions". As for my warning being "offtopic"—pointing out to other editors that they were dealing with someone who has repeatedly ignored policy in the very matter under discussion (introducing nonstandard personal notations) was, sadly, perfectly relevant. —Steven G. Johnson 21:00, 20 August 2006 (UTC)
I am not ignoring policy. The notation 11/N is not against policy. It is neither new research nor nonstandard notation. All Steven's arguments in that direction have by now been refuted. The only problem with that notation is that it was new to Steven, and Steven considers himself to be an authority on the subject. Steven's attitude is against the spirit of wikipedia. He should let conclusions depend on arguments and not the other way round. Some editors were not aware of the connection between fourier transform and roots of unity, and my contributions, rather than Steven's, arose that awareness. By the way, what is the point of putting the word contribution in quotes? Bo Jacoby 06:19, 21 August 2006 (UTC)
As I've already explained before, the problem with the notation you were using is not that it is nonstandard, but you gave the notation a nonstandard meaning. That's why your edits were reverted. If you use the word chair to mean table, of course someone else will correct the mistake. Arguing that chair is a standard English word and therefore is correct is stupid and pointless if you used it to mean something besides chair. -- Schapel 12:21, 21 August 2006 (UTC)
11/N is multivalued like 'furniture', not singlevalued like 'chair'. 'Furniture' can mean 'table', it doen't necessarily mean 'chair'. Likewise 11/N can mean e2·π·i/N , it doesn't necessarily mean 1. Bo Jacoby 13:33, 4 September 2006 (UTC)
Exactly. That's why this notation was called non-standard. -- Schapel 17:45, 7 September 2006 (UTC)


AAGGGHHHH! I have just spent a long time reading his discussions and if I had read this I would not have done, and possibly spent time reading more of the excellent infomation on mathmatics Wikipedia has to offer. Has he defined 1/0 yet? DougBrown 17:20, 2 November 2006 (UTC)

first function definition

I'm not a mathemetician. The first definition of a function states that 'the binary relation denoted by "less than" contains the ordered pair (2,5) because 2 is less than 5'. In that case, doesn't the same relation also contain the ordered pair (2,6)? Doesn't this then contradict the next paragraph, which says that if (a,b) and (a,c) are in the set, then b must equal c?

The less than relation is not a function. The article could be more clear about this. CMummert 00:23, 23 August 2006 (UTC)
I suspect many computer programmer would hold that a binary relation is a function: one that maps ordered pairs to the set {true, false} :-) - Fredrik Johansson 16:03, 23 August 2006 (UTC)
I think that's a red herring in this context. The definition in the article is completely standard. I agree it is common in computability theory to identify sets with their characteristic functions, but this identification is not common in most areas of mathematics. Since the article title is Function (mathematics), it's fine. I take it from the :-) that you're not serious anyway. CMummert 16:17, 23 August 2006 (UTC)
I suppose we could really picky here. From the text: "A function is a binary relation, f, with the property that for an element x there is no more than one element y such that x is related to y." Seems to me this implies there can be no y, "... no more than one ..." when in reality there is "one and only one" y for a given x. The text is inconsistent in it's definition of a function.
What about undefined points for functions like the log function at 0 and so on? "One and only one" y seems to imply bijective function, not all functions to me. Obscurans 07:18, 26 May 2007 (UTC)

a vital article should be good for reference

I think we all agree on that this is a vital article.

It should be as clear as possible, but it is not clear at all, since several (not only 2) contradictory definitions are given, and sections are unrelated.

I think it's OK to start by giving some examples, so everybody has a rough idea of what we're talking about. (Even if I am about 99% sure that no person reading this article does not already roughly know what it is about.) But I'm sure that (much) over 50% of those who come to this page want some precision about functions. They will be heavily disappointed, since they find only contradictions.

When starting the definition, I think it is not too complicated to distinguish right from the start the range from the codomain, and the function from its graph (which is defined later on, but equal to the first "definition", without this being mentioned).

In other words, a function is defined by 3 things : the "departure set", the "arrival set", and its graph. This insofar more than concensus seems to have been found on defining a function as a binary relation. Once this concensus is reached, one must accept the consequences.

No one would impose on a binary relation to be always total (else a strict order like "<" would not be a binary relation on the interval [0,1] since for x=1 there is no y such that x < y ; and the same would be the case for most partial orders). This implies that not every function is a map (for which the "domain of definition" is equal to the "departure set"), but I will not insist on this here. (I can live with the fact that on wikipedia, in contrast to all classical mathematical books as well as all current work in mathematics, this is (explicitely) called a partial function [while this term has another meaning for mathematicians].)

Also, knowing "from where" the function comes and "to where" it goes is important not only for being able to question whether it is surjective (as alluded to), but also for function composition.

Also, this article should not be about functions in computer science. The notion of "computable function" should not be discussed on this page, since in this context, "function" is not used in the sense of the Definition given here (binary relation). (The set of functions, or maps, from N to N, aka NN, is not countable, although any given function f=(f(x))x∈N from this set is easily computable since it is sufficient to look up the value in the "table" (f(x))x∈N.)

I think this needs heavy cleanup (a starting point could be to delete here what is duplicate with the page "partial function"). — MFH:Talk 14:10, 13 October 2006 (UTC)

I agree that this article could be substantially cleaned up. I second the opinion that partial function should be merged here, and this article significantly editied.
One difficulty with your proposal will be reaching a consensus about what the formal definition of a function is. I would say that the definition of a function is literally the same as its graph. So when you say the function and its graph must be distinguished, I can only guess what you mean. I also don't know what you mean when you say that there is another meaning for partial function in mathematics; a partial function on a set A is just a function whose domain is a proper subset of A. CMummert 15:47, 13 October 2006 (UTC)
I agree the "two definitions" in the article are not ideal. I wrote a possible replacement defintion here. Feel free to edit it or comment on it here. CMummert 16:37, 13 October 2006 (UTC)
On a regular basis we see editors wanting to make mathematics consistent. It is impossible not to sympathize; it is also impossible to do. Wikipedia documents, it does not dictate nor editorialize.
Some authors treat a function as a set of ordered pairs satisfying certain constraints; this would be a "graph" approach. Other authors insist that the domain and codomain (not the range) are essential to include as well. We also see "function" used in contexts like "Dirac delta function", or like "rational function" in algebraic geometry (undefined at the zeros of the denominator polynomial), and so on. And we see alternative names like "map", which sometimes are synonymous and sometimes not.
What to do? We first emulate the maps of transit systems, like the London Tube map, and focus attention on the information needed to guide the reader through the maze of possibilities. However, we also later include enough details to be reasonably complete. This demands writing skills and a breadth of knowledge few individuals possess, but perhaps the Wikipedia "hive mind" can overcome that limitation. --KSmrqT 02:18, 14 October 2006 (UTC)
Resp. to KSmrq: that is a very accurate opinion about the general state of things. So what is your particular opinion about this particular situation? Did you look at my proposed change, and did you have any opinion about it? I agree (somewhat) with MFH that the current article could be improved. CMummert 02:28, 14 October 2006 (UTC)

Merge?

(Moved from Talk:Partial function)

I say this should not be merged into function (mathematics). 'Partial function' is a useful clear idea, much used in computer science. Charles Matthews 11:03, 14 October 2006 (UTC)

Do those reasons really support having a seperate page? The material on partial functions would not be lost if it were merged and redirected here. Unlike domain and codomain, few people are going to run into the phrase partial function until well into college, so the article on partial functions is of less general interest than other vocabulary articles on functions.
Another issue. There is a great deal of repetition among many the vocabulary articles such as: Domain (mathematics), Range (mathematics), Codomain, Injective function, etc. And these articles individually have their own problems, including references and POV claims (which I am noting here so I will remember it later). I think these vocabulary articles could use a link to this article, which could be put at the very top as an italicized header:
For a general discussion of functions, please see the article Function (mathematics).
CMummert 12:57, 14 October 2006 (UTC)

Partial function is a self-contained article and better be kept separately. This function (mathematics) is already huge, adding even more to it would make it hard for people to look up relevant information that way.

I also disagree with putting the note

For a general discussion of functions, please see the article Function (mathematics).

The term "function" is proeminently linked within the text in the appropriate places in those articles, and that should be enough. Oleg Alexandrov (talk) 17:51, 14 October 2006 (UTC)

Definition of a function

I will try to find a referance to this fact but I was told recently by a tutor of mathmatics that the strict definition of a function is that for each function there must be a corresponding inverse function and therefore each input can only correspond to one output AND each output can only correspond to one input.

So f(x)=x^2 can only be a function if restricted to x >= 0

I know that this is not the place to discuss mathmatics, however if the above is true I think it should be noted. DougBrown 16:32, 2 November 2006 (UTC)

That's an Injective function, f(x)=x^2 is a function without the restriction x >= 0. skip (t / c) 14:00, 2 November 2006 (UTC)
Thanks, Do you think that a short mention of Injective Functions would be useful on this page? with a link to the Injective function page? DougBrown 16:32, 2 November 2006 (UTC)
It's already mentioned in the vocabulary section, linked from "injections". It may be helpful to link to the Horizontal line test and/or Vertical line test articles. skip (t / c) 07:19, 3 November 2006 (UTC)

I see that Bijection, injection and surjection has been redirected here; however, there was a lot more detail on the last version of that page before it was changed to a redirect[1] that doesn't seem to be here anymore. I read through the talk page and don't see any discussion of this merge; am I missing something? It seems to me that either that page should be restored, or its redirect is pointing to the wrong place, or there's a bunch of info that needs to be added here. Personally, I lean towards reverting the redirect on Bijection, injection and surjection - any thoughts? Perel 04:37, 5 December 2006 (UTC)

Revert. This merge/redirect was a dubious idea that should have been discussed first. --KSmrqT 06:19, 5 December 2006 (UTC)
I agree. Revert. Rick Norwood 13:29, 5 December 2006 (UTC)
Done. If anyone strongly opposes this revert, start an AFD and mention it here. Perel 03:21, 6 December 2006 (UTC)
The more difficult question is why there is a page Bijection, injection and surjection as well as pages bijection, injection, and surjection. I can't see any benefit to this redundancy. CMummert 13:05, 6 December 2006 (UTC)
The closer we look, the stranger the situation appears. First, we have the obvious redundancy of content. Second, "Injection" itself is a disambiguation page (which makes sense). Third, we have "Bijection", but "Injective function" and "Surjective function". Fourth, although there is redundant content, there is also distinct content. Fifth, we have nearly duplicate figures, but in the joint article they are PNGs, while in the individual article they are SVGs.
So the question would seem to be, is there enough broad content for the joint article to so limit itself (rather like the manifold article)? If not, should it absorb the others or should it disappear? One concern: I would find it annoying if a passing reference to a surjection dumped me at the beginning of an omnibus article, when all I wanted was a quick definition; I do not believe we can rely on editors to link to a subheading, nor to avoiding renaming subheadings.
Meanwhile, the mathematical formatting in all could use some polish. --KSmrqT 15:11, 6 December 2006 (UTC)
I would keep the three separate pages, since most editors will link to the words surjection, bijection, etc. when writing other articles. Over 200 articles link to bijection, only a handful link to the joint article. Fixing all the double redirects if bijection were removed would be a pain, and even then more would appear.
Since the function article already has links to the individual articles, I don't see why the joint article needs to be preserved. The content in it can be divided between the individual articles and the main function article. I suppose the joint article could be made a redirect to the main function article, to avoid an AFD. CMummert 15:35, 6 December 2006 (UTC)
Yes, this does get stranger and stranger. I'm thinking that we may want to rename "Bijection" "Bijective function" for consistency, and remove the joint article. That really shouldn't be done until there's consensus that anything relevant from the joint article has been moved back into the individual articles. Perel 16:11, 6 December 2006 (UTC)
Given the options contemplated, we should move this discussion to the joint talk page. But first, if there is very little unique material in the joint page, perhaps that extract could move to the function page. Thoughts? --KSmrqT 05:55, 7 December 2006 (UTC)

Hardy's definition

I think it's important to note that "function" has previously been defined to include multi-valued functions. I know many mathematicians are sensitive about this - but, Hardy is, uh, hardly a trivial guy. Anyway, the term "function" is now almost strictly including an implicit "single-valued". That's standard usage, but maybe it should be mentioned in that regard in the article. Tparameter 22:20, 22 January 2007 (UTC)

I moved this section to the bottom of the talk page. I would be interested to see a quote from Hardy, if you have the book handy. I realized recently when working on exponentiation that it is common to call a function "multivalued" not to mean that it is set-valued but just to mean it could be defined to have one of several possible values. I would like to know which of these two options Hardy is talking about. CMummert · talk 00:09, 23 January 2007 (UTC)
Here is a link to google books, and Hardy's book. Simply type in page "26", and read. You will see that he give THE definition, and carefully notes that "most" functions obey that definition, then lists functions that do not. y^2=x is a good example of one that defies Hardy's #2 characteristic of common functions. He refers to this thing as a "function", and notes clearly that it does not obey the single-value rule. Accordingly, Hardy is very clear on this matter - so I removed the "ambiguity" quote from the article. LINK: http://books.google.com/books?vid=OCLC02103061&id=a3gsxbGBdfIC&pg=PA249&lpg=PA249&dq=hardy+math#PPA26,M1 Tparameter 22:15, 23 January 2007 (UTC)
Strange. I have a cc of Hardy and Wright 1979 5th edition of 1938, An Introduction to the Theory of Numbers, Oxford Science Publications, Clarendon Press, Oxford UK, ISBN 0-19-853171-0. Nowhere in the "General Index" do the words "function" or "formula" appear. So I go hunting for first usage. Starting on page 5 (italics added for emphasis),
"(1) Is there a simple general formula for the n-th prime pn (a formula, that is to say, by which we can calculate the value of pn for any given n with less labour than by the use of the sieve of Eratosthenes)? No....
"(2) is there a simple general formula for the prime which follows a given prime (i.e. a recurrence formula such as pn+1 = p2n + 2?)
"Another natural question to ask is:
"(3) is there a rule by which, given any prime p, we can find a larger prime q?
"This question of course presupposes that, as stated in Theorem 4, the number of primes is infinite. It would be answered in the affirmative if any simple function f(n) were known...[etc]" (p. 5-6)
From this I devine that the authors have "identified" .e. equated as synonymous the notions of "formula", "rule" and "function". Sounds like "agorithm" to me -- the dead give-away is "rule".wvbaileyWvbailey 17:57, 9 September 2007 (UTC)

Explanation of revert

I've just reverted a "clarification" that said a function is a "rule". Though that may sound helpful, we have deliberately avoided that kind of language, for reasons discussed previously. Briefly, while many commonly encountered functions are specified by a rule, that is mathematically impossible for most functions. We have only countably many rules, but uncountably many functions.

The reversion also removed a new leading image and caption. I actually prefer the cubic, since the parabola is a little too special; and the formula for the parabola had a bad line break in the middle. The only problem I see with the cubic is that within the image is a "Fortran"-style text version of the formula using "**" for the power. I'd actually prefer to see a more interesting function generated by an elementary formula. We could even include bounds on the range, to make it even more informative. For example,

has some nice wiggles between −1 and 32, but we must bound x to avoid problems with the square root. --KSmrqT 16:13, 25 January 2007 (UTC)

Terminology

Function vs. map

While the words "function" and "map" are indeed defined synonymously, mathematicians do not use them interchangeably. Look for example at the distinction in differential geometry between "smooth maps" and "smooth functions", or in algebraic geometry between "rational maps" and "rational function": it seems to me that "function" is usually reserved for a map with numerical codomain (depending on context, "numerical" may be "real or complex", or "with values in the ground field", etc.).

Maybe something to that effect should be mentioned in the article. But I thought I'd discuss it here first. (I also note that similar remarks have been made by several contributors in the French and German equivalents of this discussion page.) Mathanor 23:09, 22 February 2007 (UTC)

I don't see that any such distinction holds, nor is it helpful. Perhaps "map" is used more often in a topological context, but "function" is used with sets, and the reals have topology. --KSmrqT 00:27, 23 February 2007 (UTC)
The point is not that "map" is used in some contexts and "function" in others, but that several contexts use both terms, with the customary difference I mentioned. Mathanor 09:32, 23 February 2007 (UTC)

The vocabulary I hear is "function" or "map" interchangably if the codomain is a point set, with map more common, probably because it is shorter, and functional if the codomain is the reals or the complex. But I've heard a metric called a map. Rick Norwood 13:50, 26 February 2007 (UTC)

Input, output, argument, value

I came to this article because I was unable to recall the term 'argument' as it pertains to functions, even though I know the concept. After spending a few minutes with the article, I eventually found the word I was looking for, but it was frustrating not to find this term in the basic definitional statement, where 'input' is used instead, and correspondingly 'output' is used to denote the concept of value of a function. In order to introduce the conventional technical terms 'argument' and 'value' the passage A standard notation for the output of the function f with the input x is f(x). could be changed to A standard notation for the output, or "value" of the function f with the input, or "argument" "x" is f(x). Jeff Johnson 24.159.60.119 00:27, 25 February 2007 (UTC)

I agree—in mathematical language, "argument" and "value" are at least as commonly used (and probably more so) as "input" and "output" (which seem to be influenced by computer science). Mathanor 06:41, 25 February 2007 (UTC)
Computer science does use "input" and "output" when describing processes, perhaps borrowing the terms from manufacturing processes; however, formal language for functions uses "argument", "parameter", "(return) value", and so on. Some literature draws a careful distinction between the slots or free variables of a function, and the instances of things used in those slots or bound to those variables upon invocation. With the Curry mechanism, we also may treat a function of two variables, F(a,b), as F(a) returning a function of one variable, [F(a)](b).
That said, please remember that the introduction, and especially the opening sentence and paragraph, cannot be all things to all people. In article after article, efforts to make them so end badly. At the beginning, it is more important to engage the general public than to satisfy the specialist; the masses will leave us soon enough once we start to get technical. --KSmrqT 16:50, 25 February 2007 (UTC)

When I began in math fifty years ago, everyone used function, domain, range, epimorphism, monomorphism, argument, and value. Today, I usually hear map, domain, codomain, one-to-one, onto, input, and output. Language naturally morphs to simpler, more descriptive words. Remember "ordinate" and "abscissa"? Rick Norwood 13:55, 26 February 2007 (UTC)

  • "Function" and "map" are still both used today, cf. the previous subsection.
  • Likewise for "range" and "codomain", with the frequent distinction that for a map f:AB, the codomain is B but the range is the set {f(x)|x in A}.
  • "Monomorphism" and "epimorphism" are still used in category theory, in a slightly different sense: there are categories whose objects are sets and whose morphisms are maps, but in which a morphism that is one-to-one (as a map between sets) need not be a monomorphism (in the categorical sense). But "one-to-one" and "onto" are more frequent in "everyday" mathematics, as are their synonyms "injective" and "surjective" (and I certainly don't wish to imply that "monomorphism" and "epimorphism" should appear in this article).
  • For what it's worth, "abscisse" and "ordonnée" are still very common in French, where they probably sound less pedantic than in English. But even in French, they are not thought of as synonyms for "argument" and "value", but just as coordinates in the plane (so the connotation is geometric rather than analytical). Mathanor 08:10, 27 February 2007 (UTC)

Plea for flexibility

This is really a very decent article, in my opinion (as a newcomer to this page), but I'm really quite surprised how unaccommodating the discussion on the talk page is. As many have pointed out, Wikipedia is an encyclopedia and not a mathematical textbook. The word "function" has many uses in mathematics, and the intuition varies from field to field, and from person to person, so we should be accommodating to any widely-held points of view, and also some history. Yet, as I read through the talk page, I find myself reading again and again comments like "A function should not be a fuzzy concept", "y=x^2 is not a function", "I've never seen anyone say f=x^2", "This is not pedagogical in my experience", "Don't confuse a function with its values", despite the fact that the usages being criticised are widespread. I don't intend to point the finger at any individual whose quotes resemble these; I think it just reflects the nature of the a fundamental term such as "function", that everyone has their own idea or ideas, and different intuitions are useful in different fields. I also agree that at the present moment the precise set-theoretic concept of a function (or map) is the dominant one in mathematics (although this was not the case 200 years ago, nor is it so clear-cut in related fields such as statistics or computer science!), and the article should certainly reflect this. But we can perfectly well give a precise and easily understandable set-theoretic definition, while also acknowledging that the word is also used in more specific ways, more general ways, and more "intuitive" ways. Also times are changing (for instance, after an era of derision as "abstract nonsense", category theory seems to be on the rise).

Let me illustrate my point by some examples with varying degrees of sophistication.

  • In some categories, the morphisms are intuitively regarded as functions, without them being set-theoretic functions. This is the case, for example, in synthetic differential geometry. There are of course, even more examples where the categories are set-theoretic, but the functions are not arbitrary functions: they can be more specialised, or even only partially defined, and the article acknowledges this to some extent.
  • A constructivist would insist that a function should be given by a rule or formula, whereas a set-theorist might admit all sorts of wild functions such as choice functions. The intuition of most "working mathematicians" lies somewhere inbetween.
  • The concept of a function in applied mathematics is a relation between a dependent and independent "variable", such as the relation y=x^2, but the notion of a variable is usually not precisely defined.
  • In logic these variables are place-holders which we can quantify over.
  • In my own field of differential geometry, there is a different interpretation of variables such as these: x and y are both functions on a space (e.g. the line, but sometimes even an unspecified space), and the relation y=x^2 says that y(p) = x(p)^2 for all points p in the space. In this context, the expression f(x) is usefully interpreted to mean the composite of the function f with the function x. (This is useful in calculus too.) Writing f instead of f(x) (for f o x) is called omitting pullbacks and this "abuse" of notation is common throughout mathematics, for example when we write u=t^2+t instead of u=s^4+s^2 where t=s^2.
  • Even only 100 years ago, functions rarely had precise domains and codomains. This was because, for example, mathematicians had recently discovered the value of using complex numbers to understand real objects: even "ordinary space" (Euclidean 3-space) had complex points. Modern category theory provides many ways of making these intuitions precise, such as the notion of a point as a functor, for instance in the theory of schemes.

I'm not suggesting that an elementary article on functions should address all such points of view in detail, but we should acknowledge, at least in talk pages, if not in articles, that many points of view exist and not constrain our articles to be single-minded in their approach. I was drawn to this page because I noticed that someone who appears to be an expert on harmonic maps has quit wikipedia after a short stay because he/she felt that it was fruitless to make even minor suggestions in an apparently unaccommodating atmosphere of editors with entrenched opinions. Please, wikipedia cannot afford to lose experts like this. Please be accommodating! Geometry guy 20:58, 2 March 2007 (UTC)

Well, it does take a thick skin to work here. Especially the articles on basic topics are continually inundated by people who do not understand what is going on, which I think leads over time to an expectation that all suggestions are from such users. Editors who do understand the concepts may find it easier to just edit the article and defend their edits rather than asking about them first. It also helps to ask "why is the article written in this way" instead of saying "The article is wrong! Why hasn't anyone fixed it?". Often the state of an article reflects a careful compromise of wording to accomodate several viewpoints.
I can make two specific comments about the examples you included above. First, morphism is not the same as function, and this article covers the latter. But it includes a brief discussion and pointer for the former. Second, a function is not the same as a binary relation, but the article gives a link to the latter. So the article does have some depth if you read it in the right way.
As a thought experiment, suppose that someone with a background in physics came to the calculus pages and explained how they had been taught to work with infinitesimals (which is still common in physics and engineering) and that the interpretation that dx is an infinitesimal real number ought to be included in the article. How would you respond? The article as it stands just says "Historically, dx represented an infinitesimal quantity, and the long s stood for "sum". However, modern theories of integration are built from different foundations, and the notation should no longer be thought of as a sum except in the most informal sense. Now, the dx represents a differential form." CMummert · talk 05:21, 3 March 2007 (UTC)

Interesting comment, though it seems both to miss and to illustrate my point. I agree the article does quite a good job in discussing related notions. I was not criticising the article, but the mind-set that believes it knows what a function is and what it is not ("a function is a map", "a function is not a morphism", "a function is not a binary relation" etc.). This is not about having a thick skin (and thankfully, this talk-page is reasonable free of the ad hominem) but an open mind. I have seen from the long debates over the first sentence (!?) that the wording is a often a delicate compromise, but this is only a compromise among the editors at the time and one day it will probably be completely rewritten - a strength and weakness of the wikipedia model.

The thought experiment also illustrates my point - indeed I've taken the advice to "edit first" to remove the inappropriate tone of the word "should" in the quoted sentence from integral. The physicist's point of view is perfectly legitimate:

So the calculus articles can (and in fact do) discuss the interpretation of differentials as infinitesimals. I agree that the flag-ship integral article (just like this article) should emphasise the main modern notions, but not at the expense of calling other approaches illegitimate.

Let me repeat my main point for clarity: wikipedia is an encyclopedia, not a new book on the foundations of mathematics. It is not our job to update Principia Mathematica, nor to write a textbook to educate (e.g.) high-school students on what is the "correct" meaning of "function" or "dx". Geometry guy 11:16, 3 March 2007 (UTC)

I agree. If this article calls any of the other viewpoints of functions illegitimite, then that wording should be changed ASAP. I thought that the integral article was quite reasonable about dealing with the issue early and then forgetting about it.
In the case of "function" I would argue that there is a well-understood common concept of function that is defined in myriad textbooks at the undergraduate level as a set of ordered pairs. Other concepts of function are not "wrong" but they are not the concept that this article attempts to cover. Like infinitesimals in the integral article, we should acknowledge other interpretations early, give pointers to the articles where they are discussed, and then move on. The difficulty is that many editors do not have this "high-level" view of the field, which accepts that the same word is "function" is used to mean many different things.
If you are not already familiar with the bike shed problem, you might want to read that essay. The moral is that we should refuse to discuss the color of the shed. For this article, that means we never discuss what a function is, because we all know all the different meanings. But we can decide which of the specific concepts of function are important enough to cover here.
When I mentioned a thick skin, I meant the ability to accept that we will never have complete agreement, and that we do not write from a position of authority no matter how qualified we are. This is very different from the academic world, where authors have full control of what they write and are free to adopt the conventions they personally find appealing. CMummert · talk 15:19, 3 March 2007 (UTC)

Thank you for these clarifications and further interesting comments. Even if we don't have complete agreement, it seems our views are not so far apart! This for me is part of the spirit of wikipedia. Thanks again for both this and the previous reply, and happy editing! Geometry guy 18:44, 3 March 2007 (UTC)

My experience in academia differs from CMummert's idyllic picture. When I submit work to a journal, I must follow that journal's style, and heed the demands of anonymous reviewers. Even when I write for a book I must work with an editor and attend to the comments of reviewers (though these are not demands). Working with coauthors brings further compromise.
The big difference is that in academia we work with people who know a great deal about the topic or about writing (or both), while many Wikipedia editors have little expertise of either kind. Thus we could find a post-doc at the Institute for Advanced Study having to wrestle with a pre-university student who has aggressive opinions, poor English skills, and lots of free time.
The intermediate editor can be worse. Consider a bright engineering student who took the required mathematics classes at university, and who now has a fairly high opinion of his own knowledge of mathematical topics and conventions. A graduate student in mathematics very quickly learns humility, with guest lectures whose title is incomprehensible. Not so the engineer, who "knows" without hesitation and writes with conviction.
These two groups are discouraging, but they are not the worst. That honor falls to the cranks, the crackpots, and the extremists. For example, an editor like Melchoir knows a little mathematics, but seems addicted to inline citations, with a bizarre interpretation of what Wikipedia calls original research. These folks distort Wikipedia's processes and goals to frustrate sensible editors, and may compulsively edit a target article dozens of times a day for a week or more. (See the history of 0.999... for August 24 to September 4 of 2006, when many stabilizing editors were away.) If you criticize or disagree with them, they will claim you are violating the behavioral rules of Wikipedia, and may bring (or threaten) formal Wikipedia action against you. This is the kind of thing that finally drove away Chris Hillman, an expert in general relativity theory, while Asmodeus and DrL are still here, despite misbehavior severe enough to draw disciplinary action. (So far, Melchoir has not gone that far.)
Suprisingly, the least troublesome group is the vandals. Several times a week some "wit" will edit E = mc2 to say mc hammer (a rapper) or mc3, and some student who should be studying will blank the geometry article to express a dislike for the subject; these are quickly reverted.
Wikipedia can be a strange, disorienting place. Ironically, mathematicians — who often have underdeveloped social skills — form a relatively sane and civil community here. The more esoteric the topic, the easier the editing. It's articles like this, viewed and edited by a wide audience, that cause most of the commotion. And within such articles, the introduction gets the bulk of the attention, with the first sentence the most prominent target.
How to survive and thrive? One option is to avoid popular topics. Another is to make a home in the community, so when trouble comes you have friends. Perhaps you are willing and able to practice extraordinary diplomacy; we have two mathematicians on the Arbitration Committee. Most important, as in negotiating with a car dealer, is to be prepared to walk away. In fact, our newest ArbCom member, Paul August, deliberately separated himself from Wikipedia for one month before returning and deciding to stand for the committee.
Should you decide to edit a popular article, do so with eyes open, knowing the ride may get rough and the outcome may be disappointing. But also know that sometimes this peculiar consensus process leads to unexpectedly good results, and the benefits will be shared with readers around the globe. If you like, try the philosophy of Meher Baba: "Do your best, then don't worry, be happy." --KSmrqT 04:01, 4 March 2007 (UTC)

Yes, I've found the math community very sane and civilized, which was one of my motivations for flagging up an unfortunate loss. I agree with the observation that the more esoteric articles are easier to handle and there is so much to do there, that I'm sure they will keep this Geometry guy busy for a while. Still I might occassionally dip into to something more popular just to see the bigger picture and make contact with other editors such as those here. Geometry guy 15:56, 4 March 2007 (UTC)

Changes to the introduction

First, I'd like to apologize for not providing the summary of the edit — clicked on the wrong button! Moreover, I've changed quite a bit more than originally intended, however, instead of apologizing, I would like to explain some of my motives. After reading back-and-forth between the editors, it appeared that the article is "eyeless by virtue of having too many nurses" (a russian proverb). For an encyclopedic article intended for general audience, and even for general mathematical audience, its introduction was practically worthless. On the other hand, Battles of the Bulge were fought over every word in the first sentence. For 99.74% of the reading public, the resulting difference didn't amount to much.

However, I finally came across very well thought out comments from User:Geometry guy and especially the bike shed metaphor,

This was pointed out by User:CMummert, not myself, but thank you for the compliment. Geometry guy 22:40, 19 March 2007 (UTC)

and I thought: why not be bold? After all:

  • After splitting many a thousand hair, the esteemed editors agreed on a compromise set-theoretic definition of a function. But Wikipedia is decidedly not Éléments de mathématique. This is the article on function, for example, there is no function (physics), and it has to address what functions are, what is the intuition behind them, what makes them different from other mathematical concepts, such as number, algebraic structure, shape, what makes them "tick". To some extent, it does, but you wouldn't know it from reading the introduction and even quite a bit beyond.
  • I am no stranger to algebra myself, but reading this article I kept thinking of David Mumford's amusing story about the definition of a plane that his daughter brought him from school when he worked in France at the height of Bourbakization: he wrily remarked that it differed only insignificantly from the hot new concept discussed at IHES at the time under the name torseur. For those who are not in on it: New Math is dead, and for a good reason.
  • Most functions in mathematics, not to mention other sciences, are fairly concrete objects: differentiable functions in real analysis, algebraic operations in number fields or finite fields in Algebra, heck, even homotopies in algebraic topology! Moreover, mathematics of both past and present is replete with implicit functions, multivalued functions or other types of functions that do not fit the Procrustean bed of the axiomatic definition Űber alles, and yet are called functions. Worse yet, even though nearly every iteration produced results further and further from ordinary experience of even most mathematician, with a possible exception of our respected colleagues in abstract set theory (hmm-m-m!), it was still not pure enough to be 100% consistent and unambiguous. Like, it carefully avoided word rule, yet used "inputs" and "outputs", which are objects of what kind? (Unfortunately, this criticism still stands!)
  • If there is something valuable about general notion of function, it's that you (sometimes) can compose them!
  • Just because functions are different from their graphs doesn't mean we should carefully tuck the graphs away. In fact, I would wager that for a vast majority of people, functions are given by either graphs, formulas, or tables. Moreover, unlike many more esoteric concepts in mathematics, functions are fairly familiar to many people under those guises. We should be building up on this intuition, not destroying it.

I do, however, want to state that I tried to the best of my ability to stay faithful to the intent of many previous editors as well as keep most existent terminology (although I would disagree with some of both). My changes were primarily aimed at increasing the quality of presentation, and especially encyclopaedic nature of the article. With this incomplete Mathematician's Apology, I'll let my dinghy sail over rough seas of Wikipedia. Arcfrk 22:21, 19 March 2007 (UTC)

And good luck to you! I agree with almost all these comments (although the word torsor may be enjoying a renaissance, simply because mathematicians like myself are beginning to get fed up of writing principal homogeneous space or free transitive action in its place!). I also entirely support this edit, not least because it finally supplies this article with a proper lead and hence moves some of the hair-splitting disputes out of the introduction and into the body of the text where they belong. I hope other editors will build on this lead. Geometry guy 22:40, 19 March 2007 (UTC)

Inconsistent or ambiguous definitions of the word "function"

Please see the third figure in this edit of mine (that I undid). The caption of that picture was consistent with the very strict (but clear) definition given in section "Partial functions and multi-functions" (which implies that partial functions are, strictly speaking, "not true" or "improper" functions; and that "partial function" is a misnomer, like multivalued function).

However, the definition given in the lead and the "modern definition" given in the section "History of the concept" are not clear in this respect. Moreover, the article partial function seems to suggest that a partial function is a true function. On the contrary, the article multivalued function says very clearly that a "multivalued function" is not a true function.

It is important to be crystal clear:

  • According to the "modern formal" definition by Dirichlet and Lobachevsky (which is what is given also in the lead, I assume), are "partial functions" true functions?

Paolo.dL 18:01, 7 September 2007 (UTC)

The way that partial functions are commonly defined, every function is a partial function but not every partial function is a function. This is a typical example of how mathematics terminology can differ from the natural language meanings of its terms, and how terminology phrased as a specialization of a definition can be a generalization. — Carl (CBM · talk) 18:12, 7 September 2007 (UTC)

Really? I hate this kind of counter-intuitive terminology (see Talk:Partial function)!!! Ok, since total functions are commonly regarded as partial functions, then I have to rewrite my question. I meant:

  • According to the "modern formal" definition by Dirichlet and Lobachevsky (which is what is given also in the lead, I assume), are "non-total" functions true functions? In other words, is the definition given in section "Partial functions and multi-functions" consistent with the modern "formal definition"?

Paolo.dL 18:20, 7 September 2007 (UTC)

The sentence "In some contexts, a relation that is total, but not necessarily single-valued, may be called a multivalued function; and a relation that is single-valued, but not necessarily total, may be called a partial function." is correct. Is that what you are asking? — Carl (CBM · talk) 18:29, 7 September 2007 (UTC)
This relation is not a proper function (it is not defined for some elements in X). It is sometimes called a non-total function.

Not at all! I was talking about the strict definition of the word "function". The only crystal clear and not ambiguous definition that I can find in the article is contained in the section "Partial functions and multi-functions":

"The condition for a binary relation f from X to Y to be a function can be split into two conditions:"
"1) f is total, or entire: for each x in X, there exists some y in Y such that x is related to y."
"2) f is single-valued: for each x in X, there is at most one y in Y such that x is related to y."

This definition is absolutely clear, although it is only valid for binary relations. On the contrary, the definition in the lead is ambiguous. Again, please see the third figure in this edit of mine (I copied it here and replaced "partial" with "non-total", in its caption). Can this figure be added to the others in the lead? Is its caption correct? Paolo.dL 14:17, 9 September 2007 (UTC)

Being a curious person immediately a question comes to mind about the drawing: what happens when you plug "1" into the machine (aka "function")? What pops out of "the machine" (aka your function?) Where does the little arrow go? Maybe you plug in "1" and the machine (Turing machine, counter machine, done-by-hand recursion, whatever) goes into an endless loop so "the machine" never produces an output, and thus the arrow goes nowhere (draw it with an "x" at the end outside the domain: e.g. a failure-of-a-function: "IF the input-number is 1 then loop back to this instruction else go to the next number...".).
What you seem to be debating here is the nature of "effectively computable" or "effective calculation", where the word "effective" means: "causing the desired effect: in particular, given any natural number or 0, terminating (or at least presenting, together with a signal) the result (output) of the computation/calculation as a natural number or 0." Partial functions (aka computational machines) are "effective" only for some natural numbers in their domain. Thus we restrict the über-domain (the natural numbers and 0) so that the function behaves as if it were total. All this information about "restriction" and what we expect from the machine (aka function) must be part of the function itself, given "up front" in a specification, otherwise "the function" (aka machine) may fail to do its job.
This is my understanding of it. If I'm wrong someone please lemme know. Thanks, wvbailey Wvbailey 17:12, 9 September 2007 (UTC)

The definition of the expression "partial function" is given in another article. This section is just about the standard formal and strict definition of the word "function". A very specific topic. Paolo.dL 17:46, 9 September 2007 (UTC)

I am quite aware of what this article is about. I was referred by that talk page to this talk page. Your drawing makes no sense. That's my point. wvbailey Wvbailey 18:00, 9 September 2007 (UTC)

The question is: are "non-total" functions true functions? The answer is crucial, and should somehow appear in the lead of this article (possible in the caption of a figure). Paolo.dL 18:11, 9 September 2007 (UTC)

I think I see your question better now. They are "functions" if the domain is redefined to be the set of input values for which there is an associated output value, but only "partial functions" if a larger set of possible input values is considered. So it matters not only what pairs are in the relation, but also what set the function is meant to be defined on. For example, the function is a perfectly valid function from the nonnegative real numbers to the nonnegative real numbers, but only a partial function from the real numbers to the real numbers. — Carl (CBM · talk) 18:15, 9 September 2007 (UTC)

Thank you very much. I deduce (from your "but only") that your anwser to my question is no, as I expected. If in the next week nobody will express a different opinion about the standard formal definition of the word "function", I will insert my figure in the lead. With regards, Paolo.dL 20:23, 9 September 2007 (UTC)

Notice that the formal "Definition" in the article says that a function is a set Gf. However, in the next sentence, we learn that Gf is the graph of the function! The readability of the whole section is very low. I tried to improve it, by rearranging a little bit, but I can't fix it completely. Paolo.dL 13:47, 12 September 2007 (UTC)

Relations, functions, and partial functions

This is neither a relation nor but not a function because the domain "X" has not been restricted to only those values that map to the codomain "Y". If an additional oval S were drawn around the "2" and "3" then this drawing would be an example of a "partial" function. It is a partial function from the set {1,2,3} to the set {a,b,c,d}. Note: strikeouts and italicized additions by — Carl (CBM · talk) 20:38, 9 September 2007 (UTC)

A question for CBM: Wouldn't the caption of the above drawing be more accurate if it were something like this? wvbaileyWvbailey 19:02, 9 September 2007 (UTC)

The picture above does show a relation - the definition of a relation is very weak, and does not require that every element be related to some other element. The picture shows a rule that defines a function on the set {2,3} (but no oval is shown for this set). This rule defines a partial function on the set {1,2,3}, but not a total function on that set. — Carl (CBM · talk) 19:11, 9 September 2007 (UTC)
Based on the lead and first section of the article partial function, I understand that the expression "partial function" would not even exist, if the set "on which" the function is defined were not a proper superset of its restricted "domain" (or "domain of definition" or "input range" if you like). Partial just means that some values may exist "somewhere" for which the "function" is not defined. "Somewhere" means in the domain of "f", for some authors, or in a proper superset of it, for others. However, notice that a figure identical to the one I copied in the previous section is included in the lead of the article partial function, with this caption:
  • "An example of a partial function that is not a total function".
Paolo.dL 20:09, 9 September 2007 (UTC)
Yes, the image you included is an example of a partial function on the set {1,2,3} that is not a function with that domain. The term "partial function" exists because sometimes the rule that is used to try to define a function on a set only defines the function on a subset of the original set. When that happens, you can make two claims:
  • The rule defines a function on a subset of the original set
  • The rule defines a partial function on the entire set
The example of and the real numbers is a typical example of this; the rule only defines values for inputs that are nonnegative real numbers. — Carl (CBM · talk) 20:58, 9 September 2007 (UTC)

Survey of the literature for definitions

Hmm. So I will do some research (see what I conclude at the end of this entry). I have gotten out my latest books Boolos-Burgess-Jeffrey (2002) and Sipser (2006), as well as my set-theory books. Of course, Kleene 1952 makes his stance crystal-clear: "the idea of a function as a many-one correspondence ... [this] is the more comprehensive one, which the student should keep uppermost in his mind." (p. 33) He seems, by examples, also to be restricting his domain to the natural numbers (and zero) or subsets thereof.

  • Sipser 2006, Introduction to the Theory of Computation: 2nd Edition: "A function is an object that sets up an input-output relationship. A function takes an input and produces an output. In every function, the same input always produces the same output.... A function also is called a mapping.... ¶ The set of possible inputs to the function is called its domain. The outputs of a function come from a set called its range.... Note that a function may not necessarily use all the elements of the specified range." (p. 7); "codomain" appears nowhere; "partial function" does not appear.
  • B-B-J 2002, Computability and Logic: 4th Edition: "A function is an assignment of values to arguments. The set of all those arguments to which the function assigns values is called the domain of the function. The set of all those values that the function assigns to its arguments is called the range of the function. In the case of functions whose arguments are positive integers, we distinguish between total functions and partial functions. A total function of positive integers is one whose domain is the whole set P of positive integers. A partial function of positive integers is one whose domain is something less than the whole set P. From now on, when we speak simply of a function of positive integers, we speak simply of a function of positive integers, we should be understood as leaving it open whether the function is total or parital. (This is a departure from the usual terminology, in which function of positive integers always means total function).(italics in original, p. 7); They use the words "domain or universe of discourse w.r.t. model theory etc; "codomain" appears nowhere.
  • Kleene 1952 again: he is trying to extend "effective calculability" by allowing for partial functions (p. 325) "...extend the class of the general recursive functions to take on incompletely defined functions, calling the resulting class of functions the partial recursive functions" (p. 325). Just before this he proposes the intentional design of algorithms that would normally terminate without giving a number as value of φ(x) to, rather, go on forever without termination. [Why would anybody do this intentionally is beyond me.]); "codomain" appears nowhere.
  • Saracino 1980, 1992, "Abstract Algebra: A First Course" (the book my kid used in Saracino's class): "DEFINITION If S and T are sets, then a function f from S to T assigns to each s ε S a unique element f(s)ε T. ... "DEFINITION (precise) A function from S to T is a set of ordered pairs (s,t), where each s ε S and each t ε T, such that each s ε S occurs as the first element of one and only one pair (s,t).... (The word "mapping" is sometimes used for "function"). (p. 59). He uses the words "domain" and "image (or range)" (p. 60) ; "codomain" appears nowhere.
  • Halmos 1970, Naive Set Theory: "If X and Y are sets, a function from (or on) X to (or into) Y is a relation f such that dom f = X and such that for each x in X there is a unique element y in Y with (x, y) ε f. The uniqueness condition can be formulated explicitly as follows: if (x,y)εf and (x,z)εf, the y=z. ... The words map or mapping, transformation, correspondence, and operator are among some of the many that are sometimes used as synonyms for function ... For relations in general, and hence for functions in partiular, we ahve defined the conepts of domain and range" I" (p. 30-31); "codomain" appears nowhere.
  • Suppes 1960, Axiomatic Set Theory: "If R is a relation then the domain or R (in symbols: DR) is the set of all things x such that, for some y, <x,y> ε R. ... The range of R ... is the set of all things y such that, for some x, <x,y> ε R. ... The range of a relation is also called the counterdomain or converse domain ... The field of a relation ... is the union of its domain and range." (p. 59). At last we see where "co-domain" may have derived from; from "counter- or converse-" domain.
  • Other books (Knuth: no definitions), a book on finite algebra (domain and range, no co-domain), a book on complex variable theory (domain and range, no co-domain).
  • Tarski 1961, 1946 Introduction to Logic, uses "counter-domain and converse-domain", does not use "range" (!) Moreover, if I understand him, he defines functions backwards from typical analysis and set-theoretic conventions , as in "x R y" being equivalent to "x = R(y)" (cf pp. 99-100). updated wvbaileyWvbailey 19:37, 10 September 2007 (UTC)
  • Suppes 1957 Introduction to Logic, "A function is a rule which assigns to each element of a given set a unique element of some other, not necessarily distinct set ... this definition is intuitively satisfactory. On the other hand... More formally, a function R is a binary relation such that if x R y and x R z then y = z." (p. 230). He uses the word "counterdomain" again. "A function is sometimes said to map its domain onto its range. ... In logic a function is often called a many-one relation." (p. 231)
  • Thomas (calculus) (older than God -- my old college text) Calculus and Analytic Geometry: "... a variable is a symbol, such as x, that may take any value in some specified set of numbers. The set of number over which x may vary is coalled the domain of x. In most of our applications, the domains of our vairables will be intervals of numbers... DEFINITION. A function is a set of ordered pairs of numbers (x, y) such that to each value of the first variable (x) there corresponds a unique value of the second variable (y)" (p. 16-17. "The set of all values taken on by the independent variable is called the domain of the function. The set of all values taken on by the dependent vairables is called the range of the function. If the pair (a, b) belongs to the function f, that is, f(a)=b, we also say that b is the image of a under f. Similarly, the range of a function is the image of its domain. We also say that the function maps its domain onto its range." (p. 19).
  • Stewart 3rd edition 1995 Calculus: Early Transcendentals: "A function f is a rule that assigns to each element x in a set A exactly one element, called f(x) in a set B. We usually consider functions for which the sets a and B are sets of real numbers. The set A is called the domain of the function. the number f(x) is the value of f at x and is read "f of x." The range of f is the set of all possible values of f(x) as x varies throughout the domain, that is {f(x)|x ε A}. It is helpful to think of a function as a machine"(p. 2-3) .... "In Examples 1 and 2 the domain of the function was given explicitly. But if a function is given by a formula and the domain is not stated explicitly, the convention is that the domain is the set of all numbers for which the formula makes sense and defines a real number" (italics in original, p. 7). A similar definition exists for "Functions of Several Variables"; ditto for "domain" and "range" (p. 740). No mention of co-domain.
  • Anton 8th edition 2000 (1973 the 1st) Elementary Linear Algebra (aka "...is the work of Satan's minions"): This is in a chapter titled "Linear Transformations from Rn to Rm": "Functions from Rn to R. Recall that a function is a rule f that associates with each element in a set A one and only one element in a set B. If f associates the element b with the element a, then we write b = f(a) and say that b is the image of a under f or that f(a) is the value of f at a. The set A is called the domain of f and the set B is called the codomain of f. The subset B consisting of all possible values for f as a varies over A is called therange of f." (p. 173) Thus "the range" is a subset (proper or improper) of "the codomain".
  • J. V. Uspensky and M. A. Heaslet (1939), Elementary Number Theory: No mention of "function", "domain", or "range" in the index. Commonplace f(x) is used throughout the later parts; "algorithm" and "equation" are connected; "equation" is a statment of equality used in an "algorithm".
  • Stephen R. Lay (1990), Analysis: with an Introduction to Proof:
"7.1 DEFINITON: Let A and B be sets. A function between A and B is a nonempty relation f [is a subset of ] A x B ["x" is the Cartesian i.e. cross-product of] such that if (a,b) ε f and (a,b') ε f, then b = b'. The domain of f is the set of all first elements of members of f and the range of f is the set of all second elements of member of f. Symbolically,
"domain f = { a: There exists b ε B such that (a,b) ε f }
"range f = { b: There exists a ε A such that (a,b) ε f }
"The set B is referred to as the codomain of f. If it happens that the domain of f is equal to all of A, then we say f is a function from A into B and we write f: A --> B." (p. 49)
"7.4 DEFINITION: "A function f: A --> B is surjective (or is said to map A onto B) if B = range f." The question of whether or not a function is surjective depends on the choice of codomain. the function can always be made surjetive by restricitng the codomain to being equal to the range, but sometimes this is not convenient." (p. 50-51).
Definitions for injective (or one-to-one) and "well-behaved" = bijective (i.e. both sur- and in-jective) follow. Also the "characteristic" i.e. "indicator" function is defined here and agrees with wikipedia).( all p. 51).
  • Minsky (1967): Always gentle and discoursive, Minsky gives these definitions:
"What is a function? Mathematicians ahve sever more or less equivalent ways of definiting this. Perhaps the most usual definition is something like this:
"A function is a rule whereby, given a number (called the argument), one is told how to compute another number (called the value of the function for that argument). ...
"Another way mathematicians may define a function is:
"A function is a set of ordered pairs <x,y> such that there are no two pairs with the same first number, but for each x, there is always one pair with that x as its first number. ... [he pokes fun at texts that leave the reader confused with distinctions ... so unimportant]
"So we will think of a function as an association between arguments and values -- as a set of ordered pairs <x,y> such that there is just one pair for each x. For each function there may be many definitions or rules that tell how to find the value y, given the argument x." (p. 132-134)
No mention of co-domain, domain, range. [ unicode symbols to be used below: ←⊆∉∈∸→⊂∀∃ℕ∩∪]
"When we talk about a partial-recursive function (or partial function, for short) F(x), it is understood that there may be no value defined for some (or even any!) values of x. If F(x) happens to be defined for all values of x, then we call it a total-reucrsive function or, for short, a total function." (p. 186)
  • Yuri I. Manin 1977, A Course in Mathematical Logic, ff. Has the best definitions I've seen. cf pages 11-12 for definitions leading to "function" and pages 177ff (in particular p. 178). I am using his definitions in the following section with the drawings.
  • Herbert Enderton 2001, A Mathematical Introduction to Logic, No mention of co-domain. "Universe" is discussed with respect to ∀. But I see no reason why this cannot include all members of a finite set, to wit:
"∀: "For every natural number." The symbol ∀ is the universal quantifier symbol. More generally, with each translation of the language into English there will be associated a certain set A (the so-called universe); ∀ will then become "for every member of the univers A." (p. 68)
Word-usages and definitions -- Cartesian product of A and itself n times is An or A and B is A x B, domain, range and field (union of domain and range) (cf p. 5) -- are pretty much the same as all of the other same excepting the use of subset as ⊆ and no use whatever of ⊂ (e.g. a list of symbols in the back does not include this symbol ⊂).
RE distinctions between graph, relation, function, operation:
"At one time it was popular to distinguish between the function and the relation (which was called the graph of the function). Current set-theoretic usage takes a function to be the same as its graph. But we still have the two ways of looking at the function." (p. 209).
"A relation R is a set of ordered pairs." (p. 4)
"An n-ary relation on An" is a subset of An. If n>1, it is a relation. But a 1-ary (unary) relation on A is simply subset of A." (p. 5)
"For an n-ary relation R on A and subset B of A, the restriction of R to be is the intersection R ∩ Bn. "(p. 5)
"A function is a relation F with the property of being single valued: For each x in dom F there is only one y such that <x,y> ∈ F. As usual [as is customary], this unique y is said to be the value F(x) that F assumes at X. (This usage goes back to Euler. ...) ...We say that F maps A into B and write
"F : A → B
"To mean that F is a function, dom F = A, and ran F ⊆ B. If in addition ran F = B, then F maps A onto B.
"An n-ary operation on A is a function mapping An into A. For example, addition is a binary operation on ℕ [his ℕ includes "0", i.e. the natural numbers plus 0, i.e. "the positive integers" cf p.2]. ... If f is an n-ary operation on A, then the restriction of f to a subset B of A is the function g with domain Bn which agrees with f at each point of Bn. Thus,
"g = f ∩ (Bn x A)
"This g will be an n-ary operation on B iff B is closed under f, in the sense that f(b1,...,bn)∈ B whenever each bi is in B. In this case, g = f ∩ (Bn+1, in agreement with our definition of the restriction of a relation." (p. 5"

[The following is CBM's answer to my query for more references, with my bold-face and paragraphing (the original is still there)]:

  • Rogers (1967, p. xvi) makes the same definition as Suppes 1960, but only for single-valued relations.
  • Soare (1987, p.2 ) doesn't define either function or domain but defines a partial function on ω as a function whose domain is a subset of ω. The usage is completely standard in computability theory - the domain of a partial function is the set of values for which the partial function is defined. — Carl (CBM · talk) 19:55, 10 September 2007 (UTC)

Comments on the above

Conclusion: all agree to use a word "domain" and all seem to agree on its usage: "domain" is a set of elements that describes only those elements that, when input to function f, produce an output into range Y. All agree that a function is "many-one." All except Tarski seem to agree to use the word "range"; "co-domain" is not used in any book that I have. Anton muddies the water with his "codomain" as used explicily in his book; the Lay definition is more precise except for what "first" and "second" means (he means "on the left" and "on the right" (predecessor and successor ? this was used by one of the above references!)). The derivation from "counter domain" and "converse domain" is obvious, its descent into usage obscure, perhaps archaic, and only connected with the logicians (how far back?) or "rediscovered". None of these "co-" formas are used in any other books that include in 2 modern computation theory books, an abstract algebra and a discrete math book, and my naive set theory, logic and calculus books. (I had never encountered the word until wikipedia). All agree that some set [this überset the "codomain"] the range may be "broader" (bigger, contain more unique elements than) the set of elements onto/into which the function maps (the "range"). That is, the "codomain" is some predeclared set (e.g. the continuum) in which a subset called "the range" exists, and every element of the range is associated with an element of domain X. Only metamathematicans seem to fret over "partial function". I dunno. Is something amiss here with respect to "domain" w.r.t. "a relation"? I'm not liking all these latinate words and extremely nuanced, finicky definitions which don't quite agree. We may be seeing instances of infrequent (graduate-level metamathematics) versus frequent (all other mathematics) usage. Suggestions as to other sources are welcome. wvbaileyWvbailey 22:03, 9 September 2007 (UTC), updated wvbaileyWvbailey 00:16, 10 September 2007 (UTC), updated wvbaileyWvbailey 01:36, 10 September 2007 (UTC). Updated with Enderton wvbaileyWvbailey 16:40, 15 September 2007 (UTC)

Bill here: Carl, I partly agree with the first part of your edit: what is drawn is not a function. What bothers is (i) the relation business (see Suppes Axiomatic set theory above for why I'm bothered), (ii) the partial function thing. I have been exploring the notion of "effectively computable" and that's what got me interested in this... wvbailey Wvbailey 22:10, 9 September 2007 (UTC)

Interesting. At least, we all agree about the fact that non-total relations are not functions (see previous section). Paolo.dL 23:30, 9 September 2007 (UTC)
Actually, the concept of a "domain" from category theory differs from all of these. and the "domain" of a relation R may not be . However, I don't quite agree that a "partial function" is not a function. In the definitions in my mother's book, Set Theory for the Mathematician, there is no such thing as a partial function. The term for what most people call "a function on X" is "a function with domain (containing) X". — Arthur Rubin | (talk) 04:46, 10 September 2007 (UTC)
Please be careful; this article is about "function" as used in many areas of mathematics, but not so much computer science. It is really easy to look at the parts of mathematics one is familiar with and not realize the differences found elsewhere.
  • In algebraic geometry, many of the "functions" considered are ratios of polynomials. What happens when the denominator takes the value zero? If pressed hard, practitioners might acquiesce to "partial function", but would grumble loudly because it would be decidedly inconvenient and confer little benefit.
  • In functional analysis, the Dirac delta function is more properly called a distribution rather than a function. However the name is standard in this field (and its neighbors) without causing great confusion.
  • In most areas of mathematics it is essential to distinguish between the codomain and the image (or "range") of the function. It is at the heart of cardinality, and it is required if not all functions are to be surjective (onto).
  • A relation can make multiple associations from both sets; it's really much the same as a bipartite graph.
  • We can only give explicit rules for countably many functions; it's a wonder rules are so useful!
  • In studying the semantics of programming languages, the meaning of "function" becomes a world in itself. It would be a disaster to include those ideas here; yet that study is both interesting and highly mathematical.
The Springer online Encyclopaedia of Mathematics article is a helpful survey, including some enlightening history. Today the language and organizing gestalt of category theory pervade mathematics; the prefix "co" is found there, but also in "covariant" versus "contravariant" as found in tensor theory. --KSmrqT 05:47, 10 September 2007 (UTC)
Arthur, I was just referring to this sentence (from this section of Partial function):
  • "Many other mathematicians, including recursion theorists, prefer to reserve the term "domain of f" for the set of all values x such that f(x) is defined. In this terminology, a partial function on a set S is simply a function whose domain is a subset of S." [I higlighted in bold the preposition "on"]
I cannot guarantee that this sentence is correct, but the specific reference to recursion theorists at least provides a method to substantiate it. Paolo.dL 13:57, 10 September 2007 (UTC)

After finally finding 2 references and mulling the concept, I agree that "codomain" should stay [see KSmrq's comment] and in fact it should be expanded a bit. (Please correct me if I've got the following wrong ...) The definition of "range" should make it clear that every element in the range is "used" by the function (associated to an element of the domain); thus the range is a subset (proper, improper) of the codomain (archaic usage: converse domain, counter domain). The article thus needs a drawing that shows a subset (the range) inside Y (the codomain); every element inside the range-set has an arrow pointing at it (I don't know how to copy/modify the drawings here. But I could create a new one, if need be.)wvbaileyWvbailey 14:40, 10 September 2007 (UTC)

Universe, Universe of discourse, unrestricted domain of discourse

The symbol "Ø" stands for "empty"; [X]=Ø stands for "the place named "X" is empty of content." When restricted to a proper subset of the unrestricted universe of discourse = {Ø, 1, 2, 3, 4, 5} the function has the domain of definition {2, 3, 4} and is "effective at" (i.e. does a good job of) putting an output y ="o" or y="e" into the subset range={o,e}. This "effective" range is a place1 inside the place2 inside the place called "the codomain Y". The "computable range" {{o,e},u} (place2) includes an output y="u" produced when the input(s) is(are) not in the defined domain D(f). Thus, because "u" is not an element of the "effective" range, D(f) is a proper subset of X: f(D) ⊂ X. If the function fails to HALT (for whatever reason) it apparently fails to put anything into the "computable range". But at the start, the counter-machine model "clears out" this place Y; a mathematician would start with a blank sheet of paper, or erase an area to work in. In this sense (due to the clearing, erasing, emptying) the function has put "nothingness" into the codomain Y, i.e. Ø → [Y]. Thus, because Ø is not an element of the "computable range", the "computable range" is a "proper subset" of the "semi-computable range". The drawing shows that this happens when the function is given no input i.e. [X]=Ø or if it is given the input "5". This example also works when symbol "5" represents any of the positive integers. wvbaileyWvbailey 19:25, 12 September 2007 (UTC)
Given the universe of discourse X = {Ø, 1, 2, 3, 4, 5} and the codomain Y = {Ø, e, o, u} we create a "direct product" of the two sets X x Y and end up with a set of 24 ordered pairs of the form <xi,yi> where x and y are any elements in their respective sets. X x Y = { <Ø,Ø>,<Ø,e>,<Ø,o>,<Ø,u>,<1,Ø>, ... <5,u> }. These can be "plotted" to form a set of dots in an X-Y plane. The partial function, shown in bold-face, are just those elements defined by the function over the entire universe of discourse i.e. f(Ø, 1, 2, 3, 4, 5) = {<Ø,Ø>, <1,u>, <2,e>, <3,o>, <4,e>, <5,Ø>}. The total function would be the following: f(2, 3, 4) = {<2,e>, <3,o>, <4,e>}. The "computable function" f(1, 2, 3, 4) = {<1,u>,<2,e>, <3,o>, <4,e>}. Thus the total function is a (proper) subset of both the "computable" and "semi-computable" functions. The "computable function" is a (proper) subset of the "semi-computable" function. The mu-operator is to be blamed for this (Manin 1977:182). wvbaileyWvbailey 15:09, 12 September 2007 (UTC)(UTC)

Is there a formal (legit) name for this "unrestricted universe of discourse"? [I've striken out "unrestricted" because it turns out to be redundant. This comment added by wvbaileyWvbailey 17:19, 15 September 2007 (UTC) ]. B-B-J indeed uses "domain or universe of discourse" (p. 103). Manin refers to "the von Neumann universe". So the only problem is the use of "unrestricted.: One book refers to "intervals" i.e. on the number line, which this is sort of demonstrating (i.e. the function is restricted to the closed interval 3 to 6 on the integer number line. Maybe this usage is correct only for the reals?)

I hesitate to present the following example because it is (clearly) from computation theory. But it points out the definitions with regards to the "domain" and "partial function" etc. Even Kleene 1952 had to invent some phrases [more on this to follow...]

The definitions of Manin really help here. But these have been translated from Russian, so we need to be careful:

←⊆∉∈∸→⊂

The purpose of a brief survey of "set theory" would be to get to (i.e. develop, lead to) the notion of "graph" of a function, point out how a relation can be one-many, many-one, many-many etc. But a function is many-one.

A set is the notion of elements that belong to the set : "A set is a collection of things -- the set's members or elements". "The two primitive constants of the language are the membership relation symbol '∈' ["belonging" Halmos 1960:2] and "the constant 0", which denots the empty set" (quote from Suppes 1972:14).

"If x belongs to A (x is an element of A, x is contained in A), we shall write:
" x ∈ A " (Halmos 1960:2, Suppes 1972:14)
"Set theory is concerned with a domain ℬ of individuals, which we shall call simply objects and among which are the sets [thus, sets are objects in the domain]. If two individuals, a and b, denote the same object, we write a = b, otherwise a ≠ b. We say of an object that it "exists" if it belongs to the domain ℬ." (Zermelo 1908a:201)

"One thing that the development will not include is a definition of sets" (Halmos 1960:1).

{ }: Null or empty set Ø: Is a major source of confusion. Zermelo called "0" "a (fictitious) set ... that contains no element at all"(Zermelo 1908a:202). Also used by Frankel 1922, Skolem 1922 to indicate the empty set { }. But this usage is risky because, for example, "0" is a valid symbol -- distingushable ink-marks on a page -- in the place adjacent to this word 0 , whereas the empty set { } means that, truly, the place between the brackets has no ink in it, no symbol-content whatever. (cf Hilbert 1904, also Turing 1936-7; Hilbert started with | and adjoined it to || etc; Turing discusses the notion of "symbols on paper"). "O" used by von Neumann 1925. Nowadays "Ø" seems to be the preferred symbol (Halmos 1960, Suppes 1972, Enderton 2001, B-B-J 2002) . Another example: In 7-bit + parity ASCII teletype code the NULL is 0008, i.e. NULL represents no activity on "the line" ("the line" is a place in space, and "a symbol" is a certain type of activity "on the line), whereas the octal 0608 = 4810 = 0,110,0002 represents the symbol numeral "0".

Subset: A ⊆ B: "If A and B are sets and if every element of A is an element of B, we say that A is a subset of B, or B includes A and we write:

A ⊂ B (Halmos 1960:3). NOTE: This is ambiguous usage: In some books this means that A is a proper [smaller] subset than B, i.e. some elements not in A can be found in B. This usage is not ambiguous:
A ⊆ B =definition A ⊂ B [A is a proper subset of B] OR A = B [A and B have the same elements] OR BOTH SIMULTANEOUSLY
A ⊂ B (Halmos 1960:3, Manin 1977 ? ) A ⊆ B (Enderton 2001:2, Suppes 1972:22)
A ⊂ B =definition "proper subset" (Suppes 1972:22)

However: note that " A ∉ A ". A set cannot be an element of itself. That is: subsethood (a set is determined by its elements) is not the same as "element-hood". Thus: NOT TRUE: "set A = { x, y, z, A } because if this were true, A= { x, y, z, {x, y, z, {x, y, z, { ad infinitum }}}}. (cf theorem 105 in Suppes 1972:

A universe, "domain" or "universe of discourse"': "A restricted class [collection] of sets (a universe)"(Manin 1977:95). "...a nonempty set |M| called the domain [of "an interpretation or model" cf index B-B-J 2002:351] or universe of discourse (cf index ibid:355) of the interpretation, [is] the set of things M interprets the language to be talking about."(B-B-J 2002:103). "... a certain set A (the so-called universe); ∀ will then become "for every member of the universe A." (Enderton 2001:68)

Ordered pair < u, v > : { {u}, {u,v} where {u} is the left or first element and {u,v} is the right or second element (see below. (Suppes 1972:33 etc). This usage goes back to Zermelo 1908a; the notion derives from Peano-Dedekind and the induction axiom (or the successor function).

Cartesian product u x v: Manin defines "u x v" as the "direct product of sets u and v" (p. 11). This notion is called the "Cartesian product" by Halmos 1960:24 and by Suppes 1972:49. A Cartesian product between two sets u x v is the uber-set of all the possible ordered pairs { <ui, vi> } that we can create out of sets u and v. Intuitively, if u contains "6" members and "v contains 4 members then the total number of members is the arithmetic product 24 = 6*4.

Given u = { Ø, 1, 2, 3, 4, 5 } and v = { Ø, o, e, u }
u x v = { < Ø,u >, < 1,u >, < 2,u >, < 3,u >, < 4,u >, < 5,u >, < Ø,e >, < 1,e >, < 2,e >, < 3,e >, < 4,e >, < 5,e >, < Ø,o >, < 1,o >, < 2,o >, < 3,o >, < 4,o >, < 5,o >, < Ø,Ø >, < 1,Ø >, < 2,Ø >, < 3,Ø >, < 4,Ø >, < 5,Ø > }

First and second coordinates: The so-called first element (Manin p. 11) or first term (Manin p. 101) is drawn from set u: ui and the second element (Manin p. 12) or second term (Manin p. 101) is drawn from set v: vi. Halmos calls the "first element" the first coordinate (p. 23) and the "second element" the second cooordinate (p. 23). Suppes does not use any of these notions. von Neumann actually wrote the two coordinates backward {{u,v}, {u}} from the customary usage. "the ordered pair < x,y > of objects x and y must be defined in such a way that < x,y > = < u,v > iff x=u and y = v. Any definition that has this property will do..."(Enderton 2002:3)

Projection: Conversely, If we are given a set (of ordered pairs) named R = { <ui, vi> }, then a uber-set u x v exists (Halmos 1960:24). The set A is "the projection of R onto the first coordinate" and the set B is the projection of R onto the second coordinate. (Halmos p. 23).

Relation: A description of, or mechanism for, how to form a set. Given that a set of ordered pairs R represents a "relation":

"...every relation should uniquely determine the set of all those ordered pairs for which the first coordinate does stand in that relation to the second." (Halmos 1960:26)

Domain and range with respect to a relation: These words are used with relations and functions, but range has slightly different meaning

"...we saw that associated with every set R of ordered pairs there are two sets called the projections of R onto the first and second coordinates. In the theory of relations these sets are known as the domain and the range of R." (Halmos 1960:27)
"If r∈V is a relation, then its domain of definition dom(r) is the class of all first terms in the elements of r, and the range of values rng(r) is the class of all second terms."(Manin 1977:

Function: Requires that "the function" uses every element of the domain, but not necessarily every element of the range.

"If X and Y are sets, a function from (or on) X to (or into) Y is a relation f such that dom f = X and such that for each x in X there is a unique element y in Y." (Halmos 1960:30)

Manin defines a function:

"3.8. "f is a mapping from the set u to the set v."
""...mappings, or functions, are identified with their graphs; otherwise, we would not be able to consider them as elements of the universe. The following formula successively imposes three conditions on f: [1] f is a subset of u x v; [2] the projection of f onto u coincides with all of u; and, [3] each element of u corresponds to exactly one element of v: [a huge formula follows here]" (numbering added, Manin 1977:12)
"A function is a binary relation in which each elment is uniquely determined by its first term." (Manin 1977:101)

Value and argument: Given a function f, in any of its ordered pairs <xi, yi> the second coordinate/element yi is the value; first coordinate/element xi is the argument.

←⊆∉∈∸→⊂∀∃ℕ⇔

Graph: ...function is reserved for the undefined object that is somehow active, and the set of ordered pairs that we have called the function is then called the graph of the function. (Halmos 1960:30). "Recall that any function f:ℕk → ℕ is also a (k+1)-ary relation on ℕ: <ai,...,ak,b> ∈ f ⇔ f(a1,...,ak) = b. At one time it was popular to distinguish between the function and the relation (which was called the graph of the function). Current set theoretic usage takes a function to be the same thing as its graph. But we still have the two ways of looking at the function." (Enderton 2001:209).

Range of a function: Unlike the range of a relation Y, the range of a function A can be a subset of X, i.e. A ⊆ X. (Halmos 1960:31). (At variance with Enderton 2001 ?).

Image: If A is a subset of domain X, i.e. A ⊆ X, the subset of elements of y (in range Y) such that f(x)=y is called the image of A under f. "This subset of Y is called the image of A under f and is frequently denoted by f(A). The notation is bad but not catastrophic." (Halmos 1960:31)

Operation: cf Enderton 2001:5

Restriction of a relation to a subset B of the domain A: cf Enderton 2001:5

Restriction of a function or operation to a subset B of the domain A: cf Enderton 2001:5

Operation closed under function f: cf Enderton 2001:5

Example of a "function" defined by a set of ordered pairs

So, using these definitions we can describe our set of u x v in the above. We can plot the (totality of, universe of) ordered pairs in the conventional manner, i.e. label the X axis with the elements from the universe of discourse (need not be ordered) and label the Y axis with the elements of the co-domain (need not be ordered). Then we locate the universe of ordered pairs in a grid-like pattern. We now have the totality of all the ordered pairs that we could potentially include in our function.

The function we "graph" (create) by selecting only one ordered pair (aka "point") from every column and then include it in a set called "the function"; this forms the partial function. To form a total function from within this partial function we select one ordered pair from each of a restricted set of columns.

To have a function at all, the X-projection must produce only one ordered pair in each column and "project" its x-value on the X-axis. Whenever the function is undefined for a particular input x, the Ø appears at the output (i.e. causes the function to be semi-computable).

The "graph" of the function is shown in the drawing. The projections of the function onto the X-axis (universe of discourse) and the Y-axis (co-domain) allow us to collect, on the X-projection, the "domain of definition" for the total function and the "universe of discourse" for the partial function, and on the Y-projection, the semi-computable range, the computable range and the "effective" range.

The total function, as defined over the restricted domain { 2, 3, 4 } is a proper subset of the partial function as defined over the unrestricted universe of discourse {Ø, 1, 2, 3, 4, 5}

∈∉⊂⊆→

Manin's definition of "partial function":

"Let X and Y be two sets. A partial function (or mapping) from X to Y is any pair <D(f),f> consisting of a subset D(f)⊂X and a mapping f:D(f)→Y. Here D(f) (instead of the early dom f) is called the domain of definition of f: f is defined at a point x∈X if x∈D(f); f is nowhere defined if D(f) is empty, and there exists a unique nowhere defined partial function.
"We let " Z+ = {1, 2, 3, ... } denote the set of natural numbers, excluding zero. (It is not necessary, only convenient, to exlcude 0)."(p.178)

Manin goes on to make three distinctions:

"(a) A partial function f from (Z+)m to (Z+)m is called computable if there exists a "program" [algorithm] which, whenever [an] x is entered in the input, gives as output:
" f(x), if x ∈ D(f)
" 0, if x ∉ D(f)
"Here 0 merely indicates that f is not defined at x; we could allow the output in this case to be anythong not in Z+.
"(b) A partial function f from (Z+)m to (Z+)m is called semi-computable if there exists a "program" which, whenever [an] x ∈ (Z+)m is entered in the input, gives f(x) as output if x ∈ D(f), and either gives 0 as output or else works infinitely long without stopping if x ∉ D(f).
"In particular, computable functions are semi-computable, and everywhere define semi-computable functions are comptuable.
(c) A partial function f is callled noncomputable if it does not satisfy condition (b) (and a fortiori (a)). (p. 178)

Thus we have, given the u x v that f is defined on :

semicomputable f: { <Ø,Ø>, <5,Ø>, <4,e>, <2,e>, <3,o>, <1,u> }
computable f: { <4,e>, <2,e>, <3,o>, <1,u> }

And we see from our drawing that "computable f" ⊂ "semicomputable f".

Example of the "function" defined by a machine (aka "algorithm" or "computational process")

Shown below is "the function" shown in the drawing: a counter machine described as follows:

The machine has three counters "X" (this counter has an input ability), "Y" and "C" (the mu-operator's counter).

The machine works "in unary" on "tally marks" in the counters. Its input and output are as follows:

INPUT:
  • Ø indicates the counter is empty, has no tally marks.
  • 0 is not used as input (! important !) and can be thought of as [Ø]rj i.e. an empty register. (Manin takes a similar tack p. 178ff; this allows his algorithms to create partial- but computable- functions (as opposed to "semi-computable"). If we wanted to use "0" as a symbol but retain the notion of "null" (empty, Ø) we would start with "0" = |, "1" = ||, "2" = ||| ...; this usage is not that unusual when working with abstract machines. These definitions (specifications) must happen at the outset: (i) Where/how the machine will find its "input", (ii) Where we will find its output, and (iii) How to represent the "numerals" at both "the input" and "the output" -- our "domain of discourse", our "universe" -- for both us and the machine.
INPUT to appear in place X:
  • Ø is
  • 1 is |
  • 2 is ||
  • 3 is |||
  • 4 is ||||, or 4 is any ||||...| in the case of an infinite "unrestricted universe of discourse"
OUTPUT to appear in place Y:
  • Ø is
  • u is |
  • e is ||
  • o is |||
The symbolization [X] means "there is a place (a "counter") named "X" the contents of which is a heap or jumble of "counters", e.g. identical rocks, marks, abacus beads, blank playing cards, electrical wires with +5 volt signals on them (as opposed to 0 volts), etc. If used, "x" will represent this contents in the "variable" sense. For example if the counters are tally marks then "[X] = x = |||" means that "at this particular time, the contents x of place X is the amount that happens to be tally marks |||". At all times place X must contain either a numeral (a heap of counters) or be empty (represented by Ø). Thus "[X] = Ø" is a legitimate symbolization, as is "Ø → X".

Except for "INPUT" the instruction set is nothing unusual and renders the machine (with its three registers) Turing complete:

  • JE rj,rk,zzz stands for "Jump to instruction zzz if contents of counter rj Equals the contents of contents rk else go to next instruction in sequence,
  • J zzz is "Jump unconditionally to instruction zzz" (not technically necessary: JE rj,rj,zzz will do the trick (i.e. rj=rk)
  • INC rj is "increment contents of (i.e. the successor function) and go to next instruction in sequence",
  • CLR rj is "CLeaR to Ø, i.e. empty the contents of" counter rj and go to the next isntruction in sequence..
  • HALT
  • INPUT rj means that, by some clever means, a count or (empty) gets "jammed" or "loaded" into rj "all at once" from some other place called e.g. "keyboard" or "pencil and paper". or if one is fussed by this, then skip this INPUT business and assume [X] is some count "x" that is any amount of tally marks or none at all i.e. Ø.

"The user" selects a symbol (aka "number" of tally marks or none at all i.e. Ø) from the "universe of discourse" and presents it to the machine's "INPUT-region". The machine "inputs" the symbol from the "INPUT-region" into counter X. If there is no symbol e.g. [X]=Ø then the machine "waits" (loops ad infinitum) for some marks to test. If and when [X] ≠ Ø, the machine "parses" the symbol by use of its counter C. The "parse" is a CASE statement that "returns", to the machine's internal Instruction Counter (IC: part of its state machine), the jump-to address of "start"=0, "u"=13, "o"=14, "e"=15.

  • Start:
  • 0 CLR C ;Ø => C, C acts as a counter
  • 1 CLR Y ;Ø => Y, where the output y is to appear
  • 2 INPUT X ;an element from the "unrestricted universe of discourse" X => X
CASE: ;the following is a CASE instruction that "parses" the contents of X and "returns" a jump-to address to the "Instruction Counter" embedded in the counter-machine's internal state machine i.e. {0, 13, 14, 15}=>IC
  • 3 JE C,X,start ;If [C]=[X]=Ø then cycle back to start
  • 4 INC C  ; [C]=Ø => |="1"=|
  • 5 JE C,X,u ;IF [C]=[X]="1"=| then go to undefined_u
  • 6 INC C  ; [C]=| => ||="2"=||
  • 7 JE C,X,e ;IF [C]=[X]="2"=|| then go to even_e
  • 8 INC C  ; [C]=|| => |||="3"
  • 9 JE C,X,o ;IF [C]=[X]="3"=||| then go to odd_o
  • 10 INC C  ; [C]=||| => ||||="4"
  • 11 JE C,X,e ;IF [C]=[X]="4"=|||| then go to even_e
  • 12 J start ;loop to "jump-to-address = "0"
  • 13 o: INC Y ; [Y] = |
  • 14 e: INC Y ; [Y] = || if odd, | if even
  • 15 u: INC Y ; [Y] = ||| if odd, || if even, | if undefined
  • HALT

So what is shown here are the (some of the ways) our (badly-designed) function behaves as if it is partial:

  • on [X] = { Ø, >4 } it loops forever or until "not Ø" (cf Kleene 1952:325),
  • on [X] = { 1 }, it halts with one tally mark |="u", i.e. x was not in the defined domain (cf Kleene 1952:324)
  • on [X] = {{2, 4}, {3}=o} the function "maps" {2, 4} to "e" and {3} to "o", and {o,e} define the the "effective range"

Kleene 1952 goes on to define partial function to include function. He says that when the function produces a natural number as a value it is defined; when it produces no natural number it is undefined "sometimes written u" (Kleene). He defines:

"The range [sic ! ] of definition is the set of the n-tuples x1, ...,xn for which φ(x1, ...,xn) is defined" (Kleene 1952:325-6).

In their §7.2 Semicrusive Relations, B-B-J introduce the notion of "(positvely) effectively semidecidable if there is an effective procedure that, applied to any number, will if the number is in the set in a finite amount of time give the answer "yes", but will if the number is not in the set never give an answer. For instance, the domain of an effectively computable partial frunction f is always effectively semidecidable..."(p. 80)

But Mangin does allow for a finite domain for a partial function (and this solves one mystery -- infinite domains are not required for partial functions):

"4.19 Corollary
"(a) Finite sets and their complements in (Z+)n are decidable.
"(b) Every partial funtion from (Z+)m to (Z+)n with a finite domain of definition is recursive and computable.(p. 200)

More work is necessary to firm up the notion of "partial function". What was here has been completely redone. wvbaileyWvbailey 20:47, 11 September 2007 (UTC)

B-B-J 2002 make it very clear that a partial function has a restricted domain D that is selected from "the whole set P of postive integers" (i.e. D is a subset of P "the positive integers") (p. 7). With regards to this can anyone else produce a quotation from a source? Only the two sources quoted above B-B-J (2002) and Kleene (1952) discuss "partial functions". wvbaileyWvbailey 19:37, 10 September 2007 (UTC) updated wvbaileyWvbailey 22:17, 15 September 2007 (UTC)

[The following is CBM's answer to the question above]:

Rogers (1967, p. xvi) makes the same definition as Suppes 1960, but only for single-valued relations. Soare (1987, p.2 ) doesn't define either function or domain but defines a partial function on ω as a function whose domain is a subset of ω. The usage is completely standard in computability theory - the domain of a partial function is the set of values for which the partial function is defined. — Carl (CBM · talk) 19:55, 10 September 2007 (UTC)
Wvbailey, you've done a huge amount of work here, and you can't get better references than Manin and Halmos, but I wonder where this fits in a general encyclopedia. An encyclopedia is not intended to replace textbooks, but rather to provide an introduction for the general reader, together with a guide to the important books on the subject. This is just a guess, but I would imagine most of the people reading this article looking for information are going to have little or no mathematical background. Understanding functions is a prerequisite for understanding calculus and liner algebra, which are the gateways to higher mathematics. A little bit of set theory is fine, but Halmos and Manin are writing for mathematicians, and the best course, or so it seems to me, is just to reference their books. Rick Norwood 13:15, 16 September 2007 (UTC)
You are entirely correct, that as it stands now this is (much) too complicated. At this point I'm just feeling my way through the morass, in particular the vocabulary. I don't intend to insert any of this into the article, as it stands now. In the following I'm thinking out loud:
The first thing I'm trying to do is get the vocabulary defined. I'm aware of wiki's "symbol library" for mathematics. But I want to see for myself. Next, I will "feel out" whether or not if any of this can go into this and other articles, and if so, how. What I may do, as I've done for other articles, is write one or more "extension articles" that delve deeper into the ambiguities and/or offers extended examples (such as the counter machine ... I'm working on a better example than the above).
One article that this will have an impact on is partial function.
Something (relevant to this article) that I have uncovered is the incorrecteness and/or incompleteness of the little drawings as they stand now. For example, a function is (i.e. represented by) the arrows between the domain and range. There can be many "arrow sets" from one domain into one range: a particular "arrow set" represents the function under discussion.
Next, try to tie together the customary algebra-notion of function with the set-theoretic notion as a set of ordered pairs. First, label each arrow with its ordered pair i.e. just the x,y coordinates of middle-school pre-algebra (as I've shown in the drawing above). Second, introduce the next notion -- of Cartesian product X x Y as just all the points on the x-y plane. This leads directly to the notion of plotting the function's "graph". (And the set-theoretic notions of "projections" and "first coordinate" "x" and "second coordinate" "y" just fall out, virtually without comment). Thus all this ties together -- little set-theory drawings of domains and ranges, little x,y plots of functions, as pointed out by Enderton: "...we still have the two ways of looking at the function" (p. 209).
The next point to clarify is that a "function" is just a restricted type "relation" i.e. restricted so that it must produce only one output y for every x in its "domain of defintion/discourse" (that the notion of "relation" is broader than "function" was pointed out to me by CBM) [But why? the student asks, "I thought when we solve square-roots that we get two values. Stick 9 into the function SQRT and out pops +3 and -3!" Good question.] This leads to an interesting point about computers [and computation in general] -- that computers (including us humans) really only work on the "positive" integers, that to indicate a negative number "tricks are used": the computer might always put a lead 0 in front of a positive number and always put a 1 in front of a negative number (and it may "invert" the rest of the negative number, or maybe invert and add 1... tricks are indeed used). As far as a computer is concerned there's no such thing as a negative number: when confronted with SQRT the computer calculates two functions, one after the other. The first function computes the (positive) square root and prints it with a lead "plus" sign, the second function tacks a "minus" symbol on the front of the first number that we-the-onlookers interpret as the "negative sign". If it has to use this "negative number" the computer itself has to pay attention to the extra symbol and modify its (the computer's) behavior accordingly. This same strategy also applies when the computer encounters SQRT of a negative number leading to an "imaginary number" -- more tricks are required if the computer is to do this.
Even a kid in upper grade-school can get the drift of the next point: what happens when you build a little divider-machine -- say, one that divides "12" by a whole, positive number that you give it. The number has to be chosen from this collection (the restricted domain) {12, 6, 4, 3, 2, 1, 0}. Just what does happen? The kid can get some idea from this: divide 12/12=1, 12/6=2, 12/4=3, 12/3=4, 12/2=6, 12/1=12. Graph the results <12,1>, <6,2>, <3,4>, <2,6>, <2,12>. Note that as you shrink your "x" the "y" gets biggger, fast [the x-y graph goes here]. What might the little machine do when it gets "0" plugged into its "input"? The next point is a bit more subtle. Suppose you open your domain X to include all the numbers {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0} but the range Y is restricted to the (integer, whole) numbers? What happens when your machine is confronted with 12/5? It will produce something, but do we want it to? All this leads to a discussion of "total function" and "partial function", "computable" and "semicomputable". At this point the reader would link to those discussions.
The part I haven't tackled yet is the problem of "continuous function" versus "discrete" or "number-theoretic" function. Anyway, that's what I'm up to. wvbaileyWvbailey 15:25, 16 September 2007 (UTC)

Inverse function

Subsection extracted from "The vocabulary of functions" (end of section)

Informally, the inverse of a function f is one that "undoes" the effect of f, by taking each function value f(x) to its argument x. The squaring function is the inverse of the non-negative square root function. Formally, since every function f is a relation, its inverse f−1 is just the inverse relation. That is, if f has domain X, codomain Y, and graph G, the inverse has domain Y, codomain X, and graph

For example, if the graph of f is G = {(1,5), (2,4), (3,5)}, then the graph of f−1 is G−1 = {(5,1), (4,2), (5,3)}.

The relation f−1 is a function if and only if for each y in the codomain there is exactly one argument x such that f(x) = y; in other words, the inverse of a function f is a function if and only if f is a bijection. In that case, f−1(f(x)) = x for every x in X, and f(f−1(y)) = y for any y in Y. Sometimes a function can be modified, often by replacing the domain with a subset of the domain, and making corresponding changes in the codomain and graph, so that the modified function has an inverse that is a function.

For example, the inverse of y = sin(x), f(x) = arcsin (x), defined by y = arcsin (x) if and only if x = sin(y), is not a function, because its graph contains both the ordered pair (0, 0) and the ordered pair (0, 2π). But if we change the domain of y = sin(x) to −π/2 ≤ x ≤ π/2 and change the codomain to −1 ≤ y ≤ 1, then the resulting function does have an inverse, denoted with a capital letter A, f(x) = Arcsin (x).

This does not work with every function, however, and inverses are sometimes difficult or impossible to find.

Comments

I moved the above subsection away from the article, because it defines incorrectly the expression "inverse function" (see inverse function). An inverse function not only reverses, but must be reversible by f! The definition given is only valid for a "left inverse", which however does not need to be a bijection... I will not be able to fix this paragraph soon. Paolo.dL 20:59, 13 September 2007 (UTC)

The structure of this paragraph is consistent with the rest of the article. First, for the non-mathematician, give a rough idea what an inverse function does, without going into details. Almost at once, the paragraph explains for the more technically inclined which functions have an inverse (one-to-on onto functions) and what a partial inverse is. The technical language "left inverse", "right inverse" is more appropriate for the main article that for the introductory article. Rick Norwood 12:41, 14 September 2007 (UTC)

Rick, you restored the section, and inserted this sentence:

"It is important to note, however, that the inverse of a function may not be a function. If a function sends two different inputs to the same output, then its inverse associates two different outputs with the same input, violating one of the rules for a relation to be a function." [...and for a function to be an inverse!]

You missed my point. Please see my latest edits and the article inverse function. If you read them carefully you will understand that the sentence you inserted was nonsense, as well as most of the text you restored. You described a non-injective function, and a non-injective function is non-invertible. Moreover, it is even irreversible: it fails to meet even the incomplete "informal" defintion given above. To be invertible, a function must be both injective and surjective. The old text confused "reversible" with "invertible". Please see also the sections on reversibility in the articles surjection (i.e a function that can undo another function) and injection (i.e. a function that can be undone). Paolo.dL 21:00, 14 September 2007 (UTC)

I was forced to rewrite everything from scratch. Paolo.dL 22:56, 14 September 2007 (UTC)

The usage you object to is standard. The usage you replace it with is not. Instead of rewriting from scratch, you need to cite a reference. I do not have any idea what you mean by the phrase in bold above. Every function is the inverse of its inverse.
I think you are using the definition that g is the inverse of f iff f(g(y)) = y for all y in the domain of g and g(f(x)) = x for all x in the domain of f. This is a perfectly good definition in certain contexts, but it is not the only definition. Another perfectly good definition is that a function is a relation R with the property that (a,b),(a,c) elements of R implies b = c. Relations F and G are inverses when (x,y) is in F iff (y,x) is in G. It is not a case of one of these definitions being right and the other wrong, it is a case of one definition being used in certain contexts and the other in other contexts.
The advantage I see in the second definition is that it helps to explain the difference between arcsine, a relation, and Arcsine, a partial function.
I used the word "undoes" in an informal sense, and said so. None of the books I am familiar with use the word "reversible" in the sense that you use it but, of course, there are more books that I haven't read than there are books I have read. Please let me know what your source is.
I avoided the word "invertible" for several reasons, chief among which was the common use of "invert" to mean "take the reciprocal of".
Certainly, what you have written now is better than a blank section, but I have some problems with it. In particular, you wrote:
A function that has an inverse is called invertible. A function that can be undone by another function is "reversible" but not necessarily invertible.
 + An equivalent definition: 
 + * A surjection can always undo (reverse) another function.  
 + * An injection is always reversible by another function. 
 + * To be invertible, a function must be both injective and surjective, that is a bijection. 
This is the usage that I am requesting a reference for.
I would like to work with you on this rather than get into a revert war. On an invert war as the case may be.
Rick Norwood 20:48, 15 September 2007 (UTC)

Thanks for the explanations. I didn't know about the two different definitions. In Wikipedia, you could find only one definition (the one I gave). Everything I wrote was perfectly consistent with what was written (and explained in more detail) in the article about inverse functions. Today, someone rewrote completely the article about inverse functions, (and made it much less readable, in my opinion) but the definition is still equivalent to what I gave...

Reversed (=undone), and reversible are just plain emglish words, as far as I know. Reversible is just a short word to mean "that can be reversed". Hence, it is useful if you adopt a definition of "invertible" which is not equivalent to "reversible. Of course, "invertible" functions means a function that has an inverse.

By the way. how can you write "I think you are using the definition..."? The definition I am using was absolutely clear in the new section I wrote. You don't need to guess. According to that definition, the function in your example is clearly not an inverse. Hence, the statement in bold should be also easy to understand.

I do not have a reference for the equivalent definition. It was given in the article inverse function and it was explained there. We discussed this in the relevant talk page. Paolo.dL 20:43, 16 September 2007 (UTC)

More on inverse functions

I'm starting a new subhead, since the old section was getting rather long to add to easily.

In Wikipedia, a reference is to a source outside of Wikipedia. Also, it is not a good idea to introduce original vocabulary (reversable/invertable). Wikipedia should use the same vocabulary as standard sources. In this case, examples of standard sources would include Munkres Topology, which uses your definition, and the more elementary Morash Bridge to Abstract Mathematics, which uses my definition. It is important to realize that both definitions are widely used, and which definition is being used in a particular case must be either specified or else clear from the context.

I'm going to attempt a rewrite of the section in question that makes all this clear, and then I'll take a look at what is going on in inverse function. Rick Norwood 13:19, 17 September 2007 (UTC)

Notice that reversible is not a new word. It is just plain english. In an introduction or short summary, plain english is needed. We should always remember that the reader may just ignore "the previous chapters" of the book. An encyclopedia is not a book.
Of course primary or secondary sources are needed. But also, there's a need of consistency between what is written in the main article and what is written in this summary section. I suggest you to work on the main article first.
Paolo.dL 17:41, 17 September 2007 (UTC)

And so I did -- work on the main article first, that is. But now the main article mentions both ways of handling function inverses, with references, and the article inverse function, as you say, needs to reflect the main article, and vice versa. Tomorrow I'll try to work on the other article, for the sake of consistency. Rick Norwood 23:21, 18 September 2007 (UTC)

The main article about inverse functions is inverse function. See also the very first row of the section you just edited. It says "Main article: Inverse function". I am glad that you agree about consistency. I have quickly read your new version. I now understand that you are talking about an inverse relation! You are not maintaining that this can be considered an inverse function, are you? In sum, a particular kind of inverse relations exists which, weirdly,
  1. is the inverse of a function, but
  2. is not an inverse function.
If my interpretation of your own words is correct, there's only one valid definition of "inverse function". However, on 17 September 2007 you wrote that two definitions exist, valid in different contexts: "my definition", and "your definition". Please clarify. Are you maintaining that two different definitions of "inverse relation" are currently used in different context? Notice that I never gave a definition of "inverse relation". I only gave a definition of "inverse function". Paolo.dL 13:30, 19 September 2007 (UTC)
By the way, I am not sure that the existence of this weird kind of inverse relations is so important to deserve a special mention in a short summary about inverse functions within an article about functions. But this is not my main point. I don't mind if you decide to keep the mention in this summary. Paolo.dL 13:34, 19 September 2007 (UTC)

You are quite right. The inverse of a function that is not a bijection is an inverse of a function but is not an inverse function. The main reason it is important is that almost all elementary mathematics courses, and almost all calculators, cover this kind of inverse of a function. The examples in the article, y = arcsin(x) (not a function) and y = Arcsin(x) (a function, but only an inverse of the sine function if we restrict the domain and range) are usually the first examples a student encounters of the inverse of a function failing to be a function. (Students in the US today are taught the "vertical line test" for whether a graph is or is not the graph of a function.) Whether or not they have seen the definition of a function as a set of ordered pairs, at this point in their education, probably varies widely from student to student. Rick Norwood 19:16, 20 September 2007 (UTC)

Thanks. Now your point is much clearer. But I can't see why you are talking about "different contexts". Since you are not talking about a different kind of "inverse function", incompatible with the two-sided definition given above, but just about an inverse relation (of a function), which we just don't need and don't want to make compatible with that definition, then inverse functions and inverse relations can coexist in the same contexts without conflict. See if you like my edit in the article. With regards, Paolo.dL 20:52, 20 September 2007 (UTC)
Notice that I just made clearer your point, by untieing some knots, but I am still puzzled about the fact that your definition of inverse relation is one-sided (unidirectional), while the definition of inverse function is two-sided. Paolo.dL 22:15, 20 September 2007 (UTC)

Looks good to me. Rick Norwood 17:36, 21 September 2007 (UTC)

Thanks! And also thanks for spotting the missing concept about notation in the article about inverse function. It was one of the three main arbitrary and undocumented deletions by Jim Belk in that paper. Paolo.dL 19:26, 21 September 2007 (UTC)

New version by KSmrq

KSmrq did a good job, but the work done by Norwood and me about "inverse function vs function inverse" was lost.

Some sentences in the first paragraph of KSmrq's new version contained a very interesting analogy, but were linguistically incorrect. I tried to fix them, moved first part in new section (identity functions) and added a short sentence ("Intuitively, ƒ−1 is a function that undoes and can be undone by ƒ"). KSmrq summarily reverted my edits without explaining why (this is not the first time he behaves this way). Today, I restored and condensed my revision. KSmrq, you teach "Patience... patience... patience..." (see below). You should not forget that politeness favours patience. Paolo.dL 16:35, 2 October 2007 (UTC)