Talk:Partial function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Priority
 Field: Basics

2005[edit]

If a partial function associates with every element in its codomain precisely one element of its domain, then it is called a total function, or simply a function.

This doesn't sound right to me. I think the words codomain and domain should be swapped. The function described above sounds like a 1:1 function, not an arbitrary total function.

We need a better definition of "total function" Pizza Puzzle


Partial Function from-set contains members not in the domain, i.e. domain is subset of the from-set. Total Function Domain is the entire from-set -Mikael-


alrighty smartyhairsplitterses. What is to domain of a partial function what range is to codomain? (whaddya call {x|f(x) exists}?) Kwantus 2005 June 28 17:23 (UTC)

In my usage, {x|f(x) exists} is the domain of the partial function f. What I don't know a name for is the set X, when f is a partial function from X to Y. This needs to be clearly explained--someone following the link here from Uniformization (set theory) would be confused. --Trovatore 19:12, 6 September 2005 (UTC)

Cleanup[edit]

I am confused by the grammar in this explanation. It would be nice if somebody could explain the concept in a clearer fashion, perhaps something that would not confuse a non-mathematician. If nobody does so by this weekend, I'll get around to it if I have time. Suggestions? --Kooky 02:19, 20 July 2005 (UTC)

Kooky: Your prayers have been answered (I hope). I'll get right on it. Vonkje 16:21, 1 August 2005 (UTC)
Okay, I reworked the intro, but I'm keeping the to-be-cleaned-up tag 'cuz the rest of this article needs work, namely: 1) The section on Discussion and examples was kept from the original article, although it makes those annoying types of plays on mathwords that had turned me off to Mathematics as a lower-division undergraduate. 2) A modern formal definition like the kind from the MathWorld site will be needed in a new section titled: Formal definition. This would be a nice couple of things for you to do if you are interested. Vonkje 20:47, 1 August 2005 (UTC)


Total Function[edit]

I noticed that total function redirects to partial function. While the article in question does explain what a total function is, I think it is quite confusing to have total function simply redirect here. I'm not sure that creating a page called "total function" would be advisable, perhaps we could rename this to something like Partial vs Total functions, although I think that wording is too cumbersome. Anyone have any suggestions? Grokmoo 17:59, 24 January 2006 (UTC)

I agree it's a little peculiar, but there's plenty of precedent for this sort of thing. I don't think it's worth a whole article. Changing the redirect so it points to function (mathematics) would be defensible; I don't have a strong preference one way or the other for which article it should point to. --Trovatore 20:48, 24 January 2006 (UTC)
I agree too. It's just impossible to come up with what a total function should be, with this article. It gave me nothing and was useless, except for knowing that a total function seems to be the “opposite” of a partial function. But on what dimension, and what the center point of inversion for this opposition is, stays absolutely in the dark.
So: What the hell is a total function now???
94.220.250.151 (talk) 08:53, 3 November 2009 (UTC)
It's not the opposite of a partial function. All total functions are partial functions, but not vice versa. A partial function f:A\to B is a total function just in case the domain of f\, is all of A\,; that is, for every x\in A, f(x) is defined. --Trovatore (talk) 09:43, 3 November 2009 (UTC)

Merge[edit]

This section moved to Talk:function (mathematics)#Merge? where the mergeto template points. CMummert 12:32, 14 October 2006 (UTC)

Partial functions versus functions[edit]

The whole is a part of itself[edit]

In the lead:

"However, not every element of the domain has to be associated with an element of the codomain."

This implies that a total function is a special kind of partial function!!! Why? Are you sure? I would write:

"However, some element of the domain is not associated with an element of the codomain."

Paolo.dL 17:26, 7 September 2007 (UTC)

A total function is a special kind of partial function; this is completely standard. This sort of thing is quite usual in mathematics -- typically, when you loosen a restriction, you just loosen it; you don't require that an object in the new category actually fail the old definition. Similarly, a subset doesn't have to omit an element of the larger set; it's just permitted to. --Trovatore 17:43, 7 September 2007 (UTC)
This reminds me of the so-called "red herring principle" in mathematics--in general, a red herring need not be either red or a herring. A partial function may be total, and hence need not be "partial", and in the original definition of 'function', all functions must be total. This is reminiscent of such definitions as 'manifold with boundary', 'non-associative algebra' and 'nonunital ring'. Formally, a partial function is nothing but a 'span' in the category of sets, where we impose the requirement that the 'left' arrow (function) be an injection. If we were to combine partial and 'multivalued functions' (left-total relations) to form 'partial multivalued functions', we would just have spans in Set. This becomes of interest in the theory of (meromorphic functions defined on) Riemann surfaces, which need not be defined everywhere on the Riemann surface which surjectively maps to the complex plane. So in some sense, complex analysis is the study of 'analytic spans' in an appropriate category of complex manifolds.

--Daviddwd (talk) 20:05, 14 September 2014 (UTC)

The whole is part of a proper part of it[edit]

Thanks for your comment. Ok, I can understand the usefullness of calling a set a subset of itself. But in this case the use of the word "partial" to describe a total function seems crazy to me, because this terminology has a huge drawback: if what I suspect is confirmed (see this discussion), according to the modern formal and strict definition of the word "function", non-total functions are not functions! Thus, some "partial functions" are functions, but most of them are not! This is equivalent to a definition such that A+B is allowed to be a subset of A, with B \notin A (A=true functions, B=non-total functions, which by strict definition are not true functions, A+B=partial functions)! The whole is part of a proper part of it! That's too loose to be acceptable.

Alternative terminology 1. Imagine how simple the strict definition of the word function would become if this counter-intuitive terminology were abandoned and a more intuitive definition of the expression "partial function" were adopted:

  • Only total and single-valued relations are functions (this is the currently adopted standard definition).
  • There are two kinds of relations:
  1. total relations (also called functions, when single-valued).
  2. partial (=non-total!) relations (this is the change).
  • Partial (=non-total!) relations are not true functions. Thus, strictly speaking, the expressions "partial function" (="non-total function") is a misnomer.

(Similarly, "multivalued" or "multiple-valued" should mean "non-single-valued", and "multivalued function" should be replaced by "multivalued relation")

Isn't that much simpler and nicer? A question: does your counter-intuitive terminology include the expression "proper partial function" (analogous to "proper subset"), meaning "non-total function"? By the way, of course, "crazy" terminology is profuse in my field as well :-) Paolo.dL 15:38, 9 September 2007 (UTC)

Yes, both "partial function" and "multivalued function" are misnomers, since neither of these types of objects must be a function. But the terminology is nevertheless common in mathematics. The term "proper partial function" is not common; the only way to express that is to say that the partial function isn't total. The word "domain" also has multiple, mutually contradictory, meanings in teh context of partial functions - see domain (mathematics). — Carl (CBM · talk) 18:33, 9 September 2007 (UTC)

Ok, I know that this is not the place to express opinions. But I conclude as follows: if you accept this terminology, you accept that the whole is part of a proper part of it! As I wrote in the 1st paragraph of this section, Georg Cantor and others were only able to show that, in some cases, the part can be the same size as the whole... Paolo.dL 18:57, 9 September 2007 (UTC)

Is the definition of the word function a Procrustean bed?[edit]

Alternative terminology 2. Another radically different possibility to avoid the above described terminological inconsistency would be an alternative less-restrictive definition of the word function:

  • Total and non-total relations (i.e. "partial functions") are both true functions.
  • But only single-valued relations are true functions.
  • Multivalued relations are not true functions.
  • Thus, strictly speaking, only the expression "multivalued function" is a misnomer.

Thank you for your answers. :-) With kind regards, Paolo.dL 18:57, 9 September 2007 (UTC)

As you say earlier, non-total functions are not functions. All functions are total functions and also partial functions. But not all partial functions are functions (though some of them are, namely the total ones). I see nothing wrong with any of this, nor are there any misnomers here; it's quite alright for a frumious bandersnatch not to be a bandersnatch, but rather something else. That's just a feature of the English language.
But in any case we're not here to change the world; our job is to report the conventions that exist.
--Trovatore 03:27, 10 September 2007 (UTC)

A unreasonably complex convention. "My" alternative terminology 2 is much simpler. I really can't see the reason why mathematicians need to restrict the meaning of the word function! Yes, we are not here to change the world, but terminology does evolve. Unless there's a good reason, that I cannot see, to keep the current terminology, I hope this (apparently) absurd restriction to the meaning of the word function will be progressively abandoned by those who have the guts to change the world and make it better. :-) Paolo.dL 09:16, 10 September 2007 (UTC)

See also this wonderfully written sentence, posted in this interesting section by Arcfrk, one of the main authors of Function (mathematics):

Paolo.dL 16:15, 10 September 2007 (UTC)

That is true, to some extent. But if you ask the same mathematicians to define a function simpliciter they will almost certainly give the standard calculus definition. — Carl (CBM · talk) 16:59, 10 September 2007 (UTC)
I think the complaint about partial functions being possibly but not necessarily functions is frankly a little odd. Does it also bother you that skew fields may be, but need not be, fields? That manifolds with boundary may be, but need not be, manifolds? That weak inaccessibles may be, but need not be, inaccessibles? This is just the way mathematical English has evolved, for maximum utility and economy as its users see it. And it's not that different from everyday English in that regard. --Trovatore 17:18, 10 September 2007 (UTC)

You did not read with attention my latest comments. You seem to be answering to my very first comment, which I abandoned. I added subheaders to help you. As you can see, I use discussions to learn, not to defend my initial idea:

  1. I am not advocating against the general concept that "the whole is a part of itself" (which implies that a total function is a partial function, a set is a subset of istelf, etc.). This is not inconsistent. It is just weird. It is useful and therefore acceptable.
  2. Similarly, I am not against the general concept that "one" can be "many" (which implies that a single can be a couple and a group, and that a "one-to-one" function is a "many-to-one" function, and that a "single-valued" function is a "multiple-valued" function).
  3. I am advocating not against but in favour of spontaneous current and widely used language (see my Alternative 2, and Arcfrk's sentence).

Everybody uses the expression "partial function", but at the same time a strict definition (the Procrustean bed) exists somewhere in the heaven ("Űber alles"), which implies that everybody is guilty for incorrectly using the word "function". Here, mathematicians seem to be at the same time Procrustes (the "serial killer" who set the impossible rule) and Theseus (who killed Procrustes for not being able to comply with his own rule). This is masochistic. We are talking about scientific terminology, which should have an internal consistency. And we are talking about mathematics, by definition the most abstract and self-coherent science. Unless you can give a sound rationale for this Procrustean bed (the strict definition which forces us all to be inconsistent), you are not going to change my mind on that.

A function is strictly defined as a many-to-one and total relation. Since everybody keeps using the expression "partial function", you need a very sound rationale for forcing a function to be total. Let's admit that you have such a sound rationale and you strongly believe in it. In that case, for the sake of consistency, you should stop using the expression "partial function" and start using "partial relation". As for multivalued relations with more than one value, we should not call them functions (indeed, Wikipedia already states that "multivalued function" is a misnomer).

I conclude that either a rationale does not exist, or it is so weak that nobody believes in it. Hence, the strict definition of function is just a Procrustean bed. Regards, Paolo.dL 08:34, 11 September 2007 (UTC)

If you pick up any common calculus text, undergraduate analysis text, or undergraduate algebra text, you will get the definition of "function" as a total single-valued relation. It is completely standard. Studying mathematical terminology with the mindset "we are talking about scientific terminology, which should have an internal consistency" is bound to be disappointing. As Trovatore pointed out: a skew field may not be a field, a manifold with boundary may not be a manifold, and a partial function may not be a function. Wikipedia is not the place to change the widely-used definition of function, or to change the terminology. We just report on things as they are.
By the way, it isn't true that "everyone uses the term partial function". Only a few areas of math have any use for partial functions, and the terminology is not common outside those fields. — Carl (CBM · talk) 12:31, 11 September 2007 (UTC)
Paolo, if you want internal consistency, then think of it this way (not guaranteed to work 100% of the time but should get pretty close). There are two kinds of adjectives in mathematical English. We might call them, just for now, strengthening adjectives and weakening adjectives (and whether an adjective is strengthening or weakening can depend on the noun it modifies). If grezzlish is a strengthening adjective when applied to oddlewad, then every grezzlish oddlewad is an oddlewad, but perhaps not every oddlewad is grezzlish.
On the other hand, if tiluent is a weakening adjective when applied to roniform, then every roniform is a tiluent roniform, but not every tiluent roniform is necessarily a roniform.
So "partial" is a weakening adjective applied to "function", "weak" is a weakening adjective applied to "inaccessible", "skew" is a weakening adjective applied to "field".
Weakening adjectives tend to show up when it's the more restrictive concept that's generally found more useful, and therefore wants a shorter name. As in this case -- total functions are more generally useful than partial functions, so we prefer not to have to say "total" all the time.
Note that this terminology about strengthening and weakening adjectives is not remotely standard; I just made it up now to explain the situation as I see it. --Trovatore 15:01, 11 September 2007 (UTC)

Alternative terminology 1b[edit]

This is the most conservative alternative (see below for the rationale):

  • Only total and single-valued relations are functions (this is the currently adopted standard definition).
  • There are two kinds of relations:
  1. Total relations (also called functions, when single-valued).
  2. Non-total relations (which are not functions)
  • There's no need to use the word "partial", or the expression "partial function"; hence, there's no misnomer.

Similarly, "multivalued functions" could be replaced by "single-valued relation" or "non-single-valued relation". (Note that, according to the current definitions, some partial functions are total, and some multivalued functions are single-valued)

Paolo.dL 12:13, 12 September 2007 (UTC)

This is completely unacceptable, being not used in any published mathematical works. — Arthur Rubin | (talk) 14:56, 12 September 2007 (UTC)

Amazing! How can I answer to someone who knows all published mathematical works? First, I will ask you to explain why in Function (mathematics) you can read that sometimes non-total relations may be called partial functions (by the way, I just deleted "sometimes called" from the captions of two figures, because I wanted them to be very concise; the details are in the text). Second, I will remind you that in this section we are critically comparing hypothetical alternative definitions with standard definitions. It might be useful but it is not necessary to know whether the alternative hypotheses are used or not in the literature. What's more useful is to discuss pros and cons. This reveals the rationale behind the standard conventions (e.g., see latest comments by CBM and Trovatore). Paolo.dL 09:03, 13 September 2007 (UTC)

The burden of proof is on you to name a work in which it's used. All I can say for sure is that it's not standard. — Arthur Rubin | (talk) 09:07, 13 September 2007 (UTC)

Well, of course this terminology is not standard! Did I ever imply the contrary? I repeat that in my opinion the "burden of [this] proof" is not necessary in this context, because the purpose of this discussion is another. Paolo.dL 09:27, 13 September 2007 (UTC)

Examples of widely used but questionable terminology[edit]

Many authoritative scientists regard this terminology as "standard" and sometimes they defend it by saying: "lots of Wise Men adopted it"! Paolo.dL 10:06, 13 September 2007 (UTC)

Copied from Talk:Exterior algebra#Exterior to what? Ausdehnungslehre means "extension theory", not "exterior theory"

1. Homogeneous transformation.

An example of widely misused terminology is the expression "homogeneous transformation matrix", widely and rather conventionally used (unfortunately) by many experts in computer graphics, robotics, biomechanics, to indicate 4x4 transformation matrices containing 4-D homogeneous coordinates. These matrices are used to perform non-linear (affine and projective) transformations of vectors in 3-D space. This is neither an homogeneous matrix, nor it performs homogeneous transformations. It performs transformations that are non-homogeneous in 3-D. In 4-D, the transformation becomes linear and homogeneous. But all matrices, even 2x2 or 3x3 matrices, perform linear and homogeneous transformations (see discussion on this topic on the BIOMCH-L mailing list).
Paolo.dL 6 May 2007 (UTC)
I agree with you about the improper term homogeneous transformation for a projective general linear transformation. The classical term for such things is homographic transformation, and I fully support a revival of this more precise terminology. Silly rabbit 16:46, 6 May 2007 (UTC)

2. Inertial force and centrifugal force

Do not recur to Wise Men, please. There are many examples of wise men who found useful algorithms, wrote successfull formulas, but used terribly inadequate terminology. One example: D'Alembert and his imaginary, fictitious, appearant "inertial force" (e.g., the "centrifugal force"). Newton, if he were alive, would explain that this terminology is against nothing less than the logical foundations of mechanics. He spent much of his lifetime trying to convince others that there does not exist a centrifugal force, to stress the distinction between inertia and force (Newton's first law), and to fight against the "appearance" (inertial forces are appearant). Newton's outstanding theory stemmed from the study of the elliptical motion of planets (inspired and initiated by Kepler). Newton realized that they were acted upon by a centripetal force, while the absence of this force, and not a centrifugal force, produced rectilinear uniform motion. D'Alembert naively ignored Newton's effort, and brought back prejudice in science, by just using terminology incompatible with Newton's insightful teaching, unfortunately associated with a perfectly legitimate and useful rearrangement of Newton-Eulero's equations of motion. However, scientists and engineers have been using extensively D'Alembert's naive terminology... There have been dramatic examples in history about Wise Men being just men and being wrong, with the world blindly believing in them. And not only in the field of terminology! Before Galileo and Newton there was Aristoteles. He was for several centuries acclaimed as "The Wisest Man", but unfortunately everybody trusted him too much, and whenever somebody tried to say that the Earth was not the heart of the universe, somebody else could answer: "you are crazy, don't you know about Aristoteles and all of these Wise Men who for centuries embraced geocentrism? How dare you say they were wrong? Do you think you are smarter than all of them?". Now we know that was the case, indeed. But before our "awakening", this even became a religious issue, with the Catholic Church contrasting Galileo's teaching with forced exile.
Paolo.dL 9 May 2007 (UTC)
What you have written is entirely beside the point. When someone on one of these pages points out that a terminology is (or is not) standard, there is no implication that the standard terminology is necessarily the best possible one. The point is that even if you come up with something that's better, you still can't put it in the article, not until you first get the community at large, outside Wikipedia, to accept it. Therefore strictly speaking this talk page is not an appropriate place to discuss it, because the purpose of the talk page is to discuss improvements to the article, and we know in advance that we can't put in your proposed change.
I think it's counterproductive to be too strict on the latter point (the one about talk pages); editors can be more effective if they understand the reasons behind the accepted view, so sometimes it's worth discussing to some extent. But there has to be a cutoff at some point, or the talk page will lose effectiveness for its actual purpose. --Trovatore 22:31, 13 September 2007 (UTC)
I agree. This subsection was just to stress the point that (saying it with your own words): "there is no implication that the standard terminology is necessarily the best possible one". Although, as you perfectly know, many will just assume the contrary. And I also agree that this discussion can be considered to be closed. Paolo.dL 07:42, 14 September 2007 (UTC)

Tentative conclusions[edit]

As Arthur Rubin pointed out, the above presented alternative terminologies are just hypothetical. They are not necessarily used in the literature. The purpose of this discussion was to critically compare them with the standard terminology, as described in Partial function and Function (mathematics).

Carl and Trovatore, thank you very much for your enlightening contributions. Trovatore, by explaining the reason why the standard strict definition of function is necessary, you convinced me that the hypothetical "alternative terminology 1b" is better than 1 and 2. You also showed that the inconsistency in standard terminology is a "weak" inconsistency :-). However, in this case, full consistency is possible and easy. My opinion on this is irrelevant: the readers are free to choose what they prefer. For sure, now they are better informed.

Carl, when possible, I prefer full terminological consistency because I believe it facilitates the learning process and makes it stabler (I see it as a service for students). Yes, we are not here to change the world, but this discussion will provide good food for thought for the readers. They will be able to compare the definitions of partial function and function with possible alternative ones. At least, the text in this section will help them to better understand the standard definitions, and what's more important, the rationale behind them.

With kind regards, Paolo.dL 11:46, 13 September 2007 (UTC)

A partial function as one defined on a restricted domain "domain of definition" which is a proper or improper subset i.e. ⊆ (and not this ambiguous symbol ⊂) of the "universe of discourse"[edit]

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, a machine "clears" 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:40, 12 September 2007 (UTC)

∈∉⊂⊆→

Manin's definition of "partial function" makes this very clear (he excludes "0" for a very good reason, shown below):

"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)

In his immediately-following definition of "computable" (i.e. it always terminates, but sometimes with "0") to indicate that "x ∉ D(f)". Manin states the following: "Here 0 merely indicates that f is not defined at x; we could allow the output in this case to be anything not in (Z+)n [this is just a vector of elements off the domain] (p. 178)

Boolos-Burgess-Jeffrey 2002 also say that "domain of partial function" ⊂ "domain of universe of discourse" but only in words:

"A partial function of positive integers is one whose domain is something less than the whole set P [of positive integers]" (p. 7)
Yu. I. Manin, 1977, A Course in Mathematical Logic, Springer-Verlag, New York, ISBN 0-387-90243-0.
Boolos, Burgess, Jeffrey 2002, Computability and Logic: Fourth edition", Cambridge University Press, Cambridge UK ISBN 0521 00758 5 paperback.
Herbert B. Enderton, 2001 2nd ed, 1971, A Mathematical Introduction to Logic: Second Edition, Harcourt Academic Press (Elsevier), Burlington, MA, ISBN-13: 978-0-12-238452-3

Manin lives up to its name "Graduate Texts in Mathematics" (and is a bit quirky in a nice way -- it's translated from the Russian, sometimes has proverbs in it, etc), but is by far the clearest treatment I've seen. wvbaileyWvbailey 14:11, 12 September 2007 (UTC), Enderton added: wvbaileyWvbailey 16:52, 14 September 2007 (UTC)

WV, you appear to be assuming that Manin uses the ⊂ symbol to mean "proper subset" rather than just "subset". You are aware that there are two possible conventions on this point? Without some indication as to which convention Manin is using, we can't tell whether he is requiring D(f) to be a proper subset of X.
(I note in passing that I have never ever ever heard anyone use "partial function" in a way that required the domain to be a proper subset. That would be a very unweildy convention, requiring us to prove theorems twice, once for partial functions and once for total, when only one proof is in fact necessary.) --Trovatore 20:22, 12 September 2007 (UTC)

↔∈∉⊂⊆←→øØℕǎă

Good point, I wasn't aware of this, but a little lucky research showed you are correct (but see my suggestion below about proving twice, based on Suppes's definitions -- i.e. if you prove the case for the partial function you get the total function for free). I honestly can't tell what convention Manin's using (what I would call the exclusive-⊂ vs inclusive-⊂ i.e. ⊆). Throughout the book he refers to the "von Neumann universe" (cf where he defines this in his II.Appendix: the von Neumann universe (p. 95-102)) but he never bothers to define the symbol ⊂, at least that I can find in the text. In the instance of defining V0=Ø, V1={Ø}, V2=={0,{Ø}} he says "It is easy to see that Vn⊂Vn+1." (p. 96). But I don't know enough set theory to know, in other instances of his usage, whether its the exclusive- or inclusive- usage. To add to the confusion, on p.145 he writes "we have replaced ⊆ by ≥ ...". I checked out von Neumann's original paper in van Heijenoort and this is his usage as well (i.e. >, <, ≤, ≥). However, the plot thickens. Halmos in his Naive Set Theory uses the inclusive- form: A ⊂ A (cf p. 3). Whereas Suppes in his Axiomatic Set Theory strongly distinguishes the two with: A ⊆ A (p. 22); he defines the "exclusive" form as follows;

"THEOREM 3. A ⊆ A
"We now define proper inclusion.
"DEFINITION 4. A ⊂ B ←→ A ⊆ B & A ≠ B" (p. 23)

This becomes useful when he also cites:

"THEOREM 10. A ⊂ B → A ⊆ B" (p. 23)

And Enderton 2001 uses only ⊆ as defined in the manner of Suppes. This becomes important for his definitions of partial function and computable function; he does not allow for semi-computable function in the manner of B-B-J:

"DEFINITION. An m-place partial function is a function f with dom f ⊆ ℕ [his ℕ includes 0, i.e. ℕ={ 0, 1, 2, 3, ...}]. If ă ∉ dom f, then f(ă) is said to be undefined. If dom f = ℕm [N x N x ...] then f is said to be total.
"DEFINITION. An m-place partial function f is computable iff there is an effective procedure such that (a) given an m-tuple ă in dom f, the procedure prduces f(ă); and (b) given an m-tuple ă not in dom f, the procedure produces no output at all. (Enderton 2001:250)

What do we do about the Boolos-Burgess-Jeffrey (B-B-J) quote? If a set is defined by its elements, then we are truly stuck with the "proper" inclusion because a partial function will always include at least one extra element.

My suggestion about proving twice is based on the Suppes definition and THEOREM 10: If you prove the case for the partial-and-semi-computable function you are proving the partial-and-computable and the total sub-functions as well; the converse is NOT true: if you prove the case for the total function (with its restricted domain) then if you widen the domain to include rogue elements your proof will be insufficient. A real-life example:

I've figured out a better (less arbitrary) example than the one shown above: Suppose I build a counter machine that computes/calculates a Q = quotient_part(N/(X - k)), i.e. counter Q will contain the quotient. It turns out that the residue can be found in "X", iff the function halts. N and k are specified at the outset for example N=12, k=2 so we have: Y=12/(X-2). Now to get our answer, we concatenate the quotient and the residue, i.e. Q.X, where "." means "concatenate".

If I restrict my domain to the positive integers (3, 4, 5, 6, ... ) then Q.X="0.0" never occurs because there's always a non-zero residue in counter X or a non-zero quotient in counter Q, or both, and the "function" always halts. Thus the function is total over this restricted domain. If I expand the domain to include "2", i.e. {2, 3, 4, 5, 6} then when X=2 indeed the function will not halt -- it forever increments Q (i.e. Q = N/0) and the function is now partial. Now, if I expand the domain to include {0, 1, 2, 3, 4, 5, 6, ...} but restrict it by excluding "2", and I define the subtraction "X-2" to be proper, then when X < 2, it will terminate the calculation with Q.R = 0.0. Now the function is "partial but computable" over {0, 1, 3, 4, 5, 6, ...}. If I expand the domain to the whole "universe of discourse" by including the rogue "2" i.e. so X = {0, 1, 2, 3, 4, 5, 6, ...} the function of course remains semi-computable, it is both partial and semi-computable.

I've actually built the "function" as a counter machine in Excel and it does the above (however, along the way, mistakes were made...). Once I was able to "prove" the "inner part" -- the total machine over its restricted domain -- ) I then widened the domain to take care of all the other cases (the computable and semi-computable cases). Indeed -- After I got the "total" piece to work, the other part (the proper subtraction part) didn't. I had to fiddle with the algorithm as I expanded the domain. At last I got it to work "as advertised". Thus, when I had "proved" (verified as working correctly) the whole thing (semi-computable and partial) my proof implied I had also proved all the restricted sub-parts (computable and partial, total). I hope I am using the words correctly. wvbaileyWvbailey 15:38, 13 September 2007 (UTC),

Like B-B-J (2002), Enderton also uses a counter machine (he calls it a register machine) as one example of "equivalent definitions of the class of recursive functions functions" (p. 261ff). Enderton references Boolos and Jeffrey 3rd edition 1989, not their latest 4th edition 2002; the 4th B-B-J was significantly changed from the 3rd edition when they added Burgess as a middle-author. ( Updated with Enderton) wvbaileyWvbailey 16:52, 14 September 2007 (UTC)

Changed the heading. Am now convinced by Kleene 1952: "To fix our terminology, let us now call a function from any subset (proper or improper) of the n-tuples of the natural numbers to the natural numbers a partial function. [Kleene's definition of the "natural numbers" includes 0 cf p. 3]. In other words, a partial function φ is a function which for each n-tuple x1, ..., xn of natural numbers as arguments takes at most one natural number φ(x1, ..., xn) as value." (Kleene 1952:326). Kleene goes on to define a "defined function" at a value x1, ..., xn, "undefined function" at a value x1, ..., xn, "range of definition" (what we would now call the "domain of definition"), "completely defined function" [defined for all 1, ..., xn in the domain of definition] and "incompletely defined" function [incompletely defined for some 1, ..., xn in the "domain of definition" ⊆ "universe of discourse"], and "completely undefined" (p. 327). wvbaileyWvbailey 15:31, 17 September 2007 (UTC)

What the hell is going on here?[edit]

"A function is an algorithm calculated by a person, or computed by a machine." This is nonsense. And the 200-odd lines which follow (lengthy examples of abstract state machine computations) have little to do with partial functions themselves. This is an article about set relations, not computability. cf. pages on surjections and injections - it should be clear that the last 3/4 of this article doesn't belong here. --117.53.136.79 (talk) 16:31, 20 September 2008 (UTC)

I do think you have a point, the abstract state machine stuff seems excessive. There may be some point about computability which the section is trying to address. --Salix alba (talk) 16:50, 20 September 2008 (UTC)
I concur. There's too much material on the computational perspective, but a computational perspective per se does not seem off-topic. But then, I'm a computer scientist... Also, I don't have time to work on this article today; don't take that as an endorsement of wholesale deletion of that material. VG 16:55, 20 September 2008 (UTC)
I suggest that you look at Kleene 1952 beforehand re the definition of what a "partial function" is, at least with respect to number-theoretic functions. Bill Wvbailey (talk) 17:19, 20 September 2008 (UTC)
I did not object the computational perspective, but the examples do seem excessively long to me, along the lines of WP:NOTTEXTBOOK. YMMV. VG 18:03, 20 September 2008 (UTC)
I don't object to a computational perspective either (as a computer scientist-in-training myself), if indeed there's something meaningful to say. But I can't find anything salvageable in there. I don't see any relevance to the preceding sections, any motivation for the examples, or any kind of conclusion relating to partial functions.
The entire section seems to say little more than this: You can view an algorithm as a function. If some input produces no output, then the analogous function is partial (which I'd have thought was fairly self-evident anyway). Nothing is said about why applying this label to an algorithm is of any significance.
Aside from that, there are longwinded examples of such algorithms, some speculation about "wrong" output (which is nonsense - a function cannot be wrong, it can only disagree with your expectations / intentions), and another longwinded example of debugging an "incorrect" machine. I don't think any of this has a place here.
I guarantee that, in your last moments as your jet slammed into a mountain because the autopilot algorithm failed to compute the correct flight path -- e.g. it hangs on a div by 0 -- that you would say that the algorithm had produced "wrong output". The algorithm failed to meet its specification, and what you have missed here, because your definition of algorithm is too narrow, is that the specification is part of the algorithm. Bill Wvbailey (talk) 19:59, 20 September 2008 (UTC)
If the algorithm hangs, then it has not produced any output. This isn't the case I'm talking about here. I'm talking about the case outlined at the start of the section "Subtraction with a Post–Turing machine model" - an algorithm which returns a result, but not the result you wanted.
If your machine deterministically maps every input to an output, then it does not correspond to a partial function. A given function is partial or it is not; its formal properties do not change with the author's intentions.
And specification is certainly not part of the algorithm. An algorithm is a sequence of instructions, and nothing more. --117.53.136.79 (talk) 01:13, 21 September 2008 (UTC)


@Wvbailey: If this entire section is working under a different definition of partial functions, then perhaps that definition should be provided. --117.53.136.79 (talk) 18:46, 20 September 2008 (UTC)
Kleene 1952: "To fix our terminology, let us now call a function from any subset (proper or improper) of the n-tuples of the natural numbers to the natural numbers a partial function. [Kleene's definition of the "natural numbers" includes 0 cf p. 3]. In other words, a partial function φ is a function which for each n-tuple x1, ..., xn of natural numbers as arguments takes at most one natural number φ(x1, ..., xn) as value." (Kleene 1952:326). Kleene goes on to define a "defined function" at a value x1, ..., xn, "undefined function" at a value x1, ..., xn, "range of definition" (what we would now call the "domain of definition"), "completely defined function" [defined for all 1, ..., xn in the domain of definition] and "incompletely defined" function [incompletely defined for some 1, ..., xn in the "domain of definition" ⊆ "universe of discourse"], and "completely undefined" (p. 327).
Yuri Manin 1977, A Course in Mathematical Logic first discusses "partial function" in context of his Chapter V: Recursive functions and Churh's thesis, section 1.1 Introduction. Intuitive computability (p. 177ff) It is unclear from his definition of "partial function" whether or not the domain and range are restricted to the natural numbers. But in the next paragraph this is clearly the case.
Herbert Enderton 2001, A mathematical Introduction to Logic 2nd Edition first mentions, and defines, "partial function" in context of his Chapter 3. Undecidability, section Recursive Partial functions (p. 250ff). He restricts his domain of definition, and his range, to the natural numbers.
Thus in these three cases, at least, the notion of partial function appears only in the context of "computability", and in two of the three cases, the definitions are clearly in terms of number-theoretic functions. Thus, at least in these cases, examples from computability are not out of place. Bill Wvbailey (talk) 19:59, 20 September 2008 (UTC)
We need at most one of the equivalent definitions of (computable) function. We may also need to distinguish between an algorithm computing a partial function and the function itself. — Arthur Rubin (talk) 20:08, 20 September 2008 (UTC)
(edit conflict) Yes, classic computability (recursive function theory) deals with partial functions on natural numbers (including 0). So? It's normal for Kleene and the others not to give a more general definition of partial function because it's not relevant to their domain. That does not mean one cannot define partial functions in general. Their definition is not in contradiction with the general one from set theory, but rather a specialization thereof. BTW, Wikipedia errs by having a disambiguation page for computability theory; the CS and mathematical theories are compatible and there should be one main article explaing the equivalence with sub-articles as necessary. There are even books that cover them together, e.g. S. B. Cooper's "Computability Theory", ISBN 1584882379. VG 20:16, 20 September 2008 (UTC)
I see there's a long discussion (in which even Martin Davis took part) on the talk page there about the pros/cons of having separate articles. For the sake of keeping this already long discussion focused, please ignore the off-topic "BTW" remark here. VG 20:30, 20 September 2008 (UTC)
Wvbailey, can you summarise for me exactly what you think this section is trying to get across? What aspect(s) of partial functions are these examples supposed to be illustrating? --117.53.136.79 (talk) 01:56, 21 September 2008 (UTC)

I somewhat agree that the length of the section on algorithmic examples is out of proportion to the topic of this article. A partial function need not be related to an algorithm in any way, although the study of algorithms is one area in which the study of partial functions naturally arises. Most people are more familiar with examples such as y = tan(x), considered as a partial function from R to R. I think it would make sense to trim section 2 very heavily, while adding information about other situations where partial functions arise. — Carl (CBM · talk) 13:52, 21 September 2008 (UTC) is

Carl, I don't disagree that the examples are too long -- I agree pruning is in order. Here's where the idea came from and what I would suggest: If you look at Davis's 1958 Computability and Unsolvability 3.Examples p. 12ff he gives very specific examples of Turing-code to demonstrate the notions of "computable" versus "partially-computable" functions. In particular he demonstrates as Example 3.3 Subtraction, and he shows how and why it as "partially computable function". His answer to the case when the function (machine) encounters "improper" data (m1 < m2) in its operation to compute m1 - m2, is to send the machine into a continuous "circle", back and forth ad infinitum. (Kleene 1952 also suggested this approach). Davis then goes on to produce code that would provide "0" as an output when m1 < m2; the function is then "computable". (As I recall, Kleene also suggested this approach." Thus he shows that "we can complete any partially computble function f(m) by setting
g(m) = f(m) where f(m ) is defined,
g(m) = 0, elsewhere." (p. 16)
The problem with Davis's presentation is that the Turing code is rather daunting. I was trying to come up with an easier example, somewhat formalized to the notion of a counter machine "algorithm". Again and again I have to repeat: not everyone who encounters these articles is a math whiz and easily assimilate highly-abstract material the first time, some need examples. Again I have to point out the Busy beaver talk-page. This ends my dialog on this topic. The prunemeisters can prune to their hearts' content. I gave it my best shot. BillWvbailey (talk) 18:49, 21 September 2008 (UTC)

I think the terminology from Kleene (1952) quoted above is obsolete, so it shouldn't be used in the article. Also, "the recursive functions are exactly the partial recursive functions which happen to be total" (Odifreddi, vol I, Corrollary II.1.3, page 129), so the notions "partial" and "total" used in computability theory coincide with those from set theory, so no disambiguation is needed. I think this fact is worth mentioning in the article.

As far as examples from computability, any algorithm that is non-terminating on some inputs is a good example of a partial function. A trivial high-level example like "f(x) = f(x) if x < 1 else 0" should do. If you want to be more formal and use the μ operator that's fine too. Involving Turing machines inevitably complicates the examples a lot and offers little if any additional insight. Obviously, non-terminating computations using Turing machines are non-terminating as recursive functions, but this is essentially a detail stemming from the equivalence of the two computation models. This article is hardly the place to delve into that topic. Since this page is about functions, the most natural examples of non-terminating computations are recursive functions. VG 21:27, 21 September 2008 (UTC)

I've redone the text following Bailey's reply above. But haven't really emphesised their importance for computability theory. One question which it is easy to turn the partial function x-y into a computable function, is it always possible to do the same for any non computable one? Unless you know a-priori when an algorithm a will terminate you can redo the algorithm to make an algorithm b which returns zero when a would not terminate. --Salix alba (talk) 22:03, 21 September 2008 (UTC)
If I understood your question correctly, you're asking whether there exist a method for transforming a given partial recursive/computable function into a total one. The answer is no in the sense that no algorithm to perform this transformation exits; any such algorithm has to (at least) solve the Halting problem, but it's actually harder because it has to figure out all inputs for which the partial function does not terminate; this equivalent to solving the uniform halting problem (i.e. the problem of whether a given Turing machine halts on all inputs; I see Wikipedia has no article on that). VG 22:46, 21 September 2008 (UTC)
Re Salix alba: it's a standard grad textbook result that there are partial computable functions that cannot be extended to any total computable function. One example is the function f that, given an input n, returns the number of time steps that the nth Turing machine requires to halt on input 0, and does not return a value if the machine does not halt on input 0. If this could be extended to a total recursive function g, then g could be used to solve the halting problem as follows. Given n, compute g(n). There are two options: either f(n) is defined and equals g(n), which means that n is in the halting set, or else f(n) is undefined, and n is not in the halting set. To determine which of these is the case, it's only necessary to simulate the nth machine for g(n) steps. If it does not halt by that time, it means that g(n) is not equal to f(n), which means the machine will never halt. — Carl (CBM · talk) 02:18, 22 September 2008 (UTC)

Completion of partial recursive functions ?[edit]

I donnot understand in section "subtraction of natural numbers" this assertion :

Thus he shows that any partially computable function f(x) can be completed by setting 
g(x) = 
\begin{cases} 
  f(x)  & \mbox{where }f(x)\mbox{ is defined} \\
  0, & \mbox{otherwise}. 
\end{cases}
which seems to me ton contradict basic and well known facts (halting problem) in computability theory. —Preceding unsigned comment added by 81.57.95.102 (talk) 10:25, 5 September 2009 (UTC)

I removed that paragraph from the article just now. Thank you for pointing it out. — Carl (CBM · talk) 11:32, 5 September 2009 (UTC)

Reciprocal?[edit]

It seems to me that the reciprocal function f(x) = 1/x is one of the more basic "partial functions" over the reals (since it is not defined for x = 0), so that should be reflected in the intro or examples. It's also a partial function over the rationals and over complex numbers for the same reason. 72.19.93.38 (talk) 04:07, 20 September 2011 (UTC)

Merge Total function into this article[edit]

Fully agree with the merge. Total function only exists because of partial functions and it is a pretty tiny article. Dmcq (talk) 22:49, 10 March 2012 (UTC)

Total Function was created recently as a separate article, but total function already existed as a redirect to this article. Isheden (talk) 22:59, 10 March 2012 (UTC)
Initially, Total function (edit | talk | history | links | watch | logs) was a redirect to Function (mathematics), as it should be, but one user decided to increase the confusion. The new article should be merged to Function (mathematics)#Types of functions, not to "partial function". Incnis Mrsi (talk) 09:27, 11 March 2012 (UTC)
I believe Total function should redirect to partial function rather than to function (mathematics). Just because a total function is a function does not mean that is the best redirect, a redirect to partial function where both can be dealt with is better because it deals with the main reason a person would be looking up total function, i.e. why is the word 'total' there? Most times they'd already have a good idea of what a function is. Dmcq (talk) 11:09, 11 March 2012 (UTC)
Moreover, since "total function" is just a synonym for function, it is not a "type of function". A partial function is a generalization of the concept of a function, so partial functions should be discussed only towards the end of the article "function" in a section on extensions. I also think that single-valued function should redirect to multi-valued function, because it is natural to discuss these contrasting concepts together. Isheden (talk) 12:22, 11 March 2012 (UTC)
Please, read with attention what I said. The new article  should be merged to Function (mathematics)#Types of functions (or, maybe even better to Function (mathematics)#Definition),  not to "partial function". This implies that "total function" should redirect to a section of "function (mathematics)" where the sense of a qualifier "total" will be explained. Contrary, the article partial function should be focused not to contrasting its definition to total functions, but to uses of partial functions in computation theory, algebra, function theory and applied mathematics. Another acceptable option would be merger to something like total, partial and multi-valued functions devoted to differences in definitions. Incnis Mrsi (talk) 12:31, 11 March 2012 (UTC)
Well, I think we understood what you said the first time, so there is no need to reiterate the argument. We all agree that total function is really the same as a function, but the qualifier "total" is used to distinguish it from a partial function. It would be strange to mention total functions in Function (mathematics)#Definition when partial functions are only mentioned as a generalization at the end of the article. What you could do is redirect to that generalizations section at the end of the article, but then it is not a natural redirect anyway. I think this situation is similar to an example on WP:Merging that both "flammable" and "non-flammable" can be explained in an article on "flammability" to avoid excessive overlap. I see no problem with the article also covering the applications you mentioned. Isheden (talk) 15:01, 11 March 2012 (UTC)
Since Isheden reiterates the reference to "flammability", it is the time to explain the difference between cases. Flammability is a property of a chemical substance, not a definition of some notion at its own right. In almost any case where "X is flammable" and "X is non-flammable" can occur, an article either states explicitly or it is clear from the context that X is a substance. One can easily browse to such links as chemical compound, or to the article on a concrete substance, for explanations. But if I wrote "ƒ is a total function from X to Y", then there would be no sources of information about ƒ but the link "total function" and possibly links to its (concrete) domain and codomain (which would explain nothing about the notion of "function"). If one says "ƒ is a total function", the link may not be diverted to an article starting with definition of a partial function. Incnis Mrsi (talk) 17:10, 11 March 2012 (UTC)
Why not? If the link is to "total function" then the point is to emphasize the totality (vis-a-vis partiality) of the function. If they just meant "function" then they should not link to "total function", which I do think should redirect to this article. But at the same time the lede of this article ought to have total function in bold if it is the target of that redirect. — Carl (CBM · talk) 19:16, 11 March 2012 (UTC)
Incidentally, it has total function in bold already. Isheden (talk) 19:48, 11 March 2012 (UTC)
I'm sure we are both keen to help the reader who clicks on total function understand what it is. To my understanding, you believe that the best way is to redirect to function (mathematics), where it is mentioned that "total function" is synonymous to "function". I believe that the best way is to redirect to partial function, which defines a "total function" already in the lead in terms of a partial function for which the two sets X and X' coincide. I acknowledge your point of view, however. Isheden (talk) 19:46, 11 March 2012 (UTC)
The thing several users (Dmcq, Isheden, CBM, Habitmelon) talk about is not redirecting. It actually is a merger. If so, then for which reason the title of the resulting article is "partial function"? It must be something like "total and partial functions", because there is no special word for the total/partial opposition. Incnis Mrsi (talk) 07:04, 12 March 2012 (UTC)
There are basically two questions: What to do with the material in Total Function and to what total function should redirect. Several users answer the second question with an article on partial functions. There is no need to include "total function" in the title, since a total function can be viewed as a special case (possibly degenerate) of a partial function. Isheden (talk) 08:28, 12 March 2012 (UTC)
Good point. Let us go further and merge "function (mathematics)" to "partial function". There is no need to have two separate articles since a function can be viewed as a special case (possibly degenerate) of a partial function. Incnis Mrsi (talk) 08:33, 12 March 2012 (UTC)
I think we both agree that "function" is notable enough for an own article and that "partial function" as a generalization of function deserves an own article. But what is your answer to the two questions mentioned above? Isheden (talk) 08:46, 12 March 2012 (UTC)
As to the article title: There is a common name for this, see Totality. If this is a concern, the article could be renamed to for example "Totality (mathematics)". Isheden (talk) 09:09, 12 March 2012 (UTC)
Totality (mathematics)? An exciting thought. Could you combine total/partial functions with total/partial order such that the resulting article would not violate WP:OR? Incnis Mrsi (talk) 10:35, 12 March 2012 (UTC)
I think that "partial function" is a better title. "Totality" is not recognizable - someone could guess it is about partial functions, maybe, but most people would have no idea. "Partial function" on the other hand is perfectly clear. Moreover the main topic is partiality, not totality. — Carl (CBM · talk) 11:07, 12 March 2012 (UTC)
I'd prefer to see total function redirect to this page, because of the same argument Dmcq gave. — Carl (CBM · talk) 12:27, 11 March 2012 (UTC)
I take full responsibility for "increasing the confusion", after reading this discussion I wholeheartedly agree that Total function should redirect to Partial function. — Preceding unsigned comment added by Habitmelon (talkcontribs) 19:53, 11 March 2012 (UTC)
I think "increasing the confusion" referred to the redirect from total function to this article. However, it would be nice if you as the creator of Total Function would move any nonredundant material there to either partial function or function (mathematics). Isheden (talk) 08:32, 12 March 2012 (UTC)

I inserted a section on total functions in this article, merging the example from Total Function. Regarding the redirect I guess there is still no consensus. Perhaps it is not such a bad idea to redirect to Function (mathematics)#Generalizations after all. Isheden (talk) 07:40, 20 March 2012 (UTC)

Well where I don't feel strongly I defer to the person who actually goes and does the work! Dmcq (talk) 12:00, 20 March 2012 (UTC)