How to give a formal proof for $ \exists \space x\space \forall \space y(P(x) \rightarrow P(y))$ in fitch

Question

To practice for my exams, my teacher gave us several exercises to practice but didn't supply us any answers. Now after looking at this problem for 2 nights I have no idea left on how to solve it.

If someone can point me in the right direction on how to solve it, that would be amazing. The question is how to give a formal proof of $ \exists \space x\space \forall \space y(P(x) \rightarrow P(y))$ without any given premises.

Answer 1

This just uses quantifier movement. Suppose we have a conditional $p \to q$, where $p, q$ may have free variables (not shown). Two facts:

1. If $y$ is a variable that's not free in $p$, then you can move a universal quantifier over $q$ to outside the entire formula $p \to q$, and vice versa -- they're equivalent: $$(p \to \forall y q) \iff \forall y(p \to q)$$

2. If $x$ is a variable that's not free in $q$, then you can move an existential (respectively, universal) quantifier over $p$ to outside the entire formula $p \to q$ while changing the quantifier to universal (resp. existential). That is, the following equivalences hold: $$(\exists x p \to q) \iff \forall x(p \to q)$$ $$(\forall x p \to q) \iff \exists x(p \to q)$$ The quantifier changes when moving to/from the antecedent $p$ to the entire formula because of these equivalences: $$p \to q \iff \neg p \vee q$$ $$\neg \forall x p \iff \exists x \neg p$$

Deriving $\exists x \forall y (P(x) \to P(y))$

Let's apply these rules to derive the sentence you've been puzzling over from an obviously valid sentence: $$\forall x P(x) \to \forall y P(y)$$ is valid -- it just changes/renames variables. So, first apply 2. to move the $x$ quantifier to the outside, obtaining: $$ \exists x(P(x) \to \forall y P(y))$$ Now apply 1. to move the $y$ quantifier to the outside of $(P(x) \to \forall y P(y))$, so that it follows $\exists x$: $$\exists x \forall y (P(x) \to P(y))$$

Understanding what $\exists x \forall y (P(x) \to P(y))$ says

This sentence may not sound like it's logically valid: it says, for an arbitrary property or condition $P$, that there's some $x$ such that if $x$ has the property $P$ then everything does. Such an $x$ is somehow a "special" witness to $P$. Although the statement is surprising, it's true, given the fact that $p \to q$ is true when $p$ is false, regardless of the truth value of $q$.

If $P$ is not true of everything, then there's some $x$ for which $P(x)$ is false; such an $x$ is a "special witness"! Because $\neg P(x)$ is true, $P(x) \to q$ is true no matter what $q$ is (the conditional is "vacuously true: falsehood implies anything/everything). So in particular, $P(x) \to \forall y P(y)$ is true. For example: "If Jack the Ripper was a good person then everybody's a good person" (i.e. the phrase "good person" has become meaningless if it applies to an obviously bad person).

Answer 2

Here is a proof in Fitch. The general strategy is of course a proof by conradiciton .... the details are fairly nasty. Note that the $\neg Intro$ is used to formalize Proof by Contradiction, and it is able to remove the negation from the assumption.