# Function

In­tu­itively, a func­tion $$f$$ is a pro­ce­dure (or ma­chine) that takes an in­put and performs some op­er­a­tions to pro­duce an out­put. For ex­am­ple, the func­tion “+” takes a pair of num­bers as in­put and pro­duces their sum as out­put: on in­put (3, 6) it pro­duces 9 as out­put, on in­put (2, 18) it pro­duces 20 as out­put, and so on.

For­mally, in math­e­mat­ics, a func­tion $$f$$ is a re­la­tion­ship be­tween a set $$X$$ of in­puts and a set $$Y$$ of out­puts, which re­lates each in­put to ex­actly one out­put. For ex­am­ple, $$-$$ is a func­tion that re­lates the pair $$(4, 3)$$ to $$1,$$ and $$(19, 2)$$ to $$17,$$ and so on. In this case, the in­put set is all pos­si­ble pairs of num­bers, and the out­put set is num­bers. We write $$f : X \to Y$$ (and say “$f$ has the type $$X$$ to $$Y$$”) to de­note that $$f$$ is some func­tion that re­lates in­puts from the set $$X$$ to out­puts from the set $$Y$$. For ex­am­ple, $$- : (\mathbb N \times \mathbb N) \to \mathbb N,$$ which is read “sub­trac­tion is a func­tion from nat­u­ral num­ber-pairs to nat­u­ral num­bers.”

$$X$$ is called the do­main of $$f.$$ $$Y$$ is called the codomain of $$f$$. We can vi­su­al­ize a func­tion as a map­ping be­tween do­main and codomain that takes ev­ery el­e­ment of the do­main to ex­actly one el­e­ment of the codomain, as in the image be­low.

Talk about how they’re a pretty dang fun­da­men­tal con­cept. Talk about how we can think of func­tions as mechanisms. Add pages on set the­o­retic and type the­o­retic for­mal­iza­tions. Talk about their re­la­tion­ships to pro­gram­ming. Talk about gen­er­al­iza­tions in­clud­ing par­tial func­tions, mul­ti­func­tions, etc. Give some his­tory, e.g. Church-Tur­ing, Ack­er­man, re­cur­sion, etc. (Many of these to­dos should go into sep­a­rate lenses; this defi­ni­tion here might be fine?)

# Examples

There is a func­tion $$f : \mathbb{R} \to \mathbb{R}$$ from the real num­bers to the real num­bers which sends ev­ery real num­ber to its square; sym­bol­i­cally, we can write $$f(x) = x^2$$.

(TODO)

Children:

Parents:

• Mathematics

Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.

• Oog, I wrote a page about func­tions at /​p/​3vp be­cause it didn’t oc­cur to me that this page would be named differ­ently…

• Sorry :-p /​p/​3vp seemed too gen­eral a name for me back when I was first writ­ing this, though I think /​p/​3vp is prob­a­bly ac­tu­ally just fine. I sug­gest you merge the two and do what you want with them. (Right now I like my in­tro bet­ter than yours, but I might be bi­ased :-p)