Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I mostly study PDE, harmonic analysis, image processing, and so on, but for whatever reason I decided to be a TA for an undergraduate "introduction to proofs" course this semester. I suppose I wanted a challenge. The experience has been a rewarding one so far, but I've come across a couple things that I've found difficult to explain in a clear and concise manner. For example, consider the standard definition of uniform continuity:

"For all $\epsilon>0$ there is a $\delta>0$ such that whenever $x,y\in S$ satisfy $\vert x-y\vert<\delta$, we have $\vert f(x)-f(y)\vert<\epsilon$"

Students are asked to "convert this to logical symbols", and I have seen the following two approaches:

"$\forall \epsilon>0$ $\exists\delta>0$ s.t. $(x,y\in S \wedge \vert x-y\vert<\delta)\Rightarrow\vert f(x)-f(y)\vert<\epsilon$"

and what I consider the more standard version:

"$\forall\epsilon>0$ $\exists\delta>0$ s.t. $\forall x,y\in S$ s.t. $\vert x-y\vert<\delta$, $\vert f(x)-f(y)\vert<\epsilon$."

So my question is: Are they 100% logically equivalent...? In particular, it seems that "for all A such that B, C" is equivalent to "A and B imply C". Is there a way to "prove" this equivalence, or is it just a "functional" equivalence (i.e. they tell you to do the same thing)? I've been struggling to explain the two approaches/advocate for one over the other, so bonus points if you have simple examples for the two.

Thanks ahead!

share|improve this question
3  
The first and second ones aren't statements, they have no truth value since $x$ and $y$ aren't quantified. Analysts like to write such disgusting things, I have no idea why. –  Git Gud Jan 31 '13 at 21:31
    
@GitGud pardon my thickness, but I'm not sure I follow. Why are they not statements? It seems that given a set $S$ and a function $f$ on $S$, one could determine if it is U.C. using either of the two statements. Am I wrong? –  icurays1 Jan 31 '13 at 21:44
2  
Formula cannot be a statement if there are meaningful free variables inside, e.g. in $\forall x. P(x, y)$ there is unquantified variable $y$. However, $\exists y.\ \forall x.\ P(x, y)$ would work. Quantifiers inside "such that" are of limited scope, so that $\forall x. (\forall y. Q(y)) \implies P(x,y)$ is not a valid statement (the $y$ inside $P(x,y)$ is still unquantified), on the other hand, $\forall x.\ \forall y.\ Q(y) \implies P(x,y)$ is ok. Therefore "for all $A$ such that $B$, $C$" is not equivalent to "$A$ and $B$ imply $C$" because in the first $A$ is quantified and in other is free. –  dtldarek Jan 31 '13 at 21:54
    
@icurays1 Not sure if you already heard about it (I guess it is a standard advice for people that start to focus on proofs), but there is a book that covers all those things pretty well IMO, namely "How to Prove it: a structured approach". It could help and it could be useful for your students as well (personally, I loved it). –  Kolmin May 26 '13 at 19:24
    
@Kolmin I've recommended that book a few times ^_^. Alas, I don't think this subtle issue is treated there. –  Git Gud May 26 '13 at 19:26

1 Answer 1

up vote 10 down vote accepted

Consider the "statement" $(\exists k\in \mathbb{N})(a=2k)$. It doesn't make sense because $a$ isn't quantified (there's no $\forall$ or $\exists$ associated with it). You can't tell wether that "statement" is true or false because it isn't a statement. The following formula is a statement: $(\forall a\in \mathbb{R})(\exists k\in \mathbb{N})(a=2k)$, you can tell wether it's true or false.

Regarding your question, $x$ and $y$ aren't quantified. I could very well assume the $x,y$ in $$(\forall \epsilon>0) (\exists\delta>0) \bigl((x,y\in S \wedge \vert x-y\vert<\delta)\Rightarrow\vert f(x)-f(y)\vert<\epsilon\bigr) \tag 1$$

are existencial, meaning I could interpret the above pseudo-statement as meaning $$(\forall \epsilon>0) (\exists\delta>0) (\exists x,y)\bigl((x,y\in S \wedge \vert x-y\vert<\delta)\Rightarrow\vert f(x)-f(y)\vert<\epsilon\bigr) \tag 2$$

which isn't what you want at all.

Please note that what I said above was merely an intuitive approach to the issue at hand. I simply cannot decide that $(1)$ means $(2)$, I cannot decide it means anything because it isn't a statement.

The question rises: what is a statement? The answer to that question isn't appropiate to post here, I believe. However @dtldarek has already provided some insight into that.

I know that in the literature you'll find such "definitions" of continuity. Well, they're badly written. I know it's hard to believe, but that's the case.

If any of the variables in a formula isn't quantified, then that formula isn't a statement and has no meaning.

Edit: The following problem is analogous to your question, the difference is the formulae at hand are statements. Hopefully this will be helpful to you:

$$(\forall \epsilon>0) (\exists\delta>0) (\forall x,y)\bigl((x,y\in S \wedge \vert x-y\vert<\delta)\Rightarrow\vert f(x)-f(y)\vert<\epsilon\bigr) \tag i$$

$$(\forall \epsilon>0) (\exists\delta>0) (\forall x,y\in S)\bigl((\vert x-y\vert<\delta)\Rightarrow\vert f(x)-f(y)\vert<\epsilon\bigr) \tag {ii})$$

Are $(i)$ and $(ii)$ equivalent? In fact they are and that equivalence is "very strong". It's more than the fact that you can conclude one from the other. The statement $(ii)$ is just short hand notation for the formally correct $(i)$.

(In the above paragraph I chose to ignore the quantification regarding $\delta$ and $\epsilon$ for the sake of simplicity. The quantification regarding $\delta$ and $\epsilon$ has to be dealt with in a similar manner).

Allow me illustrate this with a simpler version of this problem.

The statement $(\forall x\in \mathbb{R})(x\ge 0)$, (which is obviously false, but that's of no interest to us) is just short for the formally correct $(\forall x)(x\in \mathbb{R} \Longrightarrow x\ge 0)$. The existential quantifier $\exists$ is a bit different. Consider the statement $(\exists n\in \mathbb{N})(n=1337)$. This of course, is just short for $(\exists n)(n\in \mathbb{N} \wedge n=1337)$ and not short for the silly $(\exists n)(n\in \mathbb{N} \Longrightarrow n=1337)$. Well, it's not silly, just not what one would expect $(\exists n\in \mathbb{N})(n=1337)$ to mean.

share|improve this answer
    
Ah, the edit makes it crystal clear, I think I completely understand the difference now. I have to admit I've really never thought about this, who knows how many times I've made this mistake myself! (I'd like to say I'm pretty good about quantifying variables, simply by habits picked up through imitation, but who knows...) Thanks! –  icurays1 Jan 31 '13 at 22:19
1  
@icurays1 Unfortunately analysts aren't rigorous in the way they write and that leads people who don't have a strong knowledge of elementary logic to ignore such things because they don't have the tools to question what it is often written in the literature. –  Git Gud Jan 31 '13 at 22:23
    
@icurays1 I added some stuff to edit regarding the quantification on $\delta$ and $\epsilon$ which was ignored. Also I treated the $\exists$ case. –  Git Gud Jan 31 '13 at 23:36
    
Excellent, thanks again! –  icurays1 Feb 1 '13 at 18:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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