Posted by: Alexandre Borovik | May 29, 2011

More on abstract thinking and computer science

From FOM DIgest Vol 101, Issue 29,  Tue, 24 May 2011 00:41:26 +0200, a post by Jeff Sarnat:

As a computer scientist, I found Cantor normal form for \epsilon_0 to be easy
to understand once I realized that exponentiation at base omega is exactly
the multiset ordering from term rewriting theory. If we choose to implement
multisets as lists sorted in descending order, then this becomes even more
straightforward: the empty list is smaller than all non-empty lists, and
non-empty lists are ordered lexicographically by their heads followed by
their tails. Moreover, ordinal addition and multiplication are easy to
explain in terms of their type-theoretic analogs, which makes it easy to
visualize how data structures built up from these three primitives would be
ordered, and why the resulting ordering should be well founded (although
multiplication is technically unnecessary, it is pedagogically helpful to

My experiences with introducing other computer scientists to the dark art of
ordinal analysis have led me to believe that this approach works well: I can
usually get people to count at least as high as \Gamma_0 [Feferman–Schütte ordinal –AB]  in about an hours
worth of hand-waiving along these lines. For those who are interested, a
(slightly) more detailed account of this approach can be found in Section
3.1 of my dissertation.

Jeff Sarnat


Leave a Reply

Fill in your details below or click an icon to log in: Logo

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


%d bloggers like this: