The first infinite number

Wow, that was a much longer hiatus than I had planned. Let’s see if I can pick this up again.

Last year, I spent several weeks describing in intricate detail what natural numbers are. If I had to describe my thesis in a sentence, this might be it:

“The natural numbers are a computational tool for answering questions about finite sets.”

Here’s a somewhat longer and possibly more helpful recap.

  • Sets are ‘pure extensions’: collections of objects that are entirely defined by what is a member, and what is not.
  • Given two sets, sometimes there’s a bijective correspondence or bijection between them: a mapping in which every element of the first set is associated to a single element of the second, and vice versa. In this case we say the sets are equipotent, or “the same size”.
  • We choose a representative from each class of equipotent finite sets, and call those representatives natural numbers. In this way we can determine whether two finite sets are equipotent just by seeing which natural number each one corresponds to. The natural number associated to a finite set is its cardinality or “size.”
  • The ordering and arithmetic on the natural numbers is defined to reflect facts about the sets they describe. For example, addition reflects what happens when two disjoint sets are put together.

An obvious next step would be to give a similar at-length development of rational numbers, integers, real numbers, and so on. But I’d prefer to move in a novel direction, so right now I want you to notice something specific about the construction above, which is how unnecessary was the limitation to finite sets.

There is nothing about the definition of a bijection that says the sets have to be finite! Taking the same construction above, and removing that limitation, won’t create any paradoxes—instead it will give us a whole new collection of numbers to work with. Instead of a computational tool for answering questions about finite sets, we’ll get a tool for answering questions about sets in general.

Continue reading

Advertisements

Perfect numbers

One would be hard put to find a set of whole numbers with a more fascinating history and more elegant properties surrounded by greater depths of mystery—and more totally useless—than the perfect numbers.

Martin Gardner, 1997

This entry is dedicated to my beloved wife, Jennifer—for supporting me in my goals, for holding me to my promises, and for putting up with my obsessions.

Let’s take a short hiatus from our program of breaking down already-simple objects into their constituent atoms. Instead we’ll investigate a relatively straightforward question in arithmetic.

A perfect number is a natural number that is the sum of all its divisors aside from itself.

The first perfect number is 6. The divisors of 6 are 1, 2, and 3; and 1+2+3 = 6. This makes it different from a number like, say, 8: the divisors of 8 are 1, 2, and 4, and 1+2+4 = 7 < 8. We say 8 is deficient. A number like 12, on the other hand, for which the sum of the divisors is 1+2+3+4+6 = 16 > 12, is called excessive.

The second perfect number is 28: the sum of its divisors is

1+2+4+7+14 = 28.

The third perfect number is 496:

1+2+4+8+16+31+62+124+248 = 496.

And the fourth is 8128:

1+2+4+8+16+32+64+127+254+508+1016+2032+4064 = 8128.

Now, the perfect numbers were first investigated about 2500 years ago by the Pythagoreans, a sort of mathematical/mystical cult of ancient Greece, and these were the only four known to them. But even with that little data to go on, they began noticing patterns.

Continue reading

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.
Continue reading

Commutativity and all that

One of the nice things about our new definitions of addition and multiplication is that they make proving basic properties of the operations a snap. Looking at the recursive definitions, it’s not at all obvious that 3+5 is 5+3, or that 4⋅5 is 5⋅4. Or, more accurately, it’s obvious for any specific number (because you can just compute each one out and compare the results), but it’s not obvious how to show in general that n+m and m+n are always equal. It happens that it is possible, using a technique called induction… but that proof method, while beautiful in its way, is often pretty unenlightening. It forces you to accept that things are true, but it doesn’t help you understand why they’re true.

If our only definition of arithmetic were the recursive one, we would have no choice but to use induction. But since we’ve got a more (ahem) natural definition, we have a chance to get into the why of things.

Unfortunately there will be no stunning new abstractions in this post. It’s mostly application of the stuff I’ve already talked about, in the form of a long string of proofs. But the proofs themselves are pretty short and easy to follow. In fact, that’s the whole point I’m trying to demonstrate: once you’ve found the right definitions, results often just fall into your lap.

Continue reading

Putting sets together

The goal of our program here is to understand arithmetic as an operation that “has something we do with sets.” This means that before we go further, I’ve got to explain the structure of sets a little more.

I’ve got to be honest here: part of the reason it took me so long to write this post is because making basic set theory interesting is hard. My impression of it upon first exposure was that it was an attempt to take something extremely simple and obscure it with elaborate jargon. Actually the truth is only slightly different: it’s an attempt to take something extremely simple and describe it very precisely. The jargon is just a side effect.

This is just a blog, not a serious attempt to build a foundation for the entirety of deductive thought, so I can afford to be a bit looser with my terms than a real set theorist. I hope I’ll be able to explain enough to get to the good part, without mystifying folks (on the one hand) or insulting their intelligence (on the other).

Continue reading

Link love: The Unapologetic Mathematician

My next real post will be a bit delayed, probably until tomorrow. In the meantime, those of you who don’t know it already ought to check out John Armstrong’s excellent blog, The Unapologetic Mathematician. He’s essentially doing the same thing I am, except that he’s been at it since 2007 and so already has plenty for you to read. If you try to start the front page you may find yourself lost—best to return to the beginning and work your way forward.

Which brings me to a question: Is there a way I can avoid ending up in the same situation? What John has done is very impressive and valuable: it’s possible, using only his site, to build up a pretty solid appreciation for modern mathematics from scratch. But I suspect most of his new readers aren’t the “outsiders” he started with.

I’d like to imagine that, three years from now, a bright high school student will still be able to discover my blog and understand most of what he sees on the front page. Advice and thoughts on accomplishing this are welcome.

My favorite number

I’ll be back to my planned sequence soon—but first, a short diversion.

A long time ago, I saw in the Guinness Book of Records that the “largest number ever used in a serious mathematical proof” was called Graham’s number. I don’t recall whether I looked it up immediately after, or waited a while…. but when I finally did, I was surprised to find out that (1) I could understand exactly how it was constructed, and (2) my mind had been completely blown out of my skull.

Graham’s number is no longer the largest number ever used in a serious mathematical demonstration—that honor probably goes to Friedman’s TREE(3). But it’s still my favorite, since it demonstrates what can be done with the power of primitive recursion alone.

Continue reading