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.

Domain, Codomain, and Image

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


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\).




  • Mathematics

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