0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Git Gud Sep 15 '15 at 10:55
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

enter image description here

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/

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.