Zorba the Hutt (zorbathut) wrote,
Zorba the Hutt
zorbathut

badger III, part 2

Someone (I'm not going to say who) (virtual256) has been bugging me to write more Badger.

Okay. Okay. I keep meaning to. I've been putting it off. More badger.

More precisely, I should continue defining what "more" means.

It should be pointed out that I will answer questions on this. I realize this is a LOT of math to sit down and digest. But if you're willing to sit there and ask questions, I'm willing to answer them - so if you get bogged down around, say, the first time I use the word "infinite", let me know and ask me something vaguely coherent and I'll try to go through it with you.

Moving on.

Last entry I was explaining that you can take an infinite number of things, add an infinite number of things, and end up with the same infinite number of things. More precisely, the size of the set of positive integers is the same as the size of the set of positive *even* integers. And I gave a few tests for people to do.

Now, remember, our basic method of figuring out if these are the same size is to make a bijection. A bijection is a way of taking an object from set A and associating it with an object in set B, such that each object in A is associated with exactly one object in B and vice-versa. With our example, we can just say "take the positive integer, multiply it by 2, bam! positive even integer!" and it's quite obvious that every integer in set A can be multiplied by two to make a positive even integer in set B. And vice-versa, replacing "multipled" by "divided".

Moving on -

(1) Which is larger - the set of positive integers, or the set of all integers?

They're the same size.

For each even integer, divide by two. For each odd integer, subtract one, divide by two, and make it negative. So we match the series 0 1 2 3 4 up to 0 -1 1 -2 2. Obviously we can easily translate back and forth at will.

(Super-informally and inaccurately, we've already proven that twice infinity is infinity. This is basically the same thing.)

(2) Which is larger - the set of all integers, or the set of prime integers?

They're the same size.

Step 1: Prove that primes are infinite.
Step 2: There's a 1st prime, obviously (it's 2). There's a 2nd prime (it's 3). So we match these up - 2, 3 - and just keep on going. For every n we could find an nth prime - it might take us a while, but we've already proven one exists.

Alternatively, we know that the set of primes is a subset of the set of integers. Therefore, |P| <= |N|. However, the size set of primes is also greater than any finite number, and therefore |N| <= |P| <= |N|, and therefore |N| = |P|.

Oh, wait, new syntax. Okay. N represents "the set of natural numbers" - i.e. positive integers. P represents the set of primes, because I say so. The |bars| mean "the cardinality of" - some of you might be saying "Hey, wait, that's also absolute value!" (and you're correct!) or "Hey, wait, that's the magnitude of a vector!" (and you're correct!) - it's all of those, because those are all pretty similar concepts.

You might note that we've proven the set of prime integers is the same size as the set of positive integers - not the set of all integers. Luckily, we've already proven the set of all integers is the same size as the set of positive integers. Convenient, no?

(3) Which is larger - the set of all integers, or the set of all integer-pairs? (i.e. (4,5), (150,-4), etc.)

They're the same size.

But we've got a problem. If we just start counting (0,0), (1,0), (2,0), (3,0), we're simply never going to increment the second value. What are we going to do?

Simple. We list all the pairs with a certain maximum sum. Then we increase the sum. (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3), and so on and so on. For any (n,0) we'll get there at number sum(x, x=1..n). Then for any (n,m) we'll get there at number sum(x, x=1..(n+m))+m. Sure, it'll get slower and slower as we go, but that's okay - we've got an infinite series in front of us.

Whoops. We haven't shown anything about (150,-4)!

Not to worry. We've got all pairs of *positive* integers - let's say we have all pairs of (N,N) and we want all pairs of (I,I). Well, we know the size of N is the same as the size of I. So we can just take our pair of N,N and convert it into a pair of I,I. Since every I will eventually be mapped to by precisely one N, the problem is solved.

Actually we've got the same problem on the other end - we're starting with the set of all natural numbers - but we've solved that problem before.

(4) Which is larger - the set of all integers, or the set of all rational numbers? (I.e. numbers that can be expressed as fractions.)

They're the same size.

This one's easy. In fact this one's so easy it's fun.

All rational numbers n/m can be expressed as an integer pair.

See the proof?

Of course, there are integer pairs that cannot be expressed as rational numbers. Let's use |T| for rationals (R is taken for reals). So |T| <= |P| (P, of course, is Pairs, for now.) All integers can be expressed as rational numbers. So |N| <= |T| <= |P|. But |P| = |N| - so |N| <= |T| <= |N| - so |N| = |T|.

(5) Which is larger - the set of all integers, or the set of all finite sets of integers?

They're the same size.

Now here's a really fun one.

We've already proven that the set of all pairs is the same size as the set of integers. We can prove that the set of triplets is the same as the set of integers easily - (N,N) becomes ((N,N),N) becomes (N,N,N). No problem. Inductively, we can prove that the set of any fixed finite-size tuple of integers is the same size as the set of integers - if we have proven n-1 integers is a certain size, then clearly we can just map the first integer to a pair and bam! Now it's n integers long.

Now let's go back to pairs. We can get any pair, as proven before - now let's interpret the first value in the pair as the size of the tuple, and the second value in the pair as which tuple it is. So (5,17) translates into "The 17th tuple of 5 elements".

(Note: technically 'tuple' isn't the same as 'set'. Right now I don't care. This is all massively informal anyway and they're close enough.)

(6) Which is larger - the set of all integers, or the set of all real numbers?

The set of all real numbers is larger.

Yes, it's larger than infinite.

Stop yelling at me.

Let's imagine we have found some bijection between the set of all positive integers and the set of all real numbers in the range [0,1). Now we can just write all the real numbers down on paper, starting from Real Number #1 and going all the way down to the last one. They're all infinitely long, because, hey, real numbers, and so our giant piece of paper ends up as square. (For certain definitions of square.)

Now let's take another really long piece of paper and start writing. Start at Real Number #1, and start at the first digit after the decimal point (since all our numbers start with 0., after all.) If the digit is a 0, we write a 1 on our piece of paper. Otherwise, we write a 0. Then we continue to the second digit of Real Number #2, then to the third digit of Real Number #3, and so on.

On our piece of paper we now have a perfectly valid real number that happens to differ in at least one place from every real number in our "complete" list.

Our "bijection" is missing at least one real number.

The set of real numbers is larger than the set of integers - and yes, they're both "infinite". Just one of them is a larger infinity.

Next entry I'll start explaining how many badgers we actually have.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments