[Logic] Order of quantifiers and brackets

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

 

[PeroK]

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,

 

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

 

[PeroK]

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.

 

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

 

[PeroK]

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.

 

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

 

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

 

[fresh_42]

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

 

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

 

[fresh_42]

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]

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?

 

[fresh_42]

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

 

[PeroK]

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

 

[TeethWhitener]

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.

 

[fresh_42]

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\,?$

 

[TeethWhitener]

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.

 

[fresh_42]

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.

 

[TeethWhitener]

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.

 

[fresh_42]

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?

 

[TeethWhitener]

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.

 

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

 

[TeethWhitener]

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.

 

[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$).