Question

Prove that the interval \(\{x \in \mathbb{R} \vert 0 \leq x \leq 1\}\) in uncountable. In other words show that no function \(f \mathbb{N} \to [0,1]\) can have one to one and onto correspondence.

Answer 1

@KingGeorge Can you take a look?

Answer 2

The classical way to do this, is by Cantor's diagonalization proof.

Suppose you can list every number in [0,1]. So you have something like
1. 0.723462349786...
2. 0.473677967453...
3. 0.012384756293...
.
.
.
And so on.

Answer 3

The thing is we dont touch on Cantor's Diagonalization. We are learning abt limts and covergence

Answer 4

So your teacher is looking for something that's not the diagonalization?

Answer 5

Yess

Answer 6

Since you're talking about limits and convergence, I would then suppose that this has something to do with taking infinite sums that converge to real numbers, and somehow showing there are an uncountable number of these sums. Hmmm... I may have to think for a little bit.

Answer 7

Gonna think abt it toooo

Answer 8

Well actually it gives us the method we should be using

Answer 9

OK whatever its 3:30 am. I cant think anymore. i will have to put something together tomorrow

Answer 10

I am gonna head to bed now. I will come back tomorrow to check if you found some direction but otherwise don't stress over it. I will hopefully figure something out. Thanks King George :) Good Night

Answer 11

For (a), perhaps a proof by induction will work.

Base: n=1. Let f(1)=\(x_1\in[0,1]\). Then you can choose \(a_1\in[0,1]\) such that \(a_1\) is minimal and less than \(x_1\). Similarly, let \(b_1\in[0,1]\) such that \(b_1\) is maximal and less than \(x_1\). If \(x_1=0\), choose any \(a_1,b_1\in(0,1]\). Clearly, \(x_1\notin[a_1,b_1]\).

Now assume true up to some \(k\in \mathbb{N}\). Then we have two cases.
Case 1: \(x_{k+1}\notin[a_k,b_k]\). Here, just choose \(a_{k+1}>a_k\) and \(b_{k+1}<b_k\) such that \([a_{k+1},b_{k+1}]\subset[a_k,b_k]\).
Case 2: \(x_{k+1}\in[a_k,b_k]\). Here, do the same kind of process we did for the base case.

Hence, by induction, we're done.

Answer 12

To show that \(\{a_n\}\) converges, WLOG let \(n>m\), and note that \(|a_n-a_m|<|b_m-a_m|\) since \(a_n\in[a_m,b_m]\). Then, since the interval gets smaller on every repetition, we can say that \(|b_m-a_m|<\epsilon\) for any \(\epsilon>0\) for sufficiently large \(m\). Hence, \(\{a_n\}\) is Cauchy, and is therefore convergent, and converges to some point A.

Answer 13

Then, we can see that A is in \([a_n,b_n]\) for all \(n\in\mathbb{N}\) since each interval is contained within the previous one, and since \(\{a_n\}\) is a strictly increasing sequence. If \(A\notin[a_n,b_n]\) for some n, then since the sequence is increasing, it must be that \(A>b_k\) for some \(k\). However, \(a_k<b_l\) for any choice of \(k\) or \(l\), so this is a contradiction.

Hence, \(A\in[a_n,b_n]\) for all \(n\in\mathbb{N}\).

Answer 14

To finish it off, notice that \(f(n)\neq A\) for any choice of \(n\) since \(A\in[a_n,b_n]\) for all \(n\), but \(f(n)\notin[a_n,b_n]\) for all \(n\). Thus, \(f\) is not a surjective function, and the reals are uncountable.

Answer 15

Just fyi, I did reference this page a little bit, however, they take some of these steps for granted (such as part (a)), and have a very informal proof.

http://boolesrings.org/scoskey/my-favorite-proof-that-r-is-uncountable/

Answer 16

I wasnt exactly sure what we are proving for case 2 of part (a)
If \(x_{k+1}\) is an element of \([a_k,b_k]\) Then it must be an element of [0,1]

Answer 17

That was the onlt part that was confusing me

Answer 18

In retrospect, I probably should have changed part (a) so that you chose the smallest \(a_1\) such that \(a_1>0\), and \(a_1<x_1\). This would make my proof of part (c) more technically correct.

However, this is assuming that \(x_1>0\). If \(x_1=0\), we would not be able to choose any \(a_1\) smaller than \(x_1\). Case 2 deals with that.

Answer 19

No wait. Let me read over that more carefully before I continue.

Answer 20

Oh right. The second case deals with the possibility of \(x_k\) landing in the interval already chosen. This limits the new interval we have to create, since \(x_k\) can not lie in the new interval. So I was lazy, and said to make the new interval in the same kind of fashion we chose the very first interval.

Answer 21

That make more sense?

Answer 22

Ohhhh ok get it

Answer 23

Yaaaaaa

Answer 24

Hmmm I am also dont follow the part where u prove that \(A \in [a_n,b_n]\) for all \( n \in \mathbb{N}\)

Answer 25

So we created the sequence \(\{a_k\}\) as a strictly increasing sequence (at least with the new revisions I just gave a few posts above). Thus, \(A>a_k\) for any \(k\in\mathbb{N}\). Therefore, we now suppose that \(A\notin[a_k,b_k]\) for some \(k\in\mathbb{N}\). So \(A>b_k\). However, since \(\{a_k\}\) converges to \(A\), we can choose some \(a_j\) such that \(b_k<a_j<A\). This is a contradiction, since we have always chosen our \(a_k\) to be less than \(b_k\). Therefore \(A\) is in the interval.

Answer 26

OHHHH I GET IT NOWWW

Answer 27

Thanks KG :)

Answer 28

Its really clear and and to the point. You always have this sleek way of proving

Answer 29

Thanks :)