Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Denote $\mathbb Q$$[x]$ = set of polynomials with coefficients $c_1$, $c_2$, $...$ ,$c_n$ in $\mathbb Q$.

A number $a$ is algebraic if there exists a polynomial $f(x)$ in $\mathbb Q$[x] such that $f(a)$ $=$ $0.$ (it is a solution to the polynomial).

1) Show that $\mathbb Q$$[x]$ is denumerable.

My attempt:

I claim that the set Q is denumerable from a theorem which I proved previously. Thus I claim that either:

$\mathbb Q$$[x]$ is denumerable or $\mathbb Q$$[x]$ is uncountable.

Because a polynomial has $n$ finitely many terms, we are able to count the class of sets that contain polynomials with rational roots. (For every $n$th term, we are able to find its corresponding coefficient $c_n$ and vice versa).

Thus $\mathbb Q$$[x]$ is a denumerable union of disjoint finite sets, which is denumerable.

2) Show that the set $A$ of algebraic numbers $a$ is denumerable.

We have established that the set $\mathbb Q$[x] is denumerable. $A$ $:=$ {$a$: $a$ is a solution to $f(x)$ $=$ $0$}

A polynomial of degree $n$ may have at most $n$ roots, or $n$ many $a$ terms. That is, each set of roots for a particular polynomial is finite.

Thus $A$ is a union of these finitely many sets of roots for particular polynomials. This is a denumerable union of finite sets, which must be denumerable.

3) Show that the set of transcendental numbers is equipotent to $\mathbb R$.

Proof by Contradiction.

Assume that the set $T$ of transcendental numbers is countable.

Then $T$ U $A$ $=$ $\mathbb R$. But clearly, the set $\mathbb R$ is uncountable.

A union of 2 countable sets cannot be uncountable; since $A$ is denumerable, then $T$ cannot be denumerable and must thus be uncountable.

share|improve this question
    
I am almost certain that I have answered all these questions in several forms on the site before. You might want to search for such questions before posting. The answers may suffice to tell you what you want to know. –  Asaf Karagila Nov 11 '12 at 0:28

2 Answers 2

Here are some remarks.

  1. I have no idea what you are trying to claim in your proof. You rely on a theorem which you have proved, but you don't tell us what it is. The fact that every set is countable or uncountable is trivial (unless you are using some intuitionistic logic).

    What you should do is argue that there are only countably many polynomial of degree $n$ for all $n$, therefore $\mathbb Q[x]$ is the countable union of countable sets, and therefore countable.

  2. Yes, this is okay.

  3. This only shows that $T$ is uncountable, but not every uncountable set is equipotent with $\mathbb R$. In fact it is possible that there are uncountable subsets of $\mathbb R$ which are not equipotent with $\mathbb R$ itself. You need to argue more.

    You need to argue that $|T\cup A|=\max\{|T|,|A|\}=|\mathbb R|$ and $A$ is countable, therefore $|T|=|\mathbb R|$.

Now, all your claims use the axiom of choice. All the claims which you have to prove can be proved without the axiom of choice, as well. It is only slightly more difficult.

share|improve this answer
    
The theorem previous proved is that $\Bbb Q$ is countable. –  Brian M. Scott Nov 11 '12 at 0:27
1  
@Brian: I see. First users asked me to find a copy of Munkers, now users request that I keep a close eye on their questions history (without even indicating that I should)... this site is become more and more demanding with each day! :-) –  Asaf Karagila Nov 11 '12 at 0:29
    
I don’t know whether it was a question asked here; I doubt that it was. But it can be inferred from the wording of this question (or at least, it can be inferred that the OP proved something that easily implies that $\Bbb Q$ is countable). (Spotting or not spotting this may be a first vs. second language thing.) –  Brian M. Scott Nov 11 '12 at 0:37

Because a polynomial has $n$ finitely many terms, we are able to count the class of sets that contain polynomials with rational roots. (For every $n$th term, we are able to find its corresponding coefficient $c_n$ and vice versa).

Thus $\Bbb Q[x]$ is a denumerable union of disjoint finite sets, which is denumerable.

The first paragraph makes very little sense, I’m afraid, and in the second it’s not at all clear what disjoint finite sets you have in mind. I can only guess that you’re confusing the polynomial $c_0+c_1x+\ldots+c_nx^n$ with the set $\{c_0,c_1,\dots,c_n\}$; if so, you’re missing some very important points.

First, in general there is more than one polynomial with the same set of coefficients: $1+2x+3x^2$ and $2+3x+x^2$ both have $\{1,2,3\}$ as their sets of coefficients. Thus, the map from polynomials to sets of coefficients is not injective (one-to-one), and you can’t assume that the cardinality $\Bbb Q[x]$ is less than or equal to the cardinality of the collection of coefficient sets.

Secondly, $\Bbb Q[x]$ simply isn’t the union of the coefficient sets; the union of the coefficient sets is simply $\Bbb Q$.

You’re not wholly on the wrong track, but instead of working with the set of coefficients of a polynomial, look at them as a tuple: there is a natural bijection between $\{p\in\Bbb Q[x]:\deg p=n\}$ and $\Bbb Q^{n+1}$. Now use (or prove) the facts that $\Bbb Q^n$ is countable for each $n\in\Bbb N$ and that $\Bbb Q[x]$ is the union of the sets $\{p\in\Bbb Q[x]:\deg p=n\}$ to show that $\Bbb Q[x]$ is countable.

Your argument for (2) is okay.

Your argument for (3) shows that $T$ is uncountable, but it does not show that $T$ has the same cardinality as $\Bbb R$. For that you need to know that $|X\cup Y|=\max\{|X|,|Y|\}$ whenever $X$ and $Y$ are infinite sets, so that you can conclude that $$|\Bbb R|=|A\cup T|=\max\{|A|,|T|\}=|T|\;.$$

share|improve this answer
    
Thank you for your help and direction. For (3), since $T$ is uncountable and $A$ is denumerable, wouldn't the maximum of $|A|$ and $|T|$ be $|T|$? –  Julian Park Nov 11 '12 at 1:21
    
@Julian: Yes, as I wrote in the very last line of my answer. –  Brian M. Scott Nov 11 '12 at 1:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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