Prove that a set of positive rational numbers is countable

[r0bHadz]

Homework Statement

Prove that the set of positive rational numbers is is countable
by showing that the function K is a 1-1 correspondence between the set of positive rational numbers and the set of positive integers if K(m/n) = $p_1^{2a_1}p_2^{2a_2}...p_s^{2a_s}q_1^{2b_1-1}...q_t^{2b_t-1}$

where gcd(m,n) = 1

and prime power factorizations of m and n are:

m = $p_1^{a_1}p_2^{a_2}...p_s^{a_s}$
n = $q_1^{b_1}...q_t^{b_t}$

2. Homework Equations

The Attempt at a Solution

If the set of positive integers is infinite then the set of positive rational numbers must be infinite as well. How can you possibly count and infinite amount of numbers? The question makes no sense to me

 

[Delta2]

There are many different levels of infinity and there is an ordering between those different levels. The basic infinity level is the infinity of the set of positive integers which is symbolized as $A_0$. After that it is the infinity of the set of the real numbers which we can prove that it is equal to the infinity of the power set (the set of subsets) of the set of positive integers. This infinity is called the continuum infinity and the symbol is $C$. After that is the infinity of the power set of the real numbers and its symbol is $P(C)$. The ordering between those infinities is $A_0<P(A_0)=C<P(C)<P(P(C))<…<P^n(C)<...$ where P is the power set operator (it acts on a set A and gives its power set P(A) as result).

So this exercise has a meaningful sense in that it wants you to prove that the set of rational numbers has also the basic level of infinity $A_0$.

 

[r0bHadz]

I see. I guess I'm interpreting the word "countable" different than the way the author/other mathematicians interpret it.

By showing the set of rational numbers a/b>0 has a one to one correspondence with the set of positive integers, it shows that the rational numbers also have a basic level of infinity $a_0$

 

[Delta2]

This exercise is fairly easy btw if you know the fundamental theorem of number theory https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

 

[r0bHadz]

This exercise is fairly easy btw if you know the fundamental theorem of number theory https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

There is one doubt that I have before I can continue.

Intuitively I would like to believe the set of a/b>0 has more elements in it than the set of n, n>0 where a,b,n, are ints and gcb(ab)= 1

If this is true then it would be impossible for a bijection to occur.

But if they have the same level of infinity, the sets would have to be of the same size. This seems like a contradiction. It is very hard to grasp this at my current level.

edit: hmm I guess this doubt would just be sidetracking as of now. it doesn't seem that I have to know this info for me to complete this problem

 

[Delta2]

I guess its one of the cases where our intuition fools us. Yes intuitively we would expect that the set of rational numbers has higher infinity level, because for example it contains all the possible fractions of integers. However this is not enough to give it a higher infinity level. As this exercise tell us, given that function K, we can map each fraction to a big enough positive integer in a way that is 1-1.

 

[Mark44]

Prove that the set of positive rational numbers is is countable
by showing that the function K is a 1-1 correspondence between the set of positive rational numbers and the set of positive integers

Intuitively I would like to believe the set of a/b>0 has more elements in it than the set of n, n>0 where a,b,n, are ints and gcb(ab)= 1

Then your intuition is wrong. Otherwise you would not be able to prove the statement you're supposed to prove. "Countable" is short for "countably infinite," and it means that the two sets are exactly the same size. If you can make a list of all the positive rational numbers, you're well along the way toward proving what you need to prove.

 

[PeroK]

There is one doubt that I have before I can continue.

Intuitively I would like to believe the set of a/b>0 has more elements in it than the set of n, n>0 where a,b,n, are ints and gcb(ab)= 1

If this is true then it would be impossible for a bijection to occur.

But if they have the same level of infinity, the sets would have to be of the same size. This seems like a contradiction. It is very hard to grasp this at my current level.

edit: hmm I guess this doubt would just be sidetracking as of now. it doesn't seem that I have to know this info for me to complete this problem

A simpler case is to show that the set of positive even integers has the same cardinality as the set of all positive integers:

$A = \{1, 2, 3 \dots \}$ and $B = \{2, 4, 6 \dots \}$

Clearly, we see that $B$ is a proper subset of $A$. But, equally clearly, we can pair the elements of each set in a 1-1 correspondence:

$1-2, 2-4, 3-6 \dots$

And, therefore. by the definition of equal cardinality, we see that the two sets are the same "size".

Further, if we think about these sets simply as collections of objects, then we could rewrite them as:

$A = \{A_1, A_2, A_3 \dots \}$ and $B = \{B_1, B_2, B_3 \dots \}$

And then it's even more obvious that the two sets have the same cardinality.

 

[member 587159]

There are many different levels of infinity and there is an ordering between those different levels. The basic infinity level is the infinity of the set of positive integers which is symbolized as $A_0$. After that it is the infinity of the set of the real numbers which we can prove that it is equal to the infinity of the power set (the set of subsets) of the set of positive integers. This infinity is called the continuum infinity and the symbol is $C$. After that is the infinity of the power set of the real numbers and its symbol is $P(C)$. The ordering between those infinities is $A_0<P(A_0)=C<P(C)<P(P(C))<…<P^n(C)<...$ where P is the power set operator (it acts on a set A and gives its power set P(A) as result).

So this exercise has a meaningful sense in that it wants you to prove that the set of rational numbers has also the basic level of infinity $A_0$.

Your answer is true or false, depending on the fact that the continuum hypothesis is true or false.

 

[r0bHadz]

So i just have to show that K(m/n) = an integer correct?

Cause right now I have$K(m/n) =(m^2)(m^2) (q_1^{-1}*...*q_t^{-1})$

 

[Delta2]

Your answer is true or false, depending on the fact that the continuum hypothesis is true or false.

Yes I took the Continuum Hypothesis for granted, in my attempt to give an intuitive approach to this subject.

So i just have to show that K(m/n) = an integer correct?

Cause right now I have$K(m/n) =(m^2)(m^2) (q_1^{-1}*...*q_t^{-1})$

It is rather obvious that $K(m/n)=integer$ cause it is $K(m/n)=m^2\prod {q_i^{2b_i-1}}$ and each $q_i^{2b_i-1}$ is an integer cause $b_i\geq 1$
You have to show that the function K is a bijection, which means two things :
1) K is an injection (or one to one) $K(m/n)=K(m'/n')\Rightarrow m/n=m'/n'$
2) K is a surjection that is for every integer $y$ there exist integers $m,n$ such that $K(m/n)=y$.

EDIT : Looking again at the statement of the problem, it just requires to prove just 1) of the above.

 

[r0bHadz]

let K(m/n) = x, x∈ℤ+

by the fundamental theorem of arithmetic x can be expressed as a product of primes.
every x will have a unique prime factorization because every m and every n has a unique prime factorization, and every m/n is unique

so the function K is invective for the domain of rationals to the co domain of ints

 

[Delta2]

let K(m/n) = x, x∈ℤ+

by the fundamental theorem of arithmetic x can be expressed as a product of primes.
every x will have a unique prime factorization because every m and every n has a unique prime factorization, and every m/n is unique

so the function K is invective for the domain of rationals to the co domain of ints

No this proof is not good. Every $x\in \mathbb{Z^{+}}$ has unique prime factorization regardless of what is happening to m and n.

Start with $K(m/n)=K(m'/n')$ where $gcd(m,n)=1$ and $gcd(m',n')=1$ and the prime factorizations of m,n as in the OP and the prime factorization of $m'={p'_1}^{a'_1}…{p'_{s'}}^{a'_{s'}}$ and for $n'={q'_1}^{b'_1}…{q'_{t'}}^{b'_{t'}}$. You have to use the fundamental theorem of arithmetic properly and prove that $s=s',t=t'$ and $p_i=p'_i, q_i=q'_i$ and $a_i=a'_i, b_i=b'_i$. You can prove all this just with the fundamental theorem of arithmetic plus with the fact that an odd exponent cannot be equal to an even exponent. I know the symbols used with all the stuff and ' is heavy but the proof is easy actually.

 

[r0bHadz]

No this proof is not good. Every $x\in \mathbb{Z^{+}}$ yes unique prime factorization regardless of what is happening to m and n.

Why do you say regardless though? Wouldn't x be dependent on m and n? And I will try it again and report back. I do have to study for my probability class now -_-

 

[Delta2]

Why do you say regardless though? Wouldn't x be dependent on m and n? And I will try it again and report back. I do have to study for my probability class now -_-

Yes x depends on m and n, however all three x,m,n have unique prime factorizations just because they are integers, and not because x depends on m and n. To be honest I didn't completely understand what you write at post #12 but I don't think you are using properly the fundamental theorem of arithmetic.

 

[Ray Vickson]

Homework Statement

Prove that the set of positive rational numbers is is countable
by showing that the function K is a 1-1 correspondence between the set of positive rational numbers and the set of positive integers if K(m/n) = $p_1^{2a_1}p_2^{2a_2}...p_s^{2a_s}q_1^{2b_1-1}...q_t^{2b_t-1}$

where gcd(m,n) = 1

and prime power factorizations of m and n are:

m = $p_1^{a_1}p_2^{a_2}...p_s^{a_s}$
n = $q_1^{b_1}...q_t^{b_t}$

2. Homework Equations

The Attempt at a Solution

If the set of positive integers is infinite then the set of positive rational numbers must be infinite as well. How can you possibly count and infinite amount of numbers? The question makes no sense to me

The mapping is not a bijection. While it is true that for each rational $r$ you get a unique integer $N$, the converse does not hold. For example
$$\frac{18}{35} = \frac{2 \times 3^2}{5 \times 7} $$ maps to $$2 \times 3^2 \times 5 \times 7 = 630,$$ but the integer $630$ can come from several different rationals, such as
$$\frac{9}{70} = \frac{3^2}{ 2 \times 5 \times 7}, \; \frac{2}{315} = \frac{2}{3^2 \times 5 \times 7}, \; \frac{10}{63} = \frac{2 \times 5}{3^2 \times 7}, \ldots $$ I think if you really want a 1:1 mapping between the rationals and the integers you need to use another type of correspondence. See, eg.,

https://www.quora.com/How-can-you-p...orrespondence-with-the-set-of-natural-numbers

 

[Delta2]

@Ray Vickson please look at the mapping function K more carefully I believe it is a 1-1. 9/70 maps to $3^4\cdot2\cdot5\cdot7$ for example and 18/35 maps to $2^2\cdot3^4\cdot5\cdot7$

 

[Ray Vickson]

@Ray Vickson please look at the mapping function K more carefully I believe it is a 1-1. 9/70 maps to $3^4\cdot2\cdot5\cdot7$ for example

Yes, I know (that should have a $3^2$, not $3^4$). But $630 = 3^2 \cdot 2 \cdot 5 \cdot 7$ could also come from $2 /(3^2 \cdot 5 \cdot 7)$ or $(7 \cdot 2)/(3^2 \cdot 5)$ or $5/(2 \cdot 3^2 \cdot 7)$ and several others. The trouble is that when we are just given the integer $N$ we do not know which of its prime factors are $p$'s and which are $q$'s, in the notation of the original question.

 

[Delta2]

Yes, I know (that should have a $3^2$, not $3^4$). But $630 = 3^2 \cdot 2 \cdot 5 \cdot 7$ could also come from $2 /(3^2 \cdot 5 \cdot 7)$ or $(7 \cdot 2)/(3^2 \cdot 5)$ or $5/(2 \cdot 3^2 \cdot 7)$ and several others. The trouble is that when we are just given the integer $N$ we do not know which of its prime factors are $p$'s and which are $q$'s, in the notation of the original question.

It is $3^4$. The mapping function raises $p$'s to even power and $q$'s to odd power and that's the trick to separate them.

 

[Ray Vickson]

It is $3^4$. The mapping functions raises $p$'s to even power and $q$'s to odd power and that's the trick to separate them.

OK: I did not notice that.

 

[WWGD]

Sorry to nitpick here, but

Homework Statement

Prove that the set of positive rational numbers is is countable
by showing that the function K is a 1-1 correspondence between the set of positive rational numbers and the set of positive integers if K(m/n) = $p_1^{2a_1}p_2^{2a_2}...p_s^{2a_s}q_1^{2b_1-1}...q_t^{2b_t-1}$

where gcd(m,n) = 1

and prime power factorizations of m and n are:

m = $p_1^{a_1}p_2^{a_2}...p_s^{a_s}$
n = $q_1^{b_1}...q_t^{b_t}$

2. Homework Equations

The Attempt at a Solution

If the set of positive integers is infinite then the set of positive rational numbers must be infinite as well. How can you possibly count and infinite amount of numbers? The question makes no sense to me

Sorry to nitpick here, but , assuming the $p_i's, q_i's$ are primes, I think you need to set up an enumeration , in that these products depend on the order of the primes used. As a general comment, notice that cardinality is just one of many possible measures of size.

 

[r0bHadz]

I appreciate it my guy. It seems I have a lot to learn. I'm going to study this question with my professor as I still have some doubts about some things, but I will report back. I will mark this thread as solved for now and bump it after discussion with my prof. I appreciate all the help guys

 

[stevendaryl]

Sorry to nitpick here, but , assuming the $p_i's, q_i's$ are primes, I think you need to set up an enumeration , in that these products depend on the order of the primes used. As a general comment, notice that cardinality is just one of many possible measures of size.

No, the mapping doesn't depend on any particular ordering of the primes. Given $m$ and $n$, you come up with two sets of pairs:

$A$ = the set of pairs $(p,k)$ such that $p$ is prime and $k$ is the largest power of $p$ that is a factor of $m$
$B$ = the set of pairs $(q,l)$ such that $q$ is prime and $l$ is the largest power of $q$ that is a factor of $n$

Then you define $f(m,n) =$ the product of all numbers $p^{2k}q^{2l-1}$ such that $(p,k)$ is in $A$ and $(q,l)$ is in $B$.

There is no ordering involved.

 

[WWGD]

No, the mapping doesn't depend on any particular ordering of the primes. Given $m$ and $n$, you come up with two sets of pairs:

$A$ = the set of pairs $(p,k)$ such that $p$ is prime and $k$ is the largest power of $p$ that is a factor of $m$
$B$ = the set of pairs $(q,l)$ such that $q$ is prime and $l$ is the largest power of $q$ that is a factor of $n$

Then you define $f(m,n) =$ the product of all numbers $p^{2k}q^{2l-1}$ such that $(p,k)$ is in $A$ and $(q,l)$ is in $B$.

There is no ordering involved.

Thanks, never mind, the ordering I was thinking about is done with the indices.

 

[r0bHadz]

Sorry for bumping an old thread guys. Let me know if my logic is still wrong:

I need to show K(m/n) = K(m_1/n_1) => m/n = m_1/n_1

or:

$p_1^{2a_1}*...*p_s^{2a_s}*q_1^{2b_1-1}*...*q_t^{2b_t-1} = j_1^{2c_1}*..*j_l^{2c_l}*k_1^{2d_1-1}*...*k_m^{2d_m-1}$

$p_1$ has to be the same prime number as some j or some k. Let $p_1$ not be any j. Then it would have to be some k. but if it is some k, and k only has odd powers, it cannot be a k since p_1 has an even power. Therefore it must be some j.

So since it must be some j, and they are primes with bases equal to each other, the powers must be equal as well. This will be true for all $p_1...p_s$

The same argument can be used for q and k.

then k(m/n) = k(m_1/n_1) => m/n = m_1/n_1If this proof still sucks can anyone give a little hint or something