Let's have a first-order language with a categorical symbol $P(x,y)$. Define the statement: $$\phi\equiv \forall xP(x,x)\land \forall x\forall y( P(x,y)\rightarrow \forall z( P(x,z)\land P(y,z) ) )\rightarrow \exists x\forall yP(y,x)$$
Formulate an interpretation that is not a model of $\phi$.
I cannot see why that wouldn't hold anywhere... Seems to me that it is true in every interpretation.
Because of the second condition of the implication and setting $y=x$, since the first condition $\forall xP(x,x)$ holds, we would obtain that every element would be related though $P$ with every other, that is $\forall x\forall yP(x,y)$ holds under the assumptions of the implication. So, in which interpretation would the implication not hold ?
You are right: it is valid.
Here is a proof with Tableau:
1) $∀xP(x,x) ∧ ∀x∀y(P(x,y) → ∀z(P(x,z)∧P(y,z)))$ --- premise
2) $\lnot ∃x∀yP(y,x)$ --- negation of the conclusion
3) $\lnot ∀yP(y,a)$ --- from 2)
4) $\lnot P(b,a)$ --- from 3) : $b$ new
5) $∀xP(x,x)$ --- from 1)
6) $∀x∀y(P(x,y) → ∀z(P(x,z)∧P(y,z)))$ --- from 1)
7) $P(b,b)$ --- from 5)
8) $P(b,b) → ∀z(P(b,z)∧P(b,z))$ --- from 6)
9a) $\lnot P(b,b)$ --- left branch from 8): it closes with 7)
9b) $∀z(P(b,z)∧P(b,z))$ --- right branch from 8)
10) $P(b,a)$ --- from 9b): it closes with 4).