Tuesday, November 01, 2005

Binary operators and the zero case

Suppose we have a binary operator S × S → S with a left identity e. Let's define a new function ◊ on finite sequences of elements of S as follows: ◊(A) = e, if A is the empty sequence; and ◊(A) = ◊(prefix(Ak))Ak, if A is a sequence of length k+1. I've found this new function referred to as the "bulk action" of , as an "iterated binary operation", and in the context of parallel programming, as the "prefix operation", but couldn't find evidence that any of these terms is in widespread use. I'll use the phrase "bulk action" until someone points me to a better phrase.

The bulk action is well-known for some common operators, and less well-known for others:

OperatorBulk ActionIdentity
+ (addition)∑ (finite sum)0
× (multiplication)∏ (finite product)1
∧ (conjunction)∀ (universal quantification)true
∨ (disjunction)∃ (existential quantification)false
↑ (maximum)max (maximum)-∞
↓ (minimum)min (minimum)+∞
Note that I'm playing a bit fast-and-loose here in using the infinities. It just means the underlying set S can't be the integers or the reals, but must instead be extended to include the infinity elements, with the natural extension of the min and max operators.

As a programmer, I've frequently found code that behaved incorrectly or was overly complex because of a failure to make the behavior on empty lists consistent with the identity element. Consider it a red flag if you have to unroll the first loop iteration.

Thursday, October 27, 2005

Zero and the empty set

How do you feel about zero and the empty set?

I just finished reading Where Mathematics Comes From, by George Lakoff and Rafael Núñez. On the whole, I enjoyed the book, and thought it was a nice overview of lots of different mathematical ideas, most of which were familiar to me, and some of which were not. As a mathematician and computer scientist with some AI/cognitive science background, I thought that some of the presentation was a little clunky. Some arguments that I find fairly easy to understand when presented as proofs were less clear when presented textually for a less mathematically inclined audience. I have three main complaints with the book.

The first is with their technique of "mathematical idea analysis", in which they state that a particular metaphor is being applied in some area of mathematics (between two mathematical domains or between a mathematical domain and some conception of the real world), and then provide an explicit mapping between concepts in the two domains. I think the concept is great, but after a few examples it became fairly tedious, and seemed like filler. Maybe this wouldn't be a problem for someone who was less familiar with the domains under discussion.

The second is that while the book did a great job of describing the metaphors and conceptual mappings, it didn't do such a good job of providing evidence that people are actually using these metaphors when doing these kinds of math. Suppose I claim that when people do modulo 3 arithmetic, they are really using mental mechanisms evolved to deal with traffic lights. Even if you think it's a good metaphor (which it probably isn't, for several reasons), it's certainly not obvious a priori that it really describes what's going on cognitively. There may well be experiments to test t he hypothesis, but they would have to be very careful not to confuse correlation and causation. Although I'm confident that Lakoff and Núñez are doing experiments to back up their claims, I don't think the book discussed such experiments sufficiently.

My third complaint is that the book seems to suggest that if a mathematical idea is not obvious or "inherent", it must be a metaphor. It is not obvious that the earth orbits the sun. Does this mean that when we think about the earth orbiting the sun, we are necessarily doing it metaphorically? In particular, I feel that the book treats zero and the empty set or collection unfairly. Just because it took people a while to start using them does not mean that they only exist as the products of metaphor. The authors seem to have a particular problem with the empty collection, and especially confuse it with the absence of a collection, even in the concrete domain of physical objects. I think the problem is that when they talk about a collection of objects in space, they do it in the absence of a notion of boundaries or containers. I can see how a person might have trouble distinguishing an empty collection of objects from the absence of a collection in a vacuum, but who has trouble distinguishing an empty bag of Scrabble tiles from not having a bag of Scrabble tiles, or a circle of string with no marbles inside from an empty floor with no circle of string?

I find zero and the empty set easy to use and understand. Admittedly, not everything about them is obvious, such as uniqueness of the empty set (types?!), the trivial subset relation, and the zero case of things like exponentiation, sums, and products. But I like them. How do you feel?

Friday, October 21, 2005

Welcome...

to a blog about Nothing and Everything.