# Thread: countable set, Q X Q

1. ## countable set, Q X Q

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.

2. ## Re: countable set, Q X Q

Since $\displaystyle \mathbb{Q}$ is countable, define $\displaystyle f:\mathbb{Q} \to \mathbb{N}$ to be any bijection. Then, define $\displaystyle g: \mathbb{N}\times \mathbb{N} \to \mathbb{N}$ by $\displaystyle g(m,n) = (2m-1)2^n$.

Show that $\displaystyle g$ is a bijection.

Then $\displaystyle g\circ(f\times f)$ is a bijection from $\displaystyle \mathbb{Q}\times\mathbb{Q} \to \mathbb{N}$.

3. ## Re: countable set, Q X Q

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 $\displaystyle \{q_2, q_2, q_3, ..., q_n, ...\}$. 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 $\displaystyle (q_i, q_j)$. 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.)

4. ## Re: countable set, Q X Q

Originally Posted by SlipEternal
Since $\displaystyle \mathbb{Q}$ is countable, define $\displaystyle f:\mathbb{Q} \to \mathbb{N}$ to be any bijection. Then, define $\displaystyle g: \mathbb{N}\times \mathbb{N} \to \mathbb{N}$ by $\displaystyle g(m,n) = (2m-1)2^n$.

Show that $\displaystyle g$ is a bijection.

Then $\displaystyle g\circ(f\times f)$ is a bijection from $\displaystyle \mathbb{Q}\times\mathbb{Q} \to \mathbb{N}$.

I follow your logic, but not sure 'how to show 'g' is a bijection?

5. ## Re: countable set, Q X Q

Originally Posted by Tweety
I follow your logic, but not sure 'how to show 'g' is a bijection?
To prove that $\displaystyle g$ is a bijection you must assume $\displaystyle 0\notin\mathbb{N}$.

All you need to do is show that there is a injection.

I suggest $\displaystyle g : (m,n)\mapsto 2^m\cdot 3^n$

6. ## Re: countable set, Q X Q

Originally Posted by Tweety
I follow your logic, but not sure 'how to show 'g' is a bijection?
$\displaystyle g$ can be broken down component-wise into $\displaystyle g_1(m) = 2m-1$ and $\displaystyle g_2(n) = 2^n$. In other words, $\displaystyle g_1$ is a bijection between the set of positive integers and the set of odd positive integers. $\displaystyle g_2$ is a bijection between the set of natural numbers and the set of powers of 2. Every natural number can be expressed uniquely as $\displaystyle 2^k m$ where $\displaystyle k,m \in \mathbb{Z}, k\ge 0, m\ge 0$, and 2 does not divide $\displaystyle m$. In other words, the number is broken into its "odd part" and its "even part". This is a very natural bijection from $\displaystyle \mathbb{N}\times \mathbb{N} \to \mathbb{N}$.

7. ## Re: countable set, Q X Q

One slight correction: to get bijectivity, you need $\displaystyle g_2(n) = 2^{n-1}$, so $\displaystyle g(m,n) = (2m-1)2^{n-1}$. Before, $\displaystyle g$ was a bijection between $\displaystyle \mathbb{N}\times \mathbb{N}$ and positive even integers. Allowing the exponent of $\displaystyle 2$ to be zero adds in all odd positive integers, as well.

8. ## Re: countable set, Q X Q

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?

9. ## Re: countable set, Q X Q

Originally Posted by Hartlw
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.
We are not dealing with ordinal numbers. Double infinity does not exist as a cardinal number. I gave a specific method for showing the map is a bijection from $\displaystyle \mathbb{N}\times \mathbb{N}$ to $\displaystyle \mathbb{N}$. It does not require the method in post #3, although that method would certainly work.

10. ## Re: countable set, Q X Q

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.

11. ## Re: countable set, Q X Q

Any positive integer $\displaystyle k$ can be represented uniquely as a product $\displaystyle k = m\cdot 2^a$ with $\displaystyle m,a \in \mathbb{Z}_{\ge 0}$ such that 2 does not divide $\displaystyle m$. In other words, $\displaystyle m$ is the "odd" part of $\displaystyle k$ and $\displaystyle 2^a$ is the "even" part of $\displaystyle k$. 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 $\displaystyle m\cdot 2^a \in \mathbb{N}$ for any choice of nonnegative integers $\displaystyle m,a$ such that $\displaystyle m$ is odd. Next, let $\displaystyle m_1 2^{a_1} = m_2 2^{a_2}$ with $\displaystyle m_1,m_2$ odd positive integers and $\displaystyle a_1,a_2$ nonnegative integers. Since $\displaystyle 2^{a_1}$ must divide $\displaystyle m_2 2^{a_2}$ and 2 does not divide $\displaystyle m_2$, it must be that $\displaystyle a_1 \le a_2$. Similarly, since $\displaystyle 2^{a_2}$ must divide $\displaystyle m_1 2^{a_1}$ and 2 does not divide $\displaystyle m_1$, it must be that $\displaystyle a_2 \le a_1$. Hence, $\displaystyle a_1 = a_2$. Then, by cancellation, $\displaystyle m_1 = m_2$. This shows that $\displaystyle g$ is one-to-one. To show that $\displaystyle g$ is onto, let $\displaystyle k$ be any natural number. Let $\displaystyle a$ be the highest power of $\displaystyle 2$ that divides $\displaystyle k$. Since $\displaystyle k$ is a natural number, $\displaystyle a\ge 0$. Let $\displaystyle m = \dfrac{k}{2^a}$. Now, $\displaystyle g\left(\dfrac{m+1}{2},a+1\right) = k$. Since $\displaystyle m$ is an odd positive integer, $\displaystyle m+1$ is an even positive integer, so $\displaystyle \dfrac{m+1}{2}$ is a positive integer. Since $\displaystyle a$ is a nonnegative integer, $\displaystyle a+1$ is a positive integer. Hence, $\displaystyle \left(\dfrac{m+1}{2},a+1\right) \in \mathbb{N}\times \mathbb{N}$, so $\displaystyle g$ is onto.

So, $\displaystyle g$ is, indeed, a bijection as I stated.

12. ## Re: countable set, Q X Q

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 = 2m3n, which is 1-1 because:
2p3q=2r3s -> 2p-r=3s-q -> even=odd -> p=r and q=s.

13. ## Re: countable set, Q X Q

In the spirit of the earlier posts, I'll also take a shot at g:ZXZ->Z+

g =(m+n) because multiple elements in a set don't count and m+x=n has a unique solution.

14. ## Re: countable set, Q X Q

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.

15. ## Re: countable set, Q X Q

Originally Posted by Hartlw
In the spirit of the earlier posts, I'll also take a shot at g:ZXZ->Z+

g =(m+n) because multiple elements in a set don't count and m+x=n has a unique solution.
As stated in another thread, this is a SURJECTION, not an INJECTION. So, this function does NOT show countability of the domain. It shows that the domain contains a countably infinite subset.

Page 1 of 2 12 Last