User talk:Wvbailey/Function definitions

test cases for article

f is a subset of u x v

the projection of f onto u concides with all of u

each element of u corresponds to exaclty one element of v —Preceding unsigned comment added by Wvbailey (talk • contribs) 22:00, 30 September 2007 (UTC)

∀z(z ∈ f ⇒ (∃u₁ ∃v₁ (u₁∈u ⋀ v₁∈v ⋀ "z = <u₁, v₁>")))

⋀ ∀u₁ (u₁∈u ⇒ ∃z(v1∈v ⋀ "z=<u₁,v₁" ⋀ z∈f))

⋀ ∀y₁ ∀v₁ ∀v₂ (∃z₁ ∃z₂ (z₁ ∈f ⋀ z₂ ∈f ⋀ "z₁ = <u₁, v₁>" ⋀ "z₂ ⋀ <u₁, v₂>" ) ⇒ v₁ = v₂

The following is a division algorithm that, in a counter machine, produces the quotient q in register (at location) Q and residue (remainder) r at location R, i.e. [Q] = q and [R] = r. Given an n in N, it computes: n = q + r/x.

" DEFINITION 1. x is a fraction ⇔ (∃m)(∃n)(n ≠ 0 & x = <m, n>) " (Suppes Axiomatic Set Theory 1972:162)

The relation ⋍_f is defined as follows:

m₁/n₁ ⋍_f m₂/n₂ ⇔ m₁n₂ = m₂n₂

" DEFINITION 38. x is a sequence if and only if x is a function on the set ω of natural numbers." (p. 174)

" DEFINITION 40. If x is a sequence, < x₁, x₂, . . ., x_n, . . .> = x (p. 174)

"Every real number can be uniquely represented by a non-terminating decimal [i.e. made of a string of integers]" (p. 189)

"THEOREM 56. Let r be an integer ≥ 2. Every real number x is uniquiely representable with respect to the radix r as a sequence <a, d1, d2, . . ., dn, . . .> such that

"(i) a is the largest integer equal to or less than x,

"(ii) for all n, 0 ≤ dn < r and dn is an integer,

"(iii) it is not the case that there is an N fsuch that for all n > N, dn = r - 1

"(iv) the sequence whose terms cn are defined recursively by

"c0 = a

"cn+1 = cn + dn+1/rn+1

"is a Cauchy sequence which converges to x. (ibid

A "Cauchy sequence" is one that converges:

DEFINITION 44. x is a Caucy sequence of real numbers if and only if x is a sequence of real numbers and for every real number e > 0, there is a positive integer N such that for every m,n > N

|x_n - x_m| < e "(ibid p. 175)

And finally,

" DEFINITION 60. If x is a sequence of real numbers and y is the limit of x then

" lim _n→∞ x_n = y "(ibid p. 185)

"Theorem 52. A sequence of real numbers has a limit if and only if it is a Cauchy sequence." (ibid p. 185)

The following is a division algorithm for a counter machine with the following instruction set operating on at least one "register" "r" and one register "A" (more likely a row of (labelled) holes in the ground that hold pebble-counters per Melzak, or perhaps (labelled) abacus wires with abacus beads strung on them, per Lambek; cf Minsky 1967 and B-B-J 2002). In this model the instructions are "strung together" (concatenated) so that they follow one after another unless a "conditional jump-if-A=zero" or an "Unconditional jump" is in the sequence:

{ LoaD_A r; STore_A r; INCrement r; DeCRement r; Jump_if_A=Zero_to instruction; Jump_unconditionally_to instruction; Halt }

	Address: [IR]	Instruction	Register	If [A]=0 goto:	Action	Description
	1	clr	Q		"clr Q" → 0 → Q → [IR+1]+1 → IR	; CLEAR: 0 => quotient then next step
outer_loop:	2	clr	R		"clr R" → 0 → R → [IR=2]+1 → IR	; CLEAR: 0 => residue
restore_D:	3	ldA	X		"ldA X" → [X] → A → [IR=3]+1 → IR	; Get cc of contents of X in order to restore input X to denominator D
	4	stA	D		"stA D" → [A] → D → [IR=4]+1 → IR	; Put cc of contents of A in D
inner_loop:	5	ldA	D		"ldA D" → [D] → A → [IR=5]+1 → IR	; Get cc of the contents of register D for testing
	6	jAz		13	( [A] = [D] = 0 ) → 10 → IR else [IR=6]+1 → IR	; IF[A] =0 THEN go to quotient+1 step 10 else next step
	7	ldA	N		"ldA N" → [N] → A → [IR=7]+1 → IR	; Get register N for testing
	8	jAz		15	( [A] = [N] = 0 ) → 15 → IR else [IR=8]+1 → IR	; test N for 0: IF N=0 then go to done step 11 else step 7
	9	dcr	D		"dcr D" → [D] - 1 → D → [IR=9]+1 → IR	;decrement denominator D
	10	dcr	N		"dcr N" → [N] - 1 → N → [IR=10]+1 → IR	;decrement numerator N
	11	inc	R		"inc R" → [R] - 1 → R → [IR=11]+1 → IR	;increment residue
	12	j		5	( [IR]=12 & "j" ) → ( 5 → IR )	;unconditional jump to inner_loop for another round
quotient+1:	13	inc	Q		[Q] - 1 → Q → [IR]+1 → IR	;increment quotient Q
	14	j		2	( [IR]=14 & "j" ) → ( 2 → IR )	;unconditional jump to outer_loop for another round
done:	15	H				;halt

Comments

What do any of the algorithms have to do with the definition of function? — Arthur Rubin | (talk) 16:37, 2 October 2007 (UTC)

---

I'm not sure yet, but I think the reasoning goes something like the following sequence of 10 steps. My sense is: an algorithm per se is probably not a function, but rather the rule behind the function. But the algorithm-function connection is this, i.e. that behind every function is an algorithm that can expressed in the form of a Turing machine. Or perhaps: every function is a Turing machine. Or something to that effect. With regards to any random assignment e.g. the little drawings in the Function (mathematics) article, these set-theoretic drawings can be simulated by a counter machine algorithm (which I intend to produce an example of).

About these silly random examples of useless mappings, Minsky points out: "No mention is made of what the rule really is [i.e. the set-theoretic relation that produces the function-set of ordered pairs]. (There might not even be one, though that leaves the uncomfortable question of what one could use the function for, or in what sense it really exists.)"(Minsky 1967:133). With regards to this issue, which I think is serious, it would seem that there is an implied problem with the axiom of specification if it is, in effect an expression of randomness. Halmos's version of the Axiom of Specification requires a specification (!):

"Axiom of Specification. To every set A and to every condition S(x) there corresponds a set B whose elements are exactly those elements x of A for which S(x) holds. ¶ A "condition" here is just a sentence." (Halmos 1970:6).

Suppes calls this "Aussonderung Axiom" the "Axiom schema of separation" and his version too requires "a property" that must be satisfied for the "assundering". But the nature of this "property" is unclear, in Suppes. But whatever, we can always write a Turing-machine algorithm that partitions any set of (expressible) numbers into any other two or more sets. And thereby the partitioning is a definite procedure (Zermelo 91929) says not... footnote in Suppes 1972:6).

The following is suggested by Minsky 1967:158, all that follows is my attempt to understand it better. Also if you are able, see the treatment of "function" in the Encyclopedia Britannica CD article, -- they start with rational function and develop from there.

Minsky analyzes the real numbers from the point of view of computation theory, in particular Turing machines. He suggests the use of Cauchy sequences. From there it's all down hill:

"§7.01. Functions of non-negative integers ... we will consider mainly a very special kind of rule -- namely, defining functions in terms of the behavior of Turing machines. " (Minsky 1967:158)

"9: THE COMPUTABLE REAL NUMBERS...a real number can be defined by an increasing or decreasing convergent infinite sequence of rationals. And it can be shown that, if the reals are suitably defined as equivalent classes of convergent sequences of rationals, we get the same structure as that defined by the cut method .... the definition by sequences is the method of Cauchy."(Minsky 1967:158)

The following is an attempt to understand the connection between the notion of "Turing machine", "function", and "algorithm", and "set theoretic notions e.g. of "ordered pair":

(1) We start with (one of two of) Minsky's definitions of "function" (1967:132), i.e. a Turing machine. Turing machines do algorithms. That is all they do. Some folks think of the Turing machine itself (TABLE and specifications for input-output) as the algorithm. I dunno; I'm agnostic. Minsky's other definition is the set-theoretic one. He gives examples of both, which I intend to ape when I get to it.

(3) A Cauchy sequence is a function in the set theoretic sense of ordered sequence (of ordered pairs) i.e. <a, x1, x2, ..., xn, ...> where the a and xi are all integers, and in the Minsky sense i.e. has an input and an output and some rule in between (Definitions is Suppes 1972:174) (Minsky 1967:132)

(3) A Cauchy sequence can be used to create any real number that is "algebraic"; non-algebraic numbers are "transcendental" (cf Hardy and Wright 1979:159 11.5 Algebraic and transcendental numbers). But some transcendentals can be created (calculated, computed), cf Turing 1936:142-143 where he shows that e.g. the transcendentals π and e are computable. "From (vi) we deduce that all real algebraic numbers are computable." And he proves this.

(4) Every real number is a Cauchy sequence (Theorem 43)

(5) A Cauchy sequence contains only integers (cf Suppes, Theorem 56 p. 189)

(6) A Turing machine/counter machine creates only positive integers from positive arguments; negative integers can be encoded e.g. by concatenating a "1" before its positive integer (e.g. this can be a definition, also see the next one)

(7) A Turing/counter machine can compute anything computable (Turing's Thesis cf Turing 1939), including all the primitive recursive functions such as addition of integers, subtraction of integers, products of integers and quotients (with residues) of integers (Kleene 1952:219ff). This is all the computing power that is necessary to create a Cauchy sequence.

(8) Therefore a Turing/counter machine can create any Cauchy sequence to any precision

(9) A counter machine is Turing-equivalent (Minsky 1955?, also Minsky 1967, also Boolos-Burgess-Jeffrey 2002)

(10) Therefore if a number can be created at all, by any manner shape or form, it can be created by a counter machine. And while in operation, a counter machine, like a Turing machine, is executing an algorithm' (or depending on your taste, perhaps: "is functioning as a function or perhaps: is functioning as an algorithm, or both).

Turing states that, and I believe him:

"We cannot define general computable functions of a real variable, since there is no general method of describing a real number, but we can define a computable function of a computable variable." (p. 140)

This is as far as I've been able to get in the couple days since this article spun off. I hope this answered your question.

References:

• Alan Turing 1936:116ff in Davis 1965, The Undecidable, Raven Press, Hewlett NY
• Alan Turing 1939:155ff in Davis (loc cit)
• Patrick Suppes 1972, Axiomatic Set Theory, Dover Publications, Inc. New York.
• Paul R. Halmos 1970, Naive Set Theory, Springer-Verlag, NY.
• George Boolos, John Burgess, Richard Jeffrey 2002, Computability and Logic: Fourth Edition, Cambirdge University Press, Cambridge UK.
• Marvin Minsky, 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.
• Stephen C. Kleene, 1952, 1971 6th edition, 10th impression 1991, Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam NY
• G. H. Hardy and W. M. Wright 1979, An Introduction to the Theory of Numbers: 5th Edition, Clarendon Press, Oxford UK.

wvbaileyWvbailey 19:16, 2 October 2007 (UTC)

Alternate example <Q = N/D, R> for use in talking about "inverse", etc

It may be that the example is too hard, and there is too much development in that one section, without adequate leadup/development and examples, in the earlier sections. I've run into what may be a simpler example: N - Q*D = R, or N/D = Q with remainder R, (usually presented as equivalence classes of residues). This appears in a couple places e.g. Minksy 1967 Finite and Infinite machines, Saracino 1980 Abstract Algebra: A First Course, Kleene 1952 Introduction to Metamathematics. I was going to explore how to use this on the "definition" page (actually, its talk page), but I might as well do here informally, since this will help me think it out. (We do not want talk about: "generating equivalence classes with modular division" -- abstract -- only about what happens. The example turns out to be quite rich in potential).

Let's limit our input numbers (the doman) to the natural numbers (counting numbers 1, 2, 3, etc). Now, what happens when we divide a number N ("Numerator") by a another number D (the "Divisor", the "Denominator")? We know from our arithmetic that we get "the quotient" Q and "the remainder" R. These are elementary concepts of arithmetic (I learned them in 4th grade, when I was ~10 yrs old). So, maybe, the outcomes can be used to demonstrate what happens as we create "sets" of (i) Q and R together (i.e. <Q, R>), (ii) Q alone and (iii) R alone.

[I can see that this is going to be complicated by the fact that we end up with two outputs from our so-called function, i.e. "Q" and "R". That means that, what we really have here in an algebraic sense, is two functions, one generating Q and the other generating R.]

[What the function is really be doing is a primitive recursion loop of this nature:

[Start with Q = 0. Do until N ≤ D: calculate N-D and add 1 to Q, i.e. count the number of subtractions Q. When the difference N-D ≤ D, then whatever is left is the remainder "+R": N - D - D - D - ... D = + R => N - Q*D = +R is actually what is being computed. In the real machine, N is being decremented-by-one, and there is some "remainder-management" going on. But the recursion does not end until N = 0, i.e. it has to decrement all the way to 0 in order to get rid of the residue too. N -Q*D -R =0 is what stops the recursion.]

[The extension-article's talk page displays this function Q (and the easy-to-come-by R) as a counter machine. In what follows, this function-as-machine is assumed, thus explaining the somewhat preculiar output when D > N, e.g. why 6/8 = <0,6>, 6/9 = <0,6>, etc. Keep in mind that the domain is the counting numbers and the simple output range will also be counting numbers and 0. This is going to create some interesting results.... as shown below.]

[As I've worked on this I have found another fly in the ointment. From a machine that generates : <Q, R> = N/D as described above (i.e. by repeated subtraction), why would we believe that we also express what it is doing in algebra as " N - Q*D -R =0 ", or, solving for D: (N - R)/Q = D, or solving for Q: (N - R)/D = Q ?? I have to go away and work on this ... but I shall persevere ...]:

In the end, after we plug a bunch of D's into our "function" (aka counter machine) we have a collection of ordered pairs <Q, R>, i.e. the quotient Q is the first coordinate and the remainder R is the second coordinate (for no good reason excepting I felt like it). These values are related to the arguments D and N via "the function" (aka counter machine).

In the following examples, we will hold N steady as "the parameter" equal to 6 and let D (aka "the variable") "range through the domain" (!) [here, => is actually logical implication]:

Here we see one method of displaying a function -- as a table.

Argument			OUTPUT value
INPUT variable	parameter		Q=INT(N/D)
Denominator	Numerator		Quotient	Remainder
D	N		Q	R
1	6		6	0
2	6		3	0
3	6		2	0
4	6		1	2
5	6		1	1
6	6		1	0
7	6		0	6
8	6		0	6
9	6		0	6
10	6		0	6

Here is another way to display the information, as a set of ordered pairs. The bad news is this will smoother us in definitions. But there's nothing scary here, just definitions. The first element e.g. input D is called the first coordinate or the "x-coordinate", the output ordered pair <Q,R> is called the second coordinate or the "y-coordinate". The collection of all the D's is called the universe of discourse or the unrestricted domain. We might assume, not knowing any better before we start but knowing a bit about counter machines, guess that the output will fall into what is called the codomain, the collection of all the possible ordered pairs of all the integers <q,r> (ω x ω of them, a really big number). Note that the ordered pairs e.g. <d,<q,r>> need not be listed in any particular order:

Example N=6: { <D,<Q,R>> } = { <1, <6,0>>, <2,<3,0>>, <3,<2,0>>, <4,<1,2>, <5,<1,1>>, <6,<1,0>>, <7,<0,6>>, <8,<0,6>>, <9,<0,6>>, <10,<0,6>>, ..., etc }

domain = { all the natural numbers }, range = { <6,0>, <3,0>, <2,0>, <1,2>, <1,1>, <1,0>, <0,6> }

Thus when we plug "4" into the D-place of our machine after a while we get out Q=1 and R=2, and we write this <4,<1,2>>.

To make a more convincing presentation on a graph, we might want to mush the Q and R into a single entity, i.e. concatenate them with a "pipe" | beween them so that the string of symbols e.g. q|r is to be considered a single "output" equivalent to <q, r>. Now we can graph the outputs q|r on a Cartesian plane as a function of the inputs d. If we do this, we end up with an (infinite) set of ordered pairs:

Example N=6: { <D,Q|R> } = { <1, 6|0>, <2, 3|0>, <3, 2|0>, <4, 1|2>, <5, 1|1>, <6, 1|0>, <7, 0|6>, <8, 0|6>, <9, 0|6>, <10, 0|6>, . . . etc }

Domain = { all the natural numbers }, range = { 6|0, 3|0, 2|0, 1|1, 1|0, 0|6 }

A Non-invertible function:

Will this N/D business "invert" so we can recover our N and D? Or to state the question as Saracino does:

"The idea of the inverse function is to undo everything f did." (Saracino 1980:62)

NO! We cannot undo everything that our function does. All but a few (i.e. all but 6) of the arrows point from a number D to the same symbol 0|6. In other words, we could partition our function-set into two classes, one of which contains all those with the symbol 0|6 in the range:

Example, N = 6: { <D,Q|R> } = { <1, 6|0>, <2, 3|0>, <3, 2|0>, <4, 1|2>, <5, 1|1>, <6, 1|0> } ∪ { <7, 0|6>, <8, 0|6>, <9, 0|6>, <10, 0|6>, ..., etc }

Only a few elements of the domain { 1, 2, 3, 4, 5, 6 } point to non-0|6 symbols. The rest i.e. { 7, 8, 9, 10, ..., etc } mess things up. To see this, we create the converse of the whole mess, that is, we swap the first and second coordinates of each ordered pair to make a new set. When we do, we see that input 0|6 is pointing at a bunch of output elements { 7, 8, 9, 10, ..., etc }, i.e. { <6|0, 7>, <6|0, 8>, <6|0, 9>, <6|0, 10>, ..., etc } . Given the input <q|r> = 6|0, we could have any of these outputs simultaneously { 7, 8, 9, 10, ..., etc}. Feel free to take your pick: pick one, pick all, pick a few. This is NOT a function, by definition.

Restricting the domain to a "domain of definition":

What to do? We restrict our domain to a subset of the natural numbers (i.e. the "defined domain", the domain of definition ) that yields what we hope to be a function that is invertible:

Example N=6: domain of definition = { 1, 2, 3, 4, 5, 6 } and { <D,Q|R> } = { <1, 6|0>, <2, 3|0>, <3, 2|0>, <4, 1|2>, <5, 1|1>, <6, 1|0> }

Will our our function Y = 6/D invert for all these values? Find the converse function. It does seem to be 1-1.

:The converse function: { <Q|R, D> } = { <6|0, 1>, <3|0, 2>, <2|0, 3>, <1|2,4>, <1|1, 5>, <1|0, 6> }  

Can we demonstrate this convincingly? NO.

[But why this is the case is really peculiar ... I need to work on this! ... It does as long as Q is not 0. Thus we find that our domain must be further restricted if the function is to invert (!) ]

Example: Given 1|2, can we recover a unique number D? (i.e. given <Q, R> = <1, 2> what do we get for divisor D? It should be "4". (The rules of algrebra allow us to derive" the formula (N - R)/Q = D):

Let N = 6, Q = 1, R = 2

YES: (6 - 2)/1 = 4, which is indeed where we started: i.e. 6/4 => <Q=1, R=2>

[But observe, to do our algebra thing. . . we are relying on a whole bunch of theorems of "formal number theory", in particular the notions of "multiplicative inverse" and the "additive inverse":

"*132. a+c = b+c => a=b. *133. c≠0 => (ac=bc => a=b)." (Kleene 1952:186) ]

Neglect commutation and distribution:

Start with N - Q*D -R = 0

Why this? We have not discussed why this is true. But this "testing equality to 0" business is how we escaped from the recursion and halted the function.

Additive inverse: add +Q*D to both sides: N -Q*D +Q*D +R =0 +Q*D; -Q*D+Q*D = 0, therefore, N -R = 0+Q*D

Additive identity: 0+Q*D = Q*D, therefore N -R = Q*D

Multiplicative inverse: (N - R)*(1/Q) = Q*(1/Q)*D => (N - R)/Q ; Q*(1/Q)=1, as long as Q ≠ 0.

Multiplicative identity: (N - R)/Q = 1*D => (N - R)/Q = D

Here's the rub: Given N = 6, Q = 0, R = 6 can we recover D? NO!

(N - R)/Q = D => (6 - 6)/0 = 0/0 = 1??

This means that we must further restrict our domain to the numbers D = { 1, 2, 3, 4, 5 } if we want the function to invert.

Given N = 6: { <D,Q|R> } = { <1, 6|0>, <2, 3|0>, <3, 2|0>, <4, 1|2>, <5, 1|1> } is an invertible function.

More Non-invertable functions:

Ignore this niggling little presentation-peculiarity and bravely soldier on: What happens if we dispose of the remainders R and keep our restricted domain 1 to 5 (inclusive)? In other words, we now have a function such as this with a doubly-restricted domain:

Q = INTEGER(N/D) given D = { 1, 2, 3, 4, 5 )

Example N = 6: { <D,Q|R> } = { <1,6|0>, <2,3>, <3,2>, <4,1>, <5,1> }

Or, dispose of the quotient Q (the so-called "modulus" function, aka MOD) and then see what happens:

R = MOD(N/D)

Example N = 6: { <D,Q|R> } = { <1,6|0>, <2,0>, <3,0>, <4,2>, <5,1> }

NO! In both examples we cannot recover the D that we started with. As before, we see the failure just as soon as we swap the coordinates of the function. For example in the MOD example if, in each ordered pair, we were to swap the x-coordinate and the y-coordinate (aka the first- and second-coordinates) so that we write the ordered pairs backwards, i.e. <5,1> => <1,5> we have created what is called the converse relation. And we would end up with:

Example N = 6, { <Q,INTEGER(N/D)> } = { <6,1>, <3,2>, <2,3>, <1,4>, <1,5> }

YIKES! Specify Q=1, we can have ... ohh, ohh: INTEGER(N/D) = { 4, 5 } ! Take your pick. We no longer have a function!

Example N = 6: { <R,MOD(N/D)> } = { <R,D> } = { <0,1>, <0,2>, <0,3>, <2,4>, <1,5> }

YIKES! Specify R=0, we can have ... ohh, ohh: MOD(N/D) = { 1, 2, 3} ! Take your pick. We no longer have a function!

Partial functions, incompletely defined functions, total functions:

The above example also shows what happens when we attempt to divide by 0. What the counter-machine does is produce increasing numbers ad infinitum, i.e. it never halts. This is as it should be. Because, for any N we choose (e.g. a really big N) and D = 1, we expect N/D = N/1 = N to be a really big number. Thus this is a partial function (by definition all functions are) but also an "incompletely defined function" i.e. not defined at D=0. Thus it is not a "total" function when we extend the domain of definition to the positive _integers (i.e. including 0), or even if we restrict our domain of definition to { 0, 1, 2, 3, 4, 5 } (cf Kleene 1952:325).

--- end of example ---

The "R" residue/remainder part of the example is used by Minsky:

"Perhaps the most usual definition [of a function] is something like this:

A function is a rule ...

"For example, suppose the rule that defines a function F is "the remainder when the argument is divided by three". then (if we consider only non-negative integers for arguments) we find that

"F(0) = 0, F(1) = 1, F(2) = 2, F(3) = 0, F(4) = 1, etc.

"Another way mathematicians may define a function is

"A function is a set of ordered pairs <x, y> ...

"If we think of a function in this way, then the function F above is [observe italics] the set of pairs

{ <0,0>, <1,1>, <2,2>, <3,0>, <4,1>, <5,2>, <6,0>, . . . }

Is there any difference between these definitions? Not really, but there are several fine points. [etc]" (Minsky 1967:132-133)

Saracino begins his chapter 7 FUNCTIONS with the following, then by chapter 9 gets to EQUIVALENCE RELATIONS: COSETS:

"DEFINITION If S and T are sets, then a function f from S to T assigns to each s∈S a unique f(s)∈T.

"As a definition this is somewhat strange,in that it tells you what a function does rather than what it is. Sometimes this difficulty is avoided by saying that function is a "rule" ... but this isn't any better because "rule" isn't defined." (Saracino 1980:59)

Kleene 1952 states this about functions:

"We have described a function as a many-one correspondence. One may go further in saying what a many-one correspondence is to be, according to the kind of theory one is working in. In set-theoretic terms, the correspondence can be identified with the set of all the ordered pairs (x, y) of corresponding elements X and Y₁ [Y₁ was previously defined as "the range of the dependent variable y" or f(x) is the subset Y₁ of Y comprising the elements of Y used in the correspondence..."]. One may speak instead of the law or rule establishing the correspondence, at least in dealing with such functions that a law or rule in some understood sense can be given for each function. In the case that X is a finite set, a function can be given as a table.

"EXAMPLE 4. Let X and Y both the re residues modulo 2, i.e. X = Y = { 0, 1 }. The functions x' [successor] and x*y can be defined by the following tables ... [they look just like Karnaugh maps]." (Kleene 1952:32-35).

wvbaileyWvbailey 01:31, 4 October 2007 (UTC)

What is (and what should be) this article?

To paraphrase Dedekind's Was sind und was sollen die Zahlen?

What I see here is a essay, with little effort to consolidate into a plausible article History of definitions of function (mathematics).

The only part that I can see that would belong in an article function (mathematics) definitions, is something like the following

The term function, in mathematics may mean one of the following:

(1) A relation (mathematics) such that for every element of the domain there is exactly one associated element in the codomain.

(2) A primitive recursive function.

(3) A recursive function.

(4) A function (1) computable by an algorithm.

(5) A function (1) computable by a Turing machine.

(6) A function (1) which is also definable.

(7) A function (1) which is also definable.

We could add commentary on partial functions and multivalued functions, and possibly "provable functions", but I don't see the article going anywhere.

In any case. this fails WP:DICT, rather than being a valid disambiguation page. — Arthur Rubin | (talk) 18:10, 5 October 2007 (UTC)

RE essay: This is a work in progress, started about 3-4 days ago. Last night I was so discouraged I truly thought I would wake up this AM and trash it, 'cept I don't know how to go about doing it. But in the AM I was a little less discouraged. It is indeed drifting, in part because of the dialog on the other page. At this point I am using an informal style, but you do notice that at least here, someone is adding footnotes and citations, and will continute to, until its full of them. (Novel idea that one is). It was, until I stupidly took out the / mark (as in Function (mathematics)/definitions, sort of a quasi-private page. On the other hand, suggestions and criticisms are good. Since it doesn't link into the Function (mathematics) article at all this page is in a kind of limbo and I figured it shouldn't offend anyone. Should I put back the /? I really should move it into my own "domain" 'cept I don't know how. And if it doesn't have content and links, a 'bot will trash it.

RE your list. I would argue that list is one of the things I want to see go into the main article Function (mathematics). I think it's pretty damn good (caveat: it could use some sort of introductory development).

RE renaming this article: I don't have a problem with that at all.

RE where this "essay" is going (today, tomorrow may be another story): One thought is to call it: "Function (mathematics) characterizations". What I am exploring (as of this day, today) is how, in the various theories of mathematics: recursion theory, computation theory, number theory, abstract algebraic theory, set theory, any other theories anyone wants to add, etc. have developed, used and continue to use, the notion of "function." Here's an example: in Hardy and Wright 1938, 1979 An Introduction to the Theory of Numbers: 5th edition, the word "function" just magically appears on p. 6, without development or definition. The set-theoretic words "domain", "range", and all the rest, aren't even mentioned. In Godel-Kleene's development of formal number theory, from a different set of axioms than those of set theory (damnit this point is so important!), the word "function" is used with respect to two, and only two, operator-symbols + and * . What are effectively the Peano axioms develop these notions (by their behaviors). In other words, you can start with different axioms that are not the set theoretic axioms and develop the behavioral-notion of function in any number of different ways. Set theory has "infected" the rest of mathematics with all of its definitions and notions, because, as stated on the page, it is effective i.e. it gives us reassurence (I need a quote to back that up, and may trash it if I can't find it; I'vre read it somewhere...).

wvbaileyWvbailey 19:40, 5 October 2007 (UTC)

Move it to a sub-page of your user page until/unless you can turn it into an encyclopaedia article. At the moment it needs a lot of work. There is far too much use of the second person, and phrases such as "the reader had better be able to read English" do not belong in an encyclopaedia article. Gandalf61 08:26, 6 October 2007 (UTC)