Monthly Archives: June 2006

Category Theory: Natural Transformations and Structure

The thing that I think is most interesting about category theory is that what it’s really fundamentally about is structure. The abstractions of category theory let you talk about structures in an elegant way; and category diagrams let you illustrate structures in a simple visual way. Morphisms express the structure of a category; functors are higher level morphisms that express the structure of relationships between categories.

In my last category theory post, one of the things I mentioned was how category theory lets you explain the idea of symmetry and group actions – which are a kind of structural immunity to transformation, and a definition of transformation – in a much simpler way than it could be talked about without categories.

It turns out that symmetry transformations are just the tip of the iceberg of the kinds of structural things we can talk about using categories. In fact, as I alluded to in my last post, if we create a category of categories, we end up with functors as arrows between categories.

What happens if we take the same kind of thing that we did to get group actions, and we pull out a level, so that instead of looking at the category of categories, focusing on arrows from the specific category of a group to the category of sets, we do it with arrows between members of the category of functors?

We get the general concept of a natural transformation. A natural transformation is a morphism from functor to functor, which preserves the full structure of morphism composition within the categories mapped by the functors.

Suppose we have two categories, C and D. And suppose we also have two functors, F, G : C → D. A natural transformation from F to G, which we’ll call η maps every object x in C to an arrow ηx : F(x) → G(x). ηx has the property that for every arrow a : x → y in C, ηy º F(a) = G(a) º ηx. If this is true, we call ηx the component of η for (or at) x.

That paragraph is a bit of a whopper to interpret. Fortunately, we can draw a diagram to help illustrate what that means. The following diagram commutes if η has the property described in that paragraph.

natural-transform.jpg

I think this is one of the places where the diagrams really help. We’re talking about a relatively straightforward property here, but it’s very confusing to write about in equational form. But given the commutative diagram, you can see that it’s not so hard: the path ηy º F(a) and the path G(a) º η<sub compose to the same thing: that is, the transformation η hasn’t changed the structure expressed by the morphisms.

And that’s precisely the point of the natural transformation: it’s a way of showing the relationships between different descriptions of structures – just the next step up the ladder. The basic morphisms of a category express the structure of the category; functors express the structure of relationships between categories; and natural transformations express the structure of relationships between relationships.

Coming soon: a few examples of natural transformation, and then… Yoneda’s lemma. Yoneda’s lemma takes the idea we mentioned before of a group being representable by a category with one object, and generalizes all the way up from the level of a single category to the level of natural transformations.

The Stupidity of Numerology, illustrated by Infinite Sequences

I was glancing at the comments on the post that I linked to about “0.999…=1”. And one of them was such a wonderful example of crap numerology, which I enjoy laughing at, that I just had to repost it here:

VERY GOOD.
But there’s a couple tricks
you missed.
First, simple pattern
completion
1/9 = .11111—
2/9 = .22222—
3/9 = .33333—
4/9 = .44444—
5/9 = .55555—
6/9 = .66666—
7/9 = .77777—
8/9 = .88888—
and therefore by logical
extension
9/9 = .99999—
but of course, 9/9 = 1.
And then there are the
SPIRITUAL implications
.9 a soul
+ .09
+ .009 adding experience
+ .0009
+ .00009
!
! infinitely increasing
!
or the infinitely
repeating process
of growing greater
i.e. life

Extreme math: 1 + 1 = 2

Finally, I have found online, a copy of the magnificent culmination of the 20th century’s most ambitious work of mathematics. The last page of Russel and Whitehead’s proof that 1+1=2. On page 378 (yes, three hundred and seventy eight!) of the Principia Mathematica.. Yes, it’s there. The whole thing: the entire Principia, in all of its hideous glory, scanned and made available for all of us to utterly fail to comprehend.

oneplusone.jpg

For those who are fortunate enough not to know about this, the Principia was, basically, an attempt to create the perfect mathematics: a complete formalization of all things mathematical, in which all true statements are provably true, all false statements are provably false, and no paradoxical statements can even be written, much less proven.

Back at the beginning of the 20th century, there was a lot of concern about paradox. Set theorists had come across strange things – things like the horrifying set of all sets that don’t contain themselves. (If it contains itself, then it doesn’t contain itself, but if it doesn’t contain itself, then it contains itself. And then really bad actors need to pretend to be robots short-circuiting while Leonard Nimoy looks on smugly.)

So some really smart guys named Bertrand Russell and Alfred North Whitehead got together, and spent years of their lives trying to figure out how to come up with a way of being able to do math without involving bad actors. 378 pages later, they’d managed to prove that 1+1=2. Almost.

Actually, they weren’t there yet. After 378 pages, they were able to talk about how you could prove that 1+1=2. But they couldn’t actually do it yet, because they hadn’t yet managed to define addition.

And then, along came this obnoxious guy by the name of Kurt Godel, who proceeded to show that it was all a big waste of time. At which point I assume Russell and Whitehead went off and had their brains explode, pretty much the same way that the bad actors would later pretend to do.

Don't forget the SB challenge

I don’t want to get too NPR-ish, but: Just a quick reminder about our SB charity thing. GM/BM readers have donated almost $1000 dollars to help get desparately needed supplies for math teachers. And our benevolent Seed overlords are matching up to the first $10,000 worth of contributions through ScienceBlog challenges.
Help some great kids get the chance to learn math and science.

Good Math, Repeating Decimals, and Bad Math

Just saw a nice post at another math blog called Polymathematics about something that bugs me too… The way that people don’t understand what repeating decimals mean. In particular, the way that people will insist that 0.9999999… != 1. As a CS geek, I tend to see this as an issue of how people screw up syntax and semantics.

And it has some really funny stupidity in the comments. 0.9999999… = 1.

One quick quote from the post, just because it’s a nifty demonstration of the fact which I’ve not seen before: (I replaced a GIF image in the original post with a text transcription.)

Let x = 0.9999999…, and then multiply both sides by 10, so you get 10x = 9.9999999… because multiplying by 10 just moves the decimal point to the right. Then stack those two equations and subtract them (this is a legal move because you’re subtracting the same quantity from the left side, where it’s called x, as from the right, where it’s called .9999999…, but they’re the same because they’re equal. We said so, remember?):

10x = 9.99999999...
-        x =  0.99999999...
-------------------------
9x = 9

Surely if 9x = 9, then x = 1. But since x also equals .9999999… we get that .9999999… = 1. The algebra is impeccable.

I also need to quote the closing of one of the comments, just for its sheer humor value:

Bottom line is, you will never EVER get 1/1 to equal .99999999… You people think you can hide behind elementary algebra to fool everyone, but in reality, you’re only fooling yourselves. Infinity: The state or quality of being infinite, unlimited by space or time, without end, without beginning or end. Not even your silly blog can refute that.

Friday Random Ten, June 16

  1. The Stills, “In the Beginning”. I accidentally downloaded this from Salon this morning. I know absolutely nothing about the band.
  2. Planet X, “Digital Vertigo”. PlanetX is quite a strange group. All instrumental, something like a cross between bebop and heavy metal. Great group, highly recommended.
  3. Darol Anger and the Republic of Strings, “Ouditarus Rez”. Darol is one of my favorite musicians. He’s a violinist who at different times has played everything from classical to jazz to bluegrass to rock; he’s performed with everyone from Emmylou Harris to Bela Fleck to Joshua Bell. The Republic of Strings is one of his recent ventures; and they do a range of styles from old-time fiddle tunes, to full-of-fire country fiddling, to jazz vocal tunes.
  4. Flook, “Larry Get Out of the Bin / Elzic’s Farewell”. Flook is the greatest instrumental Irish band in the known universe. 4 people, all accousting: probably the worlds best tinwhistle player, an great alto flute(!)/accordion player, one of the greatest bodhran player’s I’ve ever heard, and a really amazing rythym guitarist. Do not miss an opportunity to hear these guys live; even if you think you don’t like Irish music, go hear them, they’ll change your mind.
  5. Oregon, “Prelude”. Oregon is trio playing interesting bop jazz. Sometimes atonal, sometimes downright ugly, sometimes amazing. Led by an Oboe/English horn player who used to do a lot of touring with Bela Fleck before Bela hooked up with Jeff Coughin. (Who is a truly horrible player in my opinion; I don’t know what Bela sees in Jeff; the guy’s loud, repetitive, loud, dull, loud, non-creative, loud, gimmicky, and loud.)
  6. Suzanne Vega, “Straight Lines”. Great tune off of my favorite Suzanne Vega album. I really like her very sparse old stuff.
  7. Solas, “The Wiggly Jigs”. More trad Irish.
  8. Porcupine Tree, “Prodigal”. PT is one of my favorite neo-progressive bands. They’ve got a really great sound, blending almost bizzarely smooth vocals with dense distorted guitar.
  9. Dream Theater, “Stream of Consciousness”. Dream Theater is neo-progressive heavy metal. Great if you like that kind of thing, which I definitely do.
  10. Lunasa, “The Cullyback Hop”. And one more trad Irish band. Lunasa is a very traditional instrumental Irish band. Very up-tempo, a bit too much so at times, but full of amazing energy, traditional instrumentation, and a very trad style. Melody lead is generally flute and Uillean bagpipes, with guitar and bass backing. It’s damned hard to sit through a Lunasa album without wanting to get up and dance. The ultimate Irish concert experience would be a double billing of Flook and Lunasa.

What timing! Dembski again demonstrates innumeracy

Right after finishing my post about how Dembski has convinced me that he is not a competent mathematician, I find PZ linking to a Panda’s Thumb post about Dembski, which shows how he does not understand the meaning of the mathematical term “normalization”.
Go look at the PT post: Something rotten in Denmark?
Is this guy really the best mathematician the ID folks have available to represent them?

Dembski's Profound Lack of Comprehension of Information Theory

I was recently sent a link to yet another of Dembski’s wretched writings about specified complexity, titled Specification: The Pattern The Signifies Intelligence.
While reading this, I came across a statement that actually changes my opinion of Dembski. Before reading this, I thought that Dembski was just a liar. I thought that he was a reasonably competent mathematician who was willing to misuse his knowledge in order to prop up his religious beliefs with pseudo-intellectual rigor. I no longer think that. I’ve now become convinced that he’s just an idiot who’s able to throw around mathematical jargon without understanding it.
In this paper, as usual, he’s spending rather a lot of time avoiding defining specification. Purportedly, he’s doing a survey of the mathematical techniques that can be used to define specification. Of course, while rambling on and on, he manages to never actually say just what the hell specification is – just goes on and on with various discussions of what it could be.
Most of which are wrong.
“But wait”, I can hear objectors saying. “It’s his theory! How can his own definitions of his own theory be wrong? Sure, his theory can be wrong, but how can his own definition of his theory be wrong?” Allow me to head off that objection before I continue.
Demsbki’s theory of specicfied complexity as a discriminator for identifying intelligent design relies on the idea that there are two distinct quantifiable properties: specification, and complexity. He argues that if you can find systems that posess sufficient quantities of both specification and complexity, that those systems cannot have arisen except by intelligent intervention.
But what if Demsbki defines specification and complexity as the same thing? Then his definitions are wrong: because he requires them to be distinct concepts, but he defines them as being the same thing.
Throughout this paper, he pretty ignores the complexity to focus on specification. He’s pretty careful never to say “specification is this”, but rather “specification can be this”. If you actually read what he does say about specification, and you go back and compare it to some of his other writings about complexity, you’ll find a positively amazing resemblance.
But onwards. Here’s the part that really blew my mind.
One of the methods that he purports to use to discuss specification is based on Kolmogorov-Chaitin algorithmic information theory. And in his explanation, he demonstrates a profound lack of comprehension of anything about KC theory.
First – he purports to discuss K-C within the framework of probability theory. K-C theory has nothing to do with probability theory. K-C theory is about the meaning of quantifying information; the central question of K-C theory is: How much information is in a given string? It defines the answer to that question in terms of computation and the size of programs that can generate that string.
Now, the quotes that blew my mind:

Consider a concrete case. If we flip a fair coin and note the occurrences of heads and tails in
order, denoting heads by 1 and tails by 0, then a sequence of 100 coin flips looks as follows:

(R) 11000011010110001101111111010001100011011001110111
00011001000010111101110110011111010010100101011110.

This is in fact a sequence I obtained by flipping a coin 100 times. The problem algorithmic
information theory seeks to resolve is this: Given probability theory and its usual way of
calculating probabilities for coin tosses, how is it possible to distinguish these sequences in terms
of their degree of randomness? Probability theory alone is not enough. For instance, instead of
flipping (R) I might just as well have flipped the following sequence:

(N) 11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111.

Sequences (R) and (N) have been labeled suggestively, R for “random,” N for “nonrandom.”
Chaitin, Kolmogorov, and Solomonoff wanted to say that (R) was “more random” than (N). But
given the usual way of computing probabilities, all one could say was that each of these
sequences had the same small probability of occurring, namely, 1 in 2100, or approximately 1 in
1030. Indeed, every sequence of 100 coin tosses has exactly this same small probability of
occurring.
To get around this difficulty Chaitin, Kolmogorov, and Solomonoff supplemented conventional
probability theory with some ideas from recursion theory, a subfield of mathematical logic that
provides the theoretical underpinnings for computer science and generally is considered quite far
removed from probability theory.

It would be difficult to find a more misrepresentative description of K-C theory than this. This has nothing to do with the original motivation of K-C theory; it has nothing to do with the practice of K-C theory; and it has pretty much nothing to do with the actual value of K-C theory. This is, to put it mildly, a pile of nonsense spewed from the keyboard of an idiot who thinks that he knows something that he doesn’t.
But it gets worse.

Since one can always describe a sequence in terms of itself, (R) has the description

copy '11000011010110001101111111010001100011011001110111
00011001000010111101110110011111010010100101011110'.

Because (R) was constructed by flipping a coin, it is very likely that this is the shortest
description of (R). It is a combinatorial fact that the vast majority of sequences of 0s and 1s have
as their shortest description just the sequence itself. In other words, most sequences are random
in the sense of being algorithmically incompressible. It follows that the collection of nonrandom
sequences has small probability among the totality of sequences so that observing a nonrandom
sequence is reason to look for explanations other than chance.

This is so very wrong that it demonstrates a total lack of comprehension of what K-C theory is about, how it measures information, or what it says about anything. No one who actually understands K-C theory would ever make a statement like Dembski’s quote above. No one.
But to make matters worse – this statement explicitly invalidates the entire concept of specified complexity. What this statement means – what it explicitly says if you understand the math – is that specification is the opposite of complexity. Anything which posesses the property of specification by definition does not posess the property of complexity.
In information-theory terms, complexity is non-compressibility. But according to Dembski, in IT terms, specification is compressibility. Something that possesses “specified complexity” is therefore something which is simultaneously compressible and non-compressible.
The only thing that saves Dembski is that he hedges everything that he says. He’s not saying that this is what specification means. He’s saying that this could be what specification means. But he also offers a half-dozen other alternative definitions – with similar problems. Anytime you point out what’s wrong with any of them, he can always say “No, that’s not specification. It’s one of the others.” Even if you go through the whole list of possible definitions, and show why every single one is no good – he can still say “But I didn’t say any of those were the definition”.
But the fact that he would even say this – that he would present this as even a possibility for the definition of specification – shows that Dembski quite simply does not get it. He believes that he gets it – he believes that he gets it well enough to use it in his arguments. But there is absolutely no way that he understands it. He is an ignorant jackass pretending to know things so that he can trick people into accepting his religious beliefs.

A really easy "Ask an SBer".

As usual for this time of the week, the seed folks have tossed out a new “Ask a Science-Blogger” question for us to answer. This weeks is particularly easy. The question:

How is it that all the PIs (Tara, PZ, Orac et al.), various grad students, post-docs, etc. find time to fulfill their primary objectives (day jobs) and blog so prolifically?

The answer: Insanity.
(Full disclosure: I’m not a PI; that is, I’m not an academic researcher who needs to do grant proposals to get funding for my projects. However, I am a professional researcher for an industrial research lab, and while I don’t write grant proposals, I do write project proposals to get projects funded, and I have to show results to the people who give me money for my projects. In the end, it’s not all that different.)

Help the SB gang help schools.

Janet over at Adventures in Ethics and Science has gotten a bunch of us SB folks to get involved in raising money for school science programs. As the only current resident math geek around here, I’m expanding it from just science to also math.
What we’re doing is trying to get people to donate to DonorsChoose.org. That’s an organization where teachers who’s classrooms lack the supplies that they need can submit proposals, and donors can select specific proposals that they want to support. Each of the participants from SBs has picked a bunch of proposals that we think are valuable, and we’re asking you guys, our readers, to look at those proposals, and donate some money to whichever ones you think are worth supporting.
This is something that is very near and dear to my heart. Back in my college days, I did some teaching for something called the Educational Opportunity Fund in NJ. EOF is now gone due to budget cuts. But back then, the idea of it was, take a bunch of really smart kids from really bad schools, and bring them to Rutgers for the summer. For the summer, they worked two days a week, and took classes three days a week. During the school year, they also had to go to EOF classes every weekend. If they continued to participate in this all the way through high school, then EOF would give them a scholarship to Rutgers. I taught for the EOF summer program for three years. And I got to know some of the smartest, greatest kids you could ever hope to meet.
One of the things about working for EOF that used to depress me was talking to my kids about their normal schools. They went to schools where there weren’t enough textbooks – or often any textbooks – much less any better school supplies. If it wasn’t for EOF, most of these kids would never have had any chance to get to college: not because they weren’t smart enough, and not because they weren’t willing to work hard enough; and not even because the teachers in their schools weren’t good enough to prepare them for college. They would have had no chance simply because in a classroom with no books, with no paper, with no chalk – there’s no way to teach them.
My daughter started kindergarten this year. Her kindergarten classroom – just one kindergarten classroom for 20 kids – has more supplies for teaching math than the entire schools that my EOF kids went to.
It’s a god damned crime. Every school should have textbooks, blackboards, and the basic teaching materials that teachers need. Kids like the ones I taught in EOF are getting screwed over every day by schools that simply do not have the materials that they need to teach them.
So, I’ve gone through the proposals for math classes in the NYC area, and selected a big list of proposals, ranging over pretty much every grade level. They’re mostly small proposals for basic supplies that every math class should have.
Our wonderful Seed overlords have donated a bunch of goodies, as have a variety of other organizations drafted by SBers. If you want to donate some money to any of the things proposed by any of the SBers, send a copy of your contribution confirmation email to sb.donorschoose.bonanza@gmail.com, and you’ll be entered into a drawing to get one of those.
Go throw a few bucks at donorschoose. The GM/BM challenge is here. You can find all of the SB challenges through Janet’s post here.
I’ll be throwing in a couple of hundred dollars worth of pledges this afternoon. Why not help, and go over now and give them some money?