other exercises: 20241212_DiskMat_Serie12.pdf
12.6)a)
- Let A be an arbitrary interpretation that is suitable for both sides.
- Assume A(∃x∀yP(x,y))=1
⟹˙A[x→u]∀yP(x,y)=1 for some u∈U⟹˙A[x→u][y→v]P(x,y)=1 for some u∈U and all v∈U(sem. ∀)(sem. ∃)
- Thus, PA(uA,vA)=1 for some u∈U, all v∈V.
- Let f be a unary function symbol. By the semantics of terms, the interpretation of f in A is a function ϕ(f):U→U. For a given u∈U, let f(u)=v where A(v)=ϕ(f)(A(u)).
- We know that PA(uA,vA)=1 for some u∈U and all v∈V. This also holds for v=f(u), i.e. v=ϕ(f)(u). Thus:
PA(uA,ϕ(f)(uA))=1 for some u∈U
- By the semantics of ∃, there must exist some u∈U such that:
⟹˙A[x→u]P(x,f(x))=1 for some u∈U⟹˙∃x P(x,f(x))=1(sem. ∀)
- Since A(∃x∀y P(x,y))=1 implies ∃x P(x,f(x))=1 for any interpretation A, we conclude:
∃x∀y P(x,y)⊨∃x P(x,f(x))□
12.6)b)
- Let A be an arbitrary interpretation that is suitable for both sides.
- Assume A(¬(∀x P(x)))=1
⟹˙A(∀x P(x))=0⟹˙A[x→u]P(x)=0 for all u∈U⟹˙A[x→u](¬P(x))=1 for all u∈U⟹˙A[x→u](¬P(x))=1 for some u∈U⟹˙A(∃x (¬P(x)))=1(sem. ¬)(sem. ∀)(sem. ¬)(since U is non-empty)(sem. ∃)
- We have shown that if A(¬(∀x P(x)))=1, then A(∃x (¬P(x)))=1. Thus:
¬(∀x P(x))⊨∃x ¬P(x)□