20241211_DiskMat_Serie12

other exercises: 20241212_DiskMat_Serie12.pdf

12.6)a)

Let $A$ be an arbitrary interpretation that is suitable for both sides.
Assume $A (\exists x \forall y P (x, y)) = 1$

\begin{aligned} \dot{⟹} A_{[x \to u]} \forall y P (x, y) = 1 for some u \in U & (sem. \forall) \\ \dot{⟹} A_{[x \to u] [y \to v]} P (x, y) = 1 for some u \in U and all v \in U & (sem. \exists) \end{aligned}

Thus, $P^{A} (u^{A}, v^{A}) = 1$ for some $u \in U$ , all $v \in V$ .
Let $f$ be a unary function symbol. By the semantics of terms, the interpretation of $f$ in $A$ is a function $ϕ (f) : U \to U$ . For a given $u \in U$ , let $f (u) = v$ where $A (v) = ϕ (f) (A (u))$ .
We know that $P^{A} (u^{A}, v^{A}) = 1$ for some $u \in U$ and all $v \in V$ . This also holds for $v = f (u)$ , i.e. $v = ϕ (f) (u)$ . Thus:

P^{A} (u^{A}, ϕ (f) (u^{A})) = 1 for some u \in U

By the semantics of $\exists$ , there must exist some $u \in U$ such that:

\begin{aligned} \dot{⟹} A_{[x \to u]} P (x, f (x)) = 1 for some u \in U \\ \dot{⟹} \exists x P (x, f (x)) = 1 & (sem. \forall) \end{aligned}

Since $A (\exists x \forall y P (x, y)) = 1$ implies $\exists x P (x, f (x)) = 1$ for any interpretation $A$ , we conclude:

\exists x \forall y P (x, y) ⊨ \exists x P (x, f (x)) ◻

12.6)b)

Let $A$ be an arbitrary interpretation that is suitable for both sides.
Assume $A (\neg (\forall x P (x))) = 1$

\begin{aligned} \dot{⟹} A (\forall x P (x)) = 0 & (sem. \neg) \\ \dot{⟹} A_{[x \to u]} P (x) = 0 for all u \in U & (sem. \forall) \\ \dot{⟹} A_{[x \to u]} (\neg P (x)) = 1 for all u \in U & (sem. \neg) \\ \dot{⟹} A_{[x \to u]} (\neg P (x)) = 1 for some u \in U & (since U is non-empty) \\ \dot{⟹} A (\exists x (\neg P (x))) = 1 & (sem. \exists) \end{aligned}

We have shown that if $A (\neg (\forall x P (x))) = 1$ , then $A (\exists x (\neg P (x))) = 1$ . Thus:

\neg (\forall x P (x)) ⊨ \exists x \neg P (x) ◻