Predicate Logic: Being Careful with Parentheses

Question

(i) $\forall x \in S, \exists y \in T,(P(x, y) \implies Q(x))$

(ii) $\forall x \in S, ([\exists y \in T, P(x, y)] \implies Q(x))$

How can we find non-empty sets $S, T$ and non-constant predicates $P$ (over $ S \times T)$ and $Q$ (over $S$) so that one of (i) and (ii) is false and the other is true?

Answer 1

For non-empty sets and non-constant predicates we can let $S=T=\mathbb{N},P(x,y): x=y=1$ and $Q(x):x\neq 1$, then we have:

\begin{align} i)~&\forall x\in\mathbb{N},\exists y\in\mathbb{N},(x=y=1\Rightarrow x\neq 1)\\ \equiv&\forall x\in\mathbb{N},([\forall y\in\mathbb{N},x=y=1]\Rightarrow x\neq 1)\\ \equiv&\forall x\in\mathbb{N},(\bot\Rightarrow x\neq 1)\\ \equiv&\top \end{align}

\begin{align} ii)~&\forall x\in\mathbb{N},([\exists y\in\mathbb{N},x=y=1]\Rightarrow x\neq 1)\\ \equiv&\forall x\in\mathbb{N},(\top\Rightarrow \bot)\\ \equiv&\bot \end{align}

Where $i)$ is always True but $ii)$ is always False.

---

You can also check the solution use Mathematica:

i=ForAll[x,Exists[y,Implies[x==y==1,Not[x==1]]]]
Reduce[i]
ii=ForAll[x,ForAll[y,Implies[x==y==1,Not[x==1]]]]
Reduce[ii]