Why Doesn't a Proof by Contradiction Work for Cauchy Convergence?

[happyg1]

Hi,
Here's the question:
Show that if {x_n} is a cauchy sequence of points in the metric space M, and if {x_n} has a subsequence which converges to x \in M, Prove that x_n itself is convergent to x.
Now, I have proved this as follows..I didn't put in all of the details...
Let {x_n_k} be the subsequence which converges to x.
Choose n\in\mathbb{N} such that \forall k \geq N the distance from x_n_k to x \leq\frac{\eps}{2} and similarly for x_n,x_m then you wind up with \frac{\eps}{2}+\frac{\eps}{2}=\eps so you&#039;re done.<br /> My confusion lies in why can&#039;t you do a proof by contradiction?<br /> You let x_n converge to, say y, and the subsequence s_n_k (by hypothesis) converges to x...but every subsequence of a convergent (cauchy) sequence converges to the same limit. Why doesn&#039;t this work?<br /> CC

 

[happyg1]

I'm still learning latex, so forgive my funky text there. I think you can still see what I mean. I typed in \eps instead of \epsilon, so what's blank there is \frac{\epsilon}}{2}
sorry
CC

 

[matt grime]

There is no reason why you can assume the cauchy sequence x_n converges at all in the first place, is there? Just because a sequence is cauchy does not mean that its 'limit' exists in the original space.

 

[benorin]

Proposition: A Cauchy sequence that has a convergent subsequence is itself convergent.

pg. 52 of Introduction to Analysis by Maxwell Rossenlicht

 

[happyg1]

ok,
so I need to think of a cauchy sequence whose limit lies outside fo the origional space that has a subsequence whose limit lies inside the space to show that that this won't work...

 

[happyg1]

My head hurts

 

[benorin]

Do you know if the metric space is complete?

 

[happyg1]

we don't know about complete yet...

 

[happyg1]

dang it!
I was all sassy and confident about understanding this stuff...My final is coming up and now I'm all confused...I neeed a counterexample but I'm afraid to thinK about it because I'll doubt what I already proved...
arrrrrrghhhhhh

 

[benorin]

Here's my whack at it...

Hi,
Here's the question:
Show that if {x_n} is a cauchy sequence of points in the metric space M, and if {x_n} has a subsequence which converges to x \in M, Prove that x_n itself is convergent to x.
Now, I have proved this as follows..I didn't put in all of the details...
Let x_{n_{k}} be the subsequence which converges to x.
Choose n\in\mathbb{N} such that \forall k \geq N the distance from x_{n_{k}} to x \leq\frac{\epsilon}{2} and similarly for x_n,x_m then you wind up with \frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon so you're done.
CC

Here's my whack at it...

Let \left\{ x_{n_{k}}\right\} \rightarrow x be the convergent subsequence of the Cauchy sequence \left\{ x_{n}\right\} .

Choose an integer N such that \forall n,m \geq N we have d\left( x_{n},x_{m}\right) \leq\frac{\epsilon}{2}.

Fix k\in\mathbb{N} such that x_{n_k}\geq N and large enough that d\left( x_{n_{k}},x\right) \leq\frac{\epsilon}{2},

then set m = n_k \geq N so that \forall n\geq N

d\left( x_{n},x\right) \leq d\left( x_{n},x_{m}\right) + d\left( x_{n_{k}},x\right) \leq \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon

and hence \left\{ x_{n}\right\} \rightarrow x

 

[happyg1]

yes yes yes
that's exactly what I did...I need to try to understand why the contradiction method doesn't work...If the sebsequence converges to x then why won't the sequence?

 

[matt grime]

Look, here's what you're doing:

x_n is cauchy.

y_n is a subsequence that converges to y

This implies x_n converges to y.

That's fine.

What you can't do is ***suppose that x_n converges to something** and show x=y. Because we do not know x_n converges a priori. It does, as your first correct proof shows, and moreover constructively we show it converges to the right thing, but we can't assume that it converges since that is not part of the hypothesis.

After all, if x_n is convergent sequence, and any subsequence converges to x then x_n does, that's fine, no need to invoke cauchyness. But we do not know x_n converges which you incorrectly suppose when trying to prove it by contradiction.As a proof of why your misproof is a misproof, consider the sequence

0,1,0,1,0,1,0,1,...

the eve terms converge to 0, and IF the sequence converged as a whole it converges to zero therefore, but clearly it doesn't converge at all. See, you need to invoke the cauchyness of the initial sequence.

 

[matt grime]

ok,
so I need to think of a cauchy sequence whose limit lies outside fo the origional space that has a subsequence whose limit lies inside the space to show that that this won't work...

why try to do that since you've just proved that you can't?

 

[HallsofIvy]

The fact that, if a Cauchy Sequence has a convergent subsequence, the whole series converges is true in any metric space.

Let {a_n} be a Cauchy Sequence and let S be an infinite set of natural numbers such that the subset {a_n} with n in S converges to a.

Then, given \epsilon&gt; 0, there exist N₁ such that if n is in S and n> N₁, |a_n- a|&lt;\frac{\epsilon}{2}.

Since {a_n} is Cauchy, there exist N<sub>2 such that if m and n are both larger than N2 then |a_n- a_m|&lt; \frac{\epsilon}{2}.

Let n be a positive integer larger than both N1 and N2 and contained in S and, for any m> N2, look at
|a_m- a|\leq|a_m- a_n|+ |a_n- a|

You can use that "lemma" to show that if "monotone convergence" is true, then the Cauchy Criterion is true.</sub>

 

[happyg1]

Hi,
Thanks Matt for the explicit explanation. I understand this now. I hate going around and round in circles like that. That lemma is neat, too..sheds some more light on the ideas of metric spaces and cauchyness.
The fog has lifted.
Ya'll are awesome
CC

 

[matt grime]

I thought of a better explanation.

Your proof by contradiction works, in as much as it negates an assumption, it's just that your assumption was:

x_n converges AND its limit is not the limit of the subsequence.

so, you do get a contradiction and hence that is false.

 

[benorin]

I just got this problem for HW (out of Papa Rudin, ch. 3, #22):

Suppose that X is a metric space in which every Cauchy sequence has a convergent subsequence. Prove that X is complete.

Yep, thanks.