a Give an explanation for why many people would think that Z

(a) Give an explanation for why many people would think that Z is a smaller set than Q (the rationals).

(b) Use the grid argument to explain how to prove that Z Q (that is, explain how to set up a bijection between the integers and the rationals) to prove that the integers and rationals are actually the same size.

Solution

(a) It is clear that each element of Z belongs to Q,but each element of Q does not belong to Z. so Z is a subset of Q.Thus people think number of integers(Z) is less then number of rationals(Q).

(b) The main idea of the proof is to show that each set is in one-to-one correspondence with a subset of the other. Then they must have the same size.

It is clear that, every integer n corresponds in a one-to-one relation to a rational number of the form n/1. The set of rational numbers of the form n/1 is a subset of all the rational numbers. This implies that the number of integers is no larger than the number of rational numbers.

Thus, set of Integers()set of Rationals().   So number of Integers is less then number of Rationals-----(1)

Now Writing the rational numbers in a doubly-infinite array, putting the fraction a/b with b > 0 at the point (a,b) in the upper half of the xy-plane. It should look like this:

     ...    :     :     :     :     :     :     :    ...

   ... -3/3 -2/3 -1/3   0/3   1/3   2/3   3/3   ...

     ... -3/2 -2/2 -1/2   0/2   1/2   2/2   3/2   ...

     ... -3/1 -2/1 -1/1   0/1   1/1   2/1   3/1   ...

     ...    :     :     :     :     :     :     :    ...

It is clear that every rational number appears somewhere in this array. Some appear more than once, such as 1/1 = 2/2 = 3/3.

Now make a dotted line spiraling out from the center (-1/1, mark it with X) in the following way:

            o---o-- ...

            |

            o   o---o---o---o---o---o---o---o---o

            |   |                               |

            o   o   o---o---o---o---o---o---o   o

            |   |   |                       |   |

            o   o   o   o---o---o---o---o   o   o

            | |   |   |               |   |   |

            o---o   o---o   X---o---o---o   o---o

To each point along the spiral, assign a nonnegative integer according to its distance from X along this line. Then to every rational number in lowest terms there will correspond a positive integer. Every rational number is covered, and the correspondence between the rational numbers in lowest terms and a certain subset of the integers is one-to-one.

Here is part of it:

     -1/1 <--> 0

      0/1 <--> 1

      1/1 <--> 2

      +++++++++++ End of max(a,b) = 1

      2/1 <--> 3

                  (skip 4 because 2/2 is not in lowest terms)

      1/2 <--> 5

                  (skip 6 because 0/2 is not in lowest terms)

     -1/2 <--> 7

                  (skip 8 because -2/2 is not in lowest terms)

     -2/1 <--> 9

     ++++++++++++ End of max(a,b) = 2

     -3/1 <--> 10

     -3/2 <--> 11

                  (skip 12 because -3/3 is not in lowest terms)

     -2/3 <--> 13

     -1/3 <--> 14

                  (skip 15 because 0/3 is not in lowest terms)

      1/3 <--> 16

      2/3 <--> 17

                  (skip 18 because 3/3 is not in lowest terms)

      3/2 <--> 19

      3/1 <--> 20

     ++++++++++++ End of max(a,b) = 3

      4/1 <--> 21

       :       :

Thus could able to count the rational by less number of integers. This clearly tells number of Integers are more then number of rationals.-------------(2)

Combining ---(1)and----(2), We have number of Integers = number of Rationals.