How to deduce $\forall x \forall y \exists z(Gxz \land Gzy)$

Question

The task is to deduce this:

$\forall x \forall y \exists z(Gxz \land Gzy)$

From this:

$ \forall x (Gxx) $

And this:

$ \forall x \forall y ( x \neq y \to \exists z(Gxz \land Gzy) $

Using this instance of the Law of Indiscernibility of Identicals:

$ a = b \to (Gaa \equiv Gab) $

I tried to proceed by reductio, assuming as an additional premise this:

$ \neg \forall x \forall y \exists z (Gxz \land Gzy) $

And from this premise (and its instances), the instance of the Law, and the second premise above (and its instances), I was able to deduce this:

$\exists z (Gaz \land Gzb) $

Which is an instance of what I trying to prove but I won't be able to generalize appropriately to reach my conclusion, nor does it follow from the correct premises: I don't know how to use the first premise $ \forall x (Gxx) $ effectively, and further my reductio is not doing what it should be.

Thanks for any help. I really appreciate it!

This is from Goldfarb's Deductive Logic, IV5b.

Answer 1

There are two cases $x = y$ and $x \not= y$.

if $x = y$, then $\exists z (G x z \land G z y)$ is $\exists z (G x z \land G z x)$ which holds with $z = x$ because $\forall x (G x x)$.

If $x \not= y$, then $\exists z (G x z \land G z y)$ follows from $\forall x \forall y (x \not= y \implies \exists z (G x z \land G z y))$.

In both cases, $\exists z (G x z \land G z y)$ follows as required.