2
$\begingroup$

A question I have been given asks me to determine whether there is a bijection between the set of all real polynomials P and the set of (potentially infinite) real sequences $\mathbb{R}^\mathbb{N}$. However I am getting two contradictory answers.

Firstly the set of all polynomials has a countable basis which is given by the polynomials $1,x,x^2,x^3,\cdots$. However the set of all real sequences does not have a countable basis as it is possible to show that the set $\{(1,r,r^2,r^3,\cdots)| r \in \mathbb{R}\}$ is linearly independent so no countable basis exists.

Conversely it is possible to show that the set of all polynomials is in bijection with $\mathbb{R}$. Begin by saying that the polynomials of degree $0$ are in bijection with $\mathbb{R}$ which is in bijection with $(0,1)$ and so in bijection with $[0,\frac{1}{2})$. The polynomials of exactly degree 1 are in bijection with $\mathbb{R}/\{0\} \times \mathbb{R}$ which is in bijection with $\mathbb{R}$ which is in bijection with $(0,1)$ which is in bijection with $[\frac{1}{2},\frac{3}{4})$. Hence the set of all polynomials of degree at most $1$ are in bijection with $[0,\frac{3}{4})$.

Similarly the set of all polynomials of degree at most 2 are in bijection with $\mathbb{R}/\{0\} \times \mathbb{R} \times \mathbb{R}$ which is in bijection with $\mathbb{R}$ which is in bijection with $[\frac{3}{4},\frac{7}{8})$. Hence the set of all polynomials of degree at most 2 are in bijection with $[0,\frac{7}{8})$. We can repeat this argument to show that all polynomials of degree at most $n$ are in bijection with $[0,1-2^{-n+1})$. As all polynomials have a finite degree and can have any natural number as their degree the set of all polynomials is in bijection with $[0,1)$ which is in bijection with $\mathbb{R}$.

However $\mathbb{R}^\mathbb{N} = (2^\mathbb{N})^\mathbb{N} = 2^{(\mathbb{N}\times\mathbb{N})} = 2^\mathbb{N} = \mathbb{R}$ so they have the same cardinality so a bijection between $P$ and $\mathbb{R}^\mathbb{N}$ does exist.

One of these arguments is wrong. Does anyone know which one?

$\endgroup$
  • 3
    $\begingroup$ $\mathbb{R}^{\mathbb{N}}$ is the set of infinite sequences, no "potentially" about it. The first argument shows that the two are not isomorphic as vector spaces, which is a different question from whether there is a bijection between them. Both arguments are correct, they just answer different questions. $\endgroup$ – Qiaochu Yuan Oct 23 '17 at 20:33
  • $\begingroup$ Oh yes, sorry my bad. The question actually asked for an isomorphism and the first one was the proof given to me. I forgot that the bijection had to be linear as well... $\endgroup$ – Abdul Hadi Khan Oct 23 '17 at 20:36

Your Answer

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

Browse other questions tagged or ask your own question.