Equations, and undoing operations

I’ve been working on a post defining exponentials/powers for a while now, but honestly I think I’m going to admit temporary defeat in that regard. Addition and multiplication are very fundamental operations on the natural numbers, coming directly from numbers’ original purpose of “counting things.” Exponentials are a bit more subtle: it’s possible to use them for counting (they arise all the time in solutions to problems in combinatorics, a.k.a. “advanced counting”), but to explain how would require me to introduce all sorts of interesting constructions that I’m not going to actually use for much. I’d rather wait until I have the machinery anyway, than introduce it only to ignore it.

So instead I’m going to do what Thomas Tan suggested in the comments: talk about subtraction and division.

Basic Algebra

The reason I wasn’t going to talk about subtraction yet is that I really don’t think of it as an operation in its own right. Instead I think of it as something you get when you try to solve equations involving addition.

Let’s go back to that party we were throwing earlier this month, when we figured out there weren’t enough party favors for all the guests. Specifically, we noticed that we had 8 guests but only 7 party favors.

Now, if you’re a good host, you might think to yourself: “If only there were some way we could get more favors, so that we had 8 of them!”

If you’re a good host who knows something about addition, you might elaborate, “If only there were some number we could add to 7, and get 8!”

And if you’re a good host who is also a good friend of Muhammad ibn Mūsā al-Khwārizmī, the inventor of algebra, you might finally say, “If only there were some natural number k such that 7+k = 8!”

You’re in luck, my friend: 1 will fit the bill just nicely! (Proving this is left as an exercise for the reader.)  Finding this number is known as solving the equation: we’re looking for a number to fill in for k that makes the statement true.

Perhaps I overstated how lucky you were, though. In fact, if you’d needed (say) 50 party favors, and thus needed to solve the equation 7+k = 50, you still would have been able to find a solution. The same would be true for any number greater than 7. One vital fact  about the natural numbers—a fact that I wonder if anyone has ever actually mentioned to the first-graders learning subtraction in school—is that you can “get to” any larger natural number from any smaller one, just by adding the appropriate difference.

Theorem 1. For any two natural numbers n and m, if n ≤ m, there is a unique natural number k such that n+k m.

Proof. We have to prove two things: firstly, that there is such a number; secondly, that there are not two or more such numbers.

For the first part, let N and M be sets of sizes n and m, such that N is a subset of M. Then let K be the set difference of M and N: the set of all those things that are in M, but are not in N. The sets N and K are obviously disjoint, and NK is M; so, if k is the size of K, then n+k = m.

For the second part, imagine any number k* such that n+k*m. Choose a set K* of size k*, disjoint from N above, such that NK* has size m. Then since NK* and NK are the same size, there’s a bijective correspondence between them. There’s also a fairly obvious correspondence between N and N; by “ignoring” that component of our larger bijection,1 we get a bijective correspondence between K* and K, and so k* = k.  ∎

So that’s nice to know. When the equation n+k = m does have a solution, we’ll call it a difference of m and n, and write it as mn. From the above theorem, we know that we can find a unique difference of two natural numbers at least half of the time.

Unfortunately, the other half of the time things break completely.

Theorem 2. If n and m are natural numbers and nm, there is no natural number k such that n+k = m. (Or, in first-grade parlance, “You can’t subtract a bigger number from a smaller one.”)

Proof. If a set N is larger than another set M, then any union of N with another set will still be larger than M.  ∎

This is why I don’t like to think of subtraction as an operation on natural numbers: you can’t just apply it to any two natural numbers and expect an answer. If you want to sound smart, go find someone and tell them: “The natural numbers are not closed (or incomplete) under subtraction.”

Now, I can already hear some of you saying there’s a solution to this problem. “Sure you can subtract a bigger number from a smaller one! You just get a negative number—something less than zero.”

To which I say, “Bah! How can a set be smaller than the empty set? That’s just ridiculous.”

….okay, so I’m going to talk about those numbers eventually. But it’s important to understand the difference between inventing a solution and already having one. If the question you’re trying to answer is one that natural numbers are equipped to handle—that is, if you’re basically counting the elements of some real-world set—then you really can’t subtract a larger number from a smaller one. If you have too many party favors, you can’t go to the store and buy −3 more. Subtracting a larger number from a smaller requires a whole new conception of “number,” and one that is suited for a different class of problem.

…and more algebra.

This same thing applies to division. When you ask “What is 15/3?” what you’re really asking is, “What number k solves the equation 3⋅k = 15?” Or, set-theoretically, you might be asking, “I have 3 kinds of peanut butter, and I want to be able to make exactly 15 kinds of sandwich for some reason. How many kinds of jelly should I buy?”

Okay, that was a stupid example. Let’s look at the sort of exercise they actually like to give to kids in school. These are usually about sharing cookies or something, and they go like this:

Bobby has 15 cookies to split equally among his 3 friends. How many cookies should he give to each friend? (Bobby himself is too full to eat any cookies and is allergic to raisins anyway, or something.)

Well, let’s try and overanalyze this problem with our high-tech set-theoretic machinery.

There’s a set K of hungry kids, of size 3.

Each kid is going to get a set C of cookies. They’re not literally the same cookies, but if we’re sharing equitably they should be indistinguishable—at the very least there will be bijections between them. So it doesn’t hurt anything to pretend that they are. The size of C is what we are trying to find—I’ll call it n.

Imagine that each kid’s cookies had little tags on them saying “Cookie 1, Cookie 2, …” Then you could identify each cookie with a label like (Socrates, 2), meaning the Cookie 2 belonging to Socrates. So the set of all the cookies will be in bijective correspondence with the set K×C. This set, promises our narrator, has size 15.

Then, from the definition of multiplication, we know that 3⋅n = 15: the size of K, times the size of C, is the size of K×C. This is the equation we have to solve.

Fortunately, it turns out that 5 is a solution in this case. We call 5 a quotient of 15 by 3, and also write that 5 = 15/3.

Beyond that, we note that Bobby is lucky to have had exactly 3 friends over: if he’d had 2 or 4, things could have gotten ugly. The natural numbers are even more incomplete under division than they are under subtraction—at least then, we could get an answer half the time. With division, the best we can do is this:

Theorem 3. If n and m are natural numbers and n is not 0, the equation nk+r = m has a unique solution for which r is less than n.

Proof. Let k be the largest natural number for which nkm.2 Then there is a unique natural number r solving the equation nk+r = m, by Theorem 1. Furthermore, r is less than n, or else n⋅(k+1) would be less than or equal to m.  ∎

This doesn’t seem that great, but it is something: that number r is the remainder, and what the above theorem says is that every natural number division problem has a “solution,” in the sense of a best approximation to a solution, plus a remainder. The statement “17/3 = 5 R2” is actually a rewritten form of the statement “3⋅5+2 = 17.” In the case where nk m does have a solution, we say m is divisible by n.

As with subtraction, there are extensions to the natural numbers in which you can always divide exactly. But, as with subtraction, these are just that: extensions. In a situation that is really modeled with natural numbers (like splitting indivisible objects among friends), getting a remainder means there is no exact solution.

Diophantine equations

Since I’ve brought up the topic of solving equations, there’s no reason to limit myself to simple ones. I could just as soon talk about solving more difficult equations: things like

61⋅a2+1 = b2, or

an+3+bn+3 = cn+3.

(Since I’m skipping the post on exponentiation, feel free to think of it as ‘just’ repeated multiplication.)

An equation like this, where the variables are only allowed to be filled in with natural numbers (well, integers), is called a Diophantine equation.

While a few specific types of Diophantine equations are easy to solve, in general they’re pretty difficult to work with, and finding solutions is still an active area of mathematical research. For example, the first equation above has the obvious solution where a = 0 and b = 1; but does it have any others? Well, maybe, but I don’t know how you’d find them. (In fact, yes it does; the minimal example after that one is a = 226153980, b = 1766319049.)

The second equation has no natural number solutions at all. This is one form of a slightly stronger statement called Fermat’s Last Theorem, which was conjectured by Pierre de Fermat sometime around 1639, and proven through the combined efforts of several mathematicians, most directly Andrew Wiles, in 1994.

This is either a downside or an upside of the natural numbers, depending on whom you ask: there are a lot of very simple questions about them that are very hard to answer. (If you actually need the answer for something this is called “annoying,” but if you’re a number theorist it’s called “job security.”)

….and this has turned into my longest entry yet. I think it’s quitting time for tonight.


[1] I’ve actually swept a complication under the rug here: prima facie, just because we have a bijection between NK and NK*, we have no reason to suspect there is one that actually maps N to itself. It happens to be true that we do, but the proof is a lot of tedious juggling of set elements and probably isn’t worth going into.

[2] Again I’m leaving something out here: strictly speaking, I need to prove there is a largest such number.

Advertisements

4 responses to “Equations, and undoing operations

  1. FIRST TO READ! i mean, second, haha

  2. just to make sure I don’t clog up your comments with useless stuff, I like the way you use complicated set stuffies and make them simple in order to explain number theory.

  3. I really like your writing, and have enjoyed reading this entire blog so far.

    This current post has a few typographical inconsistencies:

    1. “The natural numbers are \bf{not closed} (or \bf{incomplete}) \bf{under subtraction}.”
    – I’d write (or \bf{are incomplete}) in the middle, since the way it is now looks like ‘not’ goes with ‘incomplete’ as well as ‘closed’.

    2. Theorem 3. If n and m are natural numbers and n is not 0
    – Okay, this isn’t actually an error, but in this font the zero (0) looks a lot like a lowercase letter oh (o)

    3. there are extensions to the natural numbers
    – I’d write ‘there are extensions of the natural numbers’ because saying ‘extensions to’ sounds like you are using an extension to reach the naturals, rather than using an extension to get more than the naturals.

    Also the existence of bijections as written (for the N and k thing) is not at all obvious, although I’m not sure how to make it clear.

    • Thanks for your comments on grammar, and I’ll keep them in mind for the future, but I really don’t think any of those examples could possibly be confusing. If someone tells me they were confused, I’ll change them.

      I’m not sure what you mean by “the N and k thing?” I think the least obvious thing I wrote was that, if K and K* are both disjoint from N, and the sets N∪K and N∪K* are the same size, so are the sets K and K*. I agree that proving this by finding an explicit bijection is kind of tricky (which is why I didn’t do it), but I think it’s at least “obvious” in the sense of “exactly what one would expect,” if not in the sense of “easy to prove.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s