I often have trouble maintaining long-term direction in my work. I can’t remember exactly what I worked on three days ago; what I did three weeks ago is hazy at best. This makes it hard for me to keep the big picture in mind – how much time and effort I’ve really devoted to any particular project.

That’s why I’ve written a command-line program to keep track of what I’ve done. It’s called wj, which stands for work journal. It’s free and open source – installation details below.

wj helps you record and summarize what you do each day, week, month, and year. At the end of each year you get a one or two page pdf summary of everything you did, expressed in a clean week-by-week list of your accomplishments.

This is my personal replacement for software-based todo lists. I like short-term todo lists that are meant to be disposed, because they help me think carefully about what I want to do in the next several hours. If the todo list isn’t disposable, then the things I thought I wanted to do, but don’t really, just pile up undone and build useless stress.

So wj is not a todo list – it’s a done list. It’s a way to get feedback without a manager. If your work is lagging, you can see it quickly using wj. If you’re doing well, you can see that, too, and reward yourself.

Here’s a sample screen:

To use wj, just type ./wj.py from the command line. I have a symlink set up like this:

$ sudo ln -s /path/to/my/wj.py /usr/local/bin/wj

so I can just type wj anywhere to run it. wj also has a command-line interface so it can easily be used within bash scripts or anything else that can call command-line functions (so, virtually any modern programming language). Since it’s written in python, you can also import it as a python module and gain a deeper level of control over how you interact with wj – write your own interface to it, for example.

Features

wj records a snippet of text about what you did every day, week, month, and year you use it. This is text you must enter yourself, nothing magic. It keeps these snippets organized chronologically and by time scope (day/week/month/year). It can generate a pdf for each year you use it (technically, it generates a tex file that you can turn into a pdf by running pdflatex). I’ve designed the pdf to capture a detailed overview of an entire year in just two pages. This pdf includes every snippet at the year, month, and week level. Imagine using wj for 10 years, and having a nicely formatted 20-page notebook with everything you’ve done, down to the week, for the past decade. To me, this vision is very satisfying, and I see wj as a tool to help me achieve this.

For more specific details on how to use wj, type wj -h for the command line actions, or just run wj with no parameters to enter interactive mode (screenshot above).

wj also supports two calendar modes. Gregorian is the default mode that most people use. I use a different calendar system that I created called the 7date, which basically uses the day-of-the-year written in base 7. I could easily fill another blog post detailing the advantages of the 7date, but for now I’ll be brief and simply say that it’s a better system that is fully supported by wj. If you like the Gregorian dates you’re used to (things like Dec 10th 2025), then there’s no need to worry about the 7date at all – Gregorian is the default mode in wj.

Here’s a sample pdf for my year so far. The dates on that are 7date months and weeks, so they’ll just look like numbers to most people (sorry about that). wj didn’t exist at the beginning of the year, so my entries start later in the year.

Design principles

wj.py is the only file you need to run wj, along with python2.6 or later. I despise the complexities that often go along with installations and dependencies, so I put everything in this one file.

All the data is kept in the directory ~/.wj. If you want to backup your data, copy this directory somewhere. It will contain one file called config, which has some comments to assist you in editing it, and one file per year you’ve used wj, named after the year it depicts.

wj is open source under the Apache 2 license. It is free to use and redistribute, and will remain free forever. I would be happy to have code contributions that improve it within the vision. I would like to avoid new features. Mainly I would love to see it get a little easier to use, install, and look a little better – primarily in the pdf output.

Installation

The github project for wj is here:

https://github.com/tylerneylon/wj

If you want to download it, you can get it from here:

https://github.com/tylerneylon/wj/downloads

As I said above, you can run it directly by typing ./wj.py from the directory you downloaded it to, or you can create a symlink using the above command (the “sudo ln -s …” one), and then just type wj from anywhere.

Enjoy!

On Friday (30 Sept 2011), US drones purposefully killed two US citizens without a trial. We can be confident that one of the men killed was active in supporting acts of violence against the US (and others); about the second man the situation is less clear.

Is this legal? Absolutely not. The fifth amendment states that “No person .. shall be deprived of life, liberty, or property, without due process of law.” Rising above actions like this are part of the bedrock of our country, explicitly vilified since the bill of rights was effected in 1791.

In practice, we have reached a point where sticking the label “terrorist” on a person unilaterally denies their fundamental civil protections. We look back on the days of the “unamerican” slur and laugh, yet here we are again. Black-box labels like this are dangerous, and have always been. Once someone is called an X, you’re not supposed to ask, “how do we know they’re an X?” or “don’t they still have rights?”

This is a slippery slope, one we may already be sliding down. Earlier today (2 Oct 2011), Aaron Bassler was shot and killed on suspicion of murder. The manner of his death seems questionable to me. Reading articles such as this one, it sounds as if he was shot without warning, and that he did nothing at the moment to provoke being killed. Use-of-deadly-force standards are tricky, but my impression is that they were violated here.

There’s something called the Garner standard, named after a supreme court case (Tennessee vs Garner 487 US 1, 1985), listing three major conditions in order to allow use of deadly force. One of these is that the suspect must be given warning if feasible. It sounds like Aaron Bassler was given no warning before being shot.

I have little sympathy for the individual targets of these attacks because there is strong evidence for their guilt (though I worry about the drone’s bystander victim). But we should not confuse personal judgment with justice. Something has gone wrong here. The due process of law is part of what make the US the US. It is part of civilization itself. I’m glad I’m not the only one to take note of this, and I hope we have the maturity to begin a course correction.

I just finished reading the book on programming in C, which is appropriately called The C Programming Language, by Brian Kernighan and Dennis Ritchie. It’s nicknamed “K&R” after the authors. Dennis Ritchie invented C and was a major designer of unix. Brian Kernighan wrote cron and is the k in awk, among other awesome things.

The thing is, I’ve known C for a long-ass time – since before Microsoft released their first C++ compiler, which is when I learned C++ (from the book that came with the MSVC 1.0 box). So why did I bother to read K&R now?

First, it’s an inspiringly well-written book. There are a very small number of books that start from the basics and lead you all the way through to the advanced stuff, without skimping on the details, and this is one of them (another is Calculus by Michael Spivak, or The TeXbook by Donald Knuth). I love books like that. They are both fun and efficient to read – beautiful. Secondly, the more I program, the more I appreciate deep mastery of a language. And finally, I am in the midst of designing a new programming language for fun.

Interesting stuff from K&R

I thought about turning this into an essay, but it’s more fun to read the way I took the notes: as a random jumble of interesting tidbits that caught my eye as a veteran C programmer reading K&R for the first time. If you’re in the same position – you know C but haven’t read K&R – consider this a summary just for you!

• The point of a struct tag (as in struct tagname { int i; float f; };) is to effectively define a new type called struct tagname. I’ve always used typedef’s, so I never really understood the point of the tags before.
• The authors like 4-space indents (I like 2, and Linus Torvalds likes 8).
• The authors are ok with brace-free one-line code blocks, such as a single line after an if statement. Every style guideline I’ve ever read (and yes, I’ve read a few) has forbidden this, so it’s interesting.
• They like assignment and/or increments within conditional expressions (as in the line if ((fp = fopen(*++argv, "r")) == NULL) { on page 162.) I prefer to have about one primary verb per line of code.
• They sometimes declare function prototypes within function definitions. I didn’t even know that was legal.
• They sometimes declare both variables and function prototypes in the same comma-delimited list.
• The names for argc and argv come from “argument count” and “argument vector”.
• The type void was originally not in the language.
• They didn’t seem to feel very strongly against global variables. I’ve read in many places that global variables are basically forbidden, though I personally think they are not so bad if you can use them without polluting the global namespace, treating them as essentially local to a file or very small set of files.
• There is a rationale behind the syntax for all pointer declarations (including for function pointers): they are designed so that if you replaced *myVar with just myVar, you’d get a declaration for the pointed-to object. And they chose this since, at usage time, when you dereference a pointer, you are talking about *myVar, so there is some consistency there (I wish someone had told me this idea a long time ago – it makes a lot more sense now!)
• The authors sound as if they wished malloc could have returned a more specific type based on the input, which makes sense. I like that they care more about design honesty than salesmanship.
• You can make bit-fields with a struct! As in, you can declare struct fields to be a certain number of bits in size. I didn’t know that. I guess most people prefer bit-wise operators, though, because I don’t think I’ve ever seen that used.
• In printf, you can provide variables for field-width specifiers; for example printf("%*s %*.*f", 8, "hi", 5, 2, 3.14159) will print out "      hi 3.14".
• The authors don’t mention buffer overflows when talking about things like sprintf, strcpy, or memcpy. Ruh-roh, be careful newbie coders!
• File-handling functions like fputs or fprintf accept the FILE pointer in different positions – it would be easier to use if it were always the first parameter. They also include a sample of what’s behind a FILE pointer, which is somehow very satisfying to find out (it always felt like a sort of condescending mystery to me).
• I still don’t know what the beginning c in “calloc” stands for. (Some people say “clear” but I don’t see anything definitive. See here.)
• In example 8.6, they return a pointer to a static variable, which some folks consider to be bad practice.
• Technically, you’re not allowed to compare pointers unless they’re within the same array (or one past the end). I didn’t know it was so restrictive. I also noticed their sample implementation of malloc/free breaks this rule.
• They really like one or two-letter variable names. Check out the implementation of free on page 188. I like slightly more descriptive names, sort of in the python culture (as opposed to ass-long names, as in the java culture).
• There is some insane stuff going on in setjmp.h. I had no idea.
• Here’s an example of a declaration that’s fairly tricky to parse: void (*signal(int sig, void (*handler)(int)))(int) What? It’s a function that takes an int and a function pointer as inputs, and returns a function pointer as well.
• There used to be a keyword called entry but it was dropped from the language. I wonder what it might have done (they don’t say).
• Incremental assignment operators like += used to be written in the other order (and allow spaces between them!) like x =+ 1, but that was changed due to the ambiguity of something like x=-2.

Good stuff.

A new language

I don’t have much to show yet for the new language. The primary goal of the language is to be faster than C but still allow for very nice code, even while working with large-scale programs. I have some specific ideas for the speed in mind.

Other features I’m interested in:

• No classes; instead use scopes and interfaces together. A scope is like a struct in C, but can be smart about inheritance-like behavior, and an interface is like a pure virtual class in C++ or an interface in java.
• Built to give the coder maximal control, lisp-style.
• Post-compile optimization. Nuff said.

((Click here for a pdf of the paper.))

This is a math post to serve as an introduction to the paper linked above.

Many sets of numbers, like the integers, the rationals, or the reals, can be totally ordered, which means there is a binary relation < that satisfies these properties:

1. For any two elements a, b, exactly one of these is true: a < b, a = b, or a > b.
2. If a < b and b < c, then a < c.

To give a less obvious example, think of complex numbers a+bi. Normally we don’t think of them as being totally ordered, but we can say a+bi < c+di iff (a < c or a=c and b < d). Another example that everybody knows, but maybe hasn't thought of as a "total order," is alphabetical order, which tells you exactly how to sort any list of words, even if they're words you've never seen before (as long as you know the alphabet, and the order of that alphabet).

The set of rational numbers Q has an interesting property. Given any other countable set X with a total order on X, it’s possible to embed X into Q. In other words, there is a function f:X→Q such that f is 1-1 and x < y ⇒ f(x) < f(y). To show why this is an interesting property, try to find a function f:Q→Z which does the same thing, where Z is the set of all integers.

Well, don’t try too hard, because it turns out that’s impossible. I’ll explain why. Suppose, for the sake of contradiction, that you have a 1-1 function f:Q→Z with x < y ⇒ f(x) < f(y). Then f(0) and f(1) must be integers. But there are infinitely many rational numbers in the interval (0,1), while there can only be finitely many numbers between f(0) and f(1), so such a function can’t exist.

The point is that, there’s something special about Q that really captures the full complexity of countable total orders. Georg Cantor had a name for the key property: he suggested we say an order is everywhere dense if it has the property that, for any x < y, there is another element z with x < z < y. In other words, between every two elements is another.

The question I’m exploring in the paper is this: Is there an analogue of Q, and of this “everywhere dense” property, for higher cardinalities? Using the axiom of choice, and the generalized continuum hypothesis, the answer is definitely yes, and the proofs are explained in the paper.

To give a preview of how to extend Q to higher cardinalities: Let S₁ denote the set of binary strings indexed by any countable ordinal number, ordered lexicographically with the proviso that, if s is a binary prefix of t, then t < s when the first bit after s is 0; otherwise t > s. It’s easy to see how to embed the real [0,1] interval into S₁ using binary notation, and we can also embed all of R into [0,1] by using any order-preserving bounded function, such as arctan(x)/(π/2). But the other direction is impossible: for example, the first uncountable ordinal, ω₁, is part of S₁, as the set of all 1-only strings, indexed by all the countable ordinals. However, ω₁ can’t be embedded in R. If ω₁ fit in R, then it could be embedded in [0,1]; let x_i denote the distance between f(x_i) and f(x_i+1), and we end up with an uncountable set of positive reals whose sum is finite. To show this last feat is impossible, there must exist an n such that the number of elements x_i > 1/n is uncountable; but then clearly the sum cannot be finite.

By the way, the name “surreal” comes in because the canonical orders are key subsets of the class of surreal numbers.

Download the widget!

This post is about a mac os x dashboard widget I wrote.  It shows the calendar date in a new measurement system: download it here.  (Unzip & double-click the widget to install it.)

I use a different calendar system than most people, one that I made up, but that I think is extremely practical.  I call it the 7date because it’s essentially the number of days passed in a given year, written in base 7.  Any single number-of-days system is much better than the current month/day system, which is much worse than, say, the imperial metric system (inches, feet, etc) versus the SI metric system (centimeters, meters, etc).  Because, for example, a single month is not a standardized unit of measure!!  WHAT?!?!  In the future, people will either laugh or just scratch their heads in bewildered amusement at our archaic measurement standards with respect to time.

I think it makes sense to use base 7 to measure days of the year.  Why?  Because weeks have 7 days.  Weeks are very deeply ingrained into our culture.  We are used to working Monday through Friday, and have many traditions of what to do on Saturdays or Sundays, etc.  If I were a pure scientist trying to devise a universal system of time measurement for use on any planet, by any society, I would not use weeks.  But I’m not being that abstract.  I’m trying to be very, very practical.  If we use a base 7 calendar, then we always know what day of the week a day is by the date itself, since the last digit is 0-6, each one corresponding to a given day.  In the current system, the mapping changes at the start of each year, but we could alter the first day of the week to always be a Saturday, so that days ending in 0/1 are Saturday/Sunday, and then we would immediately know the day of the week of any date – for any year – based on this system.  We could have a slightly altered idea of a month as 7 weeks (call it a 7month), and we would immediately know the 7month (and week-within-month) by looking at a single date — the month would be any digits excluding the rightmost two digits (e.g. May 3rd is 233., so we know 2 full 7months have passed).

The notation also becomes less ambiguous than current notation.  Consider the date 03/04/02, which could by written by someone in Europe thinking of April 2nd, 2003, vs 116.2003.

This system has the added bonus of giving us slightly more weekend time every year.

There are some difficulties with using any new system of measure.  Primarily, conversion.  No strongly superior system of calendar measurement will be easy to convert with the current system, because the current system is so crazy.  So, to be realistic, I admit there’s little chance of many people actually using the new system.  However, I think that nerds would enjoy it, and I can personally enjoy the new system.  I’ve used it for almost a decade now, and it works well.

However, partially since no one else uses the system, I sometimes find it hard to remember the date (I think most people forget the Gregorian date from time to time, so I think this is just human nature, not a shortcoming in the calendar system).  It’s useful to have some tools to work with any calendar system, and so this post introduces a free dashboard widget for mac users.  Just download from the link at the top of the post and double-click to install.  It’s easy to remove from your dashboard if you don’t like it.  It displays the 7date for today, like this:

PS In case any readers remember my old posts about 7date, I actually changed one small thing.  I used to consider the first day of the year as 1.2011 (e.g.), but I changed it to 0.2011.  The first minute of every hour is 00, the first hour of every day is equivalent to 00, the first second of every minute is 00, so it just made sense.  There are a lot of other benefits of starting at 0, which I won’t go into here.

This idea started with a disagreement.  Last Christmas, a good friend of mine professed his belief in a single universal system of morality, and this felt wrong to me, although I could not articulate a counterargument.  After a little thought, this post is my answer: I present a perspective on morality by which I conclude that there’s something fishy about the idea of a single universal system of morals.

Consider traffic laws.  Cars drive on the right side of the road in the US.  Some intersections have stop lights, some have stop signs, others have yield signs, or are built as on-ramps and off-ramps without any need to stop.  We have a set of rules for dealing with virtually any situation that may arise.  And when something goes wrong, there is often a sense that someone has made a mistake to cause the problem, such as a driver being drunk.

Traffic laws are designed with the global good in mind.  They are designed to be fair, and to help everyone get where they’re going.  Emergency vehicles receive special treatment, since some travel is more important than others.  Cars on a highway receive treatment so that they are never forced to stop while on the highway, unlike smaller roads.  So the rules are designed to maximize a certain function of transportation bliss, and this function takes many factors into account.

These laws have changed throughout history.  They evolve to better serve traffic as it changes.  A small intersection starts with a 2-way stop, and may one day graduate to a 4-way stop, then a stop light, and perhaps one day an overpass with on-ramps and off-ramps.  If many accidents happen at a certain spot, things change to avoid future accidents there — perhaps some warning signs, some yellow flashing lights, or even a change in the physical layout of the road itself.  So traffic laws are built from a history of experience in seeing what works and what doesn’t.

In all of these ways, traffic laws shadow moral laws.  Moral rules tend to be thought of as maximizing a nuanced sense of the global good.  When something goes wrong, we often feel that someone has done something morally wrong.  And we can see that specific (moral) laws have a history – they are created as a reaction to something that has previously gone wrong (to avoid it), or something that has gone right (to encourage it).

Now imagine an ultimate, perfect traffic bible – a single set of traffic laws which, when applied universally, exactly maximizes some absolute sense of transportation bliss.  This idea seems a bit silly to me.  It seems silly for a number of reasons:

1. It does not seem that there really is a single, objective function of transportation bliss to be maximized.  Different people will want different choices to be made.  Should ambulances take precedence over fire trucks or vice versa?  Should mothers in labor going to the hospital get a way to travel more quickly, without having to wait for an ambulance?  It seems that, no matter what choices are written down, there will always be room for reasonable argument.

2. Some laws seem quite arbitrary.  It seems necessary to decide that either all cars travel on the right or on the left side of the road by default.  But who is to say which side is better?  In practice, there does not seem to be a huge difference (between, say, the UK-left and the US-right).  Consistency is important, but we still have a sense that many decisions like this could be made either way, as long as they are made, and everything will be essentially the same either way.

3. Things change.  Once there were no cars on the road.  If the traffic bible existed then, it would have to somehow anticipate cars.  It seems inevitable that the nature of traffic will be so different in 500 years that the traffic laws will also need to change.  It does not make sense that any single set of rules could really anticipate all possible forms of practical transportation.  Even if we do not pretend that this traffic bible will ever be a reality – rather, we think of it as an ideal toward which we aspire – even then, it feels as if only a small fraction of it could ever apply to any one time period.

4. It violates the principle of mediocrity.  And this I personally find to be the single most compelling line of thought: the principle of mediocrity states that there is nothing special about humanity.  The Sun does not rotate around the Earth, we evolved from other animals, and so forth.  This principle can be seen behind many great advances in human understanding.  It is a useful principle precisely because it anticipates the type of mistake we are apt to make: considering ourselves special.  If we thought of traffic as an eternal and omnipresent issue facing all known life in the universe, it feels much easier to embrase the idea of an ultimate traffic bible.  And I do admit that traffic is quite possibly a universal problem, given some flexibility for different contexts.  But I’m guessing the reader will agree that, despite being a common problem, traffic does not feel profound.  It is a mediocre phenomena, and a bible feels out of place.

And this is exactly why I think there’s utility in comparing traffic and morality.  It lets us consider morality without the pomp.  Traffic is one version of morality minus profundity.

So I argue that it makes more sense to see morality from a perspective of mediocrity: we are building a very practical system out of a hodgepodge of past experience.  We have a feeling of universal good, but it is amorphous, and most likely induced by our human tendency to think of ourselves and our actions as special.

None of this is meant to detract from the significance of moral questions.  Indeed, traffic laws are very important in our lives.  Perhaps a bit boring by comparison, but very meaningful.  So we see a way in which a system of laws can be vitally important, have a vague sense of a general good, and be constantly improving — all this without the existence of an ultimate perfection.  Each of the reasons I’ve listed above against a traffic bible can be equally well applied to reasoning about a universal system of morals.  The difficulty is in fighting our own feeling of profundity and superhuman depth we easily attach to moral questions.  If we can see that moral questions are traffic questions in another light, our thinking becomes clear.

Tidiness is nice, but the world is not so tidy; there is no universal system of morals.

Break it up into smaller companies.

Companies are a lot like people.  They have values, direction, vision, work ethics, relationships, desires, and on some level even emotions.  They apologize when they mess up, they brag when they succeed, they occasionally make jokes.  And this is good, because people have evolved to be creative specialists, many of whom make the world a much better place.

But there are some key differences.  One of those is that almost every company gets boring with age.  It’s hard to relate to now, but IBM used to be a very cool company.  Electronic Arts used to be innovative and risky.  Microsoft used to be adroit and unpredictable.  And Google used to be awesome.

A lot of companies are built around one or two people.  Bill Gates made Microsoft, Larry Ellison made Oracle, Steve Jobs made Apple.  As far as these people are truly controlling their companies, they tend to create success.  This is especially clear when we look at how well Microsoft or Apple has done with or without Gates/Jobs — the correlation is clear.

Why do companies get boring?  I can tell you firsthand.  I’ve worked at Microsoft and Google, and I have many friends with a lot of combined work experience at most of these places.

These places get boring because they own more than they use.  Think of all the crap you have at home that you never use.  The pile of unread magazines, the orphaned remote controls, mostly-blank notebooks, the unused gadgets you paid too much for to throw away, the presents from friends you feel guilty getting rid of.  This stuff builds up, and adds constraints to your life.  Everyone does it, so it doesn’t feel like anything’s wrong.  It’s just human nature that this happens.

In software companies, they get security reviews.  They get deeper hierarchies, everyone with veto power.  They get more PM’s and managers.  They get more designers, more hardware, more tools, more buildings, more partnerships, more half-done projects, more directions.  More of everything.  And everything has an expectation pricetag, a cost on the future.  If you’re Google, and you have a mail site and a photo-sharing site and a social infrastructure, and if you want to compete with Instagram/Picplz, you can’t just build an iPhone app.  You have to integrate with your internal social stuff, you have to integrate with gmail and picasa and convince your PM’s and your manager and his/her manager and a few VP’s that this is a good idea.  You have to convince security you know what you’re doing, and follow login protocols.  You have to wait for three other projects to finish, each of which change their specs and deadlines continuously.  The list goes on.

For software companies, age is a blanket of barnacles.  The ones that survive have figured out how to keep moving despite the barnacles.  The best ones figure out how to keep the barnacles to a minimum.

Which brings me back to fixing Google.  I care about Google because the core of the company is pure gold.  They have a brilliant, community-constructive attitude.  They love to make things, and they love to make things in a way that has historically vastly improved our perspective on what is possible with technology.

Yet they are mired in cruft.  They have far more resources than they can cohesively use.

The solution is simple yet daunting.  No one person or company should own all that stuff.  I’m not saying throw it away.  I’m saying, break the company up into sister companies.  A conglomerate of smaller companies with unusually-friendly terms amongst them.  Imagine you and your ten best friends all have separate startups, with full profit sharing and mutual open source.  You don’t have any obligations to your friends to do work for them, but you will naturally look for self-benefiting ways to work with them.

How small should the pieces be?  Here’s an acid test: can one person keep in mind a single cohesive idea that encompasses everything the company does, even at a detailed level?  This person should be able to describe in an hour how every single project in the company fits into the main idea of that company.  If you can do this, then the company has returned to a low-barnacle state.  The obligations are minimized, and the energy can go toward creativity instead of constraint-grappling.

That’s the idea.

-

I want to add a note about why anyone should listen to me.  I’m not a Bill Gates or Steve Jobs.  I haven’t led a smashingly successful startup.  But I have been paying close attention to the software industry for about 20 years, and I’ve been working within it (counting school internships) for close to 15 years.  I am running my own company now, and I’ve been thinking about software entrepreneurship since I was a kid.  I care deeply about the success of the industry as a whole, how it affects the world, how well Google does in particular, and how myself and my friends can make a difference in all of this.  A lot of people care about Google, but most of those either work there, or are basically fans.  I don’t fit cleanly into these categories – my personality is averse to opinions formed out of sentiment.  So I offer a combination of detailed technical knowledge of how these companies work, what they do, who works there, aspirations for the projects at these companies, and a penchant for analytic honesty.  I’m calling it like I see it, and the cruft is killing a lot of the awesome Google can still have.

Here are the solutions for the crazy cut puzzles I posted last week.  Did you solve them all?

I recently found out about a simple and fun type of puzzle called a crazy cut, first made famous by Martin Gardner.

The general idea is to take a given shape, and cut it into two pieces with the same shape.  The cut does not have to be a straight line, and the shapes are allowed to be “flipped,” i.e., one shape can be a reflection of the other.  Here’s an example puzzle, with its solution:

Can you find the solutions for each of these four puzzles?

Puzzle number 4 is much harder than the rest.  I’ll post solutions in a few days.

Friends seem to find this puzzle pretty engaging, so I’m thinking about making an iPhone/iPad game with a bunch of these.  Do you guys have any thoughts/ideas on what would make such an app fun?

In this post I’m going to prove that there cannot exist a good notation system for talking about sizes of infinity.

It’s fun to think about big numbers.  And by big numbers, I mean different sizes of infinity.

You can define different sizes of infinity in many ways – there are the cardinal numbers, the more specific ordinal numbers, and then the even more specific (and my personal favorite), surreal numbers.  There are also the hyperreals, but those are not as cool as the surreals.

When you start talking about sizes of infinity, you have your first size of infinity – let’s call it omega – and you get numbers like omega + 1, 2 * omega, omega squared, and so forth.  In the surreals, you can even talk about crazy-sounding things like x = the square root of omega, and this number really does exist (in the surreals), and has nice properties like x * x = omega (we would be offended otherwise!).  The important thing is, I’m not just making up nonsense about some vague idea of sizes of infinity.  These are well-defined mathematical constructs that very smart people have thought about, and nodded sagely in solemn agreement.  For the sake of using something specific, when I say “size of infinity,” or “infinite number,” I’ll mean an infinite ordinal number.

So far so good.  Now for the fun stuff.

A little while ago, I sat down with pencil and paper, and decided to invent a system of notation that would capture the notion of how big different sizes of infinity are.  Having some basic math background I was already aware of Impossible Fact #1:

Impossible Fact #1: No system of notation can express every size of infinity.

Let me be more precise.  By a “system of notation” I mean a way that we can turn a human-writeable string into a fixed ordinal number.  The input string must be from a fixed-size alphabet, since otherwise humans couldn’t practically learn it.  You could suggest analog parameters, such as “the length of this line I just drew,” but then you would be assuming we have infinite-precision measuring capacity, which we don’t.  So a system of notation is any definable function from strings of a fixed alphabet into ordinal numbers.  This is an extraordinarily general definition, and probably includes any practical system any human will ever come up with.

But the first thing to notice (as a mathematician), is that the set of possible outputs from this system of notation is necessarily countable.  And there are an uncountable number of sizes of infinity.  This was one of the first big surprises when set theory was being born – a fact that can be seen in Georg Cantor’s diagonal argument.  So right away, there will be some specific size of infinity that is impossible to write down.  And I don’t mean impossible like some number with a billion kazillion digits is “impossible;” I mean literally, logically impossible.  As in, if you wrote down every number you could possibly write down, you would still be missing a number.

This will not suprise any mathematicians who are reading this, because it is a well-known idea in the math-world.  However, the next fact is something I had to think about a little before understanding.

We know we have to give up on being able to write down every size of infinity – ok.  So let’s compromise.  How about we come up with a system of notation where, for any infinite number x, we can write down some number y with x < y.  That’s a pretty big compromise.  We’re giving up on being able to write down an infinite, arbitrarily-large portion of all numbers.  But, no, infinity has no mercy.

Impossible Fact #2: Any one system of notation will have all its numbers < most numbers.

In other words, no matter what system of notation you invent, there will always be an infinite number y so that x < y for every single number x in the notation.  In fact, it’s even worse than that.  If you take the union of all numbers less than any number in the notation, the set you arrive at will still be smaller (as a set) than the numbers remaining.  In other words, even in this compromised setting, we still are forced to miss so many numbers that our “captured” set looks infinitely small in comparison.

This last point is not completely obvious to see, although the proof from the ZFC axioms (the most commonly-used axioms of set theory) is easy to understand.  Because ZFC works easily with ordinals, I’ll give the proof for ordinals as the sizes of infinity, but surreals are easy to understand as an order-preserving superset of ordinals, so the proof carries over to the surreals as well.

We think of the notation system as a definable function F(x) where x is a natural number (N = natural numbers), and F(x) is an ordinal.

1. By the axiom schema of replacement, there is a set A = {F(x) | x in N}.

Each ordinal number is itself a set, so every element a in A is a set.  Every ordinal o can be defined as the set of all smaller ordinals o = {p : p < o}.  So the union of A is the union of all elements smaller than any number F(x) that we can write in the notation.  We’ll call this union B.

2. By the axiom of union, B = union(A), given by b in B iff b in a for some a in A, is also a set.

Let’s call the rest of the ordinals R.  All ordinals O taken together form a proper class — essentially, they are too big to be considered a set.  (We get paradoxes if we do – see Russell’s paradox.)  As a class, we have R = O – B.

3. B is a set, O is not, so R cannot also be a set.

4. If there were a injective function f:R -> B, then we could use the axiom scheme of replacement (via f inverse) to show that R is a set.  This would be a contradiction, so there is no such f, meaning that R can be thought of as having more elements than B.

We could informally write card(R) > card(B), but some might object since usually we only allow taking card(x) when x is a set.  But we can safely say that R is infinitely larger than B.

QED

In fact, we’ve proven something even stronger than Impossible Fact #2, because even if we pretend that the input for our notation function F(x) is any ordinal, the same proof works to show that we still miss most infinite numbers R.  So, for example, if we allow any real number as an input into our notation, it would still fail.

Alas, there is no system of notation that does what we want.  But at least we know to stop looking.

Final score

Humanity: epsilon (for knowing to give up)

Infinity: omega