Quantifier shift logic exercise

Prove that $\exists y\forall xf(x,y) \Rightarrow \forall x\exists yf(x,y)$

Assume the opposite:

statement 1 says: there is a y so that for all x'es f is true.

So statement 1 does not lead to statement 2. So if statement 1 is true, two is false. So

$\exists y\forall xf(x,y) \Rightarrow \neg\forall x\exists yf(x,y)$ ~ $\exists x\exists y\neg f(x,y)$

The last statement means (there is an x so that there is a y so that f is untrue).

However the last statement is equivalent to $\exists y\exists x\neg f(x,y)$. Which is in contradiction with statement 1.

Is this proof correct? I'm very unsure.

• Your work is very unclear. I think I understand what you did up to line 4. You lost me completely on the fifth row of your text. "∃y∀xf(x,y) -> -∀x∃yf(x,y)", what is the character - supposed to mean? – Git Gud Sep 15 '15 at 10:55

No it's not correct. Assuming the opposite of $p\Rightarrow q$ does not mean $p\Rightarrow \neg q$.

For example assume that you're about to prove that $x\in\mathbb N\Rightarrow x\in\mathbb Q$ (which is false) by assuming that $x\in\mathbb N\Rightarrow x\notin\mathbb Q$ (which is known to be false since $\mathbb N\subset\mathbb Q$).

In addition $\exists y\exists x\neg f(x,y)$ doesn't contradict $\exists y\forall x f(x,y)$, an example would be if $f(x,y) \Leftrightarrow y=0$. There surely exists $x$ and $y$ such that $\neg y=0$, but still there exists an $y$ such that $y=0$ for all $x$.

Here is a proof of the quantifier shift using a Fitch-style proof checker.

Rather than starting with the negation of the statement to be derived, I started with the negation of an equivalent statement represented as a conjunction. After reaching a contradiction, I derived the desired conditional.

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

Prove that $$∃y∀xf(x,y)⇒∀x∃yf(x,y)$$

Assume the opposite: $$∃y∀xf(x,y)⇒\neg ∀x∃yf(x,y)$$

Nope. That is neither the direction needed, nor what the opposite actually is.

The negation of the conditional: is $$∃y∀xf(x,y)\wedge\neg ∀x∃yf(x,y)$$.

However, assuming that for a proof by contradiction will lead to a rather inellegant proof.

All you need to do is assume the antecedent and derive the consequent by eliminating and introducing the quantifiers.   That is, a conditional proof will derive this conditional statement.

Assume $$\exists y~\forall x~f(x,y)$$, and assume that term $$c$$ is a witness for this (that is $$\forall x~f(x,c)$$). If so, then for any arbitrary term $$a$$ the statement $$f(a,c)$$ is satisfied. Therefore for any arbitrary term $$a$$ there is a witness to the existential $$\exists y~f(a,y)$$.

Thusly, we may derive $$\forall x~\exists y~f(x,y)$$ when we assume $$\exists y~\forall x~f(x,y)$$; hence we deduce the conditional $$\exists y~\forall x~f(x,y)\to\forall x~\exists y~f(x,y)$$.

$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}\fitch{}{\fitch{1.~\exists y~\forall x~f(x,y)}{\fitch{2.~\forall x~f(x,c)}{\begin{array}{|l}3.~f(a,c)\hspace{19.5ex}\forall\mathsf E~2\\4.~\exists y~f(a,y)\hspace{16.5ex}\exists\mathsf I~3\end{array}\\5.~\forall x~\exists y~f(x,y)\hspace{14ex}\forall\mathsf I~4}\\6.~\forall x~\exists y~f(x,y)\hspace{17ex}\exists\mathsf E~1,2{-}5}\\7.~\exists y~\forall x~f(x,y)\to\forall x~\exists y~f(x,y)\hspace{4ex}{\to}\mathsf I~1{-}6}$$