# Thread: Infinity problem- correspondence

1. ## Infinity problem- correspondence

There are infinite roads running north to south (one for each natural number) and infinite streets running east to west (one for each natural number). At the intersection of each street and road, there is a traffic light. Doe the set of traffic lights have the same cardinality as the set of natural numbers? If so, provide a one to one correspondence.

2. I think this is equivalent to showing that $\displaystyle \bold{N} \times \bold{N}$ is countable which it is. Assuming that we know that the set $\displaystyle A = \{(n,m) \in \bold{N} \times \bold{N}: 0 \leq m \leq n \}$ is countable, then $\displaystyle A = \{(n,m) \in \bold{N} \times \bold{N}: 0 \leq n \leq m \}$ is countable since the map $\displaystyle f: A \to B$ given by $\displaystyle f(n,m) = (m,n)$ is a bijection from $\displaystyle A$ to $\displaystyle B$.

3. Sorry I don't really understand what you mean... What does each symbol signify? Is the formula you gave the formula for a one to one correspondence? As far as I can work out, the number of traffic lights (T) equals half the total amount of lines (both vertical and horizontal) (L) squared. Eg with 4 horizontal and four vertical lines, there are 16 traffic lights.
T=LXL/2. Its like half a powerset, like 0.5 T(L), and powersets have strictly greater cardinality than the set. But I guess half a powerset is not a powerset at all so there must be a way to show one to one correspondence.

4. $\displaystyle \Theta \left( {m,n} \right) = 2^{m - 1} \left( {2n - 1} \right),\,\Theta :\mathbb{Z}^ + \times \mathbb{Z}^ + \to \mathbb{Z}^ +$
It is fairly straightforward to show that the above mapping is a bijection.
So the set of ordered pairs of positive integers is in one-to-one correspondence with the set of positive integers.

5. Label the north-south roads p, so that the third road is p=3.
Label the east-west roads q, so that the fourth road is q=4.

Now the traffic light on the corner of the third NS road and the fourth EW road is called (3,4).

Now wright this as $\displaystyle \frac{p}{q}$ so that the light above is denoted $\displaystyle \frac{3}{4}$. Now we have a label for each traffic light that looks very much like a rational number. There is a slight difference because (for example) traffic light $\displaystyle \frac{2}{2}$ is different to traffic light $\displaystyle \frac{4}{4}$.

Now the website: How Big is Infinity? explains why the cardinality of the rational numbers is the same as that of the natural numbers. You should be able to mount a very similar (but slightly simpler) argument why the cardinality of the streetlights is the same as that of the natural numbers.