# [Logic] Order of quantifiers and brackets

• I
Leo Liu
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.

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

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

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?

## Answers and Replies

Homework Helper
Gold Member
2021 Award
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,

fresh_42 and Leo Liu
Leo Liu
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?

Homework Helper
Gold Member
2021 Award
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.

sysprog, SSequence and Leo Liu
Leo Liu
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.

Homework Helper
Gold Member
2021 Award
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.

sysprog and Leo Liu
SSequence
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.

sysprog and Leo Liu
Leo Liu
Let's look at both of the examples one by one:
Thank you! This explanation with a truth table like chart is very informative.

Mentor
2021 Award
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:
Leo Liu
Leo Liu
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?

PeroK
Mentor
2021 Award
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.

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

Mentor
2021 Award
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))##
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) ##.

Leo Liu
Homework Helper
Gold Member
2021 Award
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##.

Leo Liu
Gold Member
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.

Mentor
2021 Award
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\,?##

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

Mentor
2021 Award
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.

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

Mentor
2021 Award
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?

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

Leo Liu and fresh_42
SSequence
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.

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

Last edited:
Gold Member
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.

Leo Liu and SSequence
SSequence
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:
Leo Liu