Since is countable, define to be any bijection. Then, define by .
Show that is a bijection.
Then is a bijection from .
I need a little help with this question, I understand that to show a set is countable you have to show that it has a some sort of injection / surjection to N or R, i.e sets that are know to be countable, but i am still not quite sure how to show this has a function relation to either sets?
Any help appreciated.
thank you
p.s I need help with part b, I have done part a, although the diagram I drew does not help me understand the question any better.
Have you already proved, or do you know, that Q, the set of all rational numbers, is countable? If so, then you know that you can label the rational numbers as . Write an array with all rationals, in that order, horizontally along the top and all rationals, in that order, vertically on the left. In the cell, i horizontally, j vertically, we have the pair . Now zigzag through the array as is done for the proof that Q is countable.
(That method can be used for a general proof that "If A and B are countable then A X B is countable.)
can be broken down component-wise into and . In other words, is a bijection between the set of positive integers and the set of odd positive integers. is a bijection between the set of natural numbers and the set of powers of 2. Every natural number can be expressed uniquely as where , and 2 does not divide . In other words, the number is broken into its "odd part" and its "even part". This is a very natural bijection from .
g(m,n) = (2m-1)2^(n-1) maps (m,n) to a double infinity of integers, which you still have to show is countable, using the same method as post #3 , so you might as well use that right off the bat.
EDIT:
g maps (m,n) to a unique integer N. ok, but
does N=(2m-1)2^(n-1) have a unque solution (m,n) for each N?
The following is from another post because I wasn't able to post it here.
First off, previous reply with quote missed the EDIT.
let g(m,n) = (2m-1)2^(n-1)
Is this a 1-1 mapping to N? If it is, it proves the rational numbers are countable since (m,n) can be interpreted as rational numbers.
g maps (m,n) to a unique even positive integer P. OK
Given P, is there a unique (m,n) st P=2N=(2m-1)2^(n-1), or,
N=(2m-1)2^(n-2), for any N? Obviously not because the left side can be even or odd and the right side is even for n>2.
Copied from the other thread:
Any positive integer can be represented uniquely as a product with such that 2 does not divide . In other words, is the "odd" part of and is the "even" part of . Here (Link) is information on the "Odd Part" of a number. Here (Link) is information on the "Even Part" of a number. It is obvious that for any choice of nonnegative integers such that is odd. Next, let with odd positive integers and nonnegative integers. Since must divide and 2 does not divide , it must be that . Similarly, since must divide and 2 does not divide , it must be that . Hence, . Then, by cancellation, . This shows that is one-to-one. To show that is onto, let be any natural number. Let be the highest power of that divides . Since is a natural number, . Let . Now, . Since is an odd positive integer, is an even positive integer, so is a positive integer. Since is a nonnegative integer, is a positive integer. Hence, , so is onto.
So, is, indeed, a bijection as I stated.
From Rudin:
Theorem: Let A be a countable set and let Bn be the set of all n-tuples (a1,a2,..an) where ak belong to A. Then the Bn are countable.
If A= ...-3,-2,-1,0,1,2,3.... (countable)
points in the plane are a subset of B4 and therefore countable.
Explanation: Any rational number can be expressed as (n1,n2) and any point in the plane is (r1,r2) = (n1,n2,n3,n4).
The Theorem follows from B2 and induction. For B2, map (m,n) to elements amn of a matrix, which are countable (diagonally from upper left).
Previous posts seem to be based on the principle that (m,n) is countable if g exists st g maps ZxZ 1-1 into an infinite sequence of integers, which can then be numbered, to give g:ZxZ->Z.
For Ex, Plato gives g = 2^{m}3^{n}, which is 1-1 because:
2^{p}3^{q}=2^{r}3^{s} -> 2^{p-r}=3^{s-q} -> even=odd -> p=r and q=s.
Actually, a less obtuse proof that (m+n) is countable comes from *Rudins' and other's counting scheme, (m+n) ls countable by arranging it in a Matrix form:
2345678....
3456789....
456789......
56789.....
6789......
and counting diagonally from upper left.
*The elements (m,n) are countable by arranging them in matrix form, REGARDLESS of their value.