Question

Prove that the set of positive rational numbers is countable by setting up a function that assigns to a ration number\({\raise0.7ex\hbox{\(p\)} \!\mathord{\left/

{\vphantom {p q}}\right.\kern-\nulldelimiterspace}

\!\lower0.7ex\hbox{\(q\)}}\)with\(\gcd (p,q) = 1\) the base\(11\) number formed by the decimal representation of p followed by the base\(11\)digit A, which corresponds to the decimal number\(10\) followed by the decimal representation of q.

Short answer

Prove “The set of positive rational numbers is countable.” by showing that \(f:{Q^ + } \to {\{ 0,1,2,3,4,5,6,7,8,9,A\} ^*}\)such that \(f({\raise0.7ex\hbox{$p$} \!\mathord{\left/

{\vphantom {p q}}\right.\kern-\nulldelimiterspace}

\!\lower0.7ex\hbox{$q$}}) = pAq\)and \(\gcd (p,q) = 1\)is one-to-one

Step-by-step solution

Step 1

a \in A\)such that \(f(a) = b\).

The function f is one-to-one if and only if \(f(a) = f(b)\)implies that \(a = b\)for all a and b in the domain.

f is a one-to-one correspondence if and only if f is one-to-one and onto.

Cartesian product of \(A{\rm{ and B:A}} \times {\rm{B = \{ (a,b)|a}} \in {\rm{A}} \wedge b \in B\).

DEFINITIONS

A set is countable if it is finite or countably infinite.

A set is finite if it contains a limited number of elements (thus it is possible to list every single element in the set).

A set is countably infinite if the set contains an unlimited number of elements and if there is a one-to-one correspondence with the positive integers.

A set is uncountable if the set is not finite or countably infinite.

The function f is onto if and only if for every element \(b \in {\bf{B}}\)there exist an element \(