[Logic] Order of quantifiers and brackets

  • I
  • Thread starter Leo Liu
  • Start date
  • Tags
    Logic
In summary: No, not at all. In the first case you require some number a that is equal to all numbers. There is no such number.In the second case you are looking for pairs of numbers a,b, where a = b. There are lots of those.Let's look at both of the examples one by one:(1) ## \forall a \in \mathbb{N} \, [(\forall b \in \mathbb{N} \,\, a=b) \rightarrow (a=5)]## --- trueIntuitively we can think of the above as saying that all of the following sub-statements are true:##(\forall b \in \mathbb{N} \,\,
  • #1
Leo Liu
353
156
I asked a question in yesterday's lecture about whether we can change the order of quantifiers and move it around in statements involving and, or, & iif. My instructor said no and after the lecture, my fellow student made this post below, intending to demonstrate that the instructor was right.

--------------------------------------------------------------------------------------------------------
1632385198337.png

--------------------------------------------------------------------------------------------------------

However, I believe his argument for a) is moot because if we let ##a=b=9## for a) like he did in b), the implication is false, as ##\neg T \lor F\equiv F##. Am I thinking wrong?
 
Physics news on Phys.org
  • #2
Leo Liu said:
I asked a question in yesterday's lecture about whether we can change the order of quantifiers and move it around in statements involving and, or, & iif. My instructor said no and after the lecture, my fellow student made this post below, intending to demonstrate that the instructor was right.

--------------------------------------------------------------------------------------------------------
View attachment 289561
--------------------------------------------------------------------------------------------------------

However, I believe his argument for a) is moot because if we let ##a=b=9## for a) like he did in b), the implication is false, as ##\neg T \lor F\equiv F##. Am I thinking wrong?
Yes, because in a) you need to check that every ##b## is equal to ##a##.

Emre B has nailed it. Good example,
 
  • Skeptical
  • Like
Likes fresh_42 and Leo Liu
  • #3
PeroK said:
Yes, because in a) you need to check that every b is equal to a.
Sorry I am confused. Could you explain? If I find a contradiction the entire statement is false right?
 
  • #4
Leo Liu said:
Sorry I am confused. Could you explain? If I find a contradiction the entire statement is false right?
The approximate logic of a) is:

Take ##a##; if every ##b## is equal to ##a##; then ##a = 5##.

The middle "test" is false. You cannot have every number ##b## equal to a fixed ##a##. The conclusion is, therefore, vacuously true.

The logic of b) is:

Take any ##a, b##; if ##a = b##; then ##a = 5##.

The middle test is true for ##a = b = 1##, ##a = b = 2##, etc. So the conclusion that ##a = 5## does not hold.
 
  • Like
  • Love
Likes sysprog, SSequence and Leo Liu
  • #5
PeroK said:
The approximate logic of a) is:

Take ##a##; if every ##b## is equal to ##a##; then ##a = 5##.

The middle "test" is false. You cannot have every number ##b## equal to a fixed ##a##. The conclusion is, therefore, vacuously true.

The logic of b) is:

Take any ##a, b##; if ##a = b##; then ##a = 5##.

The middle test is true for ##a = b = 1##, ##a = b = 2##, etc. So the conclusion that ##a = 5## does not hold.
I think I sort of get the difference. So in the first scenario the effect of the variation of b is restricted to ##a=b##. But following the same reasoning I can conclude that the component ##a=5## is vacuously true for b). Why isn't this correct?

Thank you for the help.
 
  • #6
Leo Liu said:
I think I sort of get the difference. So in the first scenario the effect of the variation of b is restricted to ##a=b##. But following the same reasoning I can conclude that the component ##a=5## is vacuously true for b). Why isn't this correct?

Thank you for the help.
No, not at all. In the first case you require some number ##a## that is equal to all numbers. There is no such number.

In the second case you are looking for pairs of numbers ##a,b##, where ##a = b##. There are lots of those.
 
  • Like
  • Informative
Likes sysprog and Leo Liu
  • #7
Let's look at both of the examples one by one:
(1) ## \forall a \in \mathbb{N} \, [(\forall b \in \mathbb{N} \,\, a=b) \rightarrow (a=5)]## --- true

Intuitively we can think of the above as saying that all of the following sub-statements are true:
##(\forall b \in \mathbb{N} \,\, 0=b) \rightarrow (0=5)##
##(\forall b \in \mathbb{N} \,\, 1=b) \rightarrow (1=5)##
##(\forall b \in \mathbb{N} \,\, 2=b) \rightarrow (2=5)##
##(\forall b \in \mathbb{N} \,\, 3=b) \rightarrow (3=5)##
##(\forall b \in \mathbb{N} \,\, 4=b) \rightarrow (4=5)##
##(\forall b \in \mathbb{N} \,\, 5=b) \rightarrow (5=5)##
##(\forall b \in \mathbb{N} \,\, 6=b) \rightarrow (6=5)##
....

We can show that each of the above sub-statements is true. Hence the overall statement is true.

One way is to see (to see that each of the sub-statements is true) is that premise for each of the sub-statements will be false in all of the above cases.(2) ## \forall a \in \mathbb{N} \,\, \forall b \in \mathbb{N} \, [a=b \rightarrow a=5]## --- false

Intuitively we can think of the above as saying that all of the following sub-statements are true:
##\forall b \in \mathbb{N} \, [0=b \rightarrow 0=5]##
##\forall b \in \mathbb{N} \, [1=b \rightarrow 1=5]##
##\forall b \in \mathbb{N} \, [2=b \rightarrow 2=5]##
##\forall b \in \mathbb{N} \, [3=b \rightarrow 3=5]##
##\forall b \in \mathbb{N} \, [4=b \rightarrow 4=5]##
##\forall b \in \mathbb{N} \, [5=b \rightarrow 5=5]##
##\forall b \in \mathbb{N} \, [6=b \rightarrow 6=5]##
....

But we can see that that even the very first sub-statement is false:
##\forall b \in \mathbb{N} \, [0=b \rightarrow 0=5]##
If we put ##b=0## the premise becomes true but the conclusion is false (making the given sub-statement false). Hence the overall statement is false.
 
  • Like
  • Wow
Likes sysprog and Leo Liu
  • #8
SSequence said:
Let's look at both of the examples one by one:
Thank you! This explanation with a truth table like chart is very informative.
 
  • #9
Leo Liu said:
Sorry I am confused. Could you explain? If I find a contradiction the entire statement is false right?
And you are right to be confused.

It is a bad example.

It is not a good example, because the first part is equivalent to the second. He wrote ##\forall a (\forall b : a=b)## but meant ##\exists a (\forall b : a=b)## which is clear by what he wrote as justification that it is a void statement.

I'm not quite sure whether ##\exists a \exists b## commutes or not. It might depend on where and whether additional conditions are placed. But ##\forall a \forall b = \forall b \forall a##.

Distinct quantifiers do not commute!

##\forall a \exists b \, : \,P(a,b)## allows ##b## to depend on the choice of ##a##.
##\exists a \forall b \, : \,P(a,b)## guarantees the existence of a uiversal ##a## which is the same for all ##b##.
 
Last edited:
  • Love
Likes Leo Liu
  • #10
fresh_42 said:
And you are right to be confused.

It is a bad example.

It is not a good example, because the first part is equivalent to the second. He wrote ##\forall a (\forall b : a=b)## but meant ##\exists a (\forall b : a=b)## which is clear by what he wrote as justification that it is a void statement.

I'm not quite sure whether ##\exists a \exists b## commutes or not. It might depend on where and whether additional conditions are placed. But ##\forall a \forall b = \forall b \forall a##.

Distinct quantifiers do not commute!

##\forall a \exists b \, : \,P(a,b)## allows ##b## to depend on the choice of ##a##.
##\exists a \forall b \, : \,P(a,b)## guarantees the existence of a uiversal ##a## which is the same for all ##b##.
Thank you for understanding my confusion. I agree that the two distinct quantifiers do not normally commute unless in special cases.

What would you think the answer to a) is?
 
  • Like
Likes PeroK
  • #11
Leo Liu said:
What would you think the answer to a) is?
I think the only way to make sense of it is to read it as ##\forall a \forall b (a=b\Longrightarrow a=5)## which is false. The second statement is the same.

It gets difficult if we describe certain sets within a quantifier: ##\forall b : b=a##. This would simply be ##a##. I'm not completely certain about the correct syntax of first-order logic, but I think that all quantifiers have to come first, without any specification, and the statements come last.

There is one prominent example where it really matters: convergence. ##\forall \varepsilon >0 \exists N\in \mathbb{N}\, : \,\ldots## actually means ##\forall \varepsilon >0 \exists N(\varepsilon )\in \mathbb{N}\, : \,\ldots##. It is crucial that various ##\varepsilon ## may have different ##N.## This is also crucial for indirect proofs. Assume the contrary means: ##\exists c>0 \, : \, \ldots \forall N\in \mathbb{N}.##

If it was ##\exists N \forall \varepsilon ## then it doesn't look as if it makes a huge difference. But it becomes apparent if we negate it: ##\forall N \exists \varepsilon .## This is always the case since we can choose ##\varepsilon ## according to a specific ##N.## Thus all sequences except the constant ones would be divergent.
 
  • Like
Likes Leo Liu
  • #12
fresh_42 said:
but I think that all quantifiers have to come first
That's what I thought before my instructor negated my idea.
His defence was for DIC, it is okay to put the quantifiers separately, and we should do so. Case in point:
$$\forall a,b,c,\quad a|b,a|c\quad\implies\quad \forall x,y,\quad a|(bx+cy)$$
What would be your take on this?
fresh_42 said:
There is one prominent example where it really matters: convergence.
Can you elaborate more on convergence? Is it in the same spirit as def. of limit?
 
  • #13
Leo Liu said:
That's what I thought before my instructor negated my idea.
His defence was for DIC, it is okay to put the quantifiers separately, and we should do so. Case in point:
$$\forall a,b,c,\quad a|b,a|c\quad\implies\quad \forall x,y,\quad a|(bx+cy)$$
What would be your take on this?
I do not see any difference to ##(\forall a)(\forall b)(\forall c)(\forall x)(\forall y)(a|b\wedge a\,|\,c\Longrightarrow a|(bx+cy))##
Leo Liu said:
Can you elaborate more on convergence? Is it in the same spirit as def. of limit?
Yes. If ##x_n\stackrel{n\to \infty }{\longrightarrow }x## then the correct order is: ##(\forall \varepsilon >0) (\exists N(\varepsilon )\in \mathbb{N})(\forall n>N(\varepsilon ))(|x_n-x|<\varepsilon) ##.
 
  • Like
Likes Leo Liu
  • #14
I think @fresh_42 may be right. The original example is very good from a logical point of view, but the interpretation may not be valid within the strictures of formal logical notation. I.e. it should start with ##\exists##. That makes it a good example of why one cannot interchange ##\exists## and ##\forall##.
 
  • Like
Likes Leo Liu
  • #15
fresh_42 said:
I'm not quite sure whether ∃a∃b commutes or not. It might depend on where and whether additional conditions are placed. But ∀a∀b=∀b∀a.
It commutes. You can see this by converting the ##\exists##’s to ##\neg\forall\neg##’s, eliminating the double negative, swapping the ##\forall##’s, then reintroducing the double negative and converting back to ##\exists##’s.
 
  • #16
TeethWhitener said:
It commutes. You can see this by converting the ##\exists##’s to ##\neg\forall\neg##’s, eliminating the double negative, swapping the ##\forall##’s, then reintroducing the double negative and converting back to ##\exists##’s.
But what if ##b## depends on ##a##? E.g. ##\exists a \exists b \, : \,a^b<0.1##. In this case we have ##a=2## and ##b=4## but ##a=3## and ##b=3##. Doesn't ##\exists a \exists b ## allow ##\exists a \exists b(a)## whereas ##\exists b \exists a ## wouldn't allow ##\exists b(a) \exists a\,?##
 
  • #17
fresh_42 said:
But what if ##b## depends on ##a##? E.g. ##\exists a \exists b \, : \,a^b<0.1##. In this case we have ##a=2## and ##b=4## but ##a=3## and ##b=3##. Doesn't ##\exists a \exists b ## allow ##\exists a \exists b(a)## whereas ##\exists b \exists a ## wouldn't allow ##\exists b(a) \exists a\,?##
I’m afraid I don’t understand this post at all.
 
  • #18
TeethWhitener said:
I’m afraid I don’t understand this post at all.
If we have first the existence of a, and next the existence of b, then b can theoretically depend on the choice of a, while a cannot depend on the choice of b.
 
  • #19
I still don’t understand. Maybe you could explain your example more clearly. ##\exists## and ##\forall## don't commute, but ##\neg\forall\neg## is the definition of ##\exists##, so I’m not sure where my argument would fail.
 
  • #20
Sure, different qualifiers do not commute, and all quantifiers commute with each other as well. But in the definition of convergence we have ##\forall \varepsilon \exists N=N(\varepsilon )##. The existence of ##N## is dependent on the previous choice of ##\varepsilon ##, or at least the actual choice of ##N##.

The same is true for two existence qualifiers: ##\exists a \exists b=b(a)##. But if the choice of ##b## depends on the choice of ##a##, how could they commute?
 
  • #21
I’m not seeing how ##\forall \varepsilon \exists N=N(\varepsilon )## is a well-formed formula. Each of the bound variables can have a domain, but the dependence of one variable on another doesn’t enter into it until you actually get to the proposition that’s being quantified over.

Given a well-formed formula ##\varphi(x,y)##, I’m not sure why this doesn’t work:
1. ##\exists x [\exists y \varphi(x,y)]##
2. ##\neg\forall x\neg[\exists y \varphi(x,y)]## from the definition of ##\exists##.
3. ##\neg\forall x\neg[\neg\forall y \neg\varphi(x,y)]## from the definition of ##\exists## a second time.
4. ##\neg\forall x[\forall y \neg\varphi(x,y)]## from double negation elimination.
5. ##\neg\forall y[\forall x \neg\varphi(x,y)]## because you’re ok with ##\forall## commuting.
6. ##\neg\forall y\neg[\neg\forall x \neg\varphi(x,y)]## from double negation introduction.
7. ##\exists y [\exists x \varphi(x,y)]## from the definition of ##\exists##.

I honestly don’t see how this is invalid, assuming you’re ok with ##\forall##’s commuting.
 
  • Like
Likes Leo Liu and fresh_42
  • #22
Few comments/observations on the discussion. Let's take the case of:
##\forall x \, \exists y \,\, P(x,y)##

(1) Suppose our quantification is over ##\mathbb{N}##, so we are actually talking about:
##\forall x \in \mathbb{N} \, \exists y \in \mathbb{N} \,\, P(x,y)##

To show a statement like this as true we can describe a function ##f: \mathbb{N} \rightarrow \mathbb{N}## such that whenever we have ##x=a##, the value ##f(a)## is guaranteed to make ##P(a,f(a))## true. In fact, for the specific case we can make a canonical choice for ##f## [so that ##f## always satisfies the property mentioned next] in the sense that for any arbitrary ##x=a## we have:
##P(a,(fa))## is true
##P(a,i)## is false for all ##i<f(a)##

But, in general, such a choice for ##f## might not be possible if our quantification domain is ##\mathbb{Z}##, ##\mathbb{R}##, ##\mathbb{R}^+## (due to lack of guarantee of a minimum element).(2) Once again considering the statement:
##\forall x \, \exists y \,\, P(x,y)##
If, for all ##x##, there exists a single specific value ##y=b## (for a given ##x##, some other values of ##y## may work too) that makes ##P(x,b)## true then:
##\exists y \, \forall x \,\, P(x,y)##
will also be true.(3) Consider a predicate ##P## such that for all ##x,y \in \mathbb{R}^+##:
##P(x,y)## is true iff ##x \leq y##

Considering the statement:
##\forall x \in \mathbb{R}^+ \, \exists y \in \mathbb{R}^+ \,\, P(x,y)##

Then the function ##f:\mathbb{R}^+ \rightarrow \mathbb{R}^+## defined by ##f(x)=x## is guaranteed to make ##P(x,f(x))## true for all ##x##. However, a slower growing function such as ##f(x)=\mathrm{floor} (x/2)## would just work as well. It seems to me that probably a situation like this can be thought of having resemblance with ##\epsilon##-##\delta## definition (for limit) in the sense we try to find a function that works [i.e. for all ##\epsilon## gives a value of ##\delta## that works], but a slower growing function would also work.
 
  • #23
Follow-up post.

When I was going through the course notes I encountered the following example. It seemed that the student's examples and this example were very much alike. In this first question, the universal quantifier for x and y are in the brackets, whereas the quantifier is outside the brackets in the second scenario.

However, wouldn't it make more sense if the first statement were ##\forall a,b,c,\, (\exists x,y,\, a\mid(bx+cy))\implies (a\mid b\wedge a\mid c)##.

I think I somewhat understand it -- the quantifier in the first case doesn't have any effect on the conclusion, whether as the conclusion in case 2 is governed under the quantifier concerning x and y. Is this understanding correct?
Screen Shot 2021-09-26 at 10.47.51 AM.png
 
Last edited:
  • #24
Leo Liu said:
Follow-up post.

When I was going through the course notes I encountered the following example. It seemed that the student's examples and this example were very much alike. In this first question, the universal quantifier for x and y are in the brackets, whereas the quantifier is outside the brackets in the second scenario.

However, wouldn't it make more sense if the first statement were ##\forall a,b,c,\, (\exists x,y,\, a\mid(bx+cy))\implies (a\mid b\wedge a\mid c)##.

I think I somewhat understand it -- the quantifier in the first case doesn't have any effect on the conclusion, whether as the conclusion in case 2 is governed under the quantifier concerning x and y. Is this understanding correct?
View attachment 289723
Lol congratulations, you’ve discovered prenex normal form:
https://en.m.wikipedia.org/wiki/Prenex_normal_form
Yes, a ##\forall## limited to the antecedent of a conditional becomes a ##\exists## over the entire conditional.
 
  • Like
  • Informative
Likes Leo Liu and SSequence
  • #25
You are right that the first statement would (naturally) translate to (but I think there would be a "forall" at one point where you used "exists"):
(1) ##\forall a,b,c \, (\forall x,y \, (a\mid(bx+cy)) \implies (a\mid b\wedge a\mid c))##
and the second to:
(2) ##\forall a,b,c,x,y \,((a\mid(bx+cy)) \implies (a\mid b\wedge a\mid c))##

If you take a look at post#7, then you would see that for the second statement (2) to be true, all the sub-statements formed by "all possible combination" of ##b,c,x,y## should be true. For example, in the image following values were used:
##y=5, \, x=8, \, c=2,\, b=1##
The resulting sub-statement is:
##\forall a \,((a\mid(1\cdot 8+ 2 \cdot 5)) \implies (a\mid 1 \wedge a\mid 2))##
##\forall a \,((a\mid 18) \implies (a\mid 1 \wedge a\mid 2))##
This sub-statement is then wrong for ##a=3##.

=======================

(1)
##\forall a,b,c \, (\forall x,y \, (a\mid(bx+cy)) \implies (a\mid b\wedge a\mid c))##

Now one question is that why it doesn't work with the first statement (re-written above for ease). The problem here is that to evaluate this statement we must first "get-rid" of the "outer-quantifier" (yes, sorry this is very informal way of saying it, since I haven't studied it formally). So the best we can do to go "as close" to first example as possible is to put:
##c=2, \, b=1, \, a=3##
which leads to the sub-statement (which must necessarily be true if the original statement (1) is to be true):
##\forall x,y \, (3 \mid(x+2y)) \implies (3 \mid 1 \wedge 3 \mid 2)##

## x=8, \, y=5##
Of course now we are tempted to put these values to show that the given sub-statement is false (and hence the original statement is false too). But we can't do that!
If you look at the sub-statement above, the conclusion is indeed false. However, the premise is false too. That's becasue ##3## can't divide an expression like ##x+2y## for all possible combinations of ##x## and ##y## (just think ##x=1,y=2##).
 
Last edited:
  • Love
Likes Leo Liu

FAQ: [Logic] Order of quantifiers and brackets

1. What is the purpose of using brackets in logic?

Brackets are used in logic to indicate the order in which operations should be performed. They help to clarify the meaning of complex logical statements and ensure that the correct interpretation is made.

2. How do the order of quantifiers and brackets affect the meaning of a logical statement?

The order of quantifiers and brackets can significantly impact the meaning of a logical statement. Changing the order can result in a completely different interpretation of the statement, so it is crucial to use them correctly to convey the intended meaning.

3. Are there any rules or guidelines for the order of quantifiers and brackets in logic?

Yes, there are rules and guidelines for the order of quantifiers and brackets in logic. The general rule is that quantifiers should be placed before any logical connectives, and brackets should be used to group subexpressions that need to be evaluated together.

4. What happens if the order of quantifiers and brackets is not specified in a logical statement?

If the order of quantifiers and brackets is not specified, it can lead to ambiguity and confusion in the interpretation of the statement. It is essential to follow the rules and guidelines for the correct placement of quantifiers and brackets to avoid any misunderstandings.

5. Can the order of quantifiers and brackets be changed without affecting the truth value of a logical statement?

No, changing the order of quantifiers and brackets can affect the truth value of a logical statement. The order is crucial in determining the scope of the quantifiers and the grouping of subexpressions, which can ultimately impact the truth value of the statement.

Similar threads

Back
Top