I Equivalence of quantified statements

[Mr Davis 97]

Take the following statement as given: $\forall \epsilon > 0 ~ (|x-y| < \epsilon) \implies x = y$. To convert this prenex normal form, we get $\exists \epsilon > 0 ~ (|x-y| < \epsilon \implies x = y)$. How are these two statements equivalent? It seems as though they are saying different things...

 

[mathman]

They are different! Where did you get the idea they might be equivalent? I suspect the conversion is incorrect, since the result is wrong.

 

[Mr Davis 97]

They are different! Where did you get the idea they might be equivalent? I suspect the conversion is incorrect, since the result is wrong.

https://en.wikipedia.org/wiki/Prenex_normal_form

Doesn't this article give the conversion formula that I just used? In the implication section.

 

[Stephen Tashi]

Take the following statement as given: $\forall \epsilon > 0 ~ (|x-y| < \epsilon) \implies x = y$. To convert this prenex normal form, we get $\exists \epsilon > 0 ~ (|x-y| < \epsilon \implies x = y)$. How are these two statements equivalent?

You haven't specified a quantifier for $x$ or $y$. Treating them as constants, can you find specific values of $x$ and $y$ that make one statement true and the other statement false?

By the notation conventions of the article, instead of "$\forall \epsilon > 0$" , we are only allowed to use "$\forall \epsilon$". So let's conform to that notation.

Statement 1): $(\forall \epsilon (\epsilon > 0 \implies (|x-y| < \epsilon) ) \implies x = y$
Statement 2): $\exists \epsilon ( (\epsilon > 0 \implies |x -y| <\epsilon) \implies x = y)$

Suppose $x = y = 3$
Both statements are true due to the truth of $x = y$.
To satisfy the $\exists \epsilon$ in statement 2), we can find a specific value of $\epsilon$ that makes statement 2) True. (For example $\epsilon = -1$)

Suppose $x = 1, y = 29$
In statement 1), the if-part: $\forall \epsilon( \epsilon > 0 \implies |x -y| < \epsilon$ is False.
That makes implication have form: False \implies \False, so statement 1) is True.

In statement 2), consider the case \epsilon = 3.
For that value of $\epsilon$ the statement ( $\epsilon > 0 \implies |x - y| < \epsilon$ ) is of the form: True implies False, so it is False.
So the quantified expression as a whole takes on the form: False implies False, making it True.
Since we have demonstrated the existence of an $\epsilon$ that make the quantified expression True, statement 2 is True.

Note that statement 2) is different than:
Statement 3: $\exists \epsilon ( (\epsilon > 0 \implies |x -y| <\epsilon)) \implies x = y$

The feeling that statement 2) cannot be equivalent to statement 1) is caused by interpreting statement 2) to be statement 3).

SInce you used the notation "$\exists \epsilon > 0$ in writing $\exists \epsilon > 0 ~ (|x-y| < \epsilon \implies x = y)$ perhaps your interpretation of that sentence is statement 3) instead of statement 2).

 

[WWGD]

An interpretation of the two statements, within the Reals:
1) Two (Standard) Real numbers cannot be indefinitely close to each other unless they are equal
2) All Real numbers in an interval must be 0 if the interval's radius is small -enough.
First is true, e.g., by Archimedean property, second is not: assume one element, the center of the ball, is 0, since all points are 0. Then $\epsilon/2+0=\epsilon/2 \neq 0$, since $\epsilon$ was assumed to be non-zero.
EDIT: Just in case, this is not a proof of the inequality of the statements, just to motivate the discussion. For a proof, you need to show that each implies the other -- sorry, my logic Latex is not very good.

 

[sysprog]

Equivalency between existential and universal quantificational statements requires distribution of negation, as in:
$\exists x ( P x) \iff \neg \forall x (\neg P x)$
there exists an x such that x is P, if and only if it is not the case that for all x, x is not P
and
$\forall x (P x ) \iff \neg \exists x (\neg P x)$
for all x, x is P, if and only if there does not exist an x such that x is not P.

 

[Erland]

You haven't specified a quantifier for $x$ or $y$. Treating them as constants, can you find specific values of $x$ and $y$ that make one statement true and the other statement false?

By the notation conventions of the article, instead of "$\forall \epsilon > 0$" , we are only allowed to use "$\forall \epsilon$". So let's conform to that notation.

Statement 1): $(\forall \epsilon (\epsilon > 0 \implies (|x-y| < \epsilon) ) \implies x = y$
Statement 2): $\exists \epsilon ( (\epsilon > 0 \implies |x -y| <\epsilon) \implies x = y)$

Your Statement 2 is not logically equivalent to the the OP second statement

$\exists \epsilon > 0 \, (|x-y| < \epsilon \implies x = y)$.

This statement should instead be converted to

Statement (*): $\exists \epsilon\, (\epsilon > 0 \land (|x -y| <\epsilon \implies x = y) )$.

If we choose an interpretation for which $\exists \epsilon(\epsilon >0)$ is false, for example, if the underlying domain is not the set of real numbers, but the set of nonpositive real numbers (we must then also change the interpretation of the absolute value |x| to something whose values are nonpositive, but it is unimportant for the argument how), or if we reinterprete $a>b$ to mean something contradictory, such as $a=b\land a\neq b$, and choose $x=y$, then your Statement 2 is true (since $x=y$ is true) and my Statement (*) is false (since $\epsilon >0$ is false for all $\epsilon$).

But in the intended interpretation, with the domain being the real numbers and "$>$" meaning "greater than", your Statement 2 and my Statement (*), and hence the second statement in the OP, are indeed equivalent for all $x$ and $y$. This is because $\exists \epsilon(\epsilon >0)$ is true in this interpretation, and this equivalence can be seen by using truth tables.

Your Statements 1 and 2 are not logically equivalent (although they equivalent in the intented interpretation), but your Statement 1 and my Statement (*) are logically eqivalent, as are the two statements in the OP.

Note that statement 2) is different than:
Statement 3: $\exists \epsilon ( (\epsilon > 0 \implies |x -y| <\epsilon)) \implies x = y$

The feeling that statement 2) cannot be equivalent to statement 1) is caused by interpreting statement 2) to be statement 3).

I rather think that the error lies in interpreting $\exists \epsilon > 0 \, (|x-y| < \epsilon \implies x = y)$ as $(\exists \epsilon > 0 \quad |x-y| < \epsilon) \implies x = y$, that is $\exists \epsilon(\epsilon > 0 \land|x-y| < \epsilon) \implies x = y$.

 

[Erland]

An interpretation of the two statements, within the Reals:
1) Two (Standard) Real numbers cannot be indefinitely close to each other unless they are equal
2) All Real numbers in an interval must be 0 if the interval's radius is small -enough.

Your interpretation 2) is wrong. Se my previous post #7. You seem to have made exactly the error I mentioned at the end of this post.

 

[Stephen Tashi]

$\exists \epsilon > 0 \, (|x-y| < \epsilon \implies x = y)$.

This statement should instead be converted to

Statement (*): $\exists \epsilon\, (\epsilon > 0 \land (|x -y| <\epsilon \implies x = y) )$.

If we choose an interpretation for which $\exists \epsilon(\epsilon >0)$ is false, for example, if the underlying domain is not the set of real numbers, but the set of nonpositive real numbers (we must then also change the interpretation of the absolute value |x| to something whose values are nonpositive, but it is unimportant for the argument how), or if we reinterprete $a>b$ to mean something contradictory,

If we allow ourselves the liberty of changing the meaning of standard mathematical notation (such as ">" or "=") or changing the context of the problem (which I take , in the OP , to be the real numbers) then all sorts of things may happen! However, I see your point.

Interpreting your objection in generality, I put it this way:

Let P(x) and Q(x) be propositional functions. (e.g. P(x) might denote "x > 0") . You advocate that the notation "$(\exists P(x)) (Q(x))$" shall be defined to mean "$\exists x ( P(x) \land (P(x) \implies Q(x))$"

My definition of the same notation is "$\exists x ( P(x) \implies Q(x))$".

So the disagreement is about a convention of notation. I don't know whether there is standard definition for "$(\exists P(x))(...)$" in first order logic. Is that notation used in rigorous treatments?

As a side issue, how shall we define the notation "$(\forall P(x))(Q(x))$" ?
Shall it mean ""$\forall x ( P(x) \land Q(x))$""?
Or shall it mean ""$\forall x( P(x) \implies Q(x))$""?
Or "$\forall x( P(x) \land (P(x) \implies Q(x) )$" ?

 

[WWGD]

Your interpretation 2) is wrong. Se my previous post #7. You seem to have made exactly the error I mentioned at the end of this post.

Where is the error in the interpretation?

 

[Erland]

If we allow ourselves the liberty of changing the meaning of standard mathematical notation (such as ">" or "=") or changing the context of the problem (which I take , in the OP , to be the real numbers) then all sorts of things may happen! However, I see your point.

Note that I wrote "logically equivalent". Two logical formulas are logically equivalent if they are equivalent no matter how we interprete the predicate and function symbols.

Interpreting your objection in generality, I put it this way:

Let P(x) and Q(x) be propositional functions. (e.g. P(x) might denote "x > 0") . You advocate that the notation "$(\exists P(x)) (Q(x))$" shall be defined to mean "$\exists x ( P(x) \land (P(x) \implies Q(x))$"

No, it should be interpreted as $\exists x (P(x)\land Q(x))$. But I have only seen this notation in some special cases, such as e.g. $\exists x >0 \,Q(x)$ and $\exists x\in M\, Q(x)$. These are considered as abbreviations of $\exists x (x >0 \land Q(x))$ and $\exists x( x \in M \land Q(x))$, respectively. And this is the only way to interprete such statements. Consider for example the statement $\exists x>0 \,x^2$, which we interprete as "The number 2 has a positive square root". This is true if and only if there is a number which is both positive and has the square 2", thus it most mean the same as $\exists x (x >0 \land x^2=2)$.

My definition of the same notation is "$\exists x ( P(x) \implies Q(x))$".

So let us interprete $P(x)$ as $x>0$ and $Q(x)$ as $x^2=2$. Thus we obtain $\exists x (x>0\implies x^2=2)$, which is true not only for real numbers but also , e.g. for integers as the basic domain, since $x>0\implies x^2=2$ is true for all $x\le 0$, but certainly, the number 2 has no integer square root.

As a side issue, how shall we define the notation "$(\forall P(x))(Q(x))$" ?
Shall it mean ""$\forall x ( P(x) \land Q(x))$""?
Or shall it mean ""$\forall x( P(x) \implies Q(x))$""?
Or "$\forall x( P(x) \land (P(x) \implies Q(x) )$" ?

The second alternative is the correct one, because only then is (with your notation) $(\forall P(x))\neg Q(x)$ logically eqivalent to $\neg(\exists P(x))Q(x)$.

 

[Erland]

Where is the error in the interpretation?

Well, maybe I misunderstood you. But I don't understand how you can interprete $\exists \epsilon>0\, (|x−y|<\epsilon\implies x=y)$ as "All real numbers in an interval must be 0 if the interval radius is small - enough." Can you elaborate? (At least I don't think you mean that all numbers in the interval must be 0, but that the interval must be singleton point, or...? But this seems wrong too.) Note that the implication is inside the parenthesis in the formula.

 

[sysprog]

The expression ∃ϵ>0(|x−y|<ϵ⟹x=y) appears to be intended as an assertion of the existence of the positive infinitesimal, i.e. the least or smallest positive number.

As Stephen Tashi pointed out, x and y are not explicitly quantified. It might be more clear if they were, as in: ∃ϵ>0(∀xy(|x−y|<ϵ⟹x=y)).

That ϵ is a number is implied by the use of the > operator. parsing that in English would yield: there exists a number ϵ such that ϵ is greater than 0 and for all x and y, if the absolute value of x-y is less than ϵ, then x is equal to y.

That makes ϵ the smallest number that is greater than zero, and the existential quantifier asserts the existence of such a number.

A negated existential quantifier could be used instead of the universal, as in: ∃ϵ(ε>0Λ¬∃α(α>0Λα<ε)), i.e. there exists a positive number ε such that there does not exist a positive number α that is less than ε.

 

[WWGD]

If we allow ourselves the liberty of changing the meaning of standard mathematical notation (such as ">" or "=") or changing the context of the problem (which I take , in the OP , to be the real numbers) then all sorts of things may happen! However, I see your point.
#".

So the disagreement is about a convention of notation. I don't know whether there is standard definition for "$(\exists P(x))(...)$" in first order logic. Is that notation used in rigorous treatments?As Stephen Tashi pointed out, x and y are not explicitly quantified. It might be more clear if they were, as in: ∃ϵ>0(∀xy(|x−y|<ϵ⟹x=y)).

That ϵ is a number is implied by the use of the > operator. parsing that in English would yield: there exists a number ϵ such that ϵ is greater than 0 and for all x and y, if the absolute value of x-y is less than ϵ, then x is equal to y.

That makes ϵ the smallest number that is greater than zero, and the existential quantifier asserts the existence of such a number.

A negated existential quantifier could be used instead of the universal, as in: ∃ϵ(ε>0Λ¬∃α(α>0Λα<ε)), i.e. there exists a positive number ε such that there does not exist a positive number α that is less than ε.

But there is no such number in the Standard Reals, since they are densely ordered.

 

[sysprog]

But there is no such number in the Standard Reals, since they are densely ordered.

In the parlance of hyperreals under ZFC that includes the term "standard reals", the infinitesimal is a non-standard real.

 

[WWGD]

In the parlance of hyperreals under ZFC that includes the term "standard reals", the infinitesimal is a non-standard real.

I guess that means it violates the Archimedean Principle. I tried for a while to see if one could meaningfully assign non-standard hyperreals as probability values so one could maybe have uncountable sums that converge. But I became bogged down trying to figure out notions of convergence , which requires a notion of topology. But the Hyperreals are not metrizable ( at least in the standard sense , e.g., if e is an infinitesimal then d(e,0)=e is non-standard Real -valued) so we don't have a natural metric topology to work with. I ended up stranded on that one.

 

[sysprog]

This Wikipedia article includes some references that might be helpful regarding that investigative effort: https://en.wikipedia.org/wiki/Infinitesimal

 

[Stephen Tashi]

You advocate that the notation "$(\exists P(x)) (Q(x))$" shall be defined to mean "$\exists x ( P(x) \land (P(x) \implies Q(x))$"

No, it should be interpreted as $\exists x (P(x)\land Q(x))$.

You mean "Yes" - since $P(x) \land (P(x) \implies Q(x))$ is equivalent to $P(x) \land Q(x)$

 

[Erland]

You mean "Yes" - since $P(x) \land (P(x) \implies Q(x))$ is equivalent to $P(x) \land Q(x)$

OK, but there are infinitely many formulas which are equivalent to $\exists x(P(x) \land Q(x))$, but it is only this one which naturally comes to mind in this context, for me and, I think, most mathematicians.