Set Exponentiation

Exponentiation is the operation of multiplying the same element by itself a given number of times. Defined by the relation y^x = y⋅y^{x − 1}, it can be evaluated by multiplication until y¹ is encountered, which is just y. It can then be extended to rational numbers by solving an equation, then to the real numbers by the limit of a sequence, then to complex numbers by Euler's formula. Complex exponentiation is one of the most pervasive operations in all of mathematics. It can express all trigonometric functions such as sin, cos, tan, sec, csc, cot, and so on. It can express powers, polynomials, power series, Fourier series (with the help of addition), and much more. Simply put, it's everywhere.

Exponentiation can even be extended to matrices with the help of the equation Y^X = exp(log(Y)X) for square matrices, where exp and log are defined in terms of the usual power series. Exponentiation can also be extended to sets by noticing that the cardinalities of the domain |X| and codomain |Y| of a function, give |Y|^|X| = |Y^X| when exponentiated. This is the idea behind the notation of a power set (denoted 2^X), which can be thought of as the set of all functions from X to a boolean (which represents whether or not it is contained). This is illustrated by the following maps in JSON syntax:

• {"a": 0, "b": 0, "c": 0}
• {"a": 0, "b": 0, "c": 1}
• {"a": 0, "b": 1, "c": 0}
• {"a": 0, "b": 1, "c": 1}
• {"a": 1, "b": 0, "c": 0}
• {"a": 1, "b": 0, "c": 1}
• {"a": 1, "b": 1, "c": 0}
• {"a": 1, "b": 1, "c": 1}

Clearly, the number of such functions is 8, the cardinality of the domain is 3, and the cardinality of the codomain is 2, and we all know 2³ is 8. Following this to its logical conclusion, we arrive at a justification for currying. Currying is the concept that a function of two variables that returns a value is the isomorphic to a function of one variable that returns a function of one variable that returns a value. In set-theory notation this would be Z^X×Y = (Z^Y)^X, and in Haskell notation this would be X -> Y -> Z. So just as complex exponentiation is everywhere in Mathematics, so too is set exponentiation everywhere in most computer programming languages, whether or not they recognize the concept of currying. With this in mind, if the theory of algebraic datatypes includes type exponentiation, then pretty much all functions are accounted for. This is the approach that the Z notation specification language, because it defines functions as equivalent to their relations. In other words f(x) = y iff (x, y) is a member of f. To illustrate how set exponentiation characterizes many concepts in programming languages, here is a list of common structures:

• 2^X - Predicates - functions that return a boolean.
• X² - If/Then/Else - functions from booleans to a value.
• Xⁿ - Switch/Case - functions from an enumeration to a value.
• Y^X - Unary Functions - functions from any value to any value.
• X^X - Unary Operations - functions from a value to a value.
• X^X2 - Binary Operations - functions from two values.
• X^Xn - n-ary Operations - functions from many values.
• 2^X2 - Binary Relations - also called multi-functions.
• 2^Xn - n-ary Relations - also called multi-functions.

This is quite a vast array of functions, which cover most basic structured programming concepts like if/then/else and switch/case. But there is one more: X^XX. What does this stand for? Well, conceptually, it takes a Unary Operation over X, and gives a value from X. This is exactly what happens when you evaluate a function at a value, which means the "evaluate at 0" function is in X^XX. What's more, is that this is the beginnings of a set-theoretic Tetration (my other website), which I could talk about for hours, but I will save it for another time.