Counting

(Intermittent, indeed)

Counting.  What could be simpler?  Well ...

1. Origins and speculation

Counting is older than humanity.  Other primates can count, birds can count and elephants can count.  There are even claims that some insects can count.  How would we know?  Suppose an animal sees three tasty treats put behind a screen, and then two taken away from behind it.  An animal that makes a beeline for the remaining treat, but acts indifferent if all three have been taken away instead, can plausibly be said to have some form of counting.

There's clear survival value in being able to reckon in this way.  If I'm being chased by four wolves and I only see three at the moment, I should be wary.  If I see four run off looking interested in something else, I can probably go back to whatever it was I was doing.

How would a counting ability work?  Totally speculating here, I could imagine having some supply of "markers" in short term memory, which could be mentally placed in some collection of notional locations.    Even a small number of markers and locations would be useful.  If I have three markers, a "visible" location and a "hidden" location, I can track the tasty treats in the first example.  As each treat is hidden, the marker-tracking system puts a marker in the hidden location.  As each is taken out, it goes to the visible location, or is freed up for future use if the if the treat is taken away in real life.  If there's still a marker in the hidden location, I can expect a treat.

This is all handwaving over what a marker or a location might be, or how to make and dissolve the associations between markers and treats, and between the "hidden" mental location and the area behind the experimenter's screen.  Nonetheless, there are testable hypotheses to be made here.  For example, does the subject still respond appropriately if there are two separate screened areas, or seven, or twenty?  Suppose there are two kinds of objects: tasty treats and something useless.  Does the subject behave differently if there is one treat left instead of one useless object?  How many objects can the subject keep track of?

The results would put limits on how many markers, or locations, or kinds of markers there might be.  They wouldn't rule out other explanations, like some sort of purely symbolic approach, but an artful experimenter ought to be able to come up with scenarios that would make one or the other explanation more or less plausible.  I'm certain that people have done just that, but more carefully and thoroughly than what I've described.

If you're thinking this doesn't quite seem to match up with what pops into your head when you think "counting", you'd be right.  Counting as we normally think of it, "one, two, three, four, ... thirty-nine, forty, forty-one ... five thousand nine hundred and thirty-seven, five thousand nine hundred and thirty-eight ..." is a different beast.  A markers-and-locations scheme is limited by the number of markers.  Counting with a number system requires a small set of symbols and a small set of rules.  With those, you can count until you get tired, so long as your number system tells you how to add one more.  Your supply of numbers is still finite -- no one can count from a million random digits to the number after that -- but it's orders of magnitude larger.

This more familiar notion of number is probably much rarer in the animal world.   It's much more closely akin to language, though it's at least logically possible to have a number system without having a fully-developed language.  It's also possible, and I'd think highly likely, that we and any other animals that can count digitally also have a markers-and-locations style capability.  A toddler who hasn't yet mastered counting to a hundred can still track objects behind screens.

2. The mathematicians arrive

Number theory is one of the oldest branches of mathematics.  Pythagoras studied numbers extensively, trying to uncover the mystic harmonies of the universe.  Archimedes showed how to construct ridiculously large numbers, large enough to, say, number the grains of sand on a beach, or even how many it would take to fill the universe as he knew it.  Pascal, Fermat, Euler, Gauss ... all of these and many more had interesting things to say about numbers, but for my money it was Georg Cantor who got deepest into the question of "what is number"?

Cantor helped formalize the notion of a set -- a collection of objects about which we only care if a given item is in it or not.  Cantor postulated that two sets have the same number of items if, and only if, the items in them can be matched up one-for-one.  For example, if I have the set {Groucho, Harpo, Chico} and the set {Julius, Arthur, Leonard}, I can match Groucho with Julius, Harpo with Arthur and Chico with Leonard and know that there are the same number of items in each set.  I can also do the matching five other ways, but the result is always the same.  Either the two sets match up one-to-one or they don't.

Working from this basis, a number is a collection (formally, the equivalence class) of all sets that can be matched up with each other.  For example, the number three would include {Groucho, Harpo, Chico}, {Julius, Arthur, Leonard}, {1, 2, 3}, {42, 17, 23}, {uno, due, tre}, {zebra, desk, Louis XIV} and any other set that can be matched up one-to-one with any (and thus, all) of those.

The numbers that can be described this way include zero (described by the empty set, {}), one, two, and so on ad infinitum.   If you can (at least in principle) list all the objects in a set, or in other words, if the set is finite, then there is a natural number representing all sets of that size.  These numbers do not include negative numbers, fractions, irrational numbers, imaginary numbers, quaternions or other such.  Those need more machinery, but they can all be related to the basic set of natural numbers {0, 1, 2, 3 ...}.

One of Cantor's great discoveries, and one of the most important discoveries in all of mathematics, is that there are numbers, in this sense, beyond the natural numbers that denote the size of finite sets.  For example, how many natural numbers are there?  There are more than, say, three, because 0, 1, 2 and 3 are all natural numbers.  There are more than 497.  There are more than a billion and more than googolplex.  No matter matter how high you count, you can, in principle, always count one more.

If this sounds quite a bit like the second kind of number system above, where you can always count one more, that's because it is.  In a bit we'll see a mathematical description even more closely aligned with it.

If you have any finite set, you can always add another object that's not already in it.  Put yet another way, there is no finite set that you can match up one-to-one with the set of all natural numbers.  The set of natural numbers is infinite.

But Cantor's definition of a number doesn't say numbers have to be finite, so that's fine.  There was quite a bit of discussion about this, but at the end of the day Cantor's rules for reasoning about numbers work just as well for the infinite.  In fact they present a far richer picture than just the single ∞ that we often take to represent "infinity" (this symbol does have perfectly rigorous math behind it, but it has more to do with the mathematical study called analysis than with the set theory we're talking about here).

The collection of all sets that match up one-to-one with the natural numbers is itself a number, which Cantor called aleph-null (ℵ₀).  Are there actually other sets that can be matched up one-to-one with the naturals?  Yes.  For example, the set of points in an infinite square grid.  Start at any particular point and make a spiral outward.  Match the starting point up with zero, the next point with one, and so forth.  There is a natural number for every point in the spiral, and any point you care to pick on the grid, the spiral will eventually reach.

A bit surprisingly, the natural numbers can also be matched up one-to-one with what might appear to be smaller sets of natural numbers.  For example, there is an even number for every natural number, and vice versa.  You can match {0, 1, 2, 3, ...} up with {0, 2, 4, 6 ...} by matching every natural number up with twice that number: 0 with 0, 1 with 2, 2 with 4, 3 with 6 and so on.  There is an even number for every natural and vice versa.  This isn't a paradox or contradiction.  Infinite sets just behave a little differently.

How many sets of natural numbers are there?  Could you match them up with the natural numbers themselves?  Cantor's (second) proof that you can't, the diagonal argument, is a masterpiece, one of those things that sounds like magic or trickery when you first hear it (the first proof is pretty slick as well).  If you can grasp it, and you very likely can, you can probably grasp a large chunk of modern mathematics.  It goes like this:

Try to give each set a natural number.  If there are as many as there are natural numbers, then you can do just that.  For example, here's one partial attempt:

0. {} (the empty set)
1. {1, 2, 3, 4}
2. {0, 1, 2, 3, 4, 5, ...} (all of the natural numbers)
3. {0, 2, 4, 6, ...} (the even numbers)
4. ...

Suppose I come up with a scheme for listing sets of natural numbers so that I can tell you the set for any natural number you like.  Zero gets the empty set.  One, two and three get the sets listed above.  42 gets the set of all primes.  Googolplex plus five gets the Fibonacci numbers ... whatever.  Could such a scheme get them all?

Look at each row in turn, and form a new set thus:  If the row number isn't in the set on its own row, add that number to the set you're building, otherwise don't.  In the case above, the result starts off {0, 3, ...}: zero is not in the empty set, so add it.  One is in the set {1, 2, 3, 4}, so skip it.  Two is in the set of all natural numbers, so skip it as well.   Three is not in the set of even numbers, so add it.

We can continue down the line.  42 isn't prime, so it's in the set.  Googolplex plus five is (almost certainly) not a Fibonacci number, so it's (almost certainly) in the set, and so forth.  Is the set we just made already on the list somewhere?  No.  It's not in row 0, because it contains a number not in the set on that row.  It's not in row 1, because 1 is in that set but not in ours.  And so forth.

No matter how you try to number the sets of natural numbers with the natural numbers themselves, there will always be at least one you missed -- a massive understatement, but one is all it takes -- so it can't be done.

Since you can't match the natural numbers up with the sets of natural numbers, there must be an infinite number besides aleph-null, namely the number of sets of natural numbers, that is, all sets for which you can match up each member with a set of natural numbers and vice versa.  This includes, among other things, all the numbers between 0 and 1, if you include infinite expansions like 0.11111... = 1/9 or pi - 3 = .14159265... (see the bottom of this section for a rough proof).

Call this number aleph-one.  Aleph-one is a bigger infinity than aleph null.  Cantor conjectured, but could not prove, that there are no infinities between aleph-null and aleph-one as defined here, or in other words that aleph-one really should be called aleph-one and not aleph-something-else.  We now know that you can pick either way and get meaningful, though perhaps strange, results.

In any case, one of the most important facts about a set is often whether it contains

• a finite number of elements
• exactly as many elements as there are natural numbers
• more

In the first two cases, the set is countable (in the second case, countably infinite).  Otherwise it is uncountable.  Some interesting results depend on this distinction.  For example, even though there are infinitely many possible computer programs, and infinitely many numbers that a computer program might produce as output if it could run forever, including irrational numbers like the square root of two and numbers like pi that aren't the solution to any algebraic equation, there are still only countably many.  But there are uncountably many numbers between zero and one, which is so many more that if you pick a real number at random (leaving aside exactly what that means), the odds are exactly zero that there's a computer program that could calculate it, even if it had forever to do it.

The basic approach behind Cantor's diagonal argument can also be used to prove a number of other significant results that don't directly involve countability.  These include Gödel's incompleteness theorem, which says there are some true statements that can't be proven true, and Church and Turing's result that there is no computer program that can solve the halting problem of deciding whether a given computer program will always eventually stop running.

Cantor was further able to show that there were infinitely many of these infinite cardinal numbers.  There is an aleph-two bigger than aleph-one, and so forth.  For any aleph you can always find one bigger, by applying the same diagonal proof that found aleph-one in the first place.

Hmm .... "always one bigger" ... that sounds familiar.

Matching things up in order to count them makes sense, but this idea of a number as a collection of sets seems somehow distant from the simple notion of counting one, two three.  Suppose we dispense with sets and start with that?

Start with something called "zero".  This being math, it doesn't matter particularly what it is.  It's really just a symbol.  Let's use 0.  Likewise, take something to represent "one more than".  One common symbol is S, for "successor".  So we have

• 0
• One more than zero, or S0
• One more than one more than zero, or SS0
• and so forth

To translate this to something you're more used to, just count the S symbols, and to represent a particular number (again, whole, non-negative number, including zero), just stick that many S symbols before the 0 symbol.  Numbers considered this way are called ordinals, as opposed to the cardinals described above.

You can tell that one number is bigger than the other if you can make the first number by tacking some number of S symbols in front of the symbol for the second number.  Since SSSSS0 is three S symbols tacked onto SS0, we know that SSSSS0 is bigger than SS0, that is, five is bigger than two, as one would hope..

How many of these are there?  One for every natural number, clearly (just count the number of S symbols).

It would be interesting, at least to a mathematician, to capture some notion of infinity here.  If there are infinite cardinals, why not infinite ordinals?  Infinity would be a number that you can never reach by counting from zero, so let's try to pin that down.  The numbers we've described so far are finite, so let's just postulate that there's a number, call it ω, that's bigger than any of them.  Hey, it's math.  You can do that sort of thing.  You basically just add a rule that says "for any number like those we've described so far, ω is bigger".  Then you hope the new rule doesn't lead to any contradictions.

We'd like this ω to act like any other number, apart from being bigger than any of the naturals, so there should be a number one more than it.  That is, Sω is a perfectly good number in this scheme.  And so are SSω, SSSω, and so forth.  We could also call those 1+ω, 2+ω, 3+ω and so forth.  Put another way, we can add any natural number to ω and get a bigger ordinal.  Counting continues past infinity almost as though infinity never happened.  We can continue this counting as far as we like, and we can say whether one such number is bigger than another just as we did before.

So suppose there's a number bigger than ω with any number of S symbols.  We may as well call that ω + ω, or 2 times ω, or just 2ω.  Likewise, there is a 3ω bigger than 1+2ω, 2 + 2ω or 2ω plus any natural, and a 4ω, and a 5ω, and so on.  And a number bigger than any of those?  Why, that would be ω times ω, or ω².

And likewise there is an  ω³ and an  ω⁴ and so forth (along with numbers like 17  + 42ω + ω⁴) and working from that you can define  ω^ω.  By now you can probably tell that we can keep this up forever.  You end up with something like the infinite cardinals, but more finely sliced.  Ah, math.


[To see that aleph one is the number of real numbers between 0 and 1:  Every such number can be represented by a binary expansion: 0.1 = 1/2, 0.01 = 1/4, 0.011 = 1/4 + 1/8 = 3/8,  0.01010101... = 1/4 + 1/16 + ... = 1/3, etc. The corresponding set for a binary expansion has 0 in it if the first bit after the binary point is 1, 1 in it if the second is 1, and so forth.  For finite expansions like 0.01, the bits are all zero past a certain point, but that's fine.  It just means that the corresponding set only has finitely many numbers in it.  Likewise, there is a binary expansion for each set -- put a zero in the nth place when n is in the set (and only then).  QED.  You do have to be a bit careful because, for example, 0.01 = 0.00111111..., and in general every finite binary expansion can be changed to an infinite one by replacing the last 1 with 01111..., but there are only countably many finite expansions so this doesn't really matter]

3. There were bound to be lawyers involved at some point

Suppose the limit for grand theft is $5,000.  I steal an old car worth $5,000.  Clearly I've committed one count of grand theft.  What if I steal a new car worth $15,000?  I've still committed one count.  What if I steal three old cars worth $5,000?  Keeping in mind that I'm not a lawyer, that ought to be three counts of grand theft.  For example, if I steal one car, serve my time, steal another, serve my time again and steal another, at which point I'm going to be in for a good long time in most states, I've committed three crimes.

What if I snag a $4,000 trailer with three $5,000 cars on it?  Is that one grand theft of $19,000 or one petty theft and three grand thefts?  That would depend on whether we're counting acts of theft (one) or objects stolen (one petty, three grand), and that in turn depends on the particular law.  Not being a lawyer, I'm not sure which way this tends to go, but I'd guess one count of grand theft.

This sort of question comes up all the time in copyright cases.  Was that ten acts of pirating one song or one act of pirating ten songs?  What about pirating the same song ten times?  Still not a lawyer, but I believe the law in this case treats each copyrighted work as a separate count, so pirating ten songs would be ten counts, while pirating one song ten times would be one count (but maybe a more severe one than pirating it once).

The question here is not how to count, as in how to count the even numbers versus the prime numbers, but what to count.

4.  How many rivers run through it?

Pittsburgh lies at the confluence of the Allegheny and Monongahela rivers, which meet to form the Ohio river.  Thus the name Three Rivers Stadium (and several other Three Rivers designations).

In 1858, William Larimer staked a claim on a bluff overlooking the confluence of Cherry Creek and the South Platte (which had long been a seasonal camp for the Arapaho and Cheyenne), and not too long afterward named the place after the governor of Kansas Territory, James W. Denver (who had by that time already resigned his post, unbeknownst to Larimer).

How many rivers run through Pittsburgh?  How many run through Denver?  One could reasonably say that the South Platte River runs through Denver, joined by Cherry Creek, but going by the names, no river runs through Pittsburgh.  Rather, two rivers end at the Point and another begins.

A person traveling by boat from Oil City, Pennsylvania (where Oil Creek flows into the Allegheny), through Pittsburgh to Cairo, Illinois (where the Ohio meets the Mississippi) could be forgiven, though, for thinking that there was a river running through Pittsburgh, particularly since the Allegheny is larger than the Monongahela which joins it.  A hydrologist would likely agree, and go so far as to say the same river flows through New Orleans to the Gulf of Mexico, the Ohio being larger than the Mississippi at Cairo.

The hydrological definition, that when two streams meet the larger of the two is considered to continue and the smaller to end at the confluence, gives a nice, consistent definition, assuming that the size of a stream is well-defined and no two are exactly equal.  Since this definition can be at odds with local names, as at Pittsburgh and Cairo, some might be tempted to say the local names are "wrong", but that may not cut much ice with the locals.

How many rivers run through Los Angeles?  That would depend on whether you call the Los Angeles River a river.  For most of the year along most of its course it's a trickle of water in the middle of a wide concrete culvert.   Near Dodger Stadium it's joined by Arroyo Seco (Spanish for "dry stream") which, as the name implies, lacks even the trickle of water much of the time.  Nonetheless, when the water does flow it flows in significant volume along an identifiable course, so we call it a river.

The Colorado River used to flow into the Gulf of California by way of a lush delta, but for most of the past few decades it has run dry well before then.  Can we say a river runs through that region still?  At this point, maybe not.  If it ran dry some years but flowed for at least part of most years,  probably, but I doubt there's any clear dividing line between mostly dry river and ex-river, at least outside of the technical literature.

Finally, how many rivers run through the Mississippi Delta, that is, the alluvial plain between the Mississippi and Yazoo rivers in western Mississippi, as opposed to the Mississippi River Delta in southern Louisiana?  It's kind of hard to tell.  Streams cut this way and that, split, rejoin, sometimes appear to go nowhere.  Is this a lot of small streams criss-crossing a plain, or a few larger streams with a lot of unusually large islands?  Again, at some point it comes down to arbitrary definitions.

5. What counts?

At least for practical purposes, the world is continuous.  And yet, for various reasons, we comprehend it as being made up mostly of discrete objects.  Counting is fundamentally discrete.  Digital, in fact.  You can't count, or at least not very far, without dividing the world into objects.

Not every creature appears to do this.  Microbes get by on pure, unconscious reaction.  This part of the cell wall is in contact with some nutritious chemical, so those parts of the cell wall contract and the cell moves towards supper.

Only with a mind capable of parsing the world into objects can we begin to talk about counting as a useful activity.  Once there are objects, a markers-and-locations facility is not so remote.  It doesn't have to arise, but it's useful enough and plausibly a small enough step that it's not surprising that it does arise.  The full-blown symbolic version of counting using a few basic names and combining rules, is a whole different matter.

What counts?  In the markers-and-locations sense, quite a few things count, including us.  More will surely be discovered.  In the symbols-and-rules view, it may be just us.