Are any of these sequents provable using ND rules?

44 Views Asked by At

$$\large\begin{array}{ll}1. & \vdash \exists x~(Px\to\forall y~Py))\\2. & \forall x~\exists y~(Px\to Qy)\vdash \exists y~\forall x~(Px\to Qy)\\3. & Sj, \forall x~(\lnot(x=j)\to Sx)\vdash \forall x~Sx\end{array}$$

The first one doesn't seem right to me.

Isn't the second one the quantifier shift fallacy?

And the third one seems reasonable, but I can't find a way to prove it.

1

There are 1 best solutions below

10
On BEST ANSWER

The first does indeed not seem right ... but it is! It is in fact the famous Drinker Paradox

Why does it hold? Here is an algebraic demonstration:

$\exists x (P(x) \to \forall y \ P(y)) \overset{Implication}{\Leftrightarrow}$

$\exists x (\neg P(x) \lor \forall y \ P(y)) \overset{Distribution \ \exists \ over \ \lor}{\Leftrightarrow}$

$\exists x \neg P(x) \lor \exists x \forall y \ P(y) \overset{Quantifier \ Negation, Null\ Quantification}{\Leftrightarrow}$

$\neg \forall x P(x) \lor \forall y \ P(y) \overset{Replacing \ Variables}{\Leftrightarrow}$

$\neg \forall x P(x) \lor \forall x \ P(x) \overset{Complement}{\Leftrightarrow}$

$\top$

So, assuming your ND rules are complete, this is provable.

The second sequent also holds! While you are correct that in general you cannot swap quantifiers of different types, in this particular case you can. This is because the $Px$ only makes reference to the $x$, and not the $y$, and with $Qy$ ist is just the other way around. As such, you can bring the quantifiers inside, and both sides turn out to be equivalent to:

$\exists x \ Px \to \exists y \ Qy$

And yes, the third one also holds.

But in all cases: we would need to know exactly what rules you are using in order to know how to prove something like this.