Logic formulas. Deciding if one of them implies other.

Question

Let $\varphi$ will be $\forall x\forall y(y =f(g(x)) \to(\exists u(u=f(x)\land y =g(u))))$ and $\psi=\forall x[f(g(f(x))) =g(f(f(x)))]$ Decide if $\{\psi\}\models\varphi$.

Can aynone help me solve it ? I have no idea how to start.

Answer 1

The problem is to find counterexamples $f$ and $g$ that make $\psi \vdash \varphi$ untrue. I recommend starting by simplifying both formulas (I'll be leaving parenthesis off unary function applications, and treating them as binding to the right):

$$\forall x \forall y~(y = fgx \to \exists u ~ (y = gu \land u = fx))$$

Apply the rule $\forall q ~ (q = r \to Pq) \equiv Pr$ :

$$\forall x \exists u~(fgx = gu \land u = fx)$$

Now we know that since $f$ is a function, there is always a $u$ such that $u=fx$ (assuming $f$ is not the empty set...check the case of $f=\emptyset$ separately to see if it is a counterexample). So this can again be simplified:

$$\forall x ~ (fgx = gfx)$$

So $\varphi$ is equivalent to the claim "$f$ and $g$ are inverses over the entire universe".

---

Then second formula to be simplified:

$$\forall x~(fgfx = gffx)$$

If $If$ is the Image of $f$, then prior is equal to:

$$\forall y \in If~(fgy = gfy)$$

Alpha transform:

$$\forall x \in If~(fgx = gfx)$$

So $\psi$ is equivalent to the claim "$f$ and $g$ are inverses over the image of $f$".

---

So the problem becomes determining if you can find $f$ and $g$ that are counter examples to :

$$\forall x \in If~(fgx = gfx) \vdash \forall x ~ (fgx = gfx)$$

In other words, can you find 2 functions, $f$ and $g$, such that they are inverses in the Image of $f$, but otherwise not inverses? You can choose any universe for the domain that you like. If you want to see my answer, hover over the following solution (please try to find your own counterexample or reason to believe there isn't a counterexample first):

$$\begin{array} {l} \text{Domain = Real numbers from 0 to 2} \\ f(x) = \frac{1}{2}x \\ g(x) = \begin{cases} x \le 1 & 2 \cdot x \\ x \ge 1 & 2 \end{cases} \end{array}$$