- #1

- 1,456

- 44

- I
- Thread starter Mr Davis 97
- Start date

- #1

- 1,456

- 44

- #2

mathman

Science Advisor

- 7,889

- 460

- #3

- 1,456

- 44

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

Stephen Tashi

Science Advisor

- 7,543

- 1,455

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?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?

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 statments 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).

- #5

WWGD

Science Advisor

Gold Member

- 5,419

- 3,668

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

- 1,892

- 1,141

## \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.

- #7

Erland

Science Advisor

- 738

- 136

Your Statement 2 is not logically equivalent to the the OP second statementYou 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) ##

##\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.

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##.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).

- #8

Erland

Science Advisor

- 738

- 136

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.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.

- #9

Stephen Tashi

Science Advisor

- 7,543

- 1,455

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.##\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,

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

WWGD

Science Advisor

Gold Member

- 5,419

- 3,668

Where is the error in the interpretation?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.

- #11

Erland

Science Advisor

- 738

- 136

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.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.

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)##.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))##"

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.My definition of the same notation is "##\exists x ( 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)##.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) )##" ?

- #12

Erland

Science Advisor

- 738

- 136

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.Where is the error in the interpretation?

- #13

- 1,892

- 1,141

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

WWGD

Science Advisor

Gold Member

- 5,419

- 3,668

But there is no such number in the Standard Reals, since they are densely ordered.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 ε.

- #15

- 1,892

- 1,141

In the parlance of hyperreals under ZFC that includes the term "standard reals", the infinitesimal is a non-standard real.But there is no such number in the Standard Reals, since they are densely ordered.

- #16

WWGD

Science Advisor

Gold Member

- 5,419

- 3,668

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.In the parlance of hyperreals under ZFC that includes the term "standard reals", the infinitesimal is a non-standard real.

- #17

- 1,892

- 1,141

- #18

Stephen Tashi

Science Advisor

- 7,543

- 1,455

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))##"

You mean "Yes" - since ##P(x) \land (P(x) \implies Q(x))## is equivalent to ##P(x) \land Q(x)##No, it should be interpreted as ##\exists x (P(x)\land Q(x))##.

- #19

Erland

Science Advisor

- 738

- 136

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.You mean "Yes" - since ##P(x) \land (P(x) \implies Q(x))## is equivalent to ##P(x) \land Q(x)##

- Last Post

- Replies
- 9

- Views
- 1K

- Replies
- 6

- Views
- 2K

- Replies
- 6

- Views
- 3K

- Replies
- 2

- Views
- 735

- Last Post

- Replies
- 10

- Views
- 218

- Replies
- 6

- Views
- 2K

- Replies
- 6

- Views
- 14K

- Replies
- 3

- Views
- 3K

- Last Post

- Replies
- 4

- Views
- 1K

- Last Post

- Replies
- 1

- Views
- 1K