MarkPNeyer.com

Every once and a while, I come up with a unique mathematical idea. This happened to me recently. It started when I was reading a book recommended by a friend of mine named Anneliese. The book is called ‘The Mystery of the Aleph’, and it deals with Georg Cantor and his work on infinity.

Mathematical Background

(Math majors can feel free to skip this part)

Infinite sets are strange things. One of the neat things Cantor found out was that there are different kinds of infinity. For example, the numbers (0,1,2,3,4…) are called Integers. There are infinite integers. Numbers with decimal expansions (1.01232, 2.22442244, 3.14159265…) are called ‘real numbers.’ There are infinite real numbers as well. Cantor showed, however, that even though both sets (the set of real numbers, and the set of integers) are infinitely large, there are more real numbers than integers. This is hard for a lot of people to understand; both sets are inifnite – how could one be larger than the other?

In order to measure the size of a set of objects, we come up with a mapping from the set we want to count to the set of integers. If you have 10 cookies (you luck bastard, you), then there exists a mapping from the set of integers {1,2,3,4,5,6,7,8,9,10} to the set of cookies in your possession. This mapping connects each cookie with a number from the set. If you add another cookie to your set, then the set of integers from 1 to 10 is no longer large enough to map onto your cookies; you need a larger set of integers because your set of cookies is bigger.

By defining the size of a set in terms of mappings, cantor came up with a way to show that you cannot possibly have a mapping from all integers to all real numbers between 0 and 1. One proof he used is not too difficult to see. Suppose that the mapping does exist: that is, suppose the function f takes an integer n, and gives us the n^th real number. Cantor argued that you could create a real number to which no integer maps. This number (we’ll call it G) is defined as follows. The first digit of G is the first digit of f(1), with one added to it. If this first digit is a 9, just switch it to a 0 and forget about carrying. This sort of addition is called ‘mod 10′ addition. In general, the n^th digit of G is the n^th digit of f(n) + 1 mod 10. The number G cannot possibly be in the list of real numbers, because for any integer n, the n^th digit of G differs from the n^th digit of f(n). Because you cannot map the integers to the real numbers between 0 and 1, we say that there are uncountably many real numbers.

There are more levels an infinity than just these two – it can also be shown that there are more functions of real numbers than there are real numbers. For any set S, there is always a larger set: the powerset of S. The powerset of a set S is the set of all combinations of the members of S. For example, suppose S = {1,2,3}. The powerset of S is { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }.

By saying two sets have the same size if there’s a mapping from the members of one to the members of the other, you can get some interesting results. For example, consider the set of all square numbers: {0,1,4,9,16,25,36 … }. How big is this set? How does it compare with the set of all integers? It should seem that this set would be smaller than the integers, because every square number is an integer, but not all integers are square numbers. Your intuition leads you astray here. It is easy to come up with a mapping from integers to square numbers: f(n) -> n². Because there is a mapping from the integers to the square numbers, there are just as many of one as there are of the other. In more strict mathematical terms, the set of all integers and the set of all square numbers have the same Cardinality.

The Story Proper

I was thinking about power sets and orders of infinity and such, when I happened upon a rather novel idea. What if there was a set that was infinite, and yet smaller than the integers? I told this idea to Anneliese and she didn’t think it was possible. The fact that she thought it couldn’t exist, and that my intuitive mathematical sense told me it couldn’t exist convinced me that it probably did exist, and so I set off trying to think of what this set could be.

While I was in the car on the way to work, I found it ! Prime numbers! I have done a lot of thinking about prime numbers, in the past, but the idea made perfect sense in this context. A prime number is an integer that is only divisible by one and itself. The distribution of prime numbers is a strange thing; it seems almost close to random: {1,3,4,7,11,13,17,19,23,29 …}. There is a mathematical function with approximates the prime distribution, but there is no function which gets it exactly right. Maybe, I thought to myself, that is because the prime numbers are uncountable because they are too small, and therefore such a function can never exist! The intellectual absurdity of the idea appealed to me, and I tried to think of ways to show that it was the case that there were fewer prime numbers than integers.

I concocted what was a valid proof, and spent the rest of the afternoon mulling this idea. While I was mulling my proof, I had a new realization – if you take the powerset of the set of all primes, you get the set of all possible combinations of prime numbers – but any set of prime numbers can be considered a ‘recipe’ for constructing an integer. If the set of prime numbers were the same size as the set of all the integers, taking its power set should give a set of a new size – and since the power set of prime numbers is isomorphic (‘isomorphic’ means there’s a one to one correpsondence) to a subset of the integers (namely, those integers expressible as the product of primes raised to the first power), the set of primes must have a lower cardinality than the set of all integers! I was ecstatic at this point.

When I was eating dinner that night, my dad noticed that I was thinking about something and asked what it was. I explained to him, and tried to give him my proof. He instantly rejected my idea as absurd (which I had expected) and proceeded to explain why my proof didn’t work. I explained the flaw in his reasoning, and he came up with another counter example. I told him why that exapmle didn’t work, and He then came up with another reason. This went back and forth until we reached a particular example where he was sure he had shown my reasoning to be false, and I was sure he had not. After writing on a bit of scrap paper, I realized where I had erred. He showed me that my method of proof was invalid. I looked at the paper for a bit until I could fully grasp why my proof didn’t work. When it hit me, I looked up and said “Well, I still think it’s true. I just can’t prove it yet.” I could see that this irritated him slightly, but I didn’t care – I was still sure of myself. The power set buisness is what convinced me it was the case. I thought about it more that night, and when I woke up in the morning, the proof was there in my head !

I had planned to meet with Gary, my CS professor that morning and show him some thoughts I’d had on another topic (on the computational ability of a finite system, and how this ability changes as more states are added to the system), so I just showed him the proof I had instead. He was intrigued, and yet cautious. He wasn’t sure about some of the steps that I had taken, but he didn’t know enough to tell me if I was wrong or not. I ran into Jim Snodgrass, the head of the math department, and showed him my proof. He, too, felt like it wasn’t quite right but wasn’t solid enough on his set theory to say exactly what was wrong with the proof. He let me borrow a book on set theory, and I started looking through it. Later that day, I found a proof which told me I was wrong, although I wasn’t well versed enough in the book to understand it at all. I was convinced that the book was wrong; probably they made a defintion that was tight and therefore their proof didn’t rule out my claim.

I realized that I didn’t have the background in set theory to prove what I was trying to say the way I wanted to, so I gave up on that method and tried to think of a new one. I got it pretty quickly. I knew that there are more functions from integers to integers than there are integers themselves. I also had the realization that, if the primes were countable, you could consider the factorization of an integer to be a function in of itself. For example, the number 3536 factors into 2⁴*13*17. If you add in the other primes, it looks like this: 2⁴*3⁰*5⁰*7⁰*11⁰*13¹*17¹*23⁰…

In any number’s factorization, the n^th prime could be raised to any integer power, and therefore every integer represents a unique mapping from the integers to the integers. The above function would map the integers {0,1,2,3..} to the integers {4,0,0,0,0,1,1,0…} For an integer n, the n^th function at x is the integer power of the x^th prime number in the factorization of n. I was pleased! I knew everything I needed to know about sets and such to show that this was the case. I started working out a concrete proof.

I got to the point where I was about to state that any function could be converted to an integer in this manner. I had to stop and think about how I could show this was the case when I realized I was wrong. Every ‘function’ based upon the factorization of the number n will map to zero after a certain point, because in the factorization of a given number n, all primes greater than n are raised to the 0^th power. At this point, I began to doubt whether my idea was true or not. Perhaps the primes were large enough to be countably infinite. Still, the power-set buisness told me otherwise. How could a set possibly have the same cardinality as its power set?

The next morning, I realized my mistake. As long as you look only at the finite-sized elements of the powerset of the set of all primes, you can turn them into integers. Howerver, one member of the powerset of the set of all primes is the set of all primes. If you multiply all the prime numbers together, your answer is not meaningfully called an integer. I told my professors about this today. Gary started to get excited when I told him how I thought of mapping integers to functions using their factorization, but when I explained that it didn’t work because of the fact that the functions would always end up returning zero after some maximum number, he had a slightly dissapointed look on his face.

Conclusion

I’m still not sure I’m ready to believe that the primes are countably infinite, although I think that’s just because I’m stubborn and like to think that I have a new idea. Even though I’m pretty sure I’m wrong about the idea, it’s nice to have a unique idea, share it with mathematically inclined people, and have them tell you that you’re wrong but that they aren’t sure why, and then find out for yourself why you are wrong and go back and explain it to them. Perhaps the life of an academic is the life for me?