This is the third article in a series called Before I Forget, an exposition for the semi-layman of freaky high-level mathematics. Last time we talked about cardinal numbers: numbers which are used for counting the elements in very large sets. This time I’ll use the compactness theorem to introduce an infinity that you can use in ordinary arithmetic to get ordinary results. Remember limits from calculus? Turns out you don’t need ‘em to do calculus. We’ll see how this time.
This is the first article that will dive into the details of first-order logic. I’m not going to spend the time here to describe first-order logic: it is a deep subject with a rich vocabulary and lots of little nooks and crannys where faulty reasoning can hide. However, I highly recommend that everyone learn its principles and how to use it. It will change the way you think; it will endow you with the ability to approach certain situations with extreme precision, and to clear away bullshit that many authors throw at you. See the wikipedia page, including the external links section, if you’d like to know more. It’s not technically required to understand this article, but it is required to grok this article.
Sexy mathematical models
I will begin by presenting the difference between a model and a set of sentences. Okay, so we have a sentence of first order logic endowed with one extra symbol: S (successor). We will use this to represent the natural numbers. The existence of the number 0 is expressed by the following sentence: ∃x ∀y S(y) ≠ x (there is an x which is not the successor of any number) (remember we’re in the natural numbers, there is no -1). So when we say 0, we really mean to introduce a new variable and that sentence to identify our 0. The important thing is that we can express it though. And now we may represent any natural number using successor and 0. 1 = S(0), 2 = S(S(0)), 3 = S(S(S(0))), etc.
This is the second post in a series called Before I Forget, which is an exposition for the semi-layman of some freaky high-level mathematics (mostly set theory). This episode is still about infinity, but covers the Cardinal numbers.
Last time I introduced the ordinal numbers, specifically the ordinal ω—the least number greater than all the integers—and things derived from it (like ω × 2, and ωωω… an infinite number of times… (ω times, actually :-)). Today we’ll be exploring a parallel concept to the ordinal numbers called the cardinal numbers. Ordinals are used to index positions: the 1st position, 2nd position, ωth position; cardinals are used to measure sizes.
Okay, let’s step out of the context we’ve been working for just a little while. Numbers are now the numbers you are familiar with: not just the nonnegative integers, but also negatives, fractions, and irrationals. Here is an exercise: come up with a set of numbers which has no least member. This should be pretty easy, but it should be obvious that the set must be infinite.
Got one yet? I want you to come up with one before you continue reading.
One of the most obvious examples is the set of all numbers greater than (but not equal to) 0. How do you know it doesn’t have a least member? Well, suppose it did, and call it x. We know that x > 0, because it was in our set. Well, if x > 0, then x/2 > 0 also, so x/2 is in our set. But of course x/2 < x, so it turns out that x wasn’t the least member after all (but we chose x specifically to be the least member, so this is a contradiction). Our supposition that our set had a least member must have been flawed, and we have thus proved that our set has no least member.
Another example is the set of all integers (positive and negative). It extends infinitely in the negative direction, so it can’t have a least member. (Exercise for the reader: prove formally that the set of all integers has no least member like we did for the real numbers greater than 0 in the last paragraph) There are tons of sets with no least member, and yours could have been quite different from my two examples.
Here’s another challenge: come up with a (nonempty) set of positive integers that has no least member. Got one? No, come on, come up with one. I dare you. Don’t continue reading until you have one.
Yo mama’s fat.
This is the first post in a new series of mine, “Before I Forget”. This series is an exposition of all the awesome (in the British sense), marvelous, haunting mathematics I learned while in college. I’m not sure how often I’ll add to it or when it will end, but I know that I’ve been itching to write about some of this stuff for a while. I’m writing it to be somewhat accessible. I know I have several readers who skip over any math stuff, but I encourage those people to read this anyway if they have the faintest interest. Some of the notation might be confusing, but, if I’ve accomplished my goal, you should be able to understand it anyway because I’ve been redundant enough that you should be able to understand it. :-p Oh, and of course questions and comments are welcome. Without further ado, here is the first article, about Infinity and the Ordinal Numbers (which will form a basis for the rest of the series).
The Real Infinity
While I was a tutor in Calculus 2 (in 2005 I think) I noticed that the students were quite comfortable with the concept of infinity. But their comfort was not well-founded, as it turns out. The first sign of trouble was when they would write constraints like “4 < x < ∞” instead of “4 < x”; not a big deal, but an indication that they were missing the details somehow. Given a problem like: “find limx -> ∞((x2+x)/(x2+1))”, their reasoning would often proceed “the limit of x2+x is infinity, and the limit of x2+1 is infinity, so the result is ∞/∞ which is… (they look to the little table in the book)… undefined! That’s the answer, undefined!” (Exercise for the reader; why is that wrong?). The main problem is that they were using infinity as a number—a mathematical object—that you could do arithmetic on with the results as defined in the book (much like the IEEE floating point standard or Nullity… shudder).
The problem is that infinity is not a number. It is just a notation which stands for something more precise, depending on context. Saying “limx -> 2 f(x) = ∞” doesn’t mean that the value of the “limit function” is “equal to infinity” there, it means that I can make f(x) get as big (but still finite!) as I want by getting x close enough to 2. You want f(x) to be 1,000,000,000,000,000? If I set x to 2+10-400 I can do that. That’s what that expression means. More simply, if you say x ε (-∞,6], you’re just saying x ≤ 6.
So infinity is not an object… or rather, it wasn’t, until we started talking about sets.