1
$\begingroup$

this is the proof that I came up with for the question, it is somewhat similar to others but the Euclidean space doesn't appear in other questions. However, could someone tell me why the paragraph that talks about $\mathbb R^n$ is not induction?

Assume $A\times A$ is uncountable and suppose that $A$ is countable. If $A$ is finite with $|A|=m$, then $|A| \times |A|=m \times m=mm$, therefore $A \times A$ is finite, meaning that it is countable. However, this is a contradiction. If $A$ is countably infinite, then there exists an injective $\varphi: A \rightarrow \mathbb N $ from the lecture notes. Therefore, the map $g:A\times A \rightarrow \mathbb N \times \mathbb N $ given by $g(x,y)=(\varphi(x),\varphi(y))$ is injective. However, it suffices to show that $\mathbb N \times \mathbb N $ is countable, because if $\mathbb N \times \mathbb N $ is a countable set, then $A\times A$ is countable. Indeed, consider $f:\mathbb N \times \mathbb N \rightarrow \mathbb N $ where $(m,n)\rightarrow 2^m3^n$, $f$ is injective by the uniqueness of prime factorization (class lecture notes). We can therefore conclude that $\mathbb N \times \mathbb N $ is a countable set, then $A\times A$ is countable. However, this is another contradiction. Therefore, if $A\times A$ is uncountable then $A$ is uncountable.

Now assume that $A$ is uncountable and suppose that $A\times A$ is countable. If $A\times A$ is countable then that means that there exists $h: A\times A \rightarrow \mathbb N $ that is an injective function. This means that $f: A \rightarrow \mathbb N $, which means that $A$ is countable by definition. However, this is a contradiction since we assumed that $A$ is uncountable.

Therefore, we have proven that $A$ is uncountable if and only if $A\times A$ is uncountable.\

To show that $\mathbb R^n$ is uncountable, we must first show that $\mathbb R$ is uncountable. In order to do so, we must show that $(0,1)$ is not countable. Now suppose that $(0,1)$ is countable, therefore we are assuming that it is countably infinite. This means that there must exist a bijection $r: \mathbb N \rightarrow (0,1)$. We could write each number in the list in decimal form, as we did in class for each number. Now let $N$ be a number that is obtained by doing the following. For $n \in \mathbb N $, let the $n^{th}$ decimal spot of $N$ be equal to the $n^{th}$ decimal of the $n^{th}$ number in the list that we made and add $2$ mod $10$. In doing so, we end up with $N$ being different than every number in the list, indicating that the list is incomplete. This is a contradiction because we assume that there was bijection $r: \mathbb N \rightarrow (0,1)$. Therefore, $(0,1)$ is uncountable and since $(0,1) \subset \mathbb R$, then we have proven that $\mathbb R$ is uncountable from the problem above. Now suppose that $\mathbb R^{n+1}$ is given by $\mathbb R \times \mathbb R^n \times \mathbb R^{n-1} \times ... \times R^0$, since we know that $\mathbb R$ is uncountable then the cross product between uncountable sets is uncountable. Therefore we can conclude that the Euclidean space $\mathbb R^n$ is uncountable.

$\endgroup$
1
$\begingroup$

Overall, the proof looks good. You do a good job of being explicit with everything you write, which is good. Just Two things I noticed. You say

If $A×A$ is countable then that means that there exists $h:A×A\to \mathbb{N}$ that is an injective function. This means that $f:A\to \mathbb{N}$ ....

You haven't defined $f$. This section of the proof hinges on the existence of such an $f$, so it's rather important that you define it. Here is one way to do this:

Because $h$, the diagonal map $d:A \to A\times A$ given by $a \to (a,a)$, and the projection $p:A\times A \to A$ given by $(x,y) \to x$ are all injective, their composition $p \circ h\circ d: A\to \mathbb{N}$ is also injective (drawing a diagram might help). Let $f = p \circ h\circ d$... and continue with your proof.


In general, it's ok to just assert things you've done in class (have mercy on your grader), and it sounds like you've already proven $\mathbb{R}$ is uncountable, so I'll skip that paragraph.

I do not understand what you mean when you say

Now suppose that $\mathbb{R}^{n+1}$ is given by $\mathbb{R}×\mathbb{R}^{n}×\mathbb{R}^{n-1}×...×\mathbb{R}$

First off, what are you supposing? When you "suppose" something you're usually assuming it for the sake of contradiction. We already know that $\mathbb{R}^n$ looks like. Second, $\mathbb{R}×\mathbb{R}^{n}×\mathbb{R}^{n-1}×...×\mathbb{R}$ would appear to be $\mathbb{R}^{\frac{n(n+1)}{2} +1}$. I don't see what you're trying to do here.

Here's an inductive proof:

base case: $\mathbb{R}$ is uncountable. done.

Now, assume inductively that $\mathbb{R}^n$ is uncountable. Then, $ \mathbb{R}^{n+1} = \mathbb{R}^n \times \mathbb{R}$ is the product of two uncountable sets, meaning is uncountable. This closes the induction.

Hope it helps.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It does help, induction proofs are not my strongest suit so i was trying to formulate it by saying "now suppose that ..." $\endgroup$ – Kmjg Khk Nov 23 '19 at 17:23
  • 1
    $\begingroup$ I see. you were trying to suppose the inductive hypothesis. For the time being, I'd recommend sticking to the very formulaic "assume inductively that $P(n)$. We show that $P(n+1)$," where $P(n)$ is the proposition you're trying to prove (in this case, "$\mathbb{R}^n$ is uncountable"). It helps you be very explicit about what you are assuming, and what you want to prove. $\endgroup$ – Noah Caplinger Nov 23 '19 at 18:03
0
$\begingroup$

If A is countable, then A×A injects into N×N which injects into N.
Thus A×A is countable.
If A×A is countable, then A injects into A×A which injects into N.
Thus A is countable.
Exercise. Show if A is infinite, then A and A×A are equinumerous.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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