0

I want to check the arguments of the proof that every cauchy sequence with convergent subsequence converges more formally. Note that I know the proof and the proof is just chosen as an example; I want to know if my deductions are correct, which is what this question is about. My approach was as follows:

Since this is a $\forall$ statement, one starts by taking an arbitrary cauchy sequence $(x_n)$ that has a converging subsequence $(x_{n_k})$. We can now use that the sequence is Cauchy which gives $$\exists N \in \mathbb{N}(\forall n,m > N(d(x_n,x_m)<\frac{\epsilon}{2})).$$ In this context we can restate that we have a converging subsequence $(n_k)$ meaning $$\exists K>0 (\forall y (\exists k(y=n_k \wedge y>K)\implies d(x_y,x) < \frac{\epsilon}{2})).$$ Furthermore we know that there exists a natural number $a$ such that $$a=\max\{N,K\}.$$ Thus we know $$\forall m,n_k>a \ (d(x_{n_k},x_m) < \frac{\epsilon}{2} \wedge d(x_{n_k},x) < \frac{\epsilon}{2})$$ which implies $$\forall m,n_k>a \ (d(x_{n_k},x_m) + d(x_{n_k},x) < \epsilon)$$ and by definition of a distance function we can conclude $$\forall m,n_k>a \ (d(x_m,x) < \epsilon).$$ Now, $n_k$ is not used here anymore, so is this equivalent to $$\forall m>a(d(x_m,x) < \epsilon),$$ which would prove the statement or did I do something wrong?

Basically what happens is that in order to prove the statement I introduce an element $x_{n_k}$ and I wondered why one can formally do this and how this impacts the proof.

Edit for clarification: What I want to know is why one can use an independent element in proofs formally. What I mean by independent element is that here one wants to prove $\forall (x_n) (P(x_n))$ and uses an element $x_{n_k}$ to do this that does not appear in the final statement. Is this because I can always introduce elements in my proof (is this an inference rule?) and because the statements $\forall x(\forall y P(x))$ and $\forall x(P(x))$ are equivalent?

user1578232
  • 429
  • I am worried about your actual proof. You say converging subsequence $(n_k)$ - is this a typo for $(x_{n_k})$? – ancient mathematician Mar 26 '22 at 17:00
  • (ctd) then in next line what you write may or may not be true but it's not the straightforward definition of " $(x_{n_k})_{k=0}^\infty$ is convergent" so I think you have missing steps. – ancient mathematician Mar 26 '22 at 17:02
  • But I think your logic query at the very end is the point. If $y$ does not occur in $P(x)$ then $\forall y\forall x P(x)$ and $\forall x P(x)$ are equivalent. – ancient mathematician Mar 26 '22 at 17:03
  • First comment reqwritten. I am worried by what you mean by $\forall (x_n)$. You are not quantifying over sequences are you - think that's taking you outside the FOL you are using in the text of your proof. I think you ought to be proving the Thm: Let $(x_n){n=0}^\infty$ be a Cauchy sequence with a convergent subsequence $(x{n_k}){k=0}^\infty$. Then $(x_n){n=0}^\infty$ is convergent. (That is, there is no quantification in the Thm. ) – ancient mathematician Mar 26 '22 at 17:06
  • @ancientmathematician Yes it is a typo, thanks for pointing that out. As for your quantifier comment: How are the statements different? Isnt the "let" statement just a more informal version of a statement that is quantified by $\forall$ as "let" is the first step in the proof of a $\forall$ statement? Also, do you know if there is an inference rule that lets me introduce the $x_{n_k}$ in the end? – user1578232 Mar 26 '22 at 17:29
  • @user1578232 You are correct in saying that the quantification is implied. It's hard to tell if you're allowed to write $\forall x_{n_k}$ because you're abusing notation through out the proof, which is common practice (especially in analysis). Whether that's acceptable or not, depends on the audience (and not on logic, because the proof is an informal one). Personally, I don't really like what you did, but I think most of the community would accept it. – Git Gud Mar 26 '22 at 18:02
  • @GitGud I would totally appreciate another more formal way of writing the proof if you would present one. However I fear that it might take some time so I don't know how appealing that is. I wanted to let you know however, that it would help me out a lot in understanding this, especially since this notation is the only I have seen. Furthermore I now wonder, are there any restrictions which I can quantify over? I thought there are not any. – user1578232 Mar 26 '22 at 18:25
  • @GitGud Also if you know anything about the problems I mentioned in my question I would like to encourage you to write an answer! – user1578232 Mar 26 '22 at 18:26
  • As to "implied quantification": I think there's a technical difference between proving for a constant $a$ the statement $P(a)$ and proving $\forall x P(x)$. If we were arguing in FOL then we'd have no problem. But here your quantification is over sequences, and these are functions, not variables: so this is not FOL. So what you are asking for (I suggest) is a more careful informal proof, not a formal proof. I think the answer to this may be helpful: https://math.stackexchange.com/questions/2940557/getting-rid-of-quantifiers-over-functions – ancient mathematician Mar 27 '22 at 06:37

0 Answers0