Nyah, Nyah, my infinity is bigger than yours!
One really weird thing that you can do with math is compare the sizes of infinitely large things. It's a really strange notion, but it's actually a fairly important one - and one which interesting ties together computation and pure mathematics in a very clean way.
Suppose I have two infinite sets. I can show that these two infinite sets are the same size, by showing that I can build a total one-to-one map between the two sets.
For example, take the set of even numbers, and the set of odd numbers. They're the same size - because I can create a mapping function f from even to odd: f(n) = n + 1. For every even number, it maps to exactly one odd number; for every odd number, there's exactly one even number that maps to it.
A more counter-intuitive example would be: take the set of even integers, and the set of all integers. We know that the set of even integers is a subset of the set of all integers. Intuitively, most people would guess that the set of integers is twice as large as the set of even integers. But the two sets are the same size, because I can do a perfect mapping from integer to even integers: f(n) = 2*n. Every integer maps onto one even integer; every even integer is mapped to one by integer. So they're the same size.
Ok. How about the set of rationals and the set of integers? Same size. Make a two dimensional table with the integers on both dimensions. Now, trace the diagonal: 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4. Delete anything you've seen before. (1/1 is the same as 2/2, so we'd delete 2/2.) That gives us a list of every possible rational number. Map each rational to its position in the list, and poof! A one-to-one mapping from rational numbers to integers.
So, what's bigger?
The set of irrational numbers is larger than the set of rational numbers.
To remind anyone who doesn't remember: a rational number is either an integer, or a real number that can be represented as the ratio of two integers. So 1/2, 17/4, etc., are all rational numbers. On the other hand, pi, the square root of two, the root of the natural logarithm, and many other things are irrational numbers - numbers that can't be represented by a fraction. When you write in decimal expanded form, a rational number will always end in a repeating sequence of digits. 1/3 is 0.3333333 - the three repeats forever. 1/2 is 0.500000000... the 0 repeats forever. An irrational number will go on forever, never going into a continual repeating pattern. Here, you can find the first 4 million digits of pi.
How can I show that the set of irrationals is larger than the set of rationals?
Well, basically, I can't define a map from integers to irrationals. Irrationals are weird buggers, and I can't really say where they all are. They don't lay out nice and evenly the way that the rationals do.
In fact, it turns out that no matter how I try to form a map from integers to irrationals, I'll be missing something. Here's a quick version of why. It's a classic diagonalization argument.
Let's look at the set of all real numbers between zero and one. Now, suppose that this set is the same size as the set of integers. This would mean that there is a mapping from integers to real numbers between zero and one.
If that's true, then we can, in theory, make a list of the decimal expansions of all of the real numbers between zero and one.
Then we can define a function, r(n), which gives us the "r"th digit of the "r"th real number in the list.
Now here's where we pull a fast one. We define another function i(n). If r(n) = 1, then i(n) = 2. If r(n) != 1, then i(n) = 1. If we lay out a new number 0.(i(1),i(2),i(3),i(4),...), then that number is different from any number in our list of reals in at least one digit. So we have a real number between zero and one - and it's not in our list. Contradiction, therefore the list can't exist. (Note, this was corrected to fix a typo; originally, I accidentally wrote "0.(r(1),...)". Thanks to the anonymous commenter who pointed it out.)
So, now we know that the set of real numbers between zero and one is larger than the set of rational numbers between zero and one. But since we know that the set of rationals is the same size as the set of integers, then that means that the only way that the set of reals can be larger than the set of integers is if the set of irrationals is larger than the set of rationals.
How does this connect to computation? Well, there's a notion of something called a countable set. A countable set is a set which is either finite, or which has a one-to-one mapping from the integers. It turns out that the set of countable sets is a superset of the set of recursively enumerable sets. Infinite sets larger than the countable sets cannot be enumerated by any computing device. They are fundamentally non-computable things. (The last paragraph was heavily edited to correct an error pointed out in the comments. See the comment thread for the details. As usual, thanks to the commenters who pointed out the errors!)
Suppose I have two infinite sets. I can show that these two infinite sets are the same size, by showing that I can build a total one-to-one map between the two sets.
For example, take the set of even numbers, and the set of odd numbers. They're the same size - because I can create a mapping function f from even to odd: f(n) = n + 1. For every even number, it maps to exactly one odd number; for every odd number, there's exactly one even number that maps to it.
A more counter-intuitive example would be: take the set of even integers, and the set of all integers. We know that the set of even integers is a subset of the set of all integers. Intuitively, most people would guess that the set of integers is twice as large as the set of even integers. But the two sets are the same size, because I can do a perfect mapping from integer to even integers: f(n) = 2*n. Every integer maps onto one even integer; every even integer is mapped to one by integer. So they're the same size.
Ok. How about the set of rationals and the set of integers? Same size. Make a two dimensional table with the integers on both dimensions. Now, trace the diagonal: 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4. Delete anything you've seen before. (1/1 is the same as 2/2, so we'd delete 2/2.) That gives us a list of every possible rational number. Map each rational to its position in the list, and poof! A one-to-one mapping from rational numbers to integers.
So, what's bigger?
The set of irrational numbers is larger than the set of rational numbers.
To remind anyone who doesn't remember: a rational number is either an integer, or a real number that can be represented as the ratio of two integers. So 1/2, 17/4, etc., are all rational numbers. On the other hand, pi, the square root of two, the root of the natural logarithm, and many other things are irrational numbers - numbers that can't be represented by a fraction. When you write in decimal expanded form, a rational number will always end in a repeating sequence of digits. 1/3 is 0.3333333 - the three repeats forever. 1/2 is 0.500000000... the 0 repeats forever. An irrational number will go on forever, never going into a continual repeating pattern. Here, you can find the first 4 million digits of pi.
How can I show that the set of irrationals is larger than the set of rationals?
Well, basically, I can't define a map from integers to irrationals. Irrationals are weird buggers, and I can't really say where they all are. They don't lay out nice and evenly the way that the rationals do.
In fact, it turns out that no matter how I try to form a map from integers to irrationals, I'll be missing something. Here's a quick version of why. It's a classic diagonalization argument.
Let's look at the set of all real numbers between zero and one. Now, suppose that this set is the same size as the set of integers. This would mean that there is a mapping from integers to real numbers between zero and one.
If that's true, then we can, in theory, make a list of the decimal expansions of all of the real numbers between zero and one.
Then we can define a function, r(n), which gives us the "r"th digit of the "r"th real number in the list.
Now here's where we pull a fast one. We define another function i(n). If r(n) = 1, then i(n) = 2. If r(n) != 1, then i(n) = 1. If we lay out a new number 0.(i(1),i(2),i(3),i(4),...), then that number is different from any number in our list of reals in at least one digit. So we have a real number between zero and one - and it's not in our list. Contradiction, therefore the list can't exist. (Note, this was corrected to fix a typo; originally, I accidentally wrote "0.(r(1),...)". Thanks to the anonymous commenter who pointed it out.)
So, now we know that the set of real numbers between zero and one is larger than the set of rational numbers between zero and one. But since we know that the set of rationals is the same size as the set of integers, then that means that the only way that the set of reals can be larger than the set of integers is if the set of irrationals is larger than the set of rationals.
How does this connect to computation? Well, there's a notion of something called a countable set. A countable set is a set which is either finite, or which has a one-to-one mapping from the integers. It turns out that the set of countable sets is a superset of the set of recursively enumerable sets. Infinite sets larger than the countable sets cannot be enumerated by any computing device. They are fundamentally non-computable things. (The last paragraph was heavily edited to correct an error pointed out in the comments. See the comment thread for the details. As usual, thanks to the commenters who pointed out the errors!)
posted by MarkCC at
9:20 PM
RSS
10 Comments:
Back when I was taking High School honors algrebra, the teacher had a bunch of math books. (Flatland was my favorite) One of them was 1, 2, 3... Infinity, which first introduced me to this whole concept. You've certainly helped clear up some of the differences between the "lesser" and "greater" infinities.
I'm still a bit shaky on what makes one "bigger" than another. This deal with functions just seems to make one infinite set weirder or impossible to line up with another.
By
Bronze Dog, at 10:03 PM
I think that the notion of "bigger" makes a bit more sense when you get into topology. At some point, after I've had a chance to read a book or two, I'll do some posts on topology which should help.
By
MarkCC, at 10:35 PM
I thought there were countable sets that aren't recursively-enumerable. In order to be countable there must be a mapping from the integers but that mapping need not be recursive.
By
Joseph, at 10:36 PM
FYI, you defined but never used i(n).
By
Anonymous, at 11:40 PM
That's because there is a typo
"If we lay out a new number 0.(r(1),r(2),r(3),r(4),...)"
should read
"...0.(i(1),i(2),i(3),i(4),...)"
By
Anonymous, at 6:41 AM
joseph:
I'm pretty sure that I recall a proof that all countable sets are recursively enumerable, but not necessarily recursive. That does imply a recursive mapping, which seems to be a problem. When I have some time later today, I'll do a bit of research and check, and figure out what's right.
By
MarkCC, at 8:22 AM
Let f be a bijection from the set of ordered pairs (Turing machine M,input n) where n is a natural number to the set of natural numbers. Let A ={ a | f^{-1}(a)=(M,n) where M halts on input n }. I think that A is recursively enumerable, but not recursive. The mapping f must be recursive.
By
Anonymous, at 11:25 AM
----
I'm pretty sure that I recall a proof that all countable sets are recursively enumerable, but not necessarily recursive.
----
Any set of indeces of Turing machines is a subset of the integers, and must be countable. However, sets of TM indeces can be of arbitrarily complexity, not just recursively enumerable. For example, TOT, the set of Turing machines that halt on all inputs is Pi_2. This means that the complement of this set is recursively enumerable if you can use the halting problem as an oracle. So it is clearly not re.
Turing Machines can define linear orders. The TM takes two inputs x and y and tells you if one is less than the other. The set of all TMs that code well-founded linear orders (no infinite descending sequences) is Pi^1_1, which cannot be reached even by an infinite iteration of TM oracles.
By
Anonymous, at 1:59 PM
Okay, I am going to pick a fight here.
As a logician, I should point out that the claim that infinitary cardinalities represent "bigger" numbers is philosophically misguided. All they point out is that there is no bijection between the two sets. However, as Cohen's invention of forcing demonstrates, this can simply be an artifact of the limitations of set theory.
By simply adding or removing bijections from my universe of all sets (provided that I still satisfy the axioms of ZFC), I can make 2^omega (the set of all subsets of integers) have essentially arbitrary uncountable cardinality. Maybe it is omega_1 (the first uncountable cardinal), maybe it isn't. But that fact that I can make it consistently vary over ZFC is a strong argument that this is not measuring size.
By
Anonymous, at 2:05 PM
joseph:
Yup, you're right. There's a ton of countable sets which are not recursively enumerable - as usual in things like this, you can just "throw in" the halting problem. You can show the countability of the sets, but they're not enumerable.
Now I need to go back to my old textbook, and figure out what the proof I was thinking of *actually* proves.
By
MarkCC, at 3:44 PM
Post a Comment
<< Home