Equivalence of quantified statements

  • I
  • Thread starter Mr Davis 97
  • Start date
  • Tags
    Equivalence
In summary: Now that you have specified the quantifier for ##x## and ##y## and using the same interpretation of ##x=y##, you can see that statement 1) is not true in that interpretation, since the left hand side of the implication ##(\forall \epsilon ( \epsilon > 0 \implies |x-y| < \epsilon ))## is False, that makes the implication True, which makes the whole statement True.The statement with the existential quantifier, however, is true, because the left hand side of the implication in that statement is True. That makes the implication True, which makes the whole statement True.I'm not sure why you think your statement 2) is not logically equivalent to the second statement
  • #1
Mr Davis 97
1,462
44
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...
 
Physics news on Phys.org
  • #2
They are different! Where did you get the idea they might be equivalent? I suspect the conversion is incorrect, since the result is wrong.
 
  • #3
mathman said:
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.
 
  • #4
Mr Davis 97 said:
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).
 
  • Like
Likes jim mcnamara
  • #5
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.
 
  • #6
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.
 
  • Like
Likes K Murty
  • #7
Stephen Tashi said:
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.
Stephen Tashi said:
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##.
 
  • #8
WWGD said:
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.
 
  • #9
Erland said:
##\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) )##" ?
 
  • #10
Erland said:
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?
 
  • #11
Stephen Tashi said:
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.

Stephen Tashi said:
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)##.

Stephen Tashi said:
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.

Stephen Tashi said:
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)##.
 
  • #12
WWGD said:
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.
 
  • #13
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 ε.
 
  • #14
Stephen Tashi said:
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.
 
  • #15
WWGD said:
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.
 
  • #16
sysprog said:
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.
 
  • #18
Stephen Tashi said:
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))##"

Erland said:
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)##
 
  • #19
Stephen Tashi said:
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.
 

1. What is the definition of "equivalence of quantified statements"?

The equivalence of quantified statements refers to two statements that have the same meaning or truth value when the quantifiers (such as "for all" or "there exists") are exchanged or negated.

2. How do you prove the equivalence of quantified statements?

To prove the equivalence of quantified statements, you must show that both statements have the same truth value for all possible values of the variables involved. This can be done through logical equivalences, using truth tables, or by using direct or indirect proofs.

3. What is the difference between logically equivalent and equivalent quantified statements?

Logically equivalent statements have the same truth value for all possible interpretations, while equivalent quantified statements have the same meaning or truth value only when the quantifiers are exchanged or negated. Two statements can be logically equivalent but not equivalent quantified, and vice versa.

4. Can quantified statements be equivalent if they have different quantifiers?

Yes, quantified statements can be equivalent even if they have different quantifiers, as long as the quantifiers can be exchanged or negated to result in the same meaning or truth value. For example, "for all x, P(x)" is equivalent to "there exists x such that P(x)".

5. What are some common mistakes to avoid when proving the equivalence of quantified statements?

Some common mistakes to avoid when proving the equivalence of quantified statements include assuming that the statements are logically equivalent when they are not, using incorrect logical equivalences, and not considering all possible values of the variables involved. It is important to carefully analyze the statements and use valid logical reasoning in the proof.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
332
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
912
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
957
  • Calculus and Beyond Homework Help
Replies
9
Views
462
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
855
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
5K
  • Calculus and Beyond Homework Help
Replies
5
Views
809
  • Precalculus Mathematics Homework Help
Replies
11
Views
317
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Back
Top