other exercises: 20241212_DiskMat_Serie12.pdf

12.6)a)

  • Let be an arbitrary interpretation that is suitable for both sides.
  • Assume
  • Thus, for some , all .
  • Let be a unary function symbol. By the semantics of terms, the interpretation of in is a function . For a given , let where .
  • We know that for some and all . This also holds for , i.e. . Thus:
  • By the semantics of , there must exist some such that:
  • Since implies for any interpretation , we conclude:

12.6)b)

  • Let be an arbitrary interpretation that is suitable for both sides.
  • Assume
  • We have shown that if , then . Thus: