Results 1 to 5 of 5

Math Help - Infinity problem- correspondence

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2008
    Posts
    170
    I think this is equivalent to showing that  \bold{N} \times \bold{N} is countable which it is. Assuming that we know that the set  A = \{(n,m) \in \bold{N} \times \bold{N}: 0 \leq m \leq n \} is countable, then  A = \{(n,m) \in \bold{N} \times \bold{N}: 0 \leq n \leq m \} is countable since the map  f: A \to B given by  f(n,m) = (m,n) is a bijection from  A to  B .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2008
    Posts
    5
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    \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.
    Last edited by Plato; September 8th 2008 at 08:06 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    216
    Thanks
    29
    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 \frac{p}{q} so that the light above is denoted \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 \frac{2}{2} is different to traffic light \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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One-to-one correspondence between set of homomorphisms
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 13th 2012, 04:30 PM
  2. One-to-one Correspondence Questions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 19th 2010, 06:00 AM
  3. one to one correspondence
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: October 21st 2009, 03:56 AM
  4. one to one correspondence
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 12th 2009, 12:48 PM

Search Tags


/mathhelpforum @mathhelpforum