For some reason, recursion never ceases to fascinate me. Whether it’s the “garden-variety” recursion of a first-year Comp Sci course, or the more mind-bending mathematical psuedo-paradoxes you find in Hofstadter’s writings, it’s all great.
Sometimes, it isn’t immediately obvious that a thing is recursive, or self-referential. For example,
All general statements are false.
Seems logical enough on the first reading. Think about it some more; is it right, or wrong? Is there something wrong with the way it’s written? It doesn’t break any of the rules of English grammar, and it is a sensible sentence whose meaning is clear… The conundrum, of course, is that the above sentence is a general statement, which means that by it’s own proposition, it should be false; I’ll let you chase the rest of that particular chain of reasoning around on your own.
A more historically serious question, in Mathematics and logic, has to do with set theory. Normal sets are well-known; there’s the set of all integers, the set of all whole numbers, the set of all rational numbers, the set of all real numbers…. and you could go on. You could have the set of all odd numbers, even numbers, numbers divisible by 13, the set of all prime numbers, complex numbers, imaginary numbers, or any other description you could name. I suppose you could even try to form the set of all uncategorizable numbers, but I’ll leave that as an exercise for the reader (would this be the set of all numbers which do not belong to a set? Hmm).
Going on from the idea of sets, you could decide to say that S is the set of all sets — no set left out. Then you could take the set of all subsets of S… which is another set. The problem there is that S was supposed to be all the sets in existence, and here we just pulled another set out of thin air. Cantor and Russell were both aware of this problem, the main difference being that Russell was quite concerned about it, and Cantor was not[1]. Then again, Cantor is also the fellow who showed us that some infinities were more infinite than others.
It may be hard to see what the exact problem is in the above scenario, and why it would bother logicians who sought to explain all mathematics with simple rules. In that case, look at it in this way. Let’s take S again as the set of all sets. Well, S is a set, too. Therefore it ought to be a member of itself. If we allow that, then we allow that some sets are members of themselves, and if we tried, we could probably come up with other examples; from there, we could take S` as the set of all sets who are members of themselves. Now, is S’ a member of itself, or not?
By now you might be wishing you’d never started reading this post. Either that, or this is just your sort of thing. In either case, I’ll leave with this thought:
There are only two types of people in the world: those who believe that the world can be divided into only two types of people, and those who don’t.
Think about it for awhile.
[1] Crossley, J.N., et al. What is Mathematical Logic? Dover, New York: 1972
