Doublemix: A new start

Today is January 1, 2018.

Day 1 of Doublemix.

And maybe a new start, perhaps.

If you’re here for posts on the hydrogen economy, skip to the next post (in reverse chronological order), reflections on my Mirai’s first birthday.  This one is only here because I blog too little to warrant a second blog of my own, and it doesn’t fit in with any of the other blogs I like to post and comment at.

2018, if you’ll allow me to start a paragraph with a number, factors as the product of the two primes 2 and 1009.   They are the least primes with respectively one and four digits.  Furthermore each is special in is own way.

1009 in Roman numbers is MIX.  This was the name Donald Knuth gave to the pseudocomputer he used in explaining the algorithms in his volumes The Art of Computer Programming.  Twice that is 2018, hence the name Doublemix.

1009 is not only the least prime with four digits but also the least such whose fifth power, 1045817322864049, contains all ten digits.

You’ve probably heard the story how when Hardy came to visit Ramanujan in hospital he apologized for having come in a tram with such a boring number as 1729.  “Oh no,” said Ramanujan, “it is a very interesting number.  It is the least number expressible as the sum of two cubes in two ways: 9³ + 10³ and 1³ + 12³.”   Well then, what about three cubes?  Good question.  1009 is expressible in two such ways, as 1³ + 2³ + 10³ and 4³ + 6³ + 9³, and that’s the smallest.

And when you write primes in English, 1009 is the least one containing the letter ‘a’.

1009 is a remarkable number.  Many more of its properties can be found here.

So take that, 1729.  Why, you’re not even a prime!

Let’s move on now to the smaller of the two factors of 2018.  2 has been special for millennia, as the number motivating the whole idea of counting.  If whenever you counted a collection you never got past 1, no one would have invented counting.

Russell and Whitehead’s Principia Mathematica develops its subject matter with such great care that they do not feel prepared to claim 1 + 1 = 2 until page 379.  Yet two thousand years earlier, had Roman mathematicians used concatenation to denote addition, instead of multiplication as we do today, they could have proved that II est II simply by pointing harder.  (The equal sign did not appear until the 16th century.)

And half a century before Russell and Whitehead, George Boole had shocked his contemporaries with an arithmetic in which 1 + 1 was not 2 at all.  This is what we call today Boolean algebra, the arithmetic of 0 and 1.  1 +1 could not be 2 because 2 didn’t even exist in Boole’s curious system.  In Boolean algebra counting reduces to yes (1) or no (0) as the answer to the question, “Am I holding up any fingers?”, as distinct from the higher math question, “How many fingers am I holding up?”

With such a limited repertoire, the entire gamut of possible values for 1 + 1 amounts to just 0 or 1.  And in fact Boolean algebra provides for both answers by providing two ways of interpreting the operation +, namely as inclusive and exclusive disjunction respectively.  With the former, 1 + 1 = 1, and with the latter, 1 + 1 = 0.

The former was the operation that Boole regarded as the counterpart of addition in his new arithmetic, and he wrote it as +.  So in Boole’s arithmetic 0 + 0 = 0, and 0 + 1 = 1 + 0 = 1. Boole was fine with that, as were his contemporaries.

What was new about Boole’s arithmetic was 1 + 1 = 1.   This was fine with Boole, but it took his contemporaries aback.

Boole also defined conjunction, namely as the operation xy, ordinary multiplication.  This is 1 when both x and y are 1, and 0 in all three other cases.  No one had any problem with taking multiplication to mean logical conjunction.

What about the other possibility for addition?  That’s the operation in which 1 and 1 is 0.  That operation is called exclusive OR, XOR.  Today we write it as x y to distinguish it from x + y.

Boole himself knew and wrote about XOR, but he did not regard it as a basic operation.  He explained it instead as the compound operation x + y − xy : when x and y are both 1, subtract it from the result of x + y so as to not to count twice the case when both are true.

But what is subtraction x − y in Boole’s system?  Is it another basic operation?  Boole glossed over this, but the answer he should have given if anyone was to make sense of his system is that it requires one more basic operation besides x + y and xy, namely ¬x, definable on 0 and 1 at least as 1 − x.  With only the two operations x + y and xy, there is no way to construct 0 when x and y are both 1.   With ¬x we can define x − y  as the conjunction x(¬y) which is 0 except when x = 1 and y = 0.

So that’s Boolean algebra.  It has various laws that are the same as in ordinary algebra, like x + y = y + x, commutativity of addition, xyyx, commutativity of multiplication, and x(y + z) = xy + xz, distributivity of multiplication over addition.  But it also has laws not found in ordinary algebra, like x + xx, idempotence of addition, x² = x, idempotence of multiplication, and x + yz = (xy + xz), distributivity of addition over multiplication.

While these strange new laws didn’t bother Boole they bothered his contemporaries so much that they decided Boole’s system was not an arithmetic of the numbers 0 and 1 at all but the logic of truth values T and F, true and false.  With that distinction there is no reason to expect the algebra of truth values to mimic the algebra of numbers except superficially.

And that’s the way the world viewed Boolean algebra until 1927, eighty years after its introduction, when the Russian mathematician Ivan Ivanovich Zhegalkin pointed out that Boolean algebra was equivalent to arithmetic mod 2.  While keeping xy as a basic operation, he took x y as the other basic operation.  Whereas in Boole’s system xy is a compound or derived operation definable in terms of basic operations as x + y − xy, in Zhegalkin’s system x + y is a derived operation definable in terms of basic operations as  x yxy.

In this way Zhegalkin conferred legitimacy on Boole’s original concept, that truth values can be understood as numbers, by identifying arithmetical addition with XOR instead of OR and reducing all numbers to just their parity, namely their remainder mod 2, their least significant bit or LSB when represented as binary numerals instead of decimal.

Since x ⊕ x = 0 Zhegalkin had no need for a separate constant for 0.  However there was no way to express 1 and so besides the two binary operations Zhegalkin also needed a constant to denote 1.  Once he had that constant he could then express  ¬x as x ⊕ 1.  And with just xy and ¬x we can express x + y as ¬(¬x¬y), implication xy as ¬x + y, and along similar lines all of the many other operations of Boolean algebra.

And now back to the hydrogen highway.

This entry was posted in Uncategorized. Bookmark the permalink.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s