Cancellation of Addition, a forgotten property

I was working out a proof of a property of order among the integers in preparation for continuing this series when I realized that I had forgotten an important property of addition amongst the natural numbers: cancellation.

Cancellation says that if you have a+c = b+c, then a=b. It's wanted for both addition and multiplication of natural numbers (in the latter case, a*c = b*c implies a=b). It allows for the simplification of various expressions when you see the same thing on both sides of an equals sign.

I relied too much on my analysis book to list the properties of numbers. It gave additive inverses as a property of reals, which negates the need for additive cancellation.

It's easy to prove, given our definition of addition:

For the base case (c=1), you have: \[ a + 1 = b + 1 \Rightarrow S (a) = S (b) \Rightarrow a = b \] working basically with the definition of addition and with the injective property of the successor function.

For the inductive case, we get to assume a+c = b+c, and need to show this still holds for S(c). \[ \begin{eqnarray*} a + c & = & b + c\\ S (a + c) & = & S (b + c)\\ (a + c) + 1 & = & (b + c) + 1\\ a + (c + 1) & = & b + (c + 1)\\ a + S (c) & = & b + S (c) \end{eqnarray*} \]

Initially, I had done that backwards, starting with the last line and showing the first line. I think I have a tendency to do that, which is bad. In this case, and in many others, each step is an equivalence, not just an implication, which allows me to get away with it, but I need to keep an eye out for that mistake.

Addendum to "What is a number"

I reread the earlier blog posts in preparation for writing more and I realized something I had left out in the "What is a number?" posting.

I left out the concept of "embedding". I touched upon the related idea of extending but didn't get explicit about it.

One of the important aspects of all the number systems I described in that posting was that in all the newer or weirder ones the old number system still exists, inside the new one. This is what's meant by "embedded". To take the example of natural numbers and real numbers, for instance, there's a collection of real numbers which obey all the rules of natural numbers. Formally, we say the embedding is a structure-preserving one-to-one map from natural numbers to real numbers. "One-to-one" in this case means that the real numbers corresponding to two distinct natural numbers are distinct. "Structure-preserving" means that all the properties we expect of natural numbers are maintained by the map. If we map natural numbers a,b to real numbers A,B then a<b means that A<B, a+b maps to A+B, a*b maps to A*B, etc.

Sometimes the properties of the simpler system hold for all of the new system (like in the naturals to reals case), sometimes they don't. I mentioned in the prior post that Ordinals didn't have a commutative addition, and that ω+1 does not equal 1+ω. Ordinals are modeled on the natural numbers, and there is a "canonical" embedding of natural numbers in the Ordinals -- 1 maps to the first Ordinal, 2 maps to the second, etc onto all the finite Ordinals. Within the finite Ordinals, all works as expected, addition is commutative. It's only when you go into the "unmapped territory" of the transfinite Ordinals do the expected properties start to break down.

The flip-side of embedding is "extending" -- adding things to an existing system to cover gaps in what you are doing. You want to split 4 apples between 3 people; natural numbers won't let you do that, so you extend them to allow arbitrary ratios of natural numbers, filling in the gaps between the old numbers with new numbers. The old numbers still work just fine. You discover that there's still gaps between rational numbers, so you add them to the mess, getting real numbers. The rational numbers are still there (and the natural numbers too). You can't take the square root of a negative number? Add a number defined as the square root of -1 and say that all the other rules still apply and see what it gets you -- voila! Complex numbers. If one square root of -1 is good, how about 2? No dice, it doesn't work, but with three you get eggrollQuaternions! (seven yields Octonians). Natural numbers are good for telling you the number of items in any finite set, but there's not a finite number of natural numbers. How many natural numbers are there? Georg Cantor extended natural numbers to "transfinite Cardinals" to find out.

So all the varied and wonderful number systems out there have embedded in them simpler number systems, and all are extensions of simpler number systems. Well, all except natural numbers. You have to start somewhere.

Things which aren't "numbers", like n by n matrices, tend to fail in that they don't have an obvious useful embedding of a simpler system, or aren't a clear extension of a simpler system. The closest embedding I can think of for reals into an n by n matrix is simple multiples of the identity matrix, which isn't very interesting or clear.

Addition of Naturals, take S(1)....

Ok, I've looked it up figured out where I was going wrong. It turns out it's easier to prove associativity first, and then use that to prove commutivity.

To recap:

Peano's Axioms for Natural numbers are:

A. 1 is a Natural number,
B. If n is a Natural number, then S(n) (read: the successor to n) is also a natural number.
C. If n is a Natural number, then S(n) ≠ 1 (i.e., 1 is not the successor of any natural number.)
D. If S(n) = S(m), then n=m (i.e., every natural number is the successor of at most one natural number).
E. If P(1) is true, and P(n) implies P(S(n)) for all n, then P(n) is true for all n. (the Induction Axiom)

Peano's axioms don't refer to addition directly. It is necessary to define addition such that it has all the properties we associate with addition, assuming Peano's Axioms hold. Peano's Axioms limit what we can talk about, however. Our proofs can only use 1, S, and induction, until we prove other things.

Addition of natural numbers has two standard properties that are typically used in other proofs: associativity and commutivity. "Addition is associative" means that when you have 3 or more numbers added together, the grouping of addition doesn't matter. It's easy to show that if grouping doesn't matter for 3 numbers, it doesn't matter for more. By "grouping", I mean (a+b)+c = a+(b+c). It doesn't matter if you add b to a, then add c to the result, or if you add c to b, then add that to a.

"Addition is commutative", beside being a lyric in a Tom Lehrer song, means that the order of addition doesn't matter. In other words, a+b = b+a.

The trouble with saying "addition is commutative and associative" and leaving it at that is that multiplication is also associative and commutative. So those properties don't distinguish between addition and multiplication. So more properties are needed. I'm not sure how to define such properties, but I'm willing to accept a "spot check": does our definition agree with the notion that 2+3=5? It's not a perfect proof, but it'll do.

We also need to show that our definition is well defined: that a+b is a unique natural number for all natural numbers a, b. That's easy enough to do.

Here's our definition:

Def: Addition + of natural numbers.
If a, b are natural numbers, then
a+1 ≝ S(a)
a+S(b) ≝ S(a+b)

To show that a+b is well-defined, we'll use induction on b. Assume that a is a natural number.
Base case (b=1): By definition, a+b = a+1 = S(a). By property B, S(a) is a well-defined natural number, so a+1 is a well-defined natural number.
Inductive case: Assume that a+b is a well-defined natural number. Then a+S(b) = S(a+b), and the successor of a natural number is a well-defined natural number, so S(a+b) is well-defined, so a+S(b) is well defined. Therefore, a+b is well-defined.

In my first attempt, I tried to prove that addition was commutative. It turns out that it's easier to prove commutativity if you have associativity to work with first. And that's not too difficult to prove (assuming you know the right way to do it).

To show that (a+b)+c = a+(b+c), we'll do it via induction on c. Assume that a, b are natural numbers.

Base case (c=1): (a+b)+1 = S(a+b) = a+S(b) = a+(b+1).
Inductive case: Assume that (a+b)+c = a+(b+c),
then (a+b)+S(c) = S((a+b) + c) = S(a + (b+c)) = a + S(b+c) = a + (b + S(c))
So by induction (a+b)+c = a+(b+c) for all a, b, and c.

To show that addition is commutative, we can use associativity to our advantage. We have to use nested induction proofs: to prove commutativity, we'll use induction on b. To prove the base case, we'll use induction on a.

Base Case (b=1): To show a+1 = 1+a, we'll use induction on a.
SubBaseCase (a=1). If a=1, then we have 1+1 = 1+1, which is trivially true.
SubInduction Case. Assume a+1 = 1+a, then
S(a)+1 = S(S(a)) = S(a+1) = S(1+a) = 1+S(a).
So a+1 = 1+a for all a, thus proving the Base Case.

Induction Case: Assume a+b = b+a. Then
a + S(b)
= a + (b + 1)
= (a + b) + 1 (by associativity)
= (b + a) + 1 (by hypothesis)
= b + (a + 1) (by associativity)
= b + (1 + a) (by the base-case)
= (b + 1) + a (by associativity)
= S(b) + a
So by induction, a+b = b+a for all a, b.

Now to spot-check addition against our idea that 2+3=5, note that 2 = S(1), 3 is S(S(1)), and 5 is S(S(S(S(1)))), so we want to check the value of S(1) + S(S(1))

2 + 3 = S(1) + S(S(1)) = S(S(1) + S(1)) = S( S(S(1) + 1) = S( S( S(S(1)))) = 5, which is just what we expect.

Next stop, the order relationship of integers.

A pause, while I regroup....

I had a post I was working on, defining addition and proving its properties, when I ran into a glitch: my proofs didn't work.

Rather than leave you hanging, as if I had forgotten about this blog or got bored and give up, I'm letting you know what's up.

Specifically, I had given a definition of addition of natural numbers, proved it was well-defined, and was attempting to prove that it was commutative. At one part in my proof, I realized that things weren't in the form I needed them, and couldn't continue.

I'll be back soon with a good proof.

Peano's Axioms for natural numbers

The modern formalism of numbers generally begins with the "Natural Numbers" ℕ, which are fairly easy to model, and then builds from there. From natural numbers, one can create a set of definitions for integers, rational numbers, real numbers, and complex numbers, all the way making appropriate definitions for the operators and relations we want to hold for all these different numbers and verifying that the operators and relations hold the way we want. But it all begins with ℕ.

Wikipedia lists 9 axioms in for Peano's Axioms of ℕ, but most formulations I've seen generally list 4 -- the other 5 are either assumed or subsumed by the 4. Peano stated, for instance, that equality of natural numbers was reflexive (a=a), symmetric (a=b implies b=a), transitive (a=b and b=c implies a=c) and closed (if a is a natural number, and a=b, then b is a natural number). In general, people tend to assume these 4 properties of equality, but they are reasonable to state in a full formalization. When we get to defining other numbers in terms of natural numbers, we are going to have to define equality as well, and show that these 4 properties hold for our definitions, so it's good to be explicit about them. But generally, most mathematicians today hold those four properties as being part of the concept of equality.

As for the rest, Peano assumed that the system of natural numbers consisted of two things at it's base, a set ℕ, and a function S:ℕ→ℕ (i.e. a function which takes natural numbers to natural numbers), with the following properties:

A. 1 is a natural number.
B. If n is a natural number, then S(n) is a natural number.
C. For all natural numbers n, S(n) ≠ 1.
D. For all natural numbers n, m, if S(n) = S(m), then n=m
and
E. If P(n) is a proposition on natural numbers such that P(1) is true and if P(n) is true then P(S(n)) is true for all natural numbers n, then P(n) is true for all natural numbers.

The last one is a bit complex, but it allows us to prove things for all natural numbers rather easily. It's simple once you get the hang of it.

S is called the "successor" function, and the axioms can be stated as "B. Every natural number has a unique successor", "C. 1 is not the successor of any number", "D. Every natural number is the successor of at most one number", and "E. If P is true for 1, and true for the successor of any number it is true for, then it is true for all numbers". While this restatement is somewhat less formal, it provides a more fluid way of speaking of the axioms.

Here's an example of a theorem that can be proved using the axioms (and a demonstration of axiom E)

Theorem: Every natural number n other than 1 is the successor of a natural number.
Proof: Let P(n) be the proposition that n is 1 or the successor of a natural number. If P(n) is true for all n, then that proves our theorem. P(1) is obviously true. Assume P(n) is true, then P(S(n)) is true since S(n), by definition, is the successor of a natural number. So P(1) is true, and P(n) implies P(S(n)). By Axiom E, P(n) is therefor true for all natural numbers. That is what we were to demonstrate.

This technique of proving P(1) and proving P(n)→P(S(n)) to prove P(ℕ) is called "mathematical induction", and is a powerful technique. Needless to say, we will be using it alot.

Tomorrow, I'll discuss order.

What's a number?

This is a rather difficult question. Normally, things in mathematics are defined by their properties, but there doesn't seem to be any truly consistent set of properties held by things mathematicians call "numbers".

My real analysis book identifies 10 properties that the set of "real numbers", ℝ, have. Some of those are really more than 1 property, so by my count it's 13 properties. But we consider the set of "natural numbers", ℕ, to be numbers, and yet 4 of those 13 properties don't hold for natural numbers -- addition doesn't have an identity or inverses, multiplication doesn't have an inverse, and they aren't continuous (which we'll get to later).

So do all "numbers" have the remaining 9 properties? Well, no. Complex numbers, ℂ, don't have a standard ordering (which are 3 properties that ℕ has), leaving 6 properties common across all things called numbers. Is that all? Not quite. Multiplication doesn't commute with Quaternions, ℍ, so that's 5 common properties. Octonions, another system under the umbrella of "numbers", are very strange in that multiplication isn't even associative. That leaves 4 common properties: Addition is (1) commutative, and (2) associative, multiplication has (3) an identity, and (4) multiplication "distributes" over addition.

Even beyond the systems I've mentioned above, there are plenty which are considered, in some sense, "numbers" (surreal numbers, hyperreal numbers, p-adic numbers, etc) which have even stranger properties. Surely, you'd think, addition must commute. I mean, that's sort of fundamental to the concept of addition, really. Could anyone seriously think of a number system in which addition didn't commute? Yes, someone did. In ordinal numbers, ω is the smallest non-finite ordinal number, and ω+1 does not equal 1+ω. You can blame Georg Cantor for that one.

The remaining, common properties (if there are any left) are very meager to hang the concept of "number" on. Even worse, there are systems which have those properties (and more!) which aren't considered numbers. For example, n by n matrices have an associative, commutative, invertible addition operation with identity, and an associative multiplication with identity that distributes over addition, and are even continuous. But they aren't considered numbers.

So, what is a number? Generally, it's whatever mathematicians feel acts like a number. The problem is that, generally, mathematicians have felt, at different times, that different properties of numbers were important, and extended their concept of numbers in the general direction of what made sense to them at the time.

To the Greeks, two sorts of "numbers" were important: positive integers, which could be used to count things, and lengths in geometry. Pure lengths didn't have the concept of a "unit", so there was no length that corresponded to 1, but unlike integers, lengths did have the concept of arbitrary proportions: it was possible to say that length a was to length b and length c was to length d, and given any three of a, b, c, or d construct the fourth. Multiplying lengths gave areas or volumes, but if a specific length was picked to be a unit length, there are ways to multiply lengths to get other lengths (since given a, b, and c, you could construct d such that a:b=c:d, then by setting one of the 4 to the unit, you could multiply using 1:a=b:ba and divide using a:1=b:b/a). Addition and subtraction of lengths is also easy. It is also easy to multiply a length by an integer, to get lengths which are twice, thrice, or a million times as large, and to divide a length by an integer, to get lengths which are twice, thrice, or a million times smaller.

The Greeks were quite adept at dealing with proportions, and had no trouble working with proportions of integers, nor did they have trouble with working with proportions of lengths. In fact, they felt that the two were quite closely related. They felt that any two lengths, a and b, say, could be divided up into some pair of integer number of equal parts, m and n, say, such that the lengths a/m and b/n would be equal (let's call it c). In their terminology, they would say that the length c "measured" both a and b, and as such a and b were commensurate ("measurable by a common standard"). Relating to proportions, this meant that a:b = m:n, where a, b are lengths and m, n are integers, which (to the Greeks) were an important property which made lengths workable (to them) as numbers. It really rocked their world when they were able to show that there were pairs of incommensurate lengths -- and that they were really easy to find, too. I'll talk about that proof again in a later post.

Although the Greeks had counting numbers, ratios of counting numbers, and lengths as numbers, all of their numbers were positive. Their concept of subtracting lengths was such that either only one of a-b or b-a existed, or the two were equivalent (i.e., either they felt that subtracting a larger from a smaller didn't make sense, or it resulted in a length equivalent to subtracting the smaller from the larger). But the idea of a negative number just didn't enter into their thinking.

Negative numbers were long not trusted as being meaningful. The only place they come up is when doing subtraction -- taking 3 apples away from a pile of 2, or shortening a 4 foot stick by 5 feet -- where the results are nonsense. Currently, arguments can be made for the utility of negative numbers by suggesting that if you have $4 and spend $6 on a book, the -$2 that results is money you owe for the book. This argument wouldn't make sense to a medieval merchant who may, quite literally, have 4 coins in pocket can't see how to spend 6 of them. Besides, the modern form of double-entry bookkeeping was developed by and for medieval merchants to keep track of quite complex transactions, and this transaction would be recorded as $6book(dr) = $4cash(cr) + $2loan(cr). Each account (book, cash, loan) has a debit (dr) and credit (cr) side, in which positive values are summed. If the (cr) side of a loan is greater than the (dr) side, you owe money. If the (dr) side of cash is greater than the (cr) side, you have cash in hand. To pay off the loan, the bookkeeper would record $2loan(dr) = $2cash(cr), which would add a $2 debit to the loan (balancing the $2 credit that started this mess), and add a $2 credit to cash (indicating that $2 in cash was paid out). No negative numbers needed, even for arbitrarily complex transactions.

What got negative numbers accepted was their utility in intermediate results: Sometimes, for some calculations, it's faster or easier to do things with subtraction, even if partway through the result is negative. If you pretend the operation makes sense, and just keep working it formally, you'll get a sensible (positive) answer in the end. After doing this enough, mathematicians came to accept the idea that there wasn't a problem working with the nonsensical negative numbers; they worked, formally, as one would expect numbers to work. And, gradually, they became accepted.

The same thing happened with so-called "imaginary numbers", who's name belies their initial unacceptability. At one time, mathematicians in Europe showed off their prowess (and got jobs) by demonstrating their ability to solve problems that no one else could do. At one point, the problems which were most in demand was solving cubic equations -- equations of the form ax³+bx²+cx+d = 0, where a, b, c, and d are integers. There can be 1, 2, or 3 solutions to this equation (in ℝ, at least), and if you have a solution it's quite easy to verify it. But finding a solution is quite a challenge in the general case. When a general solution was found, it involved square-roots of a combination of the coefficients that sometimes were negative. The square of any real number is positive, so the idea of taking the square root of a negative number is meaningless within the reals. But if you accepted the idea that the square root of this negative number might be OK, and just continued the solution through, you ended up with a real number that solved the original equation. Over a couple of hundred years, mathematicians working with imaginary and "complex" numbers in this fashion found they worked quite well, and now they are used in engineering, mathematics, physics, etc, without any problems routinely.

So the Greeks extended their idea of lengths being commensurate (like ratios of integers) to incommensurate because it worked for what they needed, and the new "numbers" had the properties of numbers they desired. Medievalists extended their idea of numbers to include negative numbers because the new "numbers" had the properties of numbers they desired and helped solve problems they were interested in better. Renaissance mathematicians extended their idea of numbers to include complex numbers because the new "numbers" had the properties of numbers they desired and helped solve problems they were interested in better. Georg Cantor extended integers to transfinite Cardinals and transfinite Ordinals to solve problems he was interested in, and they had the properties of numbers he cared about, so he called them numbers (after all, integers were indisputably numbers, and were used for both cardinality (how many) and ordinality (what order), so why shouldn't is transfinite extensions be numbers). William Hamilton's "Quaternions" extended complex numbers in much the same way that complex numbers extended real numbers (and Octonians extend quaternions the same way), so why shouldn't they be numbers? Surreal numbers (by John H Conway) provide an alternate formulation of number which subsumes reals and ordinals in one gigantic system, with addition, subtraction, multiplication, division, order, and roots, etc all working as one would expect it to.

So what's a number? Anything which generally acts as one would expect a number to act, keeping in mind that there are a lot of different ways numbers can be expected to act.

That's not to say that specific types of numbers are loosely defined. On the contrary, each type of number that's been referred to above, plus many more, has a very specific, concrete definition, properties, etc.

Next post, I'll describe the natural numbers and some of the defining properties associated with them.

What am I doing here?

Hello, and welcome to the first real posting on Triangular Tunings, a blog about math topics I wish to blather about.

I'm a computer programmer who has an interest in math, and desire to learn as much about it as I can. While in high school, I didn't take many math courses -- not because I wasn't good at it, but because I was too good. My State had a requirement that all high school students had to take two years of high school math to graduate, and could take a third year to complete a "sequence" in math. I managed to fulfill the State's requirement for a math sequence before I even entered high school. While in high school, I was given the opportunity to take college-level courses in Calculus -- and did so, until integration turned into a major mental blocker for me. I understand what it's about, I just can't do it reliably.

In college, I met the requirements for my degree: courses in probability, statistics, as little calculus as needed, discrete maths, et.c. I had to take a 400-level elective, so I chose a course in "category theory", which (surprising for a 400-level course) had no prerequisites. The two main examples of categories used in that course were straight from abstract algebra and linear algebra. So the next year I took abstract and linear algebra courses.

I love physics, and wish to have an understanding, at the mathematical structural level, of the underlying physical theories of quantum mechanics and relativity (both special and general). Unfortunately, these theories involve math concepts a touch beyond what I know -- Hilbert spaces, hermitian operators, tensors, Chrisofel symbols, Lie groups and Lie algebras, Eigenvectors, Eigenvalues, Eigenstates and Eigenspaces. These are all things I ran into while looking at physics, and had to study up on my own. Dover is a wonderful source of cheap math books, and I have a lot of them.

Of course, many books on these topics assume prerequisites which I might not already have: Tensors are typically defined using Einstein notation and by how they transform when coordinate system transformations are performed. If you don't know Einstein notation, and don't have a grounding in multivariate calculus, then you either give up or pull open the Dover catalog again. Did I mention I have a lot of Dover math books?

As you can tell, my math education has been very eclectic. It's exposed me to a lot of math of various types. As a result, I believe that math can be very broad in scope, and very beautiful.

This isn't apparent to many people as a result of how they are educated about math. Starting in primary school, they learn arithmetic: how to do sums and products of numbers of various sorts. In high school, they are introduced to algebra, or how to manipulate equations involving variables, then geometry, where they might get a ming-numbing introduction to formal proofs. If they are going for "higher math", they take high school courses in trigonometry, where they learn to memorize and regurgitate identity formulas, and finally, at the pinnacle of their high school math career, they get to wade into the shallow end of calculus, starting with the tedium of epsilon-delta proofs of limits. It's no wonder most high school kids don't bother with the whole thing; it's no wonder people say they are no good at math almost as if they are proud of it. Math to them is tedious, boring, rote manipulation of figures by half-remembered rules which make no sense to them.

Obviously, I disagree. There is a lot of mathematics out there beyond what is learned in the quick route to calculus. Not all of math involved numbers, or variables, or calculus, or... well, just about anything you can think of. What they do all involve is critical thinking, intensely logical reasoning, and a willingness to accept some pretty remarkable results.

So what is this blog about? My goal is to provide a forum for me to help improve my own math skills, and to perhaps provide an education for others as well.

And so, with the take-home message that math can be fun and isn't all tedium and numbers, our first topic will be: numbers, and tediously defining and building them up... Um, yeah.