5
$\begingroup$

I was wondering if there is a system of mathematics where everything (except sets) is a function.

For example, 3 would be the 3 function $x \mapsto 3$.

There would be basic operators, such as $+$, $\times$, and $\circ$.

As a concrete example, the derivative $D$ would be defined

$$D = \left(f\mapsto \lim_{h\in \mathbb{k},h\to 0} \dfrac{f\circ(x\mapsto x+h)-f}{h}\right)$$

where $\mathbb{k}$ is the set of constant functions $f\in\mathbb{k}\leftrightarrow f\circ x = f\circ y\;\forall x\forall y$

$\endgroup$
9
  • 1
    $\begingroup$ Category theory is probably the closest thing to this out there, although at the foundational level it doesn't actually work quite like this. $\endgroup$
    – Ian
    Commented Jan 2, 2015 at 5:52
  • 1
    $\begingroup$ Hey, why not make sets functions too. Everything that is contained in the set is mapped to true and is false otherwise. $\endgroup$
    – dalastboss
    Commented Jan 2, 2015 at 7:03
  • 1
    $\begingroup$ You could use an arrows only approach to category theory. You could also look at the lambda calculus. $\endgroup$ Commented Jan 2, 2015 at 7:04
  • 1
    $\begingroup$ In untyped lambda calculus, everything is a function. (There are no sets!) $\endgroup$
    – Zhen Lin
    Commented Jan 2, 2015 at 7:43
  • $\begingroup$ This sounds a lot like the programming language "LITHP". LITHP ith thaid to be utheful in prothething lithtth. $\endgroup$
    – John Joy
    Commented Jan 2, 2015 at 16:39

1 Answer 1

5
$\begingroup$

As @Ian pointed out in the comments, this is exactly how people think in the branch of math called category theory. A category is a kind of mathematical gadget that captures the very general ideas of "things" and "doing stuff." It consists of two parts:

  • A collection of objects, which represent types of things.
  • For each pair of objects $A$ and $B$, a collection of arrows, which represent processes that turn things of type $A$ into things of type $B$. An arrow $f$ from $A$ to $B$ is sometimes abbreviated as $f \colon A \to B$.

The behavior of arrows is modeled on the behavior of functions. For example:

  • Every category comes with a rule for composing processes, combining an arrow $f \colon A \to B$ and an arrow $g \colon B \to C$ into an arrow $g \circ f \colon A \to C$.
  • Every object in a category has an identity arrow, which acts like the identity function.

Practically all of the tools mathematicians use (sets and functions, variables and equations, shapes and transformations, statements and proofs, data and code...) can be fruitfully thought of as part of a category. Some would even say that categories encompass all known mathematics. And arrows are totally fundamental in category theory—so fundamental, in fact, that you can forget about objects entirely, and just do everything in terms of arrows. So, I think category theory is a great example of a system of mathematics where everything is a (generalized) function.

To see this point of view in action, I highly encourage you to check out Tom Leinster's paper "Rethinking set theory", which describes a way to express the foundations of set theory in functional terms. The approach he uses was originally discovered by category theorists trying to understand what's so special about sets and functions from a categorical perspective.


A familiar example of a category, and a good place to explore some of the ideas you describe, is the category called FinSet. Its objects consist of all finite sets. The arrows from set $A$ to set $B$ are the functions from $A$ to $B$, and the composition of arrows is just plain old composition of functions.

Just as you suggested, an easy way to describe an element of a set $A$ is to give a function from the one-element set $\{\bullet\}$ to $A$. For example, the function from $\{\bullet\}$ to $\{\Box, \heartsuit, \diamondsuit\}$ that sends $\bullet$ to $\heartsuit$ describes the element $\heartsuit$.

Like @dalastboss poitned out, you can also describe subsets as functions: a subset of $A$ is described by a function from $A$ to $\{0, 1\}$ that sends everything in it to $1$ and everything not in it to $0$.

Ready for a more powerful trick? Cartesian products of sets can be described in totally functional terms. The product $X \times Y$ is characterized by the special properties of its projection functions, $$\begin{align*} p_X \colon X \times Y & \to X & p_Y \colon X \times Y & \to Y \\ (x, y) & \mapsto x & (x, y) & \mapsto y \end{align*}$$ Given two functions $f \colon A \to X$ and $g \colon A \to Y$, you can define the function $(f, g) \colon A \to X \times Y$ that sends $a$ to $(f(a), g(a))$ in terms of function composition: this function is completely determined by the way it composes with $p_X$ and $p_Y$.

How about some clock arithmetic? Let's define $\mathbf{5}$ to be the set $\{0, 1, 2, 3, 4\}$, and define functions $+$ and $\cdot$ from $\mathbf{5} \times \mathbf{5}$ to $\mathbf{5}$ which carry out clock addition and multiplication. Clock numbers are elements of $\mathbf{5}$—that is, functions from $\{\bullet\}$ to $\mathbf{5}$. Given two numbers $x \colon \{\bullet\} \to \mathbf{5}$ and $y \colon \{\bullet\} \to \mathbf{5}$, you can produce the function $(x, y) \colon \{\bullet\} \to \mathbf{5} \times \mathbf{5}$ as described above, and then compose it with $+$ to get a function $$+ \circ (x, y) \colon \{\bullet\} \to \mathbf{5}.$$ This function describes a new clock number—the sum of $x$ and $y$.

Since $\mathbf{2} = \{0, 1\}$, basic logical operations can be described by functions like ${\scriptstyle\text{AND}}$ and ${\scriptstyle\text{OR}}$ from $\mathbf{2} \times \mathbf{2}$ to $\mathbf{2}$. (Weirdly enough, ${\scriptstyle\text{AND}}$ is the same as $\cdot$, the clock multiplication function.) You can use these to do Boolean operations on subsets! Given two subsets $r \colon A \to \mathbf{2}$ and $s \colon A \to \mathbf{2}$, you can compose $(r, s) \colon A \to \mathbf{2} \times \mathbf{2}$ with ${\scriptstyle\text{AND}}$ to get a function $${\scriptstyle\text{AND}} \circ (r, s) \colon A \to \mathbf{2}.$$ This function describes a new subset of $A$—the intersection of $r$ and $s$.

Now, let's go meta and think about the set of functions between two sets. The set of functions from $A$ to $B$ is usually written $B^A$. Just like you suggested, you can take sums and products of number-valued functions. For example, given two functions $f \colon A \to \mathbf{5}$ and $g \colon A \to \mathbf{5}$, you can define their sum $[f + g] \colon A \to \mathbf{5}$ as the function $+ \circ (f, g)$. You can think of the sum and product operations as functions between sets of functions. Specifically, they're functions $+$ and $\cdot$ from $\mathbf{5}^A \times \mathbf{5}^A$ to $\mathbf{5}^A$.

A subset of $A$ is a function from $A$ to $\mathbf{2}$, which is an element of $\mathbf{2}^A$. Hey, how many elements does $\mathbf{2}^A$ have? Coincidence?

You wrote down an awesome definition of the derivative operator. We can't get that sophisticated in FinSet, but we can do something almost as cool: we can define the forward difference operator $D$, which sends a function $f$ to its "discrete derivative" $n \mapsto f(n + 1) - f(n)$. There's a forward difference operator for every set of functions from numbers to numbers. If we're working with functions $f \colon \mathbf{24} \to \mathbf{5}$, for example, the forward difference operator will be a function $D \colon \mathbf{24}^\mathbf{5} \to \mathbf{24}^\mathbf{5}$. Using sophisticated tools and a few shots of dizzying self-reference, we could probably construct $D$ from the functions we already have. I'm dizzy enough as it is, though, so I'll stop here.

$\endgroup$
2
  • $\begingroup$ Thank you, that was one of the best answers I have seen recently and certainly the best I have ever received. $\endgroup$
    – k_g
    Commented Jan 18, 2015 at 2:01
  • $\begingroup$ Aww, thanks, I'm glad you like it! #^_^# If you also like the stuff people mentioned about the lambda-calculus, you might enjoy learning about the relationship between functional programming and category theory. The lecture notes from Samson Abramsky's course on "Categories, Proofs, and Processes" look like a great place to find out more, although you may need to get a lot more comfortable with category theory before you can read them. Abramsky's notes are currently available at math.helsinki.fi/logic/sellc-2010/course, in the files LectureI.pdf through LectureV.pdf. $\endgroup$
    – Vectornaut
    Commented Jan 18, 2015 at 2:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .