## Thursday, September 12, 2002

### Experience Mathematics #13 - The cartesian society in Hilbert Hotel

A set S is countable if it can be put in one-to-one correspondence with $N$. Suppose that you are the manager of the Hilbert Hotel, a hotel with a countable number of rooms. Now, even though the hotel is full, when $200$ new guests arrive after lunch at the Restaurant at the End of the Universe, you can accommodate them. All you have to do is to move the guests in Room $1$ to Room $201$, the guests in Room $2$ to Room $202$, etc. In other words, you will move the guests in Room $n$ to Room $200+n$.

Now, suppose the hotel is empty. The members of the Cartesian Society (Motto: We Think, Therefore We Exist!) decide to have a convention. Each member of the Cartesian Society has an identification mark of the form $(a, b)$, where $a$ and $b$ are natural numbers. The chairman of the society is $(1,1)$ and for any two numbers $a$ and $b$, there is a member corresponding to the ordered pair $(a, b)$. Don’t confuse $(2,3)$ with $(3,2)$: they are quite different people. There are many, many members in this society. But all of them can be accommodated in the Hilbert Hotel. Can you find a one-to-one correspondence of the members of the Cartesian Society with the natural numbers?

First write down the ID numbers of all the members of the Cartesian Society in the form of a table. For example, put $(3,5)$ in the third row and the fifth column of the table. Now find a way to “count” them. In other words, assign a natural number to each of them in a systematic fashion.