Monthly Archives: April 2014

computer science expository math

Introduction to Communication Complexity

I just uploaded an essay “Introduction to Communication Complexity” to my website. The essay is a brief introduction to communication complexity, a field which I find fascinating. The essay is self-contained and completely elementary. It should be accessible to anyone who knows what the words “set,” “function,” and “tree” mean.

math musings

The Categorization of Set Theory

I just read an article called Rethinking Set Theory by Tom Leinster in the most recent issue of the American Mathematical Monthly. I found the article very interesting and appealing, so I thought I’d mention it here.

Set theory is the basis of the vast majority classical mathematics. As such, most mathematicians use set theory every day in their work. Yet the majority of mathematicians don’t appeal to the formal properties of set theory–i.e. the axioms of set theory–in their work. Rather, mathematicians tend to use a set of working principles about sets which they constantly rely upon. There is nothing wrong with this approach, as the working principles can be rigorously justified, but it reveals a (perhaps philosophical) disconnect between the theory and practice of set theory.

Leinster’s article in the Monthly proposes an alternate set of axioms for set theory. Instead of starting for the standard ZFC axioms, he suggests formulating axioms that appear more similar to the way in which sets are used by most mathematicians. The inspiration for Leinster’s axioms (which he attributes to F. W. Lawvere) comes from category theory. They place equal emphasis on the concepts of “set” and “function,” whereas in the traditional ZFC theory, the only formal objects are sets.

I find Leinster’s approach to be very appealing. From a practical standpoint, I very much like that his axioms directly appeal to common set theoretic applications. Philosophically, I also appreciate that the axioms seem to reference the way in which sets interact (via functions) rather than describing the internal structure of sets (as does ZFC). This emphasis of external interaction over internal structure seems analogous to humankind’s position in the universe: the internal structure of the universe is a mystery, so we must learn what we can by interacting with as diverse phenomena as possible. Thus perhaps we should learn to understand sets the same way.


Computing Round-up

For today’s computing round-up, I have a few tips that came in handy.

  • The LaTeX algorithmic and algorithm environments make nicely formatted pseudocode for describing algorithms. See the link above for details on usage
  • To recover an auto-saved file from Emacs, use the command “M-x recover-file”. That was a life-saver today when my internet connection decided to crap out. One of the perils of doing all my work remotely through SSH, I suppose.
  • Use Emacs Org mode to organize projects and to-do lists. I’m just starting to get my bearings, but I can already see how it is going to be phenomenally useful for larger projects. Some helpful links: official website; quick tutorial.
  • Unfortunately Org mode has some conflicts with yasnippet (another Emacs tool that I am quite fond of). Here is a link to some documentation on how to fix it.

More Colors on iSSH

A few years ago, I started using an iPad with an external keyboard for most of my day-to-day computing. On app that I’ve found completely indispensable is iSSH, which allows me to use SSH to log into my server from the iPad. I noticed a while ago that the terminal on iSSH didn’t have the same color palette as the terminal app on my desktop. I thought this was a limitation of iSSH, but it turns out that I was wrong. You can actually change the xterm session in iSSH to xterm-256color, which makes everything look much nicer — especially in emacs with text highlighting (see this previous post). To change the settings in iSSH, go to the “edit configuration” page for the connection you are trying to edit and go to SSH -> Shell -> Advanced and change the “Term String” to “xterm-256color”.


Here’s the before:


And after:


Much nicer, eh?


Naive Set Theory

I have posted some notes on naive set theory, available here. They cover the basic algebra of sets and functions. Many of the important identities are left as exercises to reader. A bonus section on Russell’s paradox shows that this “naive” approach to set theory is not sufficient for a rigorous theory of sets–axiomatic set theory is the only way to go.