Via The Art of Problem-Solving, a great video on Mobius transformations. I never really got how the inversion transformation fit in with the others before seeing this!
Wonderful Mobius Transformation Video
Leave a reply
Category Archives: Good Math
Basic Graphs
Let’s talk a bit about graphs, being a tad more formal about them.
The First Graph Theory Problem
Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreirós book; between that, and a new copy of Quine, I should be OK. But in the meantime, we’ll look at something else. Since I mentioned graph theory on friday, and I’ve been promising forever to write about it, I figured this is a good time.
My favorite introduction to graph theory is stolen from one of my grad school professors. It’s the first major use of what became graph theory, which is a proof by Euler.
Here’s the problem. Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it’s got parts of the city on the banks of the river, and parts on two islands. To get around
the city, there were seven bridges connecting the parts of the city. Is it possible to
take a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it’s possible to tour the city crossing each bridge exactly once?
Simple Pathology: Betterave
Sorry for the missed weeks of friday pathological programming language columns. To be honest, I’m running out of languages. I’m sure there must be more, but my usual sources (dealers?) are running out – so send links!
Anyway, today I’m going to look at a really simple one, which I find fun. It’s
not an overly exciting language, but it is a language which is has semantics almost as
trivially simple as [BrainFuck][bf], but which ends up looking almost as much like line-noise as [TECO][teco]. It’s called [Betterave][betterave].
[betterave]: http://www.esolangs.org/wiki/Betterave
[teco]: http://scienceblogs.com/goodmath/2006/09/worlds_greatest_pathological_l_1.php
[bf]: http://scienceblogs.com/goodmath/2006/07/gmbm_friday_pathological_progr.php
Alternative Axioms: NBG Set Theory
So far, we’ve been talking mainly about the ZFC axiomatization of set theory, but in fact, when I’ve talked about classes, I’ve really been talking about the von Newmann-Bernays-Gödel definition of classes. (For example, the proof I showed the other day that the ordinals are a proper class is an NBG proof.) NBG is an alternate formulation of set theory which has the same proof power as ZFC, but does it with a finite set of axioms. (If you recall, several of the axioms of ZFC are actually axiom schemas, which need to be distinctly instantiated for all possible predicates.) NBG uses one axiom scheme, but it’s possible to show that that schema only expands into a finite number of distinct axioms.
Ordinal Exponents and Really Big Numbers
With ordinals, we use exponents to create really big numbers. The idea is that we can define ever-larger families of transfinite
ordinals using exponentiation. Exponentiation is defined in terms of
repeated multiplication, but it allows us to represent numbers that we
can’t express in terms of any finite sequence of multiplications.
More on Ordinals: Ordinal Arithmetic (part 1)
I’ll continue my explanation of the ordinal numbers, starting with a nifty trick. Yesterday, I said that the collection of all ordinals is *not* a set, but rather a proper class. There’s another really neat way to show that.
From the Cardinals to the Ordinals
I’ve talked about the idea of the size of a set; and I’ve talked about the well-ordering theorem, that there’s a well-ordering (or total ordering) definable for any set, including infinite ones. That leaves a fairly obvious gap: we know how big a set, even an infinite one is; we know that the elements of a set can be put in order, even if it’s infinite: how do we talk about *where* an element occurs in a well-ordering of an infinite set?
For doing this, there’s a construction similar to the cardinal numbers called the *ordinal numbers*. Just like the cardinals provide a way of talking about the *size* of infinitely large things, ordinals provide a way of talking about *position* within infinitely large things.
Cardinal Arithmetic
This is a short post, in which I attempt to cover up for the fact that I forgot to include some important stuff in my last post.
As I said in the last post, the cardinal numbers are an extension of the natural numbers, which are used for measuring the size of sets. The extended part is the transfinite numbers, which form a sequence of ever-larger infinities.
One major problem with adding the transfinite numbers is that natural number arithmetic doesn’t work anymore with the cardinals. It still works for the natural number subset of the cardinals, but not for the transfinites.
But we *do* want to be able to talk about at least certain kinds of arithmetic on the full set of cardinals. So we need to figure out what arithmetic means for this strange sort of number.
Set Cardinalities and the Cardinal Numbers
One of the strangest, and yet one of the most important ideas that grew out of set theory is the idea of cardinality, and the cardinal numbers.
Cardinality is a measure of the size of a set. For finite sets, that’s a remarkably easy concept: count up the number of elements in the set, and that’s its cardinality. But there are interesting questions that we can ask about the relative size of different sets, even when those sets have an infinite number of elements. And that’s where things get really fun.