BB #86: Number Theory Lightbulbs

This is one of those geeky posts more a “Dear Diary” (or “Dear Lab Notebook”) entry than a post I expect anyone anywhere will get anything out of. This — in part — is about how we define numbers using set theory, so it’s pretty niche and rarified. Tuning out is understandable; this is extra-credit reading.

This is also about having a double-lightbulb moment. I finally get why what always seemed an overly complicated approach is actually perfect. A smaller lightbulb involves easily solving a programming problem that confounded me previously.

Fun for me, but your mileage may vary.

To explain the lightbulbs, I need to say a bit about defining numbers using set theory. (It’s not as bad as it may sound. Formal language can be intimidating, but the ideas it’s expressing, at least here, aren’t that complicated. And since this is more for me, I’ll try to be brief.) (Stop laughing.)

I’ve written before how I think numbers and math are inevitable for any intelligent species. [See Inevitable Math and Numbers Gotta Number] Numbers, and the math that is their grammar, force themselves on us in our experience of the physical world. (As I wrote in Inevitable Math, I think they force themselves on us even in just our thoughts.)

Two kinds of numbers present themselves to our experience: things we measure (heat, weight, distance, height) and things we count (sheep, coins, cheeses, boats). [See Magnitudes vs Numbers] Humanity seems to have discovered counting first. Our earliest measurements counted cubits or miles or days. Notions of 3/4 (let alone 0.75) miles came later.

Counting objects seems very natural, which is why the positive integers are called the natural numbers. But it would be nice to have a well-grounded theory explaining them, because they are the foundation much else in mathematics (and science and technology) stands upon.

§

The idea of counting depends on the recognition there is something that can be counted. That depends on classifying different objects as the same under some abstraction. That’s an intellectual jump.

When I walk Bentley down a familiar street, she perceives a series of specific individual objects, each with different smells and location relative to each other. I see a bunch of trees I can number because they belong to the same set of things: trees. More specifically, the set of trees along this street. That set has a size — the number of trees.

Any set of things has a size, the number of things in the set. The sheep in the pasture, the coins in the sack, the cheeses in the pantry, the boats in the harbor, these are all sets of things, and they all have a size. Indeed, they could all be the same size despite being made of very different things. [See Numbers & Sets]

This notion of things in a set and of set size is the foundation of how the natural numbers are defined using set theory. They are the cardinal sizes of abstract sets beginning with the empty set (zero) and then adding (imaginary abstract) items.

So, zero is a set with nothing in it, one is a set with one thing in it, two is a set with two things, and so on. Forever, because the natural numbers go on forever.

§

The last bit of background is the successor function. We imagine a function that, given some set (of some size), returns a new set with one more imaginary item in it. Put numerically, a successor function, given some number, returns the next number “in line” (given 41 it would return 42).

The successor function is the abstraction of counting. Think of the trees along that street. I have a small empty bag and a handful of pebbles. At the first tree, I put a pebble in the bag (my set went from zero to one). At the next tree, I put another pebble in the bag (my set size is now two). I keep doing this for every tree. At the end of the street, my set size is the count of trees.

And note the abstraction of pebbles standing for trees. The whole notion of numbers is based on the bag of pebbles and street of trees being the same a numeric level.

§ §

Okay then, so here’s the thing. In a common version of the mathematics of this set theory for numbers, the set items are themselves sets. The process starts with the empty set (called the null set, written as {}), which represents zero. And a successor function (often just called S) for getting the next set.

If we give the successor function the null set, it should return a set representing one — a set with one thing in it. The only thing we know about is the null set, so the set for the number one contains one null set (written as { {} } — a (null) set within a set).

Now it might seem obvious that the set representing two would have two null sets (written as { {}, {} }), the set for three would have three ({ {}, {}, {} }), and so on. (I’ve added spaces for clarity.) Seems simple and easy, but that’s not how it works, and until now I’ve never understood exactly why not.

The way it really works differs beginning with two. Rather than just two null sets in a set — which would indeed have the size two — the set for two contains the set for one plus the set for zero (written as {{{}}, {}}). The set for three contains the set for two, one, and zero (written as {{{{}}{}}, {{}}, {}}). And so on.

As you might imagine, this gets involved quickly. For instance, here’s the set for the number ten:

{{{{{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}},​{{{{}},​{}},​{{}},​{}},​{{{}},​{}},​{{}},​{}}

I kid you not. And I’ve long wondered exactly why it needs to be like that. What’s wrong with getting the set size by just adding the null set over and over as needed?

§

Well, as it turns out, plenty. For one thing, abstracting a bit by showing the lengths of the sets rather than the sets (because that would be crazy), what we want for the set for ten is:

10 := {9, 8, 7, 6, 5, 4, 3 ,2, 1, 0}

But in using just the null set, we’d be defining ten as:

10 := {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

And while both sets are size ten, the first version is built on all previous versions and its ten members are all distinct and sortable. Not so the second version.

Fine, that makes sense, but couldn’t each member just be a set with the right number of nulls? The definition above is recursive. Again, using just the lengths of the sets, the actual definition is:

10 := { {9,8,7,6,5,4,3,2,1,0}, {8,7,6,5,4,3,2,1,0}, {7,6,5,4,3,2,1,0} … {0} }

And each one of those lengths expands into its own set of nested sets. It seems like a lot of sets, and what do they all accomplish?

§

That’s the lightbulb. They accomplish something important. Because each number contains all previous numbers, you can trace (justify!) any number all the way back to the axiomatic zero. To follow a number down, just recursively take the largest set member (which I’ve consistently shown first, sorting sets from largest member to smallest). When you reach the empty set, that’s the zero that grounds all numbers.

All the braces make it hard to follow, so let’s try a simple example, the set for the number three:

3 := { {{{}},{}}, {{}}, {} }

It has length three and contains the sets for two, one, and zero. If we take the largest member, the set for two, we have:

2 := { {{}}, {} }

Which has length two and contains the sets for one and zero. If we again take the largest member, the set for one, we have:

1 := { {} }

Which has length one and contains the set for zero. We take the last set, and:

0 := {}

We’ve reached the axiom, which took three steps. Essentially, we’ve counted down from zero. Three recursions of the successor function count up to three:

3 := S(S(S(0)))

Because S(0)=1, S(1)=2, and S(2)=3.

You could do the same thing with the set for ten above, it just takes a few more steps.

Bottom line, sets are recursive so that every subset they contain is also a valid number-representing set. A set of, say, eight null sets to represent eight isn’t sortable and isn’t recursive, so it only has size.

And counting by adding and removing an arbitrary null set isn’t as justifiable as counting up by including all previous sets or counting down by taking the highest number in the set.

It’s actually pretty cool, and I’m glad the lightbulb finally went fully on.

§ §

The smaller lightbulb is just that I’d tried twice in the past to write some Python code to generate sets. It’s a fairly simple recursion, so how hard could it be? But twice I couldn’t seem to wrap my head around it.

I stumbled over it recently and thought to give it one more shot. Much to my surprise, it was pretty easy. Made me wonder what I’d missed before.

For whatever it’s worth, here’s that Python code (I even wrote an adder that can add two sets):

§ §

Stay theoretical, my friends! Go forth and spread beauty and light.

∇