0
$\begingroup$

While studying the countability of sets, I came across the following problem (In Methods of Real Analysis, Goldberg) : Show that Pn=set of polynomials of degree n (with all coefficients being integers and n fixed positive integer) is countable..

It was hinted to use Induction,which of course is easy to do.

I tried the following:

Let the coefficients of the terms be made into a sequence (a0,a1,a2,a3,a4...,an). e.g (2,6,1,9,3) gives the constant term as 2,coefficient of x as 6 ,of x^2 as 1 etc...

Now write a string 10 [a0] 010 [a1] 010 [a2] 010...010 [an]01 i.e enclose each number ai in the stings '010' to form a bigger number 10[a0]010 [a1]010[a2]010...010[an]01.

If some integer ai = [-x], is negative , them enclose it in 0100[x]010 rather than 010[x]010.

So basically what i tried was to assign a unique natural number to each sequence (a0,a1,a2,a3,a4...,an) and use it to show that Pn is countable. Is this correct?

$\endgroup$
2
  • $\begingroup$ That is a nice idea. But what happens if a coefficient is, for example, 330105 - does the method confuse it with two coefficients 33 and 5? $\endgroup$
    – Empy2
    Oct 23, 2013 at 14:31
  • $\begingroup$ well that shouldn't be a problem as long as we carefully use the enclose in string 010 or 0100 rule 330105 will simply turn 010330105010..but as @Joni mentioned below,this will still not work as desired... $\endgroup$
    – O_huck
    Oct 23, 2013 at 14:44

2 Answers 2

Reset to default
4
$\begingroup$

I do not have any experience in this, but it seems like you can do this with a diagonal argument. For $P_{1}$, define $(a,b) := a + bx$ then list the coordinates

\begin{align*} (0,0), &(0,1), (0,2), (0,3)\dots\\ (1,0), &(1,1), (1,2), (1,3) \dots\\ \vdots \end{align*}

This is countable by defining your bijective map down the diagonals. You can then simply reapply this to argument to $(a,b)\times(\mathbb{N}\cup\{0\})$ repeatedly to show it is true for all $P_{n}$

$\endgroup$
4
  • $\begingroup$ But how to do this if a,b can be negative too? $\endgroup$
    – O_huck
    Oct 23, 2013 at 14:32
  • $\begingroup$ Alternate the signs, (0,0), (0,1), (0,-1), (0,2), (0,-2).. Edit: Just a reminder that I do not have a lot of mathematical background. There are some details you should work out to ensure everything works $\endgroup$
    – JessicaK
    Oct 23, 2013 at 14:33
  • $\begingroup$ I suppose you could just use the fact that the countable union of countable sets is still countable and just argue by symmetry to get the negatives too $\endgroup$
    – JessicaK
    Oct 23, 2013 at 14:55
  • 1
    $\begingroup$ +1 : This is basically equivalent to ordering polynomials $p=\sum_{i=0}^d p_ix^i$ by $\max(\max_i(|p_i|), d)$; AFAICT this scheme is the 'canonical' choice for practical uses. (It gives a clean bijection, as opposed to lexical approaches like the 'base-12' one which map $P$ into a strict subset of $\mathbb{N}$, and having a bijection is useful for e.g. illustrating an ordering of $\mathbb{N}$ in order type $\omega^\omega$.) $\endgroup$
    – Steven Stadnicki
    Oct 23, 2013 at 15:40
1
$\begingroup$

With the mapping you suggest the polynomials $101 + x$ and $1 + 101x$ would both be mapped to 101010101010 so it won't quite work.

You can find simpler maps based on the same idea though: since digits 0-9 are already being used in the decimal expansion, why not map the polynomials to numbers in base 12 and let "," be the digit with value 10 and "-" the digit with value 11? Now any sequence of decimal digits with embedded commas and hyphens are integers in base 12; for example the two polynomials above would be represented by the base 12 numbers $101,1$ and $1,101$ respectively.

$\endgroup$
2
  • $\begingroup$ Thanks.I was afraid something like that could happen but couldn't exactly find when.Regarding the base 12 idea, how can we be sure if this too will not give same representation for two different sequences? $\endgroup$
    – O_huck
    Oct 23, 2013 at 14:48
  • $\begingroup$ Each polynomial has a unique representation in the suggested scheme because each integer has a unique representation in base 10. $\endgroup$
    – Joni
    Oct 23, 2013 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.