# map (m,n) to N

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Nov 6th 2013, 08:50 AM
Hartlw
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.
• Nov 6th 2013, 09:35 AM
SlipEternal
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.
• Nov 6th 2013, 10:01 AM
Hartlw
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.
• Nov 6th 2013, 10:15 AM
SlipEternal
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.
• Nov 6th 2013, 10:35 AM
Plato
Re: map (m,n) to N
Quote:

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$.
• Nov 7th 2013, 05:19 AM
Hartlw
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).
• Nov 8th 2013, 07:20 AM
Hartlw
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.
• Nov 8th 2013, 07:59 AM
SlipEternal
Re: map (m,n) to N
Quote:

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.
• Nov 8th 2013, 09:23 AM
Hartlw
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})
• Nov 8th 2013, 09:39 AM
Hartlw
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......
• Nov 8th 2013, 10:39 AM
Hartlw
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.
• Nov 8th 2013, 10:44 AM
SlipEternal
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.
• Nov 9th 2013, 06:30 AM
Hartlw
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.
• Nov 9th 2013, 07:09 AM
SlipEternal
Re: map (m,n) to N
Quote:

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.
• Nov 10th 2013, 01:11 AM
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
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last