Categories
Uncategorized

The bus problem

I’ve run across an interesting problem. On my trip home from my internship, I take a train followed by a bus. However, more than one bus will get me close enough to home so that walking the rest of the trip is reasonable.

Buses A, B, C: These three buses use the same stop that I get off at; in fact, the stop serves as a transfer point to switch from one of these buses to another. The obvious pro is that there are three such buses.

Bus D: This is only one bus, but this stop is closest to my house.

I have to cross a somewhat busy intersection in both instances; the only difference between ABC and D is where.

The train station I get off at serves as an end point for all four buses. As a result, the buses will idle for a bit and let people getting off the train get on the bus. Excluding today, for the past two days two buses–D and one of A, B, and C–were available. By some coincidence I chose the bus that left later both times, resulting in a hungry Sushi by the time I arrived home. Unfortunately it rained one of those days, making me grumpy as well as hungry.

So here’s the problem. Given no knowledge of a bus schedule, and given a choice between bus D and one of buses A, B, and C, what is the probability that the bus you choose will leave first? For my situation I could probably solve it by using common sense and looking at a bus schedule, but what about an ordinary day? What about multiple buses without three buses using the same stop? What if only two buses are available at your stop?

This bears pondering.

Categories
Uncategorized

Cantor and Infinity, Part Two

Now for Cantor’s diagonal argument. Cantor showed that the natural numbers and the integers have the same cardinality, and even the natural numbers and the rational numbers. But what about the natural numbers and all the real numbers? Let’s say we wrote down the decimal representation of every single real number and corresponded them with a natural number. Heck, let’s just write down the real numbers between zero and one. A number can have more than one decimal representation, despite what five pages of .999…=1 discussion on Wikipedia will make you think. We can get around that, though. Now number all these numbers, starting from one and not stopping. We have something like this.

a1=0.c1 d1 e1 f1…
a2=0.c2 d2 e2 f2…
a3=0.c3 d3 e3 f3…

Now let’s take the nth digit from the nth number. Imagine a number x=0.x1x1x3… and let x1 be any number besides c1, x2 be any digit besides d2, and so on. Now x can’t be a1 because the first digit is different. It also can’t be a2 because the second digit is different. And so on and so on. So congratulations, we’ve found a number that isn’t in our list. This number should be on our list but isn’t. Therefore we’ve found a brand new number, and this number x doesn’t correspond to a natural number on our list. So the set of real numbers has a higher cardinality than the natural numbers.

That’s right. A higher infinity. Now if you really want your brain to hurt, think about the power set of the real numbers.

Categories
Uncategorized

Cantor and Infinity, Part One

Only in America would someone sue someone for over a billion trillion dollars. To be exact, we’re talking $1,784,000,000,000,000,000,000,000. Kevin Houston of the University of Leeds is cited in the article as saying, “I don’t think the human brain is set to deal with those numbers.”

But are they? Mathematicians study the properties of not just very large number but the infinite. In calculus one only discusses approaching infinity, and (besides the idea of counting and counting and never having to stop) this was my first idea of infinity. Infinity isn’t a number, the teachers always said. And they’re right, at least in the numbers that most of know and love. It was just generally accepted that things got weird at infinity, but at least they got weird in a way we could understand. Despite all this talk that infinity isn’t a number, we still talked about being “at infinity” an awful lot, even though the technical term was “approaches infinity”. Heck, this infinity business wasn’t even all that rigorous to mathematicians at the time for years. Don’t like the rigor of analysis? Don’t blame Newton and Leibniz. Blame those who came after.

Then this guy named Georg Cantor gatecrashed the party and started looking at infinities. Not infinity, infinities. He didn’t mess with this language of approaching infinity not because it wasn’t his style but because he didn’t have to. It didn’t help him get too many papers published, but to be honest, it didn’t help him with too many other things either. Cantor decided to look at the set of natural numbers (yes, the ones you count with) as a set. We already know that we can start counting and never stop, so there are certainly infinitely many natural numbers. Cantor called the cardinality of this set aleph-null.

But what if we look at all the possible subsets of natural numbers (we call this the power set), like {1 2 3} or {42 56 100 2341534 8675309}? Certainly there are infinitely many of these too, but how many more? Thanks to basic set theory, we know that there have to be more subsets of natural numbers than natural numbers.

“Sushi, you’re tricking me,” I hear you say. “You just told me there are infinitely many natural numbers and now you’re pulling this on me too? Now you’re going to tell me that the moon really is made of cheese.”

If the moon’s made of cheese, sign me up for the next flight. I’m not kidding–about the math or the moon. First, let’s look at {1 2 3} and its power set.

Elements: 1, 2, 3 (cardinality 3)
Power Set: {empty set, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} (cardinality 8 )

Now try to match up an element of the original set with an element of the power set. Things go terribly wrong. Don’t believe me? Try it yourself with a different set. Besides giving an example of the fact that the power set is bigger than the original set, we also note that this can work even for infinite sets, as Cantor’s diagonal argument shows.

That’s a story for another day, though. Stay tuned! You will get your infinities.