Prove that the set of algebraic numbers is countable.
Proof:
Let A be the set of all algebraic numbers.
Let ={x E R : p(x) = 0 for some p a polynomial of degree n with integer coefficients}
∞
U = A
n=1
Consider the n-th degree polynomial
, E Z, ≠0
|{ : E Z, ≠0}| = | | = |Z| = |N|
Each such polynomial has at most n roots.
Therefore, is countable.
A countable union of countable sets is countable, thus A is countable.
============================
1) I don't understand why |{ : E Z, ≠0}| = | |. cannot be 0, so the set on the LHS is a little bit different from . How can we formally prove that it has the same cardinality as ?
2) Assuming the above, I understand why the set of all polynomials with integer coefficients is countable, but I don't understand why the set of all "roots" of these polynomials, | |, is also countable. I know each polynomial with degree n has at most n roots, but I don't see how it rigorously follows that the set of all "roots" are countable. How can we prove it formally?
These are the two fine points that I don't understand in this proof.
I hope someone can clarify these. Thanks for any help!
[note: also under discussion in math links forum]
Thanks!
A related problem:
Assuming the fact that the set of algebraic numbers is countable, prove that the set of transcendental numbers has the same cardinality R, the set of real numbers.
Attempt:
Let A be the set of algebraic numbers and T the set of transcendentals. Then R= A U T, so if T was countable then so would R be (because a countable union of countable sets is countable). Contradiction. Thus T is uncountable.
But this only proves that T is uncountable, and we need to prove MORE than that, namely, |T|=|R|, i.e. the cardinality of the set of transcendental numbers is exactly equal to the cardinality of the real numbers. How to prove this??
Any help is appreciated!
Well, it depends on what you have to go on or what you can use. Presumably you know that ? where is a countable subset of (If not, you can use the Schroeder-Bernstein theorem to show this). Then just note that .
If you assume the continuum hypothesis, which you probably shouldn't to be safe, you can note that , and since is uncountable (which you proved above), it must mean by the hypothesis.
Recall the Schroeder-Bernstein Theorem: If and are sets such that and , then .
Also recall that ( 0,1) \mapsto \mathbb R" alt="f0,1) \mapsto \mathbb R" /> defined by is a bijective function that maps the open interval onto )
Now, clearly, if is a countable subset of , we have
(1) and
(2) (The reals minus a countable set should be at least as big as the reals minus an uncountable one)
But since , (1) tells us that . But then we have and , which implies by the Schroeder-Bernstein Theorem.
Taking in your problem yields that
Thanks, I like your proof.
This is the only point I'm having trouble now. I understand this intuitively; nobody should doubt why this is true.
But the precise definition says |A|≤|B| iff there is a one-to-one map f:A->B. How can we rigorously prove, i.e. define a one-to-one map from (0,1) into R \ C?
Thanks!
Since there exists some which is bijective. So, define 0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" alt="\varphi0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" /> by the inclusion mapping . This is clearly both well-defined (since ) and injective. So, then 0,1)\to\mathbb{R}-C" alt="w\circ \varphi0,1)\to\mathbb{R}-C" /> is the composition of two injective functions and thus injective.
Hi,
I understand that |N|=|C|, so there exists a bijection bewteen N and C, but there is some gap in my understanding as to why |R\N| = |R\C|. It is intutively believable, but I don't see how it rigorously follows.
Is it provable in general that
If |A|=|C| and |B|=|D|,
then |A\B| = |C\D| ?
If so, what is the way to do a formal proof on statements like this?
Thanks!