Set Theory: Prove the set of complex numbers is uncountable

[cxc001]

How to prove the set of complex numbers is uncountable?

Let C be the set of all complex numbers,
So C={a+bi: a,b belongs to N; i=sqrt(-1)}

--------------------------------------------------
set of all real numbers is uncountable
open intervals are uncountable
set of all irrational numbers is uncountable
--------------------------------------------------

 

[radou]

Try to find a subset of C which is uncountable (for then C is uncountable, too).

 

[radou]

Btw, you mean, a, b belongs to R?

 

[cxc001]

Yeah, my bet! a, b are real numbers, typo...

I got this one.
Let C be the set of all complex numbers
C={a+bi: a, b are real no.}
For any real number r can be mapped to a complex no. by r=r+0i, where r=a and is real no., b=0 is also real no.
Let R be set of all real numbers
R={r+0i: r is real no}
It follows that set R is a subset of set C
and R is uncountable, therefore C is uncountable by Theorem!

 

[axm7473]

If we are considering the set of complex numbers of the form a+bi where "a" and "b" are real numbers, then the proof is relatively easy, because this is another way of saying "the set of points on the complex plane". As mentioned earlier, the real number line is a subset of the complex plane, which can be seen by assigning "b" the value 0. The closed interval from 0 to 1 can be shown to be uncountable by using Cantor's diagonalization argument. Thus, as concluded from earlier, the set of complex numbers is an uncountable set.

However, even though the set C defined by cxc001 is not all the complex numbers, it is a better question to ask whether this set C={a+bi:a,b natural numbers} is countable or uncountable. In fact, I believe this is probably what cxc001 meant to say the first place, but accidentally referred to such a set as "all the complex numbers". From this point forward, I will replace the set C with the notation C' to avoid confusion.

As it turns out, this set is countable. To show this, one needs to show that the set N (the natural numbers: 1,2,3,...) and the set C' have injective mappings into one another. In other words, For every natural number, I can find a unique corresponding number from C', and for every number in C', I can find a unique corresponding number from N. One direction is easy. Let any natural number "n" correspond to the complex number "n+i" which is a number from C'. For the other direction, let "a+bi" be any number from C' such that "a+bi" corresponds to the natural number (2^a)*(3^b). Because "a" and "b" are natural numbers, so is (2^a)*(3^b). Also, 2 and 3 are prime, so such a number will always be unique. Hence, our set C' is countable.

To further the discussion, consider algebraic numbers. A number is an algebraic number if it is a root value to some polynomial with rational coefficients. As a reminder, a polynomial has degree n for some natural number n. This means a polynomial, by definition, is of finite degree. Also, a root value to a polynomial is a number that is mapped to 0 by the polynomial.

ex.) x=1 is a root value of "x^2 - 1" because (1)^2 - 1 = 1-1 = 0.

For the sake of the discussion, how could one go about determining whether or not the set C'={a+bi: a,b are algebraic numbers} is countable?

 

[l'Hôpital]

For the sake of the discussion, how could one go about determining whether or not the set C'={a+bi: a,b are algebraic numbers} is countable?

If I recall correctly, algebraic numbers are countable. The Cartesian product of two countable sets is countable. C' = {a + bi: a,b are algebraic numbers} = A x A, where A is the set of algebraic numbers. So C' is countable.

 

[axm7473]

I believe you are right. If I remember correctly, the set of algebraic numbers do turn out to be countable. Again, just for the sake of this conversation, how would one go about showing this? I have a method in mind similar to the one employed to solve the previous problem that may or may not work, but I'm interested in seeing what other ideas people have.

 

[l'Hôpital]

So, how do we show that the cartesian to two countable sets is countable? Well.

Let A and B be two countable sets. So, let $$(a,b) \in A \times B$$. In particular,

$$a \in A , b \in B$$

So, we'll break A x B. Since A is countable, we enumerate the members, say $$a_i$$ for i = 1,2,3,...

So we can state the following:
$$\bigcup_{i=1}^{\infty} (a_i,b) = A \times B$$
Where $$(a_i, b)$$ is basically the set of coordinate pairs you can make with the left one being the particular $$a_i$$ and the right being all elements in B. Clearly, the cardinality of each set is at most the cardinality of B, thus this set is countable. The countable union of countable sets is countable, therefore A x B is countable.

Now, we could go prove that the countable union of sets is countable, if you wanted, though I don't see much of a point.

 

[Elucidus]

Cantor proved that the real algebraiic numbers are denumerable in his 1874 paper "On a Property of the Totality of All Real Algebraic Numbers" the proof of which is nicely summarized in "The Calculus Gallery" by William Dunham.

The Cartesian product of denumerable sets is also denumerable by a diagonal stratification argument (similar to showing Q is denumerable), hence the algebraic numbers (which include complex numbers) is also denumerable.

Since R (which is uncountable) is included in C then C cannot be countable.

Relevant theorem:

$\text{If } A \subseteq B \text{ then } |A| \leq |B|$