In a 2-dimensional Cartesian plane, i.e. x and y axes, with the origin at (0,0), suppose you want to enumerate all the lattice points. By lattice points I mean all the points whose coordinates are integers, like (1,1), (-4, 6) and (447, -993). By enumerate I mean list them in a specific sequence so that any given point in the plane will be reached in a finite number of steps.
There are many ways to do this in 2 dimensions. For example, start at the origin and go around in a square spiral. Any given point (x,y) no matter how far out will eventually be reached. A non-solution would be: First take care of all the lattice points whose Y-coordinate is 0. Once that’s done, do all the lattice points whose Y-coordinate is 1. Etc. No good, because a point like (1,1) won’t be reached in a finite number of steps.
In 3 dimensions you can still do it; e.g. by drawing concentric cubes starting at the origin and getting bigger. Again, any given point (x,y,z) will eventually be reached.
What if there are countably infinite dimensions? That is, one axis for each natural number? Can it still be done?
Doesn’t seem like it. Suppose you could only be at 0 or 1 on each axis. Then the set of points is the same as the set of real numbers 0<=r<1, expressed in binary, with each axis corresponding to a digit. But that’s an uncountable set by Cantor’s diagonalization. It just gets worse if each axis supports a countable number of positions.
If you allow for all of the coordinates to be non-zero, then the set is uncountable (as Herr Doktor Merkwürdigliebe has noted.) But interestingly, the set of all lattice points with a finite number of non-zero coordinates is countable. One way to see this is to first count all the points with all zeros after position 1 whose coordinates are all no greater than 1 in magnitude. (There are a finite number of these — in fact, only three.) Then count all lattice points will all zeros after position 2 whose coordinates are no greater than 2 in magnitude. (Again, a finite number.) Then count all lattice points with all zeros after position 3 whose coordinates are all no greater than 3 in magnitude. And so forth. At each stage you will be counting a finite number of lattice points, and a countable union of finite sets is countable.
You could also use a Gödel-like numbering. To convert a lattice point to an integer, for each non-zero coordinate, take the nth prime number (where n is the coordinate index) and raise it to the power of the coordinate value. Then multiply all those powers together. You always end up with a (finite) integer, so it’s countable. Easy to convert back as well.
Ok, I’m only dealing with non-negative integers here, but it’s easy to map from the integers to the non-negative integers and back.
Actually, forget mapping the negative integers to positive. Just let the exponents go negative. Then every lattice point translates to a positive rational (of which there are countably many).
Thanks for the responses! I thought a diagonal argument would come into the picture but wasn’t clear how. I don’t know what Godel numberings are but I’m in the middle of reading “Godel, Escher, Bach” by Hofstadter and I think he’s going to cover that sometime within the next 800 pages if he ever gets around to it
It’s just a technique for embedding all sorts of information into a single integer. Suppose you have some ordered pairs of positive integers where the first number is distinct, like \{(3, 7), (5, 3), (6, 10)\}. To encode that into a single number, take first number in each pair (call it n), then take the nth prime number and raise it to the power of the second number. Then multiply everything together. So in my example, we have P(3)=5, P(5)=11, P(6)=13, and therefore our number is X = 3^7 \cdot 11^3 \cdot 13^{10} = 401291870347778553
The really cool thing is that you can do it recursively. If I have \{(1, \{(3, 7), (5, 3), (6, 10)\}), (3, \{(1, 3)\})\}, then the encoded number is X = 2^{401291870347778553} \cdot 5^{2^3}. And so on, for however many layers you want. All the numbers have to be finite, of course.
It’s easy to go in the other direction too; you just factor the number and count the number of times each prime factor shows up.
Gödel himself used the technique to encode formulas. He would assign each symbol an integer, for example ( would be the number 11, and so on. Then you could turn any mathematical statement into a distinct number.
Note that, while that that will get you out all of the ordered pairs you put in, it won’t tell you what order those ordered pairs were in. That is to say, \{(3,7),(5,3),(6,10)\} will encode the same as \{(5,3),(6,10),(3,7)\}. So if you’re using this to encode entire formulas, you’d best make sure that your encoding includes order information in some other way. Presumably, the way Gödel did it was to have one ordered pair starting with 1, one starting with 2, one starting with 3, and so on, with the number paired with 1 being “the first symbol”, the one paired with 2 being “the second symbol”, and so on.
I don’t actually think that Hofstadter goes into the details of this particular encoding method, but rather, uses a different encoding. Which is fine. All that was really necessary for Gödel’s argument was that it’s possible to encode formulas as integers; precisely how the encoding worked didn’t matter.
