I’m sure you know how to add and multiply counting numbers, but did you ever add or multiply sets of things? Did you ever raise one set of things to the power of another set of things?
If you never did, you should. These things are fun, and fun is good. And, if you’ve ever wondered what 00 means and why, this essay will help you understand why so many mathematicians and computer scientists reject the wishy-washiness of the calculus convention “00 is indeterminate”1 and embrace the forthright (if puzzling) equation 00 = 1.
Drawing by Ben Orlin. Check out his website https://mathwithbaddrawings.com
First, though, I’ll mention a few things that this essay is not about.
If two lists of numbers have the same size, say size ten, you could add the nth number from the first list to the nth number from the second list as n goes from 1 to 10 and then record all those sums in a new list of ten numbers. This is a useful thing to do; in fact, it’s an example of what’s called vector addition, as described in my essay Vectors from Leibniz to Einstein. But this operation requires that what we’re adding are lists. And sets (the things we want to add and multiply today), unlike lists, don’t come with some notion of “1st element”, “2nd element”, and so on. Besides, I want a way to add two sets that aren’t necessarily the same size.
Another thing this essay is not about is the game where you form all possible sums a+b where a comes from the first set you’re given and b comes from the second set you’re given and you collect all those sums a+b to form a new set. For instance, if you form all possible sums a+b where a is 1, 2, or 3 and b is 4 or 5, you get the counting numbers from 5 to 8. That is, {1, 2, 3} + {4, 5} = {5, 6, 7, 8}. Here the curly brackets tell us that thenumbers 1, 2, and 3 are being grouped together to form a set, and likewise for 4 and 5, and the plus-sign is not ordinary number addition but a new operation that we could call number-set addition. We can define number-set multiplication in a similar way: {1, 2, 3} × {4, 5} = {4, 5, 8, 10, 12, 15}. These operations on sets of numbers are interesting because of the way the sizes of the new sets can vary. For instance, can you come up with a set S that has three elements and a set T that has two elements so that the number-set sum S + T has six elements and the number-set product S × T has only four (the opposite of what we saw with {1,2,3} and {4,5})? See Endnote 2 for one solution.2 To know the size of S + T or the size of S × T when + and × are defined this way, it’s emphatically not enough to know the sizes of S and T individually, and a thriving topic of current research is the project of understanding what sorts of conditions cause S + T or S × T to be smaller than expected, and understanding the extent to which the conditions that make S + T small tend to make S × T large and vice versa.
But what I’m writing about today is a way of adding and multiplying sets that allows us to predict the sizes of S + T and S × T just from knowing the sizes of S and T. In fact, in this game, the size of S + T is the size of S plus the size of T, while the size of S × T is the size of S times the size of T. Even exponentiation will join the game. And we don’t need the elements of the sets S and T to be numbers. We just need S and T to be sets.3
STICKING SETS TOGETHER
The kind of set-addition I’m telling you about today is written as ∪ rather than + and is called the union of the two sets. The union of {1, 2, 3} (a set with 3 elements) and {4,5} (a set with 2 elements) is {1,2,3,4,5} (a set with 3 + 2 = 5 elements). If we write |S| to represent the number of elements of the set S, then we have |{1,2,3} ∪ {4,5}| = |{1,2,3,4,5}| = 5 = 3 + 2 = |{1, 2, 3}| + |{4, 5}|.
Now, you might be thinking about the case in which the two sets we’re union-ing (let’s call them S and T) have some elements in common; in that case, |S ∪ T| will be less than |S| + |T|. There are two ways to handle this. One way is to shrug and say that the formula |S ∪ T| = |S|+|T| is only guaranteed to hold when the two sets S and T are disjoint (have no elements in common). A different route is to define a new operation ⊔ that forces the two sets to be disjoint by cloning the elements the sets have in common; for instance, {1, 2, 3} ⊔ {2, 3, 4} has six elements because we make extra copies of the numbers 2 and 3. This new operation is called the disjoint union of the two sets. To keep things simple, I’ll avoid the disjoint union operation and I’ll stick to union-ing sets that are already disjoint.4
Notice that the operation of taking the union of two sets doesn’t require the sets to be sets of numbers. We could let S be {box, house, car} and T be {fox, mouse}, so that S ∪ T is the set {box, house, car, fox, mouse}. I remind you that sets don’t come equipped with any specific ordering (1st, 2nd, etc.), so the set {box, house, car, fox, mouse} is the same set as the set {box, fox, house, mouse, car}. But sets aren’t the only way math lets you combine elements to form some sort of larger whole. In fact, in computer science, it’s more natural to use ordered collections because of the way computer memories work: putting the number 17 into one memory location and the number 23 into another memory location is different from putting 23 in the first location and 17 in the second. When order matters, mathematicians typically use parentheses to group items together; so (17, 23) is a different ordered pair from (23,17), even though {17,23} and {23,17} are the same set (or, if you prefer, two different ways to write the same set). You’ve seen ordered pairs before if you ever learned Cartesian geometry, since ordered pairs of numbers are used to name the points in the plane. (17, 23) is the point that’s 17 units to the right of the origin and 23 units above the origin, which is different from the point that’s 23 units to the right of the origin and 17 units above the origin.
IN A HOUSE, WITH A MOUSE
This gimmick of forming ordered pairs gives us a way of multiplying sets that has the desirable property that |S × T| equals |S| × |T|. We’ll define S × T as the set of all ordered pairs (s, t) where s is any element of S and t is any element of T. For instance, {1,2,3} × {4,5} is {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}. If we depict ordered pairs of numbers as points in the plane, then we can illustrate the product like this:
This kind of product of two sets (often called their Cartesian product) has the quirky feature that S × T is different from T × S (in contrast to ordinary number-multiplication, which is commutative), but we can live with that, especially since there’s a natural correspondence between the set S × T and the set T × S: just swap the two elements of each ordered pair, turning (s, t) into (t, s) and vice versa. We write S × T ≈ T × S to signify that even though the two sets are technically different, there’s a natural way to correspond the elements of each set with the respective elements of the other. Another virtue of our definition of set-multiplication is that it’s distributive over addition: if S, T , and T′ are sets with T and T′ disjoint, S × (T ∪ T′) = (S × T) ∪ (S × T′). Pictorially:
In the left panel, the upper rectangle is S × T and the lower rectangle is S × T′; the big rectangle in the right panel is S × (T ∪ T′).
With Cartesian set-multiplication, the empty set (the set with no elements)5 has the “absorbing property” (just as the number zero does in number-multiplication): if we write the empty set as { }, S × { } is { }. Why should this be? Well, in how many ways can you create an ordered pair (s, t) with s belonging to S and t belonging to { }? None, because there are no such elements t! So no such ordered pairs exist. Likewise, { } × S is { }. That’s what it means to say that the empty set has the absorbing property for set-multiplication. Also, the empty set has the “neutral property” (aka “identity property”) for the set-theory version of addition: S ∪ { } and { } ∪ S are both S. So in this analogy, the set containing zero elements, aka the empty set, serves as an analogue of the number zero. (For more about the empty set, see my essay The Null Salad.)
Just as in the case of forming the union of two sets, forming the Cartesian product of two sets doesn’t require that the elements of those sets be numbers. If S is {box, house, car} and T isf {fox, mouse}, S × T is the set {(box, fox), (box, mouse), (house, fox), (house, mouse), (car, fox), (car, mouse)}. These are all the different ways you can dine on green-eggs- and-ham in some location with some dining companion if you want to eat them in a box, in a house, or in a car and you want to eat them with a fox or with a mouse. Combinatorics (the kind of math I do) begins with the observation that if you have m ways to make a first choice and then n ways to make a second choice, the number of ways to make a first choice followed by a second choice is m times n. You don’t have to list all the elements of S × T to figure out |S × T|; it’s enough to determine |S| and |T| and multiply those two numbers. Combinatorics is in large part the study of the ways you can avoid counting-by-listing by using arithmetic instead (that is, by counting-by-thinking). And it starts with |S × T| = |S| × |T|.
POWERING UP
We’ll now define a kind of set-exponentiation via the concept of a function. A function can be viewed as an input-output machine that accepts as input elements of some set S and produces as output elements of some other set T. (I write “some other set T” because for now you should think of T as being different from S, although we’re allowed to have S and T be the same set.) Let’s take S = {1,2,3} and T = {4,5}. A function from {1,2,3} to {4,5} is a machine – a black box (or a box of any color you like) – that accepts 1, 2, and 3 as allowed inputs and produces 4 and 5 as allowed outputs. One behavior such a machine could have is that it always outputs 4 (regardless of what the input is); another behavior would be to always output 5; another behavior would be to output 5 when the input is 1 or 3 and to output 4 when the input is 2; and so on.
If I sell you a function-machine with input-set (or “domain”) {1,2,3} and output-set (or “codomain”) {4, 5}, and you get buyer’s remorse, you can only get your money back if you can show that some particular input in the set {1, 2, 3} fails to cause the machine to deliver an output in the set {4, 5}. If you show up in Math Claims Court alleging that the function machine I sold you was defective, the first question the judge will ask (even before the question “Did the machine produce an output belong to the codomain?”) is “Did you feed the machine an input belonging to the domain?” If your answer is “no” (because you entered an input that falls outside of the domain or didn’t enter any input at all), your case will be thrown out of court.
How many function machines are there with domain {1, 2, 3} and codomain {4, 5}? You might say “Infinitely many, because you said the box could be any color I like,” but I don’t care how the machine looks – I care what it does. That is, I care about what number the machine outputs for each of the allowed inputs. Does the machine return a 4 when it’s given a 1, or does it return a 5? What about when the machine is given a 2 as input? And when given a 3 as input? That’s what I care about. And I don’t care what the machine does when given 17 as input, or −23, because those numbers aren’t part of the domain – only 1, 2, and 3 are.
So when I ask “How many different machines are there that accept an input from {1,2,3} and produce an output from {4,5}?”, what I mean is, how many different behaviors can such a machine have? If we write f(x) for the output that the machine produces when the input is x, then there are eight possibilities:
f(1)=4, f(2)=4, f(3)=4; f(1)=4, f(2)=4, f(3)=5; f(1)=4, f(2)=5, f(3)=4; f(1)=4, f(2)=5, f(3)=5; f(1)=5, f(2)=4, f(3)=4; f(1)=5, f(2)=4, f(3)=5; f(1)=5, f(2)=5, f(3)=4; f(1)=5, f(2)=5, f(3)=5.
Here are the graphs of those eight functions:
We can in turn represent each of these eight graphs by forming the set of all points in the graph, where each point is represented an ordered pair. So for instance the first of those eight functions is represented by {(1, 4), (2, 4), (3, 4)}, a set of three ordered pairs.
What if we reverse the roles of {1, 2, 3} and {4, 5}? How many different rules can there be for outputting an element of the set {1,2,3} when the input is an element of the set {4, 5}? If we write g(x) for the output of such a machine when the input is x, then there are nine possibilities:
g(4) = 1, g(5) = 1; g(4) = 1, g(5) = 2; g(4) = 1, g(5) = 3; g(4) = 2, g(5) = 1; g(4) = 2, g(5) = 2; g(4) = 2, g(5) = 3; g(4) = 3, g(5) = 1; g(4) = 3, g(5) = 2; g(4) = 3, g(5) = 3.
Here are those nine functions pictorially:
If the numbers eight and nine smell like 23 and 32 to you, you’ve got a first-class mathematical nose: the number of functions from the set S to the set T is always equal to |T| to the power of |S|. That’s why mathematicians often write the set of functions from S to T as TS. This initially seems backwards and is hard to get used to, but it has the virtue that |TS| equals |T||S| instead of |S||T|.
This kind of exponentiation plays nicely with our definitions of multiplication and addition in three important ways. The first way is TS × TS′ ≈ TS∪S′ (valid whenever S and S′ are disjoint).6 This is the set-theory analogue of the algebraic formula ab × ac = ab+c . The second nice feature of our definition is the set-theory analogue of the algebraic formula (a × b)c = ac × bc, namely (T×T′)S ≈TS ×T′S.7
The third and most interesting way in which set-exponentiation plays nicely with our other set-operations is the set-theory analogue of the algebraic formula (ab)c = abc: (UT)S ≈ US×T. The left hand side describes a machine with the property that if you feed it an element of S it produces an element of UT, which is to say, it produces another machine! More specifically, (UT)S outputs machines that accept elements of T as input and produce elements of S as output. (Machines that create more machines – very computer-science-y, and also very Seussian!)8 So, if you feed (UT)S an element of S, you obtain an element of UT (that is, you obtain a machine), and if you feed that machine an element of T , you’ll get an element of U.9
ZERO HOUR
Before we arrive at our destination – deriving the discrete-math convention 00 = 1 from the strange ways of the empty set – let’s think about sets with just one element. Examples of such sets are {2} and {3}. Notice that these are sets, not numbers: {2} is different from 2 and {3} is different from 3. This distinction was troublesome for the inventors of set theory, and the empty set gave them even more trouble. Their bemusement is reminiscent of the problem European mathematicians had with the zero they’d imported from India and China. Even today, people are usually nonplussed (pun intended) when they first encounter the empty set; that’s why we’re sneaking up on empty sets by considering first the sets that are as close to being empty as a nonempty set can be.
Let S be {2} and T be {3}. Then there’s exactly one function from S to T, namely the function f satisfying f(2)=3. The function f can be written as {(2, 3)}, a set of ordered pairs that happens to contain just one ordered pair, so we can write {3}{2} (the set of functions from {2} to {3}) as {{(2, 3)}} (a set of functions that happens to contain just one function). So|TS| = 1 = 11 =|T||S|.
Now let’s replace the {2} or {3} in {3}{2} by the empty set to see what happens. If we look at all the functions from {2} to the empty set, we’re in trouble; we need to define f(2) to be some element of the empty set, and there are no such elements, so there are no such functions. Putting it differently, the set consisting of all such functions is empty. That is, { }{2} equals { }, a set of functions that happens to contain no functions at all. Is this what our formula |TS| = |T||S| predicts? Why yes, it is! Taking S = {2} and T = { }, we get |T||S| = 01 = 0, so we expect TS to contain 0 elements. No problem here.
Now let’s turn things around and replace {2} by the empty set while leaving {3} alone. That is, we’ll look at the set of functions from the empty set to {3}. How many such functions are there? We’re looking for machines that always produce the number 3 as output, provided that a legal input is provided – but in this case, no inputs are legal because the domain is the empty set. A machine that does nothing at all (call it the Do-Nothing Machine) fulfills all the specifications. The Do-Nothing Machine describes a function from { } to {3}, namely the “empty function”, whose graph looks like this:
The domain of the empty function is the empty set, so its graph contains no points at all; as soon as you pick up your pencil to start drawing its graph you realize you’re already done. (The empty function is easy to graph but hard to think about!) If you want to write this function as a set of ordered pairs, it’s a set of ordered pairs that happens to contain no ordered pairs at all: { }. So {3}{ } has one element, namely { }, which means that {3}{ } is the set {{ }} – the set of functions whose only element is the empty function. Is this what we should have expected from our formula |TS| = |T||S|? Yes, since 30 = 1.
Drawing by Ben Orlin. He’s got a new book coming coming out in September; stay tuned for details.
Now we get to the toughest triviality of all: the case where S and T are both empty. We’re looking for a machine which, when given an element of S produces an element of T, with S = T = { }. But since S is empty, the Do-Nothing Machine once again fulfills all the operational specifications. That is, I can guarantee that if you buy my Do-Nothing Machine and feed it an element of { }, it will produce an element of { }. I make this guarantee in full confidence that you’ll never be able to prove in court that I lied, because you’ll never be able to feed the machine an element of { } because there are no such elements, and any attempt to feed the machine an input that isn’t an element of { } will void the warranty. So there’s one function from the empty set to the empty set, as implemented by the Do-Nothing Machine. That is, { }{ } (the 0-element set raised to the power of the 0-element set) is not the empty set { } but the 1-element set {{ }}.
The upshot is that if we want |T||S| = |TS| to be true for all sets, then we need we need|{ }||{ }| =|{ }{ }|; that is, we need 00 = 1. And that’s the convention used by people who do discrete mathematics.
We’ve seen that there’s a subcommunity of mathematicians in which 00 is taken to be 1 and a different subcommunity in which 00 is regarded as indeterminate. Is there a subcommunity in which 00 is taken to be 0? I don’t know of one, but it would be fine if there were; it’s okay to have different people use different definitions as long as they’re clear with one another about what definition they’re using. In fact, you’re free to define a new operation on numbers that acts just like ordinary exponentiation except that 00 is 17 (though you probably won’t get others to adopt your convention unless you convince them that it’s useful or pretty). Computing 00 doesn’t become a mathematical problem until we specify what definition of exponentiation we’re using. Each definition may admit only one answer, but math has room for many definitions.
This essay is an online supplement to a book I’m writing, tentatively called “What Can Numbers Be?: The Further, Stranger Adventures of Plus and Times”. If you think this sounds cool and want to help me make the book better, check out http://jamespropp.org/readers.pdf. And as always, feel free to submit comments on this essay at the Mathematical Enchantments WordPress site!
REFERENCES
Dr. Seuss, Green Eggs and Ham, 1960.
Dr. Seuss, One Fish, Two Fish, Red Fish, Blue Fish, 1960.
ENDNOTES
#1. In calculus, 00 is not assigned a numerical value but is called indeterminate. That’s because the expression xx′ behaves in a weird way as the real numbers x and x′ both approach 0. xx approaches 1 as the positive number x gets closer and closer to 0, but if x approaches 0 quickly and x′ approaches 0 slowly, xx′ can approach 0. By adjusting the rates at which x and x′ approach 0, you can make xx′ approach some value between 0 and 1 or oscillate without ever settling down, and if x approaches 0 from the right and x′ approaches 0 from the left, xx′ can increase toward infinity! For these reasons, people who do the kind of math that grew out of calculus call 00 “indeterminate”.
#2. In the spirit of switching the roles of addition and multiplication, we can replace the arithmetic progression 1,2,3,4,5 by the geometric progression 1,2,4,8,16. Then {1, 2, 4} + {8,16} is {9,10,12,17,18,20} while {1,2,4} × {8,16} is {8,16,32,64}.
#3. When I was a child and my great-aunt Clara asked me what I was interested in, I told her that I was very interested in sets. Given that she was hard of hearing, you can guess why she was shocked by what she thought her ten-year-old grand-nephew had said.
#4. Another option is to abandon |S ∪ T| = |S| + |T| and to replace it by the inclusion-exclusion formula |S ∪ T| = |S| + |T| − |S ∩ T| where S ∩ T is the intersection of S and T, which is to say, the set of elements that S and T have in common.
#5. I write the empty set because from the standard point of view there’s only one set with no elements. There are nonstandard versions of set theory in which an empty set of unicorns is different from an empty set of manticores, and they can be useful in computer science where objects have data-types, but mathematicians and logicians like to say that two sets are equal when they have the same elements. Taken literally, this means that every set that has no elements is equal to every other set that has no elements. Some people write the empty set as ∅, but this notation makes us think about the empty set as a thing apart, whereas I’d rather use notation that stresses that it’s just an ordinary set that happens to contain no elements, so I’ll write the empty set as { }.
#6. The left hand side describes pairs of functions (f, f′), where f is a function that takes inputs from S and produces outputs in T and f′ is a function that takes inputs from S′ and produces outputs in T. If you’ve got two such functions, you can combine them to form a new function from S∪S′ to T, namely the function g where g(x) is f(x) if x is in S and g(x) is f′(x) if x is in S′. Conversely, if you’ve got a function from S∪S′ to T, you can break it apart into two functions, one from S to T and one from S′ to T.
#7. This formula says that if you’ve got a function from S to T × T′, you can break it apart into a function from S to T and a function from S to T′, and conversely, if you’ve got a function from S to T and a function from S to T′, you can glom them together to get a function from S to T × T′. The glomming is easily described: If you’ve got a function f from S to T and a function f′ from S to T′, define g(s) = (f(s),f′(s)); then g is a function from S to T × T′.
#8. Someday I’ll write an article about the ways in which early exposure to the works of Dr. Seuss prepared me to be a mathematician and may even have gently nudged me in that direction.
#9. Why is (UT)S essentially the same as US×T? To explain it, I’ve got a Seussian business proposition for you. I’ll give you the (UT)S machine, and I’ll put you and the machine inside a big box. This big box will have an input hopper where I’ll place elements of S×T, and you, my fine friend, have a simple job: when I put (s, t) in the input hopper, you will feed s into your (UT)S machine, obtaining a spanking-new UT machine into which you’ll feed t; then your UT machine will produce an element of U. You’ll put this element u into the output-hopper of your big box. That’s it! The big box, viewed from the outside, accepts inputs in the set S×T and produce outputs in the set U, so it is, in effect, a US×T machine. And it turns out that every US×T machine can be simulated in this way, using an appropriate machine for turning elements of S into elements of UT.
