Exercise 1
如果 M 是可数的，那么存在 和 的双射 ，这也是一个满射。若 有限，记
考虑
既是一个满射
由于 中的 是满射，故对每个 , 考虑一个 ，注意到这里的 必然互不相同（由于映射的唯一性）
则令
即为所求
我们从 开始遍历，当第 个自然数 存在对应的 满足 时（注意到这样的 是唯一的），我们将这个 定为 （）
这样的遍历是能够遍历所有 的，如果 的数量有限，显然满足 ，反之，则每个 与其下标减 1 的映射可生成 到 的一个双射，即可数
综上，证毕
Exercise 2
若 至多可数，由 Exercise 1 记 为
下面分类讨论
若 ，则 即 ，显然与其下标减 1 的映射即其与 的双射
若 有限，且 ，则考虑映射
其中 代表 第 i 个 symbol （1 - base）在 中对应的下标，基于 进制的唯一分解性已知 是一个双射
若 为可数无限， 设全体质数为
下面构造映射：
当 的时候
基于算数基本定理，我们知道每个大于 1 的数都能被唯一分解为有限个质数的乘积，这分别表明了 是满射和 是单射，故 是双射
综上，证毕
Exercise 3
注意到 S-terms 并不会有括号，即 atomic formula 不会有括号，因此 S-formulas 要有括号，当且仅当其应用了
的转换，而这个转换总保持左括号和右括号个数差值不变为 0
Exercise 4
首先将其转为更清晰的形式
则 为引入的 relation symbol， 为引入的 function symbols， 为引入的常量
将上式整理为
再对连续符号做处理得到
此时
由于 都不 free，所以上式即一个完整的 sentence