Is there a tableau proof of $\exists x \forall y (P(x)\to P(y))$

Question

I cannot figure out a counter model for this first order formula.

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

However I cannot come up with a tableau proof either.

Can somebody tell me if this formula is valid or not?

Answer 1

Is there a tableau proof of $∃x∀y(P(x)→P(y))$ ?

The answer is YES :

1) $\lnot ∃x∀y(P(x)→P(y))$

2) $\lnot ∀y(P(a)→P(y))$ --- using constant $a$

3) $\lnot (P(a)→P(b))$ --- with $b$ new

4) $P(a)$

5) $\lnot P(b)$

6) $\lnot ∀y(P(b)→P(y))$ --- from 1)

7) $\lnot (P(b)→P(c))$ --- with $c$ new

8) $P(b)$

9) $\lnot P(c)$

But 5) and 8) close the tree: thus, formula 1) is unsatisfiable.

Being 1) the negation of the original formula : $∃x∀y(P(x)→P(y))$, we have that the original formula is valid.

---

As per Sambo's answer, the formula is invalid in an empty domain (as will be every existential formula).

In that case, what we can do is to prove : $\exists x (x= x) \vdash ∃x∀y(P(x)→P(y))$.

The corresponding tableau will start with step 0) $\exists x (x= x)$ and then we can instantiate it with $a$ to get : $a=a$. Having done this, we can use the constant $a$ in 2) above.

Answer 2

The formula is not necessarily valid: if the domain of discourse is empty, then there does not exist any element; in particular none that satisfy the equation.

However, if the domain of discourse is non-empty, then the formula is valid. If there is some $x$ such that $P(x)$ is false, then $P(x) \rightarrow P(y)$ is true for every $y$. Conversely, if $P(x)$ is always true, then for any $x,y$, $P(x) \rightarrow P(y)$. So if there's one element in the domain, the statement is true.