As suggested, we show that any model of the negation of each sentence must be infinite. We also use the Prenex Normal Form Theorem to transform prenex formulas to a non-prenex form.

(a) Before considering the negation of the formula, we could try to understand its meaning. This says that there is a point $x$ such that either relation $P$ is not “transitive at $x$ ” (meaning that there are $y,z$ such that $Pxy\wedge Pyz$ but not $Pxz$ ) or $\neg Pxfx$ or $Pxx$ . This holds in any finite model, because if $P$ is not transitive, then there is a point $x$ such that $P$ is not transitive at $x$ , and if $Pxfx$ does not hold for some $x$ , then $\neg Pxfx$ for some $x$ , otherwise $P$ is transitive at all points (or, just transitive), and for all points $Pxfx$ , so, we can construct a sequence $x_{0}$ , $x_{n}=fx_{n-1}$ , for $n\ge1$ , such that $Px_{n-1}x_{n}$ holds for all $n\ge1$ , in particular, by transitivity, $Px_{n-1}x_{n-1+m}$ for all $n,m\ge1$ , and, since the universe is finite, there has to be a loop.

Formally, using the negation of the formula, we show that it is true in (some) infinite models only:

$$\neg\exists x\exists y\exists z[(Pxfx\rightarrow Pxx)\vee(Pxy\wedge Pyz\wedge\neg Pxz)]$$

$$\neg\exists x\exists y\exists z[\neg(Pxfx\rightarrow Pxx)\rightarrow(Pxy\wedge Pyz\wedge\neg Pxz)]$$

$$\neg\exists x[\neg(Pxfx\rightarrow Pxx)\rightarrow\exists y\exists z(Pxy\wedge Pyz\wedge\neg Pxz)]$$

$$\forall x\neg[\neg(Pxfx\rightarrow Pxx)\rightarrow\exists y\exists z(Pxy\wedge Pyz\wedge\neg Pxz)]$$

$$\forall x[\neg(Pxfx\rightarrow Pxx)\wedge\neg\exists y\exists z(Pxy\wedge Pyz\wedge\neg Pxz)]$$

$$\forall x[Pxfx\wedge\neg Pxx\wedge\forall y\forall z(\neg Pxy\vee\neg Pyz\vee Pxz)]$$

$$\forall x[Pxfx\wedge\neg Pxx\wedge\forall y\forall z(Pxy\rightarrow Pyz\rightarrow Pxz)]$$

If $\mathfrak{A}$ is a model of this sentence, then we can use the following argument. First, $\forall x[Pxfx\wedge\neg Pxx\wedge\forall y\forall z(Pxy\rightarrow Pyz\rightarrow Pxz)]\vdash Pxfx\wedge\neg Pxx\wedge\forall y\forall z(Pxy\rightarrow Pyz\rightarrow Pxz)$ (A2, MP), and, hence, $\forall x[Pxfx\wedge\neg Pxx\wedge\forall y\forall z(Pxy\rightarrow Pyz\rightarrow Pxz)]\vdash\{Pxfx;\neg Pxx;Pxy\rightarrow Pyz\rightarrow Pxz\}$ (A1, A2, MP), and $\mbox{Th}\mathfrak{A}\vdash\{Pxfx;\neg Pxx;\forall y\forall z(Pxy\rightarrow Pyz\rightarrow Pxz)\}$ . Then, $\vdash x=y\rightarrow Pxy\rightarrow Pxx$ (A6), $\vdash\forall y(x=y\rightarrow Pxy\rightarrow Pxx)$ (G), $\vdash x=fx\rightarrow Pxfx\rightarrow Pxx$ (A2, MP), $x=fx;Pxfx\vdash Pxx$ (MP), $Pxfx;\neg Pxx\vdash\neg x=fx$ (C), $\vdash Pxfx\rightarrow\neg Pxx\rightarrow\neg x=fx$ (D), therefore, $\vDash_{\mathfrak{A}}$ $\neg x=fx$ . At the same time, by G, A2 and MP, $\vdash Pxfx\rightarrow\{Pfxffx;Pffxfffx;\ldots\}$ , so that, by A6, G, A2 and MP, $Pxfx;Pxy\rightarrow Pyz\rightarrow Pxz\vdash P\underbrace{f\ldots f}_{m}x\underbrace{f\ldots f}_{n}x$ for all $0\le m<n$ . Then, arguing as above, by A6, G, A2, MP, C and D, $\vdash P\underbrace{f\ldots f}_{m}x\underbrace{f\ldots f}_{n}x\rightarrow\neg Pxx\rightarrow\neg\underbrace{f\ldots f}_{m}x=\underbrace{f\ldots f}_{n}x$ for all $0\le m<n$ , hence, for any $s$ , $\vDash_{\mathfrak{A}}\neg\underbrace{f\ldots f}_{m}x=\underbrace{f\ldots f}_{n}x[s]$ , $0\le m<n$ , implying that the underlying structure must be infinite.

(b) Again, before considering the negation of the formula, we try to understand its meaning. In the finite case we can think of it as an edge relation on a graph, $Qxy$ iff there is an edge from $x$ to $y$ . Let us call $I(x)=\{y|Qyx\}$ the set of vertexes connected with $x$ by incoming edges. So, the truth of the statement follows from the fact that there is a vertex $x$ with the maximum number of incoming edges (which is true in the finite case): for any other vertex $y$ either there is a vertex $z$ such that there is an edge from $z$ to $x$ but no edge from $z$ to $y$ (corresponding to $z\in I(x)$ , $z\notin I(y)$ ), or, otherwise, $I(x)\subseteq I(y)$ (both are finite), but since $x$ is a vertex with the maximum number of incoming edges, $I(x)=I(y)$ , meaning, in particular, that if $x\in I(y)$ ($Qxy$ ) then $x\in I(x)$ ($Qxx$ ).

Formally, using the negation of the formula, we show that it is true in (some) infinite models only:

$$\neg\exists x\forall y\exists z[(Qzx\rightarrow Qzy)\rightarrow(Qxy\rightarrow Qxx)]$$

$$\neg\exists x\forall y[\forall z(Qzx\rightarrow Qzy)\rightarrow(Qxy\rightarrow Qxx)]$$

$$\forall x\exists y\neg[\forall z(Qzx\rightarrow Qzy)\rightarrow(Qxy\rightarrow Qxx)]$$

$$\forall x\exists y[\forall z(Qzx\rightarrow Qzy)\wedge\neg(Qxy\rightarrow Qxx)]$$

$$\forall x\exists y[\forall z(Qzx\rightarrow Qzy)\wedge Qxy\wedge\neg Qxx]$$

If $\mathfrak{A}$ is a model of this sentence, then we can use the following argument. Select any $a_{0}\in|\mathfrak{A}|$ , and fix $s:V\rightarrow|\mathfrak{A}|$ . $\vDash_{\mathfrak{A}}\forall x\exists y[\forall z(Qzx\rightarrow Qzy)\wedge Qxy\wedge\neg Qxx]$ iff for all $d\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}\exists y[\forall z(Qzx\rightarrow Qzy)\wedge Qxy\wedge\neg Qxx][s(x|d)]$ . In particular, $\vDash_{\mathfrak{A}}\exists y[\forall z(Qzx\rightarrow Qzy)\wedge Qxy\wedge\neg Qxx][s(x|a_{0})]$ . Now, this is true iff for some $a_{1}\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}\forall z(Qzx\rightarrow Qzy)\wedge Qxy\wedge\neg Qxx[s(x|a_{0})(y|a_{1})]$ iff for some $a_{1}\in|\mathfrak{A}|$ and for all $d\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}Qzx\rightarrow Qzy[s(x|a_{0})(y|a_{1})(z|d)]$ and $\vDash_{\mathfrak{A}}Qxy[s(x|a_{0})(y|a_{1})]$ and $\vDash_{\mathfrak{A}}\neg Qxx[s(x|a_{0})]$ . Let $I(a)\subseteq|\mathfrak{A}|$ be the set $I(a)=\{b|<b,a>\in Q^{\mathfrak{A}}\}$ . Then, if $b\in I(a_{0})$ , then $\vDash_{\mathfrak{A}}Qzx[s(x|a_{0})(z|b)]$ , and, according to the first of the three expressions, $\vDash_{\mathfrak{A}}Qzy[s(y|a_{1})(z|b)]$ , i.e. $b\in I(a_{1})$ . And $I(a_{0})\subseteq I(a_{1})$ . At the same time, according to the second and third expressions, $a_{0}\in I(a_{1})$ while $a_{0}\notin I(a_{0})$ . Overall, we have $I(a_{0})\subsetneq I(a_{1})$ . Since $a_{0}$ was chosen arbitrary, we can find $a_{2}$ for $a_{1}$ the same way we found $a_{1}$ for $a_{0}$ such that $I(a_{1})\subsetneq I(a_{2})$ , and so on. In particular, for any $0\le m<n$ , we have $I(a_{m})\subsetneq I(a_{n})$ , and $a_{m}\neq a_{n}$ . This shows that the underlying structure must be infinite.