Set of Polynomials over Infinite Set has Same Cardinality

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set of infinite cardinality $\kappa$.

Let $S \left[{x}\right]$ be the set of polynomial forms over $S$ in the indeterminate $x$.


Then $S \left[{x}\right]$ has cardinality $\kappa$.


Proof

Since $S \left[{x}\right]$ contains a copy of $S$ as constant polynomials, we have an injection $S \to S \left[{x}\right]$.


We define an injection from $S \left[{x}\right]$ to the set $\mathcal F$ of finite sequences over $S$ as follows:

Each polynomial in $f \in S \left[{x}\right]$ is of the form:

$f = a_0 + a_1 x + a_2 x^2 + \dotsb + a_n x^n$

where $a_n$ is non-zero and each $a_i$ is in $S$.

We send each polynomial $f$ to the sequence of its coefficients $\left({a_0, \dotsc, a_n}\right)$.

By the definition of equality of polynomials, this is injective.


Now the set of finite sequences over $S$ is a countable union of sets of cardinality $\kappa$.

From Cardinality of Infinite Union of Infinite Sets, $\mathcal F$ has cardinality $\kappa$.

Therefore there is a bijection $\mathcal F \leftrightarrow S$.

Composing this with the injection $S \left[{x}\right] \to \mathcal F$, we have an injection $S \left[{x}\right] \to S$.


So by the Cantor-Bernstein-Schröder Theorem there is a bijection $S \left[{x}\right] \leftrightarrow S$.

Hence, we have:

$\left\vert{S \left[{x}\right]}\right\vert = \left\vert{S}\right\vert = \kappa$

$\blacksquare$