[Logic] Order of quantifiers and brackets

  • I
  • Thread starter Leo Liu
  • Start date
  • #1
296
135
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
2020 Award
18,744
10,372
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
296
135
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
2020 Award
18,744
10,372
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
296
135
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
2020 Award
18,744
10,372
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
510
78
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
296
135
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
15,565
13,677
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
296
135
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
15,565
13,677
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
296
135
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
15,565
13,677
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
2020 Award
18,744
10,372
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,095
1,591
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
15,565
13,677
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,095
1,591
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
15,565
13,677
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,095
1,591
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
15,565
13,677
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,095
1,591
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
510
78
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
296
135
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,095
1,591
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
510
78
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:

Related Threads on [Logic] Order of quantifiers and brackets

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
11
Views
1K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
8
Views
3K
Top