[Logic] Order of quantifiers and brackets

  • I
  • Thread starter Leo Liu
  • Start date
  • #1
Leo Liu
344
145
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?
 

Answers and Replies

  • #2
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,261
14,765
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
Leo Liu
344
145
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,261
14,765
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
Leo Liu
344
145
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,261
14,765
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
SSequence
517
82
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
Leo Liu
344
145
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
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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:
  • #10
Leo Liu
344
145
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?
 
  • #11
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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.
 
  • #12
Leo Liu
344
145
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?
 
  • #13
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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) ##.
 
  • #14
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,261
14,765
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##.
 
  • #15
TeethWhitener
Science Advisor
Gold Member
2,376
1,921
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
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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
TeethWhitener
Science Advisor
Gold Member
2,376
1,921
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
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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
TeethWhitener
Science Advisor
Gold Member
2,376
1,921
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
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,179
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
TeethWhitener
Science Advisor
Gold Member
2,376
1,921
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
SSequence
517
82
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
Leo Liu
344
145
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
TeethWhitener
Science Advisor
Gold Member
2,376
1,921
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
SSequence
517
82
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:

Suggested for: [Logic] Order of quantifiers and brackets

Replies
26
Views
1K
Replies
9
Views
396
  • Last Post
Replies
4
Views
385
  • Last Post
Replies
11
Views
1K
Replies
21
Views
853
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
556
Replies
2
Views
497
  • Last Post
Replies
2
Views
583
Top