# Math Help - map (m,n) to N

1. ## map (m,n) to N

This is a reply to Post QXQ countable sets which the system won't let me rreply to.

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.

2. ## Re: map (m,n) to N

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

3. ## Re: map (m,n) to N

I can't reply with quote and I can't copy first sentence.

Referencing your first sentence, if k =3, what are a and m?

By the way I couldn't understand the links. Even if I took the time, I do not think they are in the spirit of this question.

4. ## Re: map (m,n) to N

If $k = 3$, then follow the method I gave. What is the highest power of 2 that divides 3? It is $2^0$. So, $a = 0$. Then, $m = \dfrac{k}{2^a} = \dfrac{3}{2^0} = 3$. So, $g\left(\dfrac{3+1}{2},0+1\right) = g(2,1) = 3$.

Edit: Also, the links were there to give you the mathematical definitions of the "even part" and "odd part" of an integer. Definitions are necessary to mathematical understanding. So, I am not sure what "spirit" you were looking for, but definitions are intrinsic to any understanding of a problem.

5. ## Re: map (m,n) to N

Originally Posted by Hartlw
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.
Consider that mapping to be $\mathbb{Z}^+\times\mathbb{Z}^+\to\mathbb{Z}^+$

Note that $\forall x\in\mathbb{Z}^+$ it possible to write $x$ as an odd number times a power of two,

$g(2,1)=3$ and $g(9,4)=136$.

So $g$ is both one-to-one and onto.

However, because each subset of a countable set is countable one-to-oneness is all we need.

The mapping $\mathbb{Z}^+\times\mathbb{Z}^+\to\mathbb{Z}^+$ given by $(m,n)\mapsto 2^m\cdot 3^n$ is easy to show is one-to-one.

As a side bar, this is a useful theorem:
There is an injection $A\to B\text{ if and only if }$ there is a surjection $B\to A$.

6. ## Re: map (m,n) to N

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= Z = 0,1,2,3,4,5,6,…,
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.

(From original thread but partly relevant here).

7. ## Re: map (m,n) to N

Since multiple entries in a set don't count, g=(m+n) maps Z+XZ+ to Z+.

or ZXZ to Z+. Z=0,1,-1,2,-2,....

EDIT: It's not a unique mapping, but it might be thought through. Sorry. Would cancel if I could, unless someone can dig me out.

EDIT: Actually, I think I can dig myself out: given m and n, m+x=n has a unique solution.

8. ## Re: map (m,n) to N

Originally Posted by Hartlw
Since multiple entries in a set don't count, g=(m+n) maps Z+XZ+ to Z+.

or ZXZ to Z+. Z=0,1,-1,2,-2,....

EDIT: It's not a unique mapping, but it might be thought through. Sorry. Would cancel if I could, unless someone can dig me out.

EDIT: Actually, I think I can dig myself out: given m and n, m+x=n has a unique solution.
The existence of a surjection shows that the cardinality of the domain is at least as large as the cardinality of the range. The existence of an injection shows that the cardinality of the domain is no greater than the cardinality of the range. You provided a surjection, which does not show that the domain is countable.

9. ## Re: map (m,n) to N

Damn, now the system let's me respond after I started a separate thread, which isn't that bad since it's a topic in itself. Oh well. In response to last post above which I can't reply to with quote:

Slipstream has a valid point. My reason for g = (m+n) is as follow

m+n maps Z+ to {2,3,3,4,4,4,5,5,5,5,.....) which is equal to {2,3,4,5,.....} and hence has the same size, cardinality, ie, is countable.

But it involves an assumption which may be incorrect:

{a,a,a,a,...........} is equal to {a}, ie, has the same size (cardinality, countability)

(No problem with {a,a,a}={a})

10. ## Re: map (m,n) to N

Actually, the "size" question may be academic because, using Rudins' and other's counting scheme, (m+n) ls countable by arranging it in a Matrix form:

2345678....
3456789....
456789......
56789.....
6789......

11. ## Re: map (m,n) to N

SlipEternal wrote: "The existence of a surjection shows that the cardinality of the domain is at least as large as the cardinality of the range. The existence of an injection shows that the cardinality of the domain is no greater than the cardinality of the range. You provided a surjection, which does not show that the domain is countable."

Actually, any surjective map g(m,n) is countable:

Proof: Let g(m,n) = amn. Then g(m,n) is countable because amn is countable (Rudin).

So: g=(m+n) is countable because g is surjective.

12. ## Re: map (m,n) to N

If a surjection were enough to show countability, then the map $f:\mathbb{R} \to \mathbb{Z}$ defined by $f(x) = \lfloor x \rfloor$ (this is the step function, which returns the greatest integer less than or equal to x, which is obviously a surjection) shows that $\mathbb{R}$ is countable, which we know to be false. Therefore, no matter whose counting scheme you use (Rudin's or otherwise), showing the existence of a surjection to a countable set does not show that the domain is countable. It shows that the cardinality of the domain is at LEAST as large as the cardinality of the range. For example, there does not exist a surjection from the set of integers to the set of reals, so we know that the set of integers has a smaller cardinality than the set of reals. There does not exist any surjection from a finite set to an infinite set, so we know that infinite cardinalities exist. It is unknown whether or not there exists a set with cardinality greater than the cardinality of the set of integers, but less than the cardinality of the set of reals.

So, to recap, your function $g:\mathbb{Z}^+\times \mathbb{Z}^+ \to \mathbb{N} \setminus \{1\}$ defined by $g(m,n) = m+n$ is a surjection, which shows that $\mathbb{Z}^+\times \mathbb{Z}^+$ is no smaller than $\mathbb{N}\setminus \{1\}$. You provided a LOWER BOUND on the cardinality, not an upper bound. So, this does not show countability. It only shows that it contains a countably infinite subset.

Edit: But, if you show that there exists a surjection from a set to a countable set, then show that the preimage of each element of the range is a finite subset of the domain, then you have a countable union of finite sets, which is countable.

13. ## Re: map (m,n) to N

We are talking about g(m,n) where m,n are countable and g is surjective, to which Rudin applies.

g(x) x real has absoluteley nothing to do with this.

If you keep bringing up extraneous and irrelevant material this thread will never end.

14. ## Re: map (m,n) to N

Originally Posted by Hartlw
We are talking about g(m,n) where m,n are countable and g is surjective, to which Rudin applies.

g(x) x real has absoluteley nothing to do with this.

If you keep bringing up extraneous and irrelevant material this thread will never end.
What does g(x) x real mean? I did not post anything about that. I gave an example of a surjection from an uncountable set to a countable set, and explained that does not prove the uncountable set is now countable. I think the issue is that you are trying to prove something unrelated to what I am trying to prove. You seem to be trying to prove that $\mathbb{N}$ is countable by giving a surjection from a set of unknown cardinality to $\mathbb{N}$, then counting the number of elements in the image of the function. I am saying this is not helpful in any way to find the cardinality of $\mathbb{N}\times \mathbb{N}$ and gave you several examples why not. If you truly believe that your method of proof is valid, then there is nothing more to discuss.

15. ## Re: map (m,n) to N

Bài viết hữu ích!

Văn phòng phẩm, giấy photocopy, bút viết, bìa hồ sơ, và nhiều sản phẩm tiết kiệm hổ trợ công việc văn phòng ★ ★ ★
Vanphongpham.net 400 Trần Hưng Đạo, P.2, Q.5, Tp.Hồ Chí Minh Thứ 2 - 7 : 8:00am - 5:30pm

Page 1 of 2 12 Last