# Thread: The cardinality of the set of complex numbers

1. ## The cardinality of the set of complex numbers

I know $\displaystyle |\mathbb{C}|=|\mathbb{R}|$, but I am not exactly sure how to do a formal proof. I know that every element in $\displaystyle \mathbb{C}$ can be written as $\displaystyle a+bi, \, a,b\in \mathbb{R}$. So every element in $\displaystyle \mathbb{C}$ can be expressed as $\displaystyle (a,b) \in \mathbb{R \times R}$. Now, what would be a bijective function that maps $\displaystyle \mathbb{R \times R} \rightarrow \mathbb{R}$?

2. Originally Posted by Pinkk
I know $\displaystyle |\mathbb{C}|=|\mathbb{R}|$, but I am not exactly sure how to do a formal proof. I know that every element in $\displaystyle \mathbb{C}$ can be written as $\displaystyle a+bi, \, a,b\in \mathbb{R}$. So every element in $\displaystyle \mathbb{C}$ can be expressed as $\displaystyle (a,b) \in \mathbb{R \times R}$. Now, what would be a bijective function that maps $\displaystyle \mathbb{R \times R} \rightarrow \mathbb{R}$?
What have you tried? Try showing that $\displaystyle \mathbb{R}^2\simeq S^1$ and $\displaystyle S^1\simeq (-1,1)$. ($\displaystyle \simeq$ denotes equipotent...same size)

3. Ok. Here, I will give you a checklist of things to prove.

1. $\displaystyle \mathbb{R}\times\mathbb{R}\simeq S^1=(-1,1)\times(-1,1)$

Spoiler:
Draw a geometric picture and show that $\displaystyle S^1$ "bent upward" into a hemi-sphere has the property than any line projected from through a point $\displaystyle P$ will hit a unique point $\displaystyle P'\in\mathbb{R}^2$. This is an injection, apply the Schroder-Bernstein theorem.

2. $\displaystyle S^1\simeq (-1,1)\times (0,1)$

Spoiler:
You tell me!

3. $\displaystyle (-1,1)\times(0,1)\simeq(-1,1)$

Spoiler:
Note that this is merely the semi-circle "over" the interval $\displaystyle (0,1)$ consider the projection $\displaystyle \pi-1,1)\times(0,1)\mapsto(-1,1)$ given by $\displaystyle \pi(x,y)=x$. Show that this is bijective.

Note: There are other ways to do this. This is just, in my mind, the most canonical progression.

P.S. Draw a picture!

4. I am confused by the terminology. $\displaystyle S^1$ is a circle, i.e., a one-dimensional curve, without the interior points. Now, how can be easily bent upward into a hemi-sphere, which is a two-dimensional surface? In my opinion, relating a two-dimensional set, like $\displaystyle \mathbb{R}^2$, with one-dimensional set, like $\displaystyle \mathbb{R}$, is the main difficulty of this problem.

Also, I am confused by the notation $\displaystyle S^1=(-1,1)\times(-1,1)$. Doesn't $\displaystyle \times$ mean Cartesian product? Again, relating two-dimensional set $\displaystyle (-1,1)\times(-1,1)$ to one-dimensional $\displaystyle S^1$ is nontrivial.

I assume that by $\displaystyle S^1$ you do mean one-dimensional curve because you say that a projection from half of $\displaystyle S^1$ into $\displaystyle (-1,1)$ is a bijection.

5. I just started analysis, so I have not learned any of what you mentioned. But I had the idea of showing there exists an $\displaystyle f : (0,1) \times (0,1) \rightarrow (0,1)$ $\displaystyle f((0.a_{1}a_{2}a_{3}...,0.b_{1}b_{2}b_{3}...)) = 0.a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}...$

If I restrict the $\displaystyle a_{n}, b_{n}$ to be digits from 1 to 8, then this is bijective, correct?

6. I think you are right, except that numbers with decimal expansion having only digits 1 through 8 do not cover the whole interval (0, 1). For example, I don't see how to represent 0.9 this way.

We could first prove that continuum $\displaystyle \mathfrak{c}$, which is the cardinality of all real numbers, is the same as $\displaystyle 2^{\aleph_0}$. First, it is easy to show that all real numbers are equipotent with (0,1) by Drexel's suggestion. Namely, using a coordinate system on a plane, draw a lower semi-circle with radius 1 and center in (0,1). Let's call it $\displaystyle S$. Then any ray (half of a line) emitted from (0,1) and crossing $\displaystyle S$ also crosses the horizontal axis, thus relating the two intersection points. ($\displaystyle S$ should not include the endpoints (-1,1) and (1,1).) Then projection from $\displaystyle S$ to the horizontal axis is a bijection between $\displaystyle S$ and (-1,1). Finally, $\displaystyle f(x)=(x+1)/2$ is a bijection between (-1,1) and (0,1).

Next, (0,1) is equipotent with $\displaystyle 2^{\aleph_0}$, which is the set of all infinite sequences of 0 and 1. One proof is in Wikipedia, but I think there is a small mistake in the second part, which shows that $\displaystyle 2^{\aleph_0}$ can be injected in $\displaystyle \mathbb{R}$. I think, the right way is to take a sequence, change all 1's into 2's, and interpret the result as a ternary expansion of a real number in [0,1]. This mapping is injective. Indeed, if a real number from [0,1] has more than one ternary expansion, one of those expansions from some point stabilizes as $\displaystyle 11111\dots$ or $\displaystyle 22222\dots$. But since we excluded 1's from our sequences, no ambiguity is left.

Now that we don't have to pay attention to these issues anymore, it is easy to join two sequences $\displaystyle a_1a_2a_3\dots$ and $\displaystyle b_1b_2b_3\dots$ by interleaving them: $\displaystyle a_1b_1a_2b_2a_3b_3\dots$, as suggested in the previous post. This is a bijection between $\displaystyle 2^{\aleph_0}\times 2^{\aleph_0}$ and $\displaystyle 2^{\aleph_0}$.

Another way to prove equipotency of a square and a line segment is by using space-filling curves, such as Peano or Hilbert curves. Wikipedia and an excellent site Cut The Knot! have articles about them. Wikipedia article even has a section with a "Proof that a square and its side contain the same number of points", while Cut-The-Knot has the construction of the curve and a proof that it indeed fills the square, both of which require only a little calculus.

7. Hmm, I've been thinking about another approach, maybe this will work. I can find an injective function $\displaystyle f: \mathbb{R} \rightarrow \mathbb{R \times R}$, so $\displaystyle |\mathbb{R}| \le |\mathbb{R \times R}|$. Now, if I use the similar argument I made previously:
$\displaystyle f((0.a_{1}a_{2}a_{3}...,0.b_{1}b_{2}b_{3}...)) = 0.a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}...$ where I can assume that at some point along the decimal expansion of each rational number is unique (let the digits of the decimal expansion of the rational number be 0 from some position on), then that function is clearly injective, correct? If it is, then $\displaystyle |(0,1) \times (0,1)| \le |(0,1)|$, which means $\displaystyle |\mathbb{R \times R}| \le |\mathbb{R}|$. Since $\displaystyle |\mathbb{R \times R}| \le |\mathbb{R}|$ and $\displaystyle |\mathbb{R}| \le |\mathbb{R \times R}|$, $\displaystyle |\mathbb{R \times R}| = |\mathbb{R}|$.

8. Yes, I don't see anything wrong with this either.

9. Whew, thanks! I somewhat understand the suggestions you are making, but I don't think my professor expects us to use that sort of knowledge.

10. Originally Posted by emakarov
I am confused by the terminology. $\displaystyle S^1$ is a circle, i.e., a one-dimensional curve, without the interior points. Now, how can be easily bent upward into a hemi-sphere, which is a two-dimensional surface? In my opinion, relating a two-dimensional set, like $\displaystyle \mathbb{R}^2$, with one-dimensional set, like $\displaystyle \mathbb{R}$, is the main difficulty of this problem.

Also, I am confused by the notation $\displaystyle S^1=(-1,1)\times(-1,1)$. Doesn't $\displaystyle \times$ mean Cartesian product? Again, relating two-dimensional set $\displaystyle (-1,1)\times(-1,1)$ to one-dimensional $\displaystyle S^1$ is nontrivial.

I assume that by $\displaystyle S^1$ you do mean one-dimensional curve because you say that a projection from half of $\displaystyle S^1$ into $\displaystyle (-1,1)$ is a bijection.
Wow! I must have been tired last night. Let me rectify this.

Firstly, I completely forgot that $\displaystyle S^1$ was the topological standard for the unit circle. In fact, here I was referencing, as can be seen from the representation of $\displaystyle S^1=(-1,1)\times(-1,1)$ is something similar to the unit square. I came up with an easier way though, it almost looks similar to Pinkk's.

Problem: Prove that $\displaystyle \mathbb{R}\times\mathbb{R}\simeq \mathbb{R}$.

Proof: This will be proven if the following (very long) chain of equipotences can be shown $\displaystyle \mathbb{R}\times\mathbb{R}\simeq\mathcal{U}=[0,1)\times[0,1)\simeq[0,1)\times\{0\}\simeq(0,1)\simeq\mathbb{R}$. Luckily though, most of these are well known.

So let us begin

Step 1-

Claim: $\displaystyle \mathbb{R}\times\mathbb{R}\simeq\mathcal{U}$

Proof: Let $\displaystyle D$ be some open disc contained strictly within $\displaystyle \mathcal{U}$ with coenciding centers. Bend this circle up to create an open hemispherical surface at the center of $\displaystyle \mathcal{U}$. Next, construct a vertical $\displaystyle \ell$ which emanates from the center of the surface and that is perpendicular to $\displaystyle \mathbb{R}^2$. One can see (why Pinkk ?) that projecting from various positions on this line creates an injection between $\displaystyle D$ and $\displaystyle \mathbb{R}\times\mathbb{R}$. Applying the Schroder-Bernstein theorem we can then see that $\displaystyle \mathbb{R}\times\mathbb{R}\simeq D$ from which the conclusion follows.

Step 2- This is the hard part. In essence we are saying that the cardinality of this (almost) square is the same as just one of it's edges.

Claim: $\displaystyle \mathcal{U}\simeq[0,1)\times\{0\}$.

Proof: Let $\displaystyle (x,y)\in\mathcal{U}$ be arbitrary. Both $\displaystyle x,y$ have unique decimal representations which do not end in an infinite chain of $\displaystyle 9$'s (this is a convention). Now form a new number $\displaystyle z$ be interweaving the decimal expansions of $\displaystyle x,y$. In other words $\displaystyle (x,y)=(.a_1a_2\cdots,b_1,b_2\cdots)\mapsto .a_1b_1a_2b_2\cdots.$. We now note that this mapping is injective, for $\displaystyle .z_1z_1\cdots=z=z'=.z'_1z'_2\cdots$ implies that $\displaystyle z_{2n}=z'_{2n}$ which means that the x-coordinate of the ordered pair the two came from is the same, and $\displaystyle z_{2n+1}=z'_{2n+1}$ implies that the y-coordinate is the same. Appealing once again to the Shcroder-Bernstein theorem thus shows that $\displaystyle \mathcal{U}\simeq[0,1)\times\{0\}$

Step 3- This is very simple

Claim: $\displaystyle [0,1)\times\{0\}\simeq(0,1)$

Proof: Clearly the projection $\displaystyle \pi:[0,1)\times\{0\}\mapsto[0,1)$ given by $\displaystyle \pi(x,y)=x$ is clearly bijective. Also, it is trivially true that $\displaystyle [0,1)\simeq(0,1)$ from where the conclusion follows.

Step 4- This is very well known.

Claim: $\displaystyle \mathbb{R}\simeq(0,1)$

Proof: The mapping $\displaystyle f0,1)\mapsto\mathbb{R}$ given by $\displaystyle x\mapsto\tan\left(\pi\left[x-\frac{1}{2}\right]\right)$ is a bijection (I leave this to you).

Now, realizing that this string has been satisfied the result follows.

,

,

,

,

# cardinality of a complex numbers set

Click on a term to search for related topics.